Решение транспортной задачи по критерию времени

До сих пор критерием оптимальности решения ТЗ у нас была общая стоимость перевозок, и мы стремились эту стоимость минимизировать.

В большинстве случаев практики именно критерий стоимости является главным, определяющим качество (эффективность) плана перевозок. Однако в некоторых случаях на первый план выдвигается не стоимость перевозок L, а время Т, в течение которого все перевозки будут закончены. Так, например, бывает, когда речь идет о перевозках скоропортящихся продуктов или же о подвозе боеприпасов к месту боевых действий. Наилучшим планом перевозок будет считаться тот план, при котором время окончания всех перевозок минимально:

Такая транспортная задача, где оптимальным считается план с минимальным временем Т, называется транспортной задачей по критерию времени.

Задача ставится следующим образом. Имеется пунктов отправления с запасами пунктов назначения с заявками сумма запасов равна сумме заявок:

Заданы времена перевозок из каждого ПО в каждый ПН предполагается, что они не зависят от количества перевозимого груза т. е. количество транспортных средств всегда достаточно для осуществления любого объема перевозок. Запасы заявки и времена приведены в табл. 14.1, построенной так же, как обычная транспортная таблица, с той разницей, что в правом верхнем углу каждой клетки вместо стоимостей стоят времена

Таблица 14.1

Требуется выбрать перевозки таким образом, чтобы удовлетворялись балансовые условия

и, кроме того, обращалось в минимум время окончания всех перевозок Т.

Выразим время Т через времена и перевозки Так как все перевозки заканчиваются в момент, когда кончается самая длительная из всех перевозок, то время Т есть максимальное из всех времен стоящих в ячейках, содержащих ненулевые перевозки. Запишем это в виде формулы:

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

Мы хотим найти такой план перевозок для которого время Т обращается в минимум:

Поставленная задача не является задачей линейного программирования, так как величина Т — не линейная функция переменных

Эту задачу можно свести к решению задач линейного программирования, но не одной, а нескольких. Однако, мы не будем заниматься таким сведением, а продемонстрируем расчетный метод, позволяющий непосредственно найти оптимальное решение ТЗ по критерию времени преобразованием транспортной таблицы. Этот метод называется «методом запрещенных клеток». Проще всего будет пояснить его на примере.

Пример. Условия ТЗ по критерию времени (запасы, заявки и времена перевозок) даны в табл. 14.2. Требуется найти план перевозок, укладывающийся в минимальное время, и указать это время.

Решение. Начальный план перевозок можно было бы, как мы и делали раньше, составить способом северо-западного угла, но мы видим что при этом получится (за счет клетки (1,1)) очень большое время. Попытаемся этого избежать, «запретив» себе ставить отличные от нуля перевозки в клетки (1,1) и (4,1), где стоят самые большие времена в таблице. Перечеркнем в табл. 14.3 эти клетки и составим новый план перевозок так, чтобы в первую очередь занимать клетки с малыми временами.

В плане (табл. 14.3) время окончания всех перевозок равно 8 — оно достигается в клетке (3, 2). Попробуем улучшить план, запретив себе Для дальнейшего использования все клетки, где время и перечеркнув эти клетки. Перенесем 14 единиц Груза по циклу, указанному в табл. 14.3; этим мы устраним перевозки со временем 8. Получится план, приведенный в табл. 14.4, со временем окончания (клетка (3, 3)).

Чтобы еще улучшить этот план, нам нужно устранить перевозки из клетки (3, 3), запретив, кроме того, перенос в клетку (1, 5), содержащую то же время. 7 из 13 единиц, стоящих в клетке (3, 3), устраняем переносом по циклу, показанному в табл. 14.4. Новый план приведен в табл. 14.5.

Таблица 14.2

Таблица 14.3

Таблица 14.4

Таблица 14.5

Попробуем избавиться от оставшихся 6 единиц в клетке (3,3) путем их циклического переноса. Для этого испробуем все возможные переносы из этой клетки, начинающиеся горизонтально или вертикально. Горизонтальный перенос в клетку (3,5) исключен, так как столбец 5 не содержит не запрещенных клеток. Горизонтальный перенос в клетку (3,1) также исключен, так как для этого пришлось бы уменьшить перевозки в клетке (2,1), что невозможно.

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

Из этого мы делаем заключение, что план перевозок, данный в табл. 14.5, оптимален, и минимальное время перевозок равно