2.6 О конечности симплекс-метода

Вопрос, касающийся конечности числа итераций симплекс-алгоритма, решается по-разному в зависимости от используемого уточнения правила выбора ведущего элемента zrs и от такой осо­бенности задачи, как вырожденность.

Задача ЛП считается вырожденной, если у нее существуют базисные допустимые решения х такие, что \{j \ Xj ф 0}| < т. Решение х в таком случае тоже называется вырожденным.

В случае невырожденной задачи в каждой прямо допустимой симплекс-таблице все элементы нулевого столбца, кроме, быть может, ^оо, положительны: Zio > 0 для любого г > 1. Тогда при каждом преобразовании симплекс-таблицы элемент zoo увеличи­вается:

z00 — z0s-        > ^00)

zrs

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

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

21неограниченно выполнять один и тот же цикл преобразований (при условии, что выбор ведущего элемента является детермини­рованным).

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