Вырожденность

В ходе выполнения симплекс-метода проверка условия допустимости может

привести к неоднозначному выбору исключаемой переменной. В этом случае на

следующей итерации одна или несколько базисных переменных примут нулевое

значение. Тогда новое решение будет вырожденным.

В вырожденном решении нет никакой опасности, за исключением небольших

теоретических неудобств, которые мы далее кратко обсудим. С практической

точки зрения вырожденность объясняется тем, что в исходной задаче присутствует по крайней мере одно избыточное ограничение. Для того чтобы лучше понять практические и теоретические аспекты явления вырожденности, рассмотрим численный пример. Графическая интерпретация задачи поможет наглядно

разобраться в этом явлении.

Альтернативные оптимальные решения

Когда прямая (если рассматривается двухмерная задача ЛП, в общем случае —

гиперплоскость), представляющая целевую функцию, параллельна прямой

(гиперплоскости), соответствующей связывающему неравенству (которое в точке

оптимума выполняется как точное равенство), целевая функция принимает одно

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

бесконечное множество. Этот пример также проиллюстрирует практическую значимость альтернативных решений.

Неограниченные решения

В некоторых задачах ЛП значения переменных могут неограниченно возрастать

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

целевая функция может возрастать (задача максимизации) или убывать (задача

минимизации) неограниченно.

Неограниченность решения задачи свидетельствует только об одном: модель разработана не достаточно корректно. Типичные ошибки, приводящие к построению та-

ких моделей, заключаются в том, что не учитываются ограничения, не являющиеся

избыточными, и не точно оцениваются параметры (коэффициенты) ограничений.

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

и значения целевой функции.