Метод потенциалов
В результате указанных выше перемещений грузов в пределах клеток, связанных циклом с данной свободной клеткой, определяют новый опорный план транспортной задачи. Описанный выше переход от одного опорного плана транспортной задачи к другому ее опорному плану называется сдвигом по циклу пересчета.
Следует отметить, что при сдвиге по циклу пересчета число занятых клеток остается неизменным, а именно остается равным m+n-1. При этом если в минусовых клетках имеется два (или более) одинаковых числа xij, то освобождается лишь одну из таких клеток, а остальные остаются занятыми (с нулевыми поставками).
Полученный новый опорный план транспортной задачи проверяют на оптимальность. Для этого определяют потенциалы пунктов отправления и назначения и находят числа aij=Vj-Ui-cij для всех свободных клеток. Если среди этих чисел не окажется положительных, то это свидетельствует о получении оптимального плана. Если же положительные числа имеются, то следует перейти к новому опорному плану. В результате итерационного процесса после конечного числа шагов получают оптимальный план задачи.