Понятие о вырождении. Монотонность и конечность симплексного метода. Зацикливание

Базисный план ЗЛП, записанной в предпочтительном виде невырожден, когда свободные члены всех уравнений положительны, и вырожден, если среди них имеются нули.

Определение: Каноническую ЗЛП называют невырожденной, если все ее опорные планы невырождены. Если среди опорных планов есть хотя бы один вырожденный, то задачу называют вырожденной.

Пусть ЗЛП решается на максимум. На двух последовательных итерациях значения целевой функции связаны соотношением:

где

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

Конечность алгоритма следует из конечного числа опорных планов ЗЛП (их не больше ).

Если ЗЛП вырожденная, то возможны случаи, когда . В этом случае значение целевой функции не улучшится. Предположим, что процесс продолжается без остановки, порождая бесконечную последовательность опорных планов. Вследствие конечности множества опорных планов в этой последовательности некоторые планы должны повторяться. В силу равенства для них целевой функции они должны лежать в одной гиперплоскости и быть вершинами выпуклого многогранника. Поэтому должна встретиться цепочка (цикл) , в которой начальный и конечный планы совпадают, при­чем в силу монотонности метода

Процесс продолжится неограниченно, если несколько последовательных вырождении приведут к образованию цикла. Такое явление называется зацикливанием. Зацикливание возможно только для вырожденных задач. Теория и практика показывают, что зацикливание возникает при весьма маловероятном сочетании условий. Известно лишь несколько специально разработанных (очень сложных) примеров, в процессе решения которых возникает зацикливание. Точный алгоритм вывода из цикла достаточно сложен. В простейшем случае при появлении цикла следует изменить последовательность вычислений путем изменения выбора разрешающего столбца. Другое правило рекомендует изменить выбор разрешающей строки. Если в процессе симплексных преобразований появляется несколько минимальных симплексных отношений, то в качестве разрешающей выбирают ту строку, для которой будет наименьшим отношение элементов первого столбца к разрешающему. Если при этом снова оказывается несколько минимальных отношений, то составляются отношения элементов второго столбца к разрешающему, и так до тех пор, пока разрешающая строка не определится однозначно.