Переход от одного опорного решения к другому. Числа и называют потенциалами

Числа и называют потенциалами. В распределительную таблицу добавляют строку и столбец . Потенциалы и находят из равенства , справедливого для занятых клеток. Одному из потенциалов дается произвольное значение, а остальные потенциалы определяются однозначно. Если известен потенциал , то , если известен потенциал , то .

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

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

Для свободной клетки с строится цикл (цепь, многоугольник), все вершины которого, кроме одной, находятся в занятых клетках; углы прямые, число вершин четное. Около свободной клетки цикла ставится знак (+), затем поочередно проставляют знаки (-) и (+). У вершин со знаком (-) выбирают минимальный груз, его прибавляют к грузам, стоящим у вершин со знаком (+), и отнимают от грузов у вершин со знаком (-). В результате перераспределения груза получим новое опорное решение. Это решение проверяем на оптимальность и т.д. до тех пор, пока не получим оптимальное решение.