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

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

На практике в большинстве транспортных задач именно критерий стоимости является главным, определяющим эффективность плана перевозок. Однако в некоторых случаях на первый план выдвигается не стоимость перевозок 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. Эту задачу можно свести к решению задач линейного программирования, но не одной, а нескольких. А для непосредственного решения транспортной задачи по критерию времени применяется, так называемый «метод запрещенных клеток».