Транспортная задача по критерию времени

Пусть имеется т пунктов отправления А_ь А₂, …, А"" на которых сосредоточены запасы однородного груза в известных количествах а_ь а₂, …, а_т. Имеются также п пунктов потребления В_ь В₂, …, В_п, подавшие заявки на доставку этих грузов в объемах Ь_ь Ъ₂,… Ь_п. Предполагается, что общее количество грузов в пунктах отправления равно суммарной заявке на доставку грузов. Для доставки одной единицы груза из каждого пункта отправления А, — в каждый пункт прибытия В₍ необходимо время ty. Требуется составить такой план перевозок грузов, чтобы общее время окончания всех заявленных перевозок было наименьшим.

Построим математическую модель задачи. Пусть x_i; — плановый объем доставки грузов из А, в В₍ (предполагается, что все.

^xv-⁰⁾-

В задаче требуется получить матрицу X* = х*- как план, минимизирующий время окончания перевозок. Очевидно, что время плана — наибольшее из запланированных времен перевозок, т. е. задача формулируется как.

Ограничения задачи формализуются так же, как и в задаче по критерию стоимости:

Задача (14.24)—(14.27) не относится к задачам математического программирования, поскольку целевая функция не является аналитической. Вместе с тем для ее решения возможно применение некоторых идей, заимствованных из методов решения транспортных задач по критерию стоимости.

Рассмотрим один из возможных методов решения транспортной задачи по критерию времени на конкретном примере.

Пример 14.10.

Пусть задача задана в форме транспортной таблицы (цифры в верхних углах клеток — время соответствующих перевозок).

Требуется решить транспортную задачу по критерию времени.

Решение. Построим опорный план методом северо-западного угла. Получим следующую таблицу.

Время плана Т₀ = 10, которое определяет клетка (2, 3). План может быть улучшен, если перевозки в этой клетке сделать равными нулю (а не просто уменьшить, как в ТЗ по критерию стоимости). При этом нужно следить, чтобы клетки с t_tj > Т₀ не вошли в состав базисных. Для этих целей клетки, удовлетворяющие этому условию, становятся запретными (такие клетки отмечаются в таблице крестом). Для данной ситуации это клетка (1, 4).

Попытаемся для клетки (2, 3) построить цикл, обеспечивающий обнуление соответствующей перевозки. Заметим, что этот цикл не должен проходить через запрещенные клетки. Такой цикл существует: (2, 3)-, (2, 1)⁺, (1, 1)-, (1, 3)⁺. В соответствии с этим циклом изменим план и получим новую таблицу.

Теперь время плана Т_х = 8 определяет клетка (2,2). Для этой клетки строим цикл, переводящий ее в разряд свободных, запрещая одновременно прохождение цикла по клетке (2, 4). Такой цикл существует: (2, 2)-, (2,1)⁺, (1,1)-, (1, 2)⁺. Изменив в соответствии с этим циклом план, получаем новую таблицу.

Время полученного плана Т₂ = 7 определяет клетка (1, 3). Для нее нельзя построить цикл, проходящий только через разрешенные клетки и переводящий эту клетку в свободные. Следовательно, решение задачи получено. Оптимальный план перевозок: x_n = 1, х₁₂ = 9, х₁₃ = 8, х₂₁ = 10, х₃₃ = 5, х₃₄ = 7 имеет время Т = 7.