Появление вырожденного базисного решения

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

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

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

I шаг. Основные переменные: .

Неосновные переменные: .

После преобразований получим:

Х₁ = (0; 0; 2; 6; 14) – допустимое базисное решение; . Критерий оптимальности на мак­симум не выполнен, поэтому переводим в основные переменную х₁, так как в выражение для F она входит с положительным ко­эффициентом: х₁ = min{2; 6/3; 14/6} = 2. Оценочные отношения в двух первых уравнениях совпадают, поэтому в качестве разре­шающего можно взять любое из них, например, первое.

II шаг. Основные переменные: .

Неосновные переменные: .

Получим после преобразований:

Х₂ = (2; 0; 0;0; 2) – вырожденное базисное решение, основная компонента х₄ = 0.

Функция цели, выраженная через неосновные переменные, имеет вид: . Переводя переменную х₂ в основные, получаем: х₂ = min{¥; 0; 1}= 0, поэтому на следующем шаге изменения функции цели не произойдет, DF = 0. Это нарушение принципа улучшения решения, который должен выполняться при использовании симплексного метода, в связи с чем уточним данный принцип: каждый следующий шаг должен улучшить или, в крайнем случае, не ухудшить значение линейной функции.

III шаг. Основные переменные: .

Неосновные переменные: .

После преобразований получим:

X₃ = (2;0; 0; 0; 2) – это базисное решение тоже вырождено. Покомпонентно оно совпадает с Х₂, однако формально отличается набором основных переменных. Выражение линейной функции через неосновные переменные имеет вид: .

Выполненный шаг, хотя и не вызвал увеличения значения целевой функции, не является лишним, так как привел к новому базисному решению. Далее продолжаем решение симплекс-методом.

Из рассмотренного примера можно сделать следующий вывод. Если на каком-либо шаге наибольшее возможное значение переменной достигается в нескольких уравнениях одновременно (совпадают их оценочные отношения), то разрешающим является любое из них. На следующем шаге получаем вырожденное базисное решение, переход к очередному базисному решению может не изменить функцию цели (DF = 0).

Замечание. Вырождение, полученное при оптимальном ре­шении, может привести к альтернативному оптимуму даже при ненулевых коэффициентах при всех неосновных переменных и линейной функции (об этом упоминалось при рассмотрении случая альтернативного оптимума).