Неединственность оптимального решения (альтернативный оптимум)

Пример 2.3. Решить симплексным методом задачу

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

Решение. Геометрическое решение задачи приведено в примере 1.2 а (см. рис. 1.5, а): оптимум достигается в любой точке отрезка АВ, так как линия уровня параллельна этому отрезку. Покажем, как проявляется наличие альтернативного оптимума при решении задачи симплексным методом. На очередном шаге получаем:

Основные переменные: . Неосновные переменные: . Выражаем основные переменные через неосновные:

Х ₁ = (3; 5; 0; 0; 9) – допустимое базисное решение, соответствующее угловой точке А (3; 5). Целевая функция: F = 24 – х ₃.В этом выражении отсутствуют положительные коэффициенты при неосновных переменных, значит критерий оптимальности выполнен; Х ₁ – оптимальное базисное решение, . Однако в последнем выражении для F отсутствует неосновная переменная х ₄ (формально входит с нулевым коэффициентом). Поэтому изменение этой переменной не повлечет за собой изменение линейной функции. Например, можно перевести в основную переменную х ₄:

х ₄ = min{l5; ¥; 9} = 9.

Переменная х ₅ перейдет в неосновные, однако изменения линейной функции не произойдет: DF = 9*0 = 0. Действительно, на следующем шаге получим новое базисное решение Х ₂ = (6; 2; 0; 9; 0), соответствующее угловой точке В (6; 2), . Учитывая, что переменная х ₃ = 0 (в базисном решении Х ₂ она осталась неосновной), а переменная х ₄ удовлетворяет неравенству , из системы уравнений можно получить все множество оптимальных решений задачи.

Положим для удобства х ₄ = t, где [0; 9]. Тогда множество оптимальных решений:

Замечание. В соответствии с теоремами 1.3 и 1.4 множество оптимальных решений можно представить как выпуклую линейную комбинацию Х базисных решений Х ₁ = (3; 5; 0; 0; 9) и Х ₂ = (6; 2; 0; 9; 0): , где .