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

Пример 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): , где .