Лекция 3. Транспортная задача

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

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

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

Пример 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неотрицательны, то оптимальный план достигнут и тем самым задача решена.