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

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

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

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

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

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

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

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

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

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

Линейная функция цели, выраженная через неосновные переменные, имеет вид: F = 4 + х ₂ - 2 x ₃. Переводя переменную Х ₂ в основные, получаем: х ₂ = min { ;0;1} = 0, поэтому на следующем шаге изменения функции цели не произойдет . Это нарушение принципа улучшения решения, который должен выполняться при использовании симплексного метода, поэтому уточним этот принцип: каждый следующий шаг должен улучшить или, в крайнем случае, не ухудшить значение линейной функции.

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

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

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

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

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

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

III. Отсутствие конечного оптимума

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

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

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

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

- базисное решение; ; min не достигнут, так как критерий оптимальности на min не выполнен: переменная х ₃ имеет отрицательный коэффициент в выражении для F. Определяем х ₃ = min (, , ) = , так как в каждое из трех уравнений эта переменная входит с тем же знаком, что и свободный член. Уравнения не ограничивают рост х ₃, поэтому и значение функции F неограниченно и отрицательно, т.е. .

Если на каком-либо шаге получаем, что во всех уравнениях системы бесконечны оценочные отношения той переменной, которая переводится в основные, то задача не имеет конечного оптимума (, если задача на отыскание максимума, , если задача на отыскание минимума).

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