Особые случаи в симплекс-методе: Вырожденность, Неограниченность и Альтернативные оптимумы
Как распознать и корректно обработать вырожденность, неограниченность целевой функции и множественные оптимальные решения в симплекс-таблице.
Попробуйте пошаговый калькулятор симплекс-метода и чувствительности
Введите целевую функцию и ограничения, чтобы увидеть симплекс-таблицы, разрешающие элементы и анализ чувствительности в реальном времени.
Введение
Хотя стандартный симплекс-метод гарантированно находит решение за конечное число шагов в невырожденных задачах, геометрия модели может приводить к особым случаям, каждый из которых имеет четкое отражение в симплекс-таблице.
1. Вырожденность
Вырожденность возникает в том случае, когда при вычислении симплекс-отношений $\theta$ получается одинаковое минимальное значение для нескольких строк. В следующей итерации одна или несколько базисных переменных примут значение 0.
Геометрически вырожденность означает, что в одной вершине многогранника пересекается больше граничных плоскостей, чем размерность пространства. Чтобы избежать зацикливания алгоритма (бесконечного повторения одних и тех же базисов без изменения целевой функции), современные решатели используют правило Бланда (выбор переменной с наименьшим индексом).
2. Неограниченность целевой функции
Неограниченность означает, что значение целевой функции может расти до бесконечности в пределах допустимой области без нарушения ограничений.
В симплекс-таблице этот случай выявляется, когда в строке целевой функции выбран ведущий столбец с отрицательной оценкой, но все коэффициенты этого столбца меньше либо равны нулю ($a_{ik} \le 0$). Поскольку вычислить положительное отношение $\theta$ невозможно, ни одна переменная не может покинуть базис, что свидетельствует о незамкнутости многогранника решений в направлении оптимизации.
3. Альтернативные оптимумы (множество оптимальных решений)
Множественные оптимумы возникают, когда гиперплоскость целевой функции параллельна одному из активных связывающих ограничений.
В финальной оптимальной симплекс-таблице этот случай легко обнаружить: хотя бы одна свободная (небазисная) переменная имеет относительную оценку, в точности равную нулю ($\Delta_j = 0$). Если ввести эту переменную в базис, получится новая вершина с точно таким же оптимальным значением целевой функции $Z$, а весь отрезок между ними представляет собой континуум оптимальных решений.
Готовы решить задачу линейного программирования?
Мгновенные пошаговые симплекс-таблицы с полным анализом чувствительности и теневыми ценами для любой задачи ЛП.