Закрытая транспортная задача

 

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

Рассмотрим решение этой задачи на примере.

Пример 1. В двух пунктах отправления А ₁ и А ₂ находится соответственно 150 и 90 тонн груза. В пункты В ₁, В ₂ и В ₃ требуется доставить соответственно 60, 70 и 110 тонн груза. Стоимости перевозок тонны грузы из пункта А _i в пункты B_j записаны матрицей:

 

.

 

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

Сумма поставок 150+90=240, сумма потребностей 60+70+110=240. Сумма поставок равна сумме потребностей, поэтому мы имеем закрытую модель транспортной задачи.

Запишем исходные данные в таблицу 1. В правом верхнем углу клетки пишем транспортные расходы по перевозке груза из пункта  в пункты

 

Таблица 1

	60	70	110
150	10 60	12 70 -	6 + 20	10
90	5   4	5 λ + 6	8 - 90	4
	0	2	4

 

Составим опорный план по методу северо-западного угла. Заполнение начинаем с клетки (1; 1): , первый столбец закрыт. Переходим к клетке (1; 2): , второй столбец закрыт; далее, переходим к клетке (1; 3): . Т.к. в третьем столбце остался остаток, равный 90, то переходим к заполнению клетки (2; 3): . Опорное исходное решение построено. Число загруженных клеток должно равно m+n-1=2+3-1=4 – невырожденный план. Если это условие нарушается, то добавляем нулевую поставку. Чтобы это условие выполнялось. Этому плану соответствуют затраты в количестве:

 руб.

 

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

После построения опорного решения все переменные разбиты на 2 группы: x_kl – базисные и x_pq – свободные, где (p, q) – пустая клетка. Линейные функции выразятся через свободные так:

.                                (1)

Для нахождения коэффициентов γ _pq при свободных переменных сопоставим каждому пункту отправления A_i некоторую величину u_i, которую назовем потенциалом пункта A_i, и каждому пункту назначения B_j величину v_j – потенциал пункта B_j. Эти величины связаны равенством

,                                             (2)

где c_kl – стоимость перевозки одной тонны груза из A_k в B_l. Доказывается, что совокупность уравнений (2), составленных для всех базисных переменных, составляет совместную систему линейных уравнений, причем значение одной из переменных можно задавать произвольно, тогда значения остальных переменных находятся из системы однозначно. Обозначим для свободных переменных сумму соответствующих потенциалов через , т.е.  и назовем ее косвенной стоимостью. Тогда коэффициенты γ _pq в (1) определяются так:

.

Если все величины γ _pq неотрицательны, то исходное решение является оптимальным.

В нашем случае γ ₂₂= -1. Следовательно, оптимальное решение не достигнуто. План можно улучшить, «загружая» максимально клетку (2; 2). В данную клетку поместим λ (т.). Осуществляем перераспределение груза, выбрав подходящий контур (цикл), состоящий их горизонтальных и вертикальных отрезков. Выбираем λ с таким расчетом, чтобы вместо клетки, в которую поместили λ, пустой стала ранее «загруженная» клетка, баланс груза по строкам и столбцам сохранился, поставки не были отрицательными, количество загруженных клеток не превышало m + n -1. Получается квадратный цикл:

 

70- λ              20+ λ

 

λ              90- λ

 

 

По циклу перемещают наименьшую отрицательную поставку

Таким образом, λ можно принять равной 70, и получаем второй базисный план перевозок, который представлен в таблице 2.

 

Таблица 2

Bj Ai	60	70	110	ui
150	10 60 -	12   3	6 + 90	0
90	5 λ + 12	5 70	8 - 20	2
vj	10	3	6

 

 

Вычисляем транспортные расходы:

 

 руб.

 

Находим потенциалы и косвенные тарифы. В клетке (2; 1) отрицательная разность. Следовательно, оптимальное решение не достигнуто. План можно улучшить максимально «загружая» клетку (2; 1). Повторяя предыдущее рассуждение, получим

 

 

Таблица 3

Bj Ai	60	70	110	ui
150	10 40	12   10	6 110	10
90	5 20 12	5 70	8   1	5
vj	0	0	-4

 

 

Вычисляем транспортные расходы:

 

 руб.

 

Вычисляем потенциалы и косвенные тарифы. Т.к. все величины γ _pq неотрицательны, то оптимальный план достигнут и тем самым задача решена.