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

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

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

Т = min (2.14)

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

Задача ставится следующим образом. Имеется m поставщиков A1, А2, …, Аm с запасами а1, а2, …, am и n потребителей В1, В2, …, Вn с заявками b1, b2, …, bn. Сумма запасов равна сумме заявок ai = bj, (2.15)

Заданы времена перевозок tij от каждого поставщика Ai к каждому потребителю Вj, предполагается, что они не зависят от количества перевозимого груза xij, то есть, количество транспортных средств всегда достаточно для осуществления любого объема перевозок. Запасы ai, заявки bj, времена tij приведены в табл. 2.21, построенной так же, как обычная транспортная таблица, с той разницей, что в правом верхнем углу каждой клетки вместо стоимостей сij стоят времена tij.

Таблица 2.13

ПО ПН В1 В2 . . . Вj . . . Вn Запасы aj
A1 t11 t12 . . . t1j . . . t1n a1
A2 t21 t22 . . . t2j . . . t2n a2
. . . . . . . . . . . . . . . . . . . . . . . .
Аi ti1 ti2 . . . tij . . . tin ai
. . . . . . . . . . . . . . . . . . . . . . . .
Am tm1 tm2 . . . tmj . . . tmn am
Заявки bj b1 b2 . . . bj . . . bn

Требуется выбрать перевозки (хij) таким образом, чтобы удовлетворялись условия xij = ai , (2.16)

xij = bj (2.17)

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

Выразим время Т через времена tij и перевозки xij. Так как все перевозки заканчиваются в тот момент, когда кончается самая длительная из всех перевозок, то время Т есть максимальное из всех времен tij , стоящих в ячейках, содержащих ненулевые перевозки, то есть, (2.19)

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

По условию задачи требуется, чтобы (2.20)

Начальное распределение перевозок в этой задаче может быть составлено методом «северо-западного угла», то есть, начиная с клетки (1,1) либо методом наименьшего времени, то есть, начиная с клетки с наименьшим значением времени перевозок. На этом сходство подхода к решению данной задачи с задачей по критерию стоимости кончается, в связи с тем, что поставленная задача не является задачей линейного программирования, так как величина Т – нелинейная функция переменных хij. Эту задачу можно свести к решению задач линейного программирования, но не одной, а нескольких. А для непосредственного решения транспортной задачи по критерию времени применяется, так называемый «метод запрещенных клеток».