Переход от одного опорного решения к другому

Наличие положительной оценки свободной клетки (Δij > 0) при проверке опорного решения на оптимальность свидетельствует о том, что полученное решение не оптимально и для уменьшения значения целевой функции надо перейти к другому опорному решению.

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

Рассмотрим переход от одного опорного решения к другому на заданном примере.

Строим цикл для клетки (1,3), имеющей положительную оценку. У вершин цикла ставим знаки (+) и (—) и записываем грузы:

У вершин со знаком (—) выбираем минимальный груз, он равен 60. Его прибавляем к грузам, стоящим у положительных вершин, и отнимаем от грузов, стоящих у отрицательных вершин. Получаем новый цикл:

Новое опорное решение:

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

Имеем

Построим цикл для клетки с положительной оценкой Δ21 = 1:

Произведем перераспределение грузов:

Получим новое решение, которое занесем в таблицу.

Получим

Все оценки свободных клеток отрицательные, следовательно, найденное решение оптимальное. Итак,

Стоимость транспортных расходов равна

По сравнению с исходным опорным решением транспортные расходы уменьшились на 1610 — 1280 = 330 усл. ед.