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

1. Найти начальный план перевозок транспортной задачи методом «северо-западного угла» или методом минимальной стоимости. Число заполненных клеток должно быть равным .

2. Найти .

3. Найти потенциалы из системы уравнений: , составленной для занятых клеток.

4. Найти оценки для свободных клеток: .

5. Если среди чисел нет отрицательных значений, все , то найденный опорный план являетсяоптимальным.

6. Если же для некоторой свободной клетки , то исходный опорный план не является оптимальным и необходимо перейти к новому опорному плану , причем

Z( ) ≤ Z( )

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

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

7. Среди клеток, имеющих знак «–» отыскивается та, которая содержит минимальную величину поставки. Эта величина прибавляется к содержимому клеток, имеющих знак «+» и вычитается из содержимого клеток, имеющих знак «–».

8. Для нового опорного плана заново рассчитываются потенциалы , и оценки(п.3)