Появление вырожденного базисного решения

Рассмотрим задачу:

Решим задачу симплексным методом. Введем дополнительные переменные и составим симплекс-таблицу.

Базис	Свободный	Переменные	Оценочные
	член						отношения
			-1
			-2
			-4				7/3
		-2

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

Базис	Свободный	Переменные	Оценочные
	член						отношения
			-1
				-3
				-б
			-1				!

Полученное решение вырожденно, так как основная переменная и вновь не является оптимальным. Переходим к новой симплекс-таблице.

Базис	Свободный	Переменные	Оценочные
	член						отношения
				-2
				-3
					-2
				-1

Решение так же вырожденно, так как основная компонента

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

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

Замечание. Вырождение, полученное при оптимальном решении может привести к альтернативному оптимуму даже при нулевых коэффициентах при всех не основных переменных в целевой функции.