Альтернативный оптимум

При решении задач линейного программирования симплексным методом критерием оптимальности является условие Δj ≥ 0 для задач на максимум и условие Δj < 0 для задач на минимум.

Критерием альтернативного оптимума при решении задач симплексным методом является равенство нулю хотя бы одной оценки свободной переменной (Δj = 0).

Если только одна оценка свободной переменной равна нулю, то решение находится по формуле

где 0 ≤ t ≤ 1.

Если две оценки и более, например S, свободных переменных равны нулю, то оптимальное решение определяется по формуле

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

Пример. Дана задача линейного программирования

при ограничениях:

Решение. Составим симплексную таблицу.

В индексной строке имеется одна положительная оценка. Полученное решение можно улучшить. Ключевым элементом является (4). Составляем симплексную таблицу 2–го шага.

Получаем

Так как Δ2 = 0, то задача имеет альтернативный оптимум. Найдем еще одно оптимальное решение, введя вместо базисной переменной х1 свободную переменную х2.

Получаем

Найдем координаты оптимального решения задачи:

Давая t значения из [0,1], получим различные опт, при которых L() = –12.