Альтернативный оптимум
При решении задач линейного программирования симплексным методом критерием оптимальности является условие Δj ≥ 0 для задач на максимум и условие Δj < 0 для задач на минимум.
Если на каком–то шаге окажется, что хотя бы одна оценка свободной переменной Δj = 0, а все остальные Δj > 0 для задач на максимум (Δj < 0 для задач на минимум), то, приняв в качестве ключевого столбца столбец, где Δj = 0, и найдя новое оптимальное решение, заметим, что значение целевой функции при этом не изменится. Говорят, что в этом случае задача имеет альтернативный оптимум.Критерием альтернативного оптимума при решении задач симплексным методом является равенство нулю хотя бы одной оценки свободной переменной (Δj = 0).
Если только одна оценка свободной переменной равна нулю, то решение находится по формуле
где 0 ≤ t ≤ 1.
Если две оценки и более, например S, свободных переменных равны нулю, то оптимальное решение определяется по формуле
В задачах, имеющих альтернативный оптимум, возникает возможность включения в ее модель других критериев эффективности.
Пример. Дана задача линейного программирования
при ограничениях:
Решение. Составим симплексную таблицу.
В индексной строке имеется одна положительная оценка. Полученное решение можно улучшить. Ключевым элементом является (4). Составляем симплексную таблицу 2–го шага.
Получаем
Так как Δ2 = 0, то задача имеет альтернативный оптимум. Найдем еще одно оптимальное решение, введя вместо базисной переменной х1 свободную переменную х2.
Получаем
Найдем координаты оптимального решения задачи:
Давая t значения из [0,1], получим различные опт, при которых L() = –12.