Особые случаи симплексного метода

Рассмотрим особенности, которые могут возникнуть при решении задачи линейного программирования симплексным методом.

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

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

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

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

Основные переменные: х ₁, х ₂, х ₅. Неосновные переменные: х ₃, х ₄.

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

Х ₁ = (3; 5; 0; 0; 9) — допустимое базисное решение, соответствующее угловой точке А (3; 5). Линейная функция: F = 24 – х ₃. В этом выражении отсутствуют положительные коэффициенты при неосновных переменных, значит критерий оптимальности выполнен, Х ₁ — оптимальное базисное решение . Однако в последнем выражении для F отсутствует неосновная переменная х ₄ (формально входит с нулевым коэффициентом), поэтому изменение этой переменяй не повлечет за собой изменение линейной функции. Haпример, можно перевести в основную переменную х ₄; х ₄ = min{15; ;9} = 9. Переменная x ₅ перейдет в неосновные, однако изменения линейной функции не произойдет: . Действительно, на следующем шаге получим новое базисное решение Х ₂ = (6;2;0;9;0), соответствующее угловой точке В (6;2), F max= F (X ₂)=24. Учитывая, что переменная х ₃ = 0 (в базисном решении Х ₂ она осталась неосновной), а переменная х ₄ удовлетворяет неравенству: , из системы уравнений можно получить все множество оптимальных решений задачи. Положим для удобства х ₄= t, где . Тогда множество оптимальных решений: .

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