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

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

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

,

,

.

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

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

,

,

.

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

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

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

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

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

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

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

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

Базисні змінні		…							Розв’язок
…
…

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

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

;

;

.

Рисунок 3

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

Базисні змінні							Розв’язок
					+	+	+
					+	–	+
						+	+
					–	–
					+		+

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

Ознака: .

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

Базисні змінні		…							Розв’язок
…						…
…						…

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

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

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

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

Базисні змінні		…							Розв’язок
…						…
…						…

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

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

Рисунок 4

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

Базисні змінні						Розв’язок
				+	–	+
				–	–	+
				+	–	+
				+		+

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

Дата добавления: 2015-11-14