Вырожденность и зацикливание

Определение 2.13. Допустимое базисное решение, в котором одна или более базисных переменных равны нулю, называется вырожденным допустимым базисным решением. Допустимое базисное решение, в котором все базисные переменные положительны, называется невырожденным.

Вырожденность может присутствовать в первоначальной формулировке задачи (если некоторые правые части равны нулю); она может также возникать при симплексных вычислениях. Это происходит, когда, по крайней мере, две строки имеют одинаковые значения минимального отношения, вычисляемого по правилу (2.10).

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

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

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