Особливі випадки, що виникають при застосуванні симплекс-методу

5.5 Особливі випадки, що виникають при застосуванні симплекс-методу

Нехай задана ЗЛП:

Нехай – ДБР системи обмежень.

Перетворена задача, що відповідає ДБР :

Особливими випадками використання симплекс–методу є:

- виродженість розв’язку;

- необмеженість цільової функції;

- наявність альтернативного оптимуму.

5.5.1 Виродженість розв’язку

Ознака виродженості: ( )

(одна чи декілька базисних змінних приймають нульове значення).

Ознака виродженості по симплекс-таблиці відповідного розв’язку:

Так в ЗЛП, що представлена на рисунку 3, виродженою є вершина .

Точці відповідають три базиси:

;

Рисунок 3

Симплекс–таблиця для першого з наведених базисів має таку структуру:

5.5.2 Необмежена множина допустимих розв’язків

Ознака: .

Ознака необмеженості множини допустимих розв’язків по симплекс-таблиці:

5.5.3 Необмежена цільова функція

Необхідною умовою цього є необмеженість множини допустимих розв’язків.

Ознака (задача на максимум): ( і ).

Ознака необмеженості множини допустимих розв’язків по симплекс-таблиці:

ЗЛП, що представлена на рисунку 4, має необмежену зверху цільову функцію.

Примітка: прямі (1) та (3) паралельні.

Рисунок 4

ДБР відповідає така симплекс–таблиця:

У разі задачі на мінімум ознака така: ( і ).