4.5. Задача с минимизацией времени перевозки скоропортящихся грузов

Условия задачи также формулируются в виде матрицы типа табл. 4.1-4.3.

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

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

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

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

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

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

Шаг 4. Во всех клетках матрицы, где t_ij> max t_ij¹, заменить t_ij на число М = ∞.

Шаг 5. Отыскать для измененной матрицы решение, при котором линейная форма достигает минимума. Если в полученном решении x_ij>0 расположены только в клетках, где t_ij < М, то снова находим max t_ij¹¹ и повторяем шаги 4 и5. Если же в полученном решении имеется хотя бы один x_ij>0, расположенный в клетке с t_ij = М, то оптимальным по критерию t(Х) = max t_ij (x_ij>0 – план перевозок, t(Х) = время наиболее продолжительной перевозки) будет предыдущее решение. Очевидно, что после конечного числа повторений шагов 3,4 и 5 будет получено оптимальное решение, т.е. такой план перевозок, по которому грузы всем потребителям будут доставлены за возможно короткое время.

Приведем пример

В табл. 4.8 приведена матрица условий задачи.

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

.

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

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

Блокируем клетки А₁ В₁, А₃ В₄ и А₄ В₁, у которых время перевозки равно 10ч, и находим новый план (табл. 4.10). По этому плану максимальное время перевозки составляет 8 ч. Ни одна из загрузок (табл. 4.10) не попадает в блокированную клетку, поэтому решение надо продолжить.

Таблица 4.8

Матрица условий

Пункт отправ ления	С трока Столб.	Пункт назначения				Налич. Груза (т)
		B1	B2	B3	B4
		V1=8	V2=5	V3=6	V4=12
A1	U1=0	10	5 0	7	12 50	50
A2	U2=-4	4 10	1 20	2 30	8	60
A3	U1=-3	6	2	3 20	10	20
A4	U1=2	10 20	9	8	15	20
Потребность в Грузе (т)		30	20	50	50	150

Таблица 4.9