← Назад в блог••8 мин чтения

Особые случаи в симплекс-методе: Вырожденность, Неограниченность и Альтернативные оптимумы

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

Интерактивный калькулятор

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

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

Открыть симплекс-калькулятор →

Введение

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

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

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

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

2. Неограниченность целевой функции

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

В симплекс-таблице этот случай выявляется, когда в строке целевой функции выбран ведущий столбец с отрицательной оценкой, но все коэффициенты этого столбца меньше либо равны нулю ($a_{ik} \le 0$). Поскольку вычислить положительное отношение $\theta$ невозможно, ни одна переменная не может покинуть базис, что свидетельствует о незамкнутости многогранника решений в направлении оптимизации.

3. Альтернативные оптимумы (множество оптимальных решений)

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

В финальной оптимальной симплекс-таблице этот случай легко обнаружить: хотя бы одна свободная (небазисная) переменная имеет относительную оценку, в точности равную нулю ($\Delta_j = 0$). Если ввести эту переменную в базис, получится новая вершина с точно таким же оптимальным значением целевой функции $Z$, а весь отрезок между ними представляет собой континуум оптимальных решений.

Готовы решить задачу линейного программирования?

Мгновенные пошаговые симплекс-таблицы с полным анализом чувствительности и теневыми ценами для любой задачи ЛП.

Запустить калькулятор
Operations Research

Пакет исследования операций

Исследуйте полную коллекцию интерактивных калькуляторов для линейного и дискретного программирования.