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

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

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

Т = min (2.14)

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

Задача ставится следующим образом. Имеется m поставщиков A₁, А₂, …, А_m с запасами а₁, а₂, …, a_m и n потребителей В₁, В₂, …, В_n с заявками b₁, b₂, …, b_n. Сумма запасов равна сумме заявок a_i = b_j, (2.15)

Заданы времена перевозок t_ij от каждого поставщика A_i к каждому потребителю В_j, предполагается, что они не зависят от количества перевозимого груза x_ij, то есть, количество транспортных средств всегда достаточно для осуществления любого объема перевозок. Запасы a_i, заявки b_j, времена t_ij приведены в табл. 2.21, построенной так же, как обычная транспортная таблица, с той разницей, что в правом верхнем углу каждой клетки вместо стоимостей с_ij стоят времена t_ij.

Таблица 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) таким образом, чтобы удовлетворялись условия x_ij = a_i , (2.16)

x_ij = b_j (2.17)

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

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

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

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

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