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

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

c

i,j <= с

i,j ,

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

В таблице 6 мы получили в двух клетках c

i,j > с

i,j , теперь можно построить цикл в любой из этих двух клеток. Выгоднее всего строить цикл в той клетке, в которой разность c

i,j - с

i,j больше.

Таблица 7

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

После этого необходимо подсчитать потенциалы αi и βj.

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