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

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

Решим симплексным методом задачу:

F=3x1 + 3х2 à max при ограничениях:

х1 + х2 <= 8

A

2х1 - х2 >= 1

B

х1 - 2х2 <= 2

F=24

х1, х2 >= 0

Геометрическое решение:

Оптимум в любой точке отрезка АВ. Т.к. линия уровня параллельна этому отрезку. При решении задачи симплекс-методом наличие альтернативного оптимума проявляется следующим образом:

На очередном шаге получим: осн пер – х1, х2, х5;

неос п - х3, х4.

Выражение основных через неосн:

Х1 = 5 – (2/3)Х3 – (1/3)Х4

Х2 = 3 – (1/3)Х3 + (1/3)Х4

Х5 = 9 – Х3 – Х4

Х1 = (3; 5; 0; 0; 9) – ДБР, соответствует угловой точке А (3; 5). Линейная функция F = 24 – Х3. В выражении отсутствуют положительные коэффициенты при неосновных переменных, значит критерий оптимальности выполнен, т.е. Х1 – оптим БР, Fмакс = 24. Однако в последнем выражении для F = 24 – Х3 отсутствует неосновная переменная Х4 (входит с нулевым к-ом), поэтому изменение этой переменной не приведет к изменению цел функции.

Вырожденность базисного решения:

Решим симплексным методом задачу:

F=2x1 - х2 à max при ограничениях:

х1 - х2 <= 2

3х1 - 2х2 <= 6

6х1 - 4х2 <= 14

х1, х2 >= 0

На первом шаге получим: осн пер – х3, х4, х5;

неос п - х1, х2.

Выражение основных через неосн:

Х3 = 2 - Х1 + Х2

Х4 = 6 – 3Х1 + 2Х2

Х5 = 14 – 6Х1 + 4Х2

Х1 = (0; 0; 2; 6; 14) – допустимое БР. Линейная функция F = 2x1 - х2. Переводя Х1 в основные, получаем Х1 = min{2; 6/3; 14/6} = 2. Оценочные отношения в первых двух совпадают. Любое выбираем.

На втором шаге получим: осн пер – х1, х4, х5;

неос п - х2, х3.

Выражение основных через неосн:

Х1 = 5 + Х2 – Х3

Х4 = 0 – Х2 + 3Х3

Х5 = 2 – 2Х2 + 6Х3

Х2 = (2; 0; 0; 0; 2) – вырожденное БР, т.к. осн переменная Х4 = 0. Линейная функция F = 4 + Х2 – 2Х3. Переводя Х2 в основные, получаем Х2 = min{¥; 0; 1} = 0, поэтому на следующем шаге изменения целевой функции не произойдет (0 * 1). Это нарушение принципа улучшения решения. Поэтому принцип – не ухудшить.

Следующий шаг данного примера тоже приведет к вырожденному БР. Этот шаг, хоть и не вызвал увеличения значения цел функции, привел к новому БР. Наличие «пустых» шагов может привести к «зацикливанию» - не рассматриваем.

Вывод:

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

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

Решим симплексным методом задачу:

F=2x1 - 3х2 + 1à min при ограничениях:

х1 + х2 >= 4

2х1 - х2 >= 1

F=0

х1 - 2х2 <= 1

х1, х2 >= 0

A

На очередном шаге получим: осн пер – х1, х2, х5;

B

неос п - х3, х4.

Выражение основных через неосн:

Х1 = 5/3 + 1/3 Х3 + 1/3 Х4

Х2 = 7/3 + 2/3 Х3 – 1/3 Х4

Х5 = 4 + Х3 – Х4

Х1 = (5/3; 7/3; 0; 0; 4) – допустимое БР. Линейная функция F = -8/3 - 4/3x3 + 4/3х4. Переводя Х3 в основные (т.к. имеет отрицательный коэффициент, а ищем мин), получаем Х3 = min{¥; ¥; ¥} = ¥, т.к. во все уравнения эта переменная входит со знаком свободного члена. Уравнения не ограничивают рост Х3, поэтому и целевая функция неограниченно убывает.

Вывод:

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