Переход к лучшему опорному плану

Пусть рассматриваемый опорный план не оптимален. Для перехода к плану с меньшим значением целевой функции необходимо увеличить на максимально возможную величину объем перевозки в любой небазисной клетке (i, j) с. Обычно решение отыскивается быстрее, если выбрана клетка с наибольшим значением .

Пусть выбрана клетка с. Соответствующая небазисная переменная =0. Объем перевозки увеличиваем пока на неизвестную величину Q. Тогда для того, чтобы не нарушить баланс строки, необходимо в строке уменьшить объем перевозки некоторой базисной переменной на эту же величину Q. Но, уменьшив ее, мы нарушаем баланс столбца, который может быть восстановлен добавлением Q к некоторой базисной переменной столбца. Нарушенный баланс строки восстанавливается уменьшением на Q некоторой другой базисной переменной строки, и т. д.

Если таким образом удается прийти к уменьшению некоторой базисной переменной столбца, то действительно можно увеличить объем перевозки в клетке. Тем самым будут найдены объемы перевозок, увеличиваемые или уменьшаемые на величину Q. Если полученные клетки соединить прямыми линиями, то получается замкнутая линия, называемая циклом. Цикл обладает следующим свойством: линия начинается и кончается в небазисной клетке, остальные вершины ломаной принадлежат строкам и столбцам таблицы, на пересечении которых находятся базисные клетки, угол между двумя соседними сторонами равен 90⁰. Такой цикл всегда существует для любой небазисной клетки и он единственный.

Пусть цикл, соответствующий клетке, построен. В клетке ставится знак «+», а далее поочередно в вершинах цикла ставятся «-», «+»… Объемы перевозок, отмеченные «+», увеличиваются, а «-» — уменьшаются на величину Q=min{}. Таким образом, величина Q прибавляется ко всем объемам перевозок, отмеченных знаком «+», и вычитается от всех объемов перевозок, отмеченных знаком «-».

В результате получаем новый опорный план, в котором переменная становится новой базисной переменной, а одна из базисных переменных, значение которой стало =0, становится небазисной переменой (выводится из базиса). При этом значение целевой функции уменьшается на. Полученный новый опорный план записывается в новой распределительной таблице, и вновь проверяется на оптимальность и т. д. пока не получат оптимальный опорный план.

Рис. 1.

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