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

Иногда на первый план выдвигается не экономический критерий минимизации общей стоимости перевозок, а минимизация общей длительности перевозок – при перевозках скоропортящихся продуктов или боеприпасов в условиях войны. В этом случае рассматривается транспортная задача со сбалансированными запасами и заявками, но вместо таблицы стоимостей перевозок задается таблица длительностей доставки товаров от всех поставщиков ко всем потребителям в предположении неограниченности транспортных средств для выполнения перевозок – в этом случае длительности перевозок не зависят от количества доставляемого товара. Очевидно, что весь план будет выполнен, когда завершится самая длительная перевозка. В общем случае это не задача линейного программирования, так как критерий оптимальности плана – время Т – не является линейной функцией элементов таблицы длительностей перевозок. Можно свести эту задачу к нескольким задачам линейного программирования или использовать различные расчетные методы непосредственного определения оптимального решения, например, метод запрещенных клеток. По этому методу начальный план перевозок составляется не методом северо-западного угла, а предварительным запретом ставить ненулевые перевозки в клетки с самыми длительными перевозками – при этом в первую очередь заполняются клетки с малыми временами. Получив план с некоторым максимальным временем перевозок, запрещаем использование клеток с длительностью доставки большим этого времени и отыскиваем цикл улучшения плана без использования запрещенных клеток – если это удается, попытку повторяем, а если нет – значит, план улучшить уже нельзя. Такой эвристический подход может оказаться эффективнее других методов решения этой оптимизационной задачи.