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

Пусть имеется исходное базисное решение.

1. Для каждой строки и столбца матрицы перевозок необходимо задать потенциалы и для каждой базисной (заполненной) клетки записать уравнение вида (2.16). Получим систему уравнений для потенциалов.

2. Так как заполненных клеток , то соотношение (2.16) задают систему простейших уравнений с неизвестными. Дополняя ее условием: , получают единственное решение системы потенциалов. Числа удобно записать в дополнительном столбце справа от матрицы перевозок, а числа в дополнительной строке внизу таблицы.

3. Для каждой свободной строки находят косвенный тариф .

4. Если косвенный тариф больше истинного, то переходят к пункту 5. Если косвенный тариф меньше или равен истинному тарифу, то данное базисное решение является оптимальным.

5. Среди разностей между косвенным и истинным тарифами, найденных в пункте 3, выбирают наибольшую. Находят соответствующую ей свободную клетку.

6. Для свободной клетки строят цикл перечета. По нему производят сдвиг, преобразовав свободную клетку в базисную. Получают новое базисное решение.

7. Возвращаются к пункту 1 алгоритма.