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

Нередко при выполнении перевозок решающее значение приобретает фактор времени. Это имеет место, например, при вывозке зерна на заготовительные пункты во время уборки урожая, при перевозке скота и др. Рассмотрим такую задачу.

Пусть из пунктов А₁, А₂,..., А_i,...,А_m в пункты В₁, В₂,..., В_j, …, В_n необходимо доставить однородный продукт в возможно короткое время. Запасы продукта в пунктах отправления и потребность в нём в пунктах назначения равны между собой и составляют соответственно а₁, а₂,..., а_i,..., a_m и b₁, b₂, …, b_j, …, b_n единиц. Время доставки груза из каждого пункта А_i в каждый пункт В_j известно и составляет t_ij часов.

Таблица 26

Пункт отправления	Вспомогательные коэффициенты	Пункт назначения				Наличие груза, т
		B1	B2	B3	B4
		5	5	0,4	2
A1	0	5 30	7	2	4	30
A`2	4	9	9 24	6	6 0	24
A``2	1,8	7,5 10	7,5 26	5	100	36
A3	3	100	9,6	4,840	6,410	50
A4	-1,9	5	4 20	1	2	20
Потребность в грузе, т	40	70	40	10	160

Таблица 27

Пункт отправления	Пункт назначения
	B1	B2	B3	B4
A 1	30
A2	8*	24* 22**
A3			32	8
A4		20

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

T = t _ijx_ij (23)

не даст нужного результата: решение, для которого величина Т достигает минимального значения, как, правило, не будет оптимальным по времени. В табл. 28 представлен план перевозок, оптимальный по минимуму линейной формы Т. Все перевозки по этому плану будут выполнены за 8 ч. при Т = 370 ч.

Таблица 28

Пункт отправления	Потенциалы	Пункт назначения				Наличие груза, т
		B1	B2	B3	B4
		2	8	5	3
A1	0	3	8 10	6	3 20	30
A2	-4	2	4 30	1 20	7	50
A3	0	2 20	9	5 10	4	30
Потребность в грузе, т	20	40	30	20	110

В табл. 29 показан другой план этой задачи, по которому значение линейной формы несколько больше - Т = 380 ч (план по критерию Т не оптимален, так как t_ij < u_i + v_j), но все перевозки выполняются за 5 ч.

Таблица 29

Пункт отправления	Потенциалы	Пункт назначения				Наличие груза, т
		B1	B2	B3	B4
		3	9	6	3
A1	0	3 10	8	6	3 20	30
A2	-5	2	4 40	1 10	7	50
A3	-1	2 10	9	5 20	4	30
Потребность в грузе, т	20	40	30	20	110

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

Обозначим через x_ij количество груза, планируемого к отправке из пункта A в пункт B. Тогда при выбранном критерии оптимальности задача формируется следующим образом: определить набор чисел x_ij (план перевозок), для которого время t (X) наиболее продолжительной перевозки

t (X) = max t_ij для x_ij > 0 (24)

достигает минимума при условиях

x_ij = b_j, j = 1, 2, …, n; (25)

x_ij = a_i, i= 1, 2, …, m; (26)

x_ij > 0, i= 1, 2, …, m; j = 1, 2, …, n. (27)

Выражение (24) означает наибольшее из времен запланированных перевозок.

Так как t (X) - нелинейная функция своих переменных x_ij, то модель (24) - (27) не является задачей линейного программирования. Это задача на минимакс, и решить её методами линейного программирования нельзя. Вместе с тем решение задачи можно свести к последовательному решению одним из способов распределительного метода (методом потенциалов) серии обычных транспортных задач, где оптимальное решение предыдущей задачи служит исходным планом последующей задачи. Процедура вычислений складывается из следующих шагов.

1.Составить матрицу условий так, как это делают при решении обычной транспортной задачи.

2. Найти методом потенциалов план, у которого линейная форма

t_ij x_ij достигает минимального значения.

3. Определить max t_ij (наибольшее из времён) запланированных перевозок (где x_ij >0).

4. Во всех клетках матрицы, где t_ij = max t`_ij, заменить на число M =.

5. Отыскать для изменённой матрицы решение, при котором линейная форма t_ijx_ij достигает минимума. Если в полученном решении

x_ij > 0 расположены только в клетках, где t_ij < М, то снова находим mах t``_ij и повторяем шаги 4 и 5. Если же в полученном решении имеется хотя бы один x_ij > 0, расположенный в клетке с t_ij = М, то оптимальным по критерию (24) будет предыдущее решение.

Очевидно, что после конечного числа повторений шагов 3, 4 и 5 будет получено оптимальное решение, т.е. такой план перевозок, по которому грузы всем потребителям будут доставлены за возможно короткое время.

Поясним процесс вычислений на конкретном примере. В табл. 30 приведена матрица условий задачи. В правом верхнем углу клеток записано время движения автомобилей между соответствующими пунктами в часах.

Таблица 30

Пункт отправления	Пункт назначения				Наличие груза, т
	B1	B2	B3	B4
A1	10	5	7	12	50
A2	4	1	2	8	60
A3	6	2	3	10	20
A4	10	9	8	15	20
Потребность в грузе, т	30	20	50	50	150

Таблица 31

Пункт отправления	Потенциалы	Пункт назначения				Наличие груза, т
		B1	B2	B3	B4
		8	5	6	12
A1	0	10	5 0	7	12 50	50
A2	-4	4 10	1 20	2 30	8	60
A3	-3	6	2	3 20	10	20
A4	2	10 20	9	8	15	20
Потребность в грузе, т	30	20	50	50	150

Решив эту матрицу методом потенциалов, находим план (табл. 31), обеспечивающий минимум линейной формы. Наибольшее время перевозки по этому плану составляет 12 ч (перевозка А₁ в В₄). Во всех клетках, где время доставки груза равно или больше этой величины (клетки А₁В₄ и А₄В₄), заменяем его числом М = 100 (блокируем клетки) и вновь отыскиваем план, у которого линейная форма имеет наименьшую величину (табл. 32). Поскольку ни одна из загрузок не находится в блокированной клетке (с числом 100), продолжаем вычисления.

Таблица 32

Пункт отправления	Потенциалы	Пункт назначения				Наличие груза, т
		B1	B2	B3	B4
		9	5	7	13
A1	0	10	5 20	7 30	100	50
A2	-5	4 10	1	2	8 50	60
A3	-4	6	2	3 20	10	20
A4	1	10 20	9	8	100	20
Потребность в грузе, т	30	20	50	50	150

Таблица 33

Пункт отправления	Потенциалы	Пункт назначения				Наличие груза, т
		B1	B2	B3	B4
		10	5	7	14
A1	0	100	5 20	7 30	100	50
A2	-6	4 10	1	2	8 50	60
A3	-4	6 20	2	3 0	100	20
A4	1	100	9	8 20	100	20
Потребность в грузе, т	30	20	50	50	150

Теперь наибольшее время перевозки составляет 10 ч (клетка А₄В₁,), поэтому блокируем клетки А₁B₁, А₃В₄ и А₄В₁, у которых время равно 10 ч, и находим новый план (табл. 33) с минимальным значением линейной формы. Из таблицы видно, что ни одна из загрузок не находится в блокированной клетке, поэтому процесс вычислений необходимо продолжить.

Таблица 34

Пункт отправления	Потенциалы	Пункт назначения				Наличие груза, т
		B1	B2	B3	B4
		0	5	6	100
A1	0	100	5 20	7	100 30	50
A2	-5	4 30	1	2 30	100	60
A3	-4	6	2	3 20	100	20
A4	0	100	100	100	100 20	20
Потребность в грузе, т	30	20	50	50	150

Поскольку наибольшая продолжительность из планируемых перевозок равна 8 ч (клетки А₂В₄ и А₄В₃), блокируем клетки А₂В₄, А₄В₂ и А₄В₃, у которых время равно 8 ч или больше 8 ч. В найденном затем новом плане (табл. 34) две загрузки находятся в блокированных клетках.Это свидетельствует о том, что план перевозок, обеспечивающий доставку грузов всем потребителям за возможно короткое время, найден (см. табл. 33)