Алгоритм решения транспортной задачи методом потенциалов

Таблица 5.8

Таблица 5.7

Пн По	В1	В2	В3	Запасы	αi
А1	2 2 0	1 3	1 1
А2	4 4 60	3 2	3 5
А3	3 3	2 2 40	2 6
Потребности				150=150
βj

Назовем псевдостоимостью перевозки единицы груза из пункта А_i в пункт В_j величину

Рассчитанные для таблицы 5.7 псевдостоимости помещены в левых верхних углах этой таблицы.

Потенциалы и псевдостоимости имеют любопытную экономическую интерпретацию. Предположим, что имеется перевозчик, который взимает с пункта А_i плату α_i за вывоз единицы груза, а с пункта В_j - плату β_j за ввоз единицы груза. Тогда псевдостоимость – это та выручка, которую получает перевозчик за перевозку единицы груза из пункта А_i в пункт В_j. Полезно применить эту интерпретацию для лучшего понимания того условия оптимальности опорного плана, которое будет приведено ниже.

А пока докажем следуйте утверждение:

цена γ_ij цикла перерасчета, проходящего через свободную клетку (ij), выражается формулой:

Для доказательства рассмотрим рисунок 5.1.

Рис. 5.1.

Клетка (ij) - единственная свободная клетка изображенного цикла пересчета. Цена γ_ij цикла пересчета, согласно определению, равна

Так как для базисных клеток выполняются равенства (5.6), то
можно записать:

, что и требовалось доказать.

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

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

Например, опорный план перевозок таблицы 5.7 не является
оптимальным, так, как для клетки (2.2) псевдостоимость больше
стоимости. Цена, цикла пересчета, проходящего через эту клетку
отрицательна и равна 2–3=–1 (в этом можно лишний раз
убедиться, подсчитав цену, исходя из определения). Сделав максимально допустимый сдвиг величины h=40, получим таблицу 5.8.

Пн По	В1	В2	В3	Запасы	αi
А1	2 2 0	0 3	1 1
А2	4 4 20	2 2	3 5
А3	3 3	1 2	2 6
Потребности				150=150
βj

Построим систему потенциалов для таблицы 5.8. При небольшом навыке это можно сделать, не выписывая систему уравнений. Рассчитав затем псевдостоимости, видим, что для всех свободных клеток псевдостоимости не превосходят стоимостей. Следовательно, опорный план таблицы 5.8 оптимален.

f_min=40•1+20•4+40•2+50•3=350

1. Отыскиваем исходный опорный план перевозок (к примеру, методом минимального элемента). Переход к пункту 2.

2. Строим систему потенциалов. Для этого для каждой базисной
клетки (p,q) записываем уравнение α_p+β_q=c_pq. Получается
система m+n–1 уравнений с m+n неизвестными потенциалами. Один из
потенциалов полагаем равным 0 и находим из системы остальные
потенциалы. Переход к пункту 3.

3. Для каждой свободной клетки (i, j) вычисляем псевдостоимость . Если для всех свободных клеток , то план оптимален, и алгоритм останавливается. Если же найдется свободная клетка (i, j), для которой , то переход к пункту 4.

4. Строим цикл пересчета, проходящий через клетку (i, j),
делаем по нему максимально допустимый сдвиг, получив, таким образом,
новый опорный план. Переход к пункту 2.

Пример. Исходные данные задачи приведены в таблице 5.9.

Методом минимального элемента находим исходный опорный план перевозок и записываем его в ту же таблицу.