Минимаксная транспортная задача

Транспортная задача по критерию времени является минимаксной транспортной задачей и предполагает перевозку однотипного груза из т пунктов отправления в п пунктов назначения. Заранее задана матрица времени следования транспортного средства t_t- из любого i-го пункта в любой у-й. Предполагается, что / = 1,mj = 1,п. Заданы запасы грузов в пунктах отправления и потребности в пунктах назначения. Рассматривается задача, в которой количество запасов в пунктах оправления соответствует потребностям в пунктах назначения. Они составляют соответственно а_п Ь_}.

Формируется матрица, элементы которой показывают количество груза, перевезенного из i-го пункта в у-й, Для нее справедливы следующие ограничения:

Элементы матрицы времени, затрачиваемого па перевозку фуза из /-го пункта в пункту, рассчитываются следующим образом:

В минимаксной транспортной задаче по критерию времени целью является минимум общего (не суммарного) времени, которое требуется на осуществление всех перевозок^[1]. Необходимо минимизировать целевую функцию:

Решение задачи сводится к нахождению такой матрицы перевозок x_iJf которая удовлетворяет все потребности пунктов назначения, не выходя за рамки ограничений.

Алгоритм нахождения оптимального плана перевозок:

• • построение допустимого плана с использованием метода минимального элемента;
• • выбор максимального элемента t_{- из тех, для которых Х— положительно;
• • блокирование клеток, для которых t_i} > max{?,. }', Vx_;/ = 0;
• • исправление выбранного плана путем обращения элемента х., соответствующего тах{^}', в ноль. Если операция проходит успешно, уменьшается время, необходимое на выполнение нового плана;
• • построение нового плана.

Улучшение плана необходимо проводить до тех пор, пока не станет невозможным обращение перевозки х- в ноль.

Пример 11.1.3.

Постановка задачи и последовательность решения минимаксной транспортной задачи

Заданы матрица времени перевозок, запасы на складах и потребности в пунктах назначения (табл. 11.1.4).

Таблица 11.1.4

Исходные данные тестового примера

Методом минимального элемента построим допустимый план перевозок. Матрицы допустимого плана перевозок и времени выглядят следующим образом (табл. 11.1.5 и 11.1.6).

Таблица 11.1.5

Таблица 11.1.6

Из матрицы очевидно, что время всех перевозок равно 9. Блокируем клетки, время перевозок в которые выше 9. Метод потенциалов показывает, что уменьшить время нельзя. Следовательно, план является допустимым и оптимальным.

Была написана программа на языке УВД использующая инструментарий MS Excel «Поиск решения». Она сравнивает значения целевой функции между собой при переборе возможных значений матрицы дги выбирает то решение, ко;

Рис. 11.1.3. Решение тестового примера

торос минимизирует максимальное время перевозок. Вариант решения задачи показан на рис. 11.1.3.

В заключение отметим, что тема минимаксной оптимизации всегда будет актуальна в силу своей высокой хозяйственной ценности. В частности, данный тип задач широко используется в логистике.

• [1] Бабаев Л. А., Салтовская А. А. Алгоритмы решения транспортной задачи по критерию времени // Интеграция экономики в систему мирохозяйственных связей: сб. науч. тр. XVII Международной научно-практической конференции 23—25 октября 2012 г. СПб.: Изд-во Политехи. ун-та, 2012. С. 356—359.