Особливі випадки, що виникають при застосуванні СМ. Практичне заняття

Особливими випадками є:
− наявність альтернативного оптимуму;
− виродженість розв’язку;
− необмеженість цільової функції;
− відсутність ДР.

Альтернативний оптимум

max z = 2x1 + 4x2
x1 - x2 <=2
x1 + 2x2 <= 4
x1, x2 >= 0
Приклад 1

max z = 2x1 + 4x2
x1 - x2 <=2
x1 + 2x2 <= 4
x1, x2 >= 0

max z = 2x1 + 4x2
x1 - x2 <=2
x1 + 2x2 <= 4
x1, x2 >= 0
z = 8, x1 = 0, x2 = 2

max z = 2x1 + 4x2
x1 - x2 <=2
x1 + 2x2 <= 4
x1, x2 >= 0

max z = 2x1 + 4x2
x1 - x2 <=2
x1 + 2x2 <= 4
x1, x2 >= 0
z = 8, x1 = 8/3, x2 = 2/3

max z = 2x1 + 4x2
x1 - x2 <=2
x1 + 2x2 <= 4
x1, x2 >= 0
Відповідь

Альтернативний оптимум
Можливі три випадки:
1) альтернативний оптимум –(нескінчена) обмежена множина;
2) альтернативний оптимум – (нескінчена) необмежена множина;
3) при наявності ознаки альтернативного оптимуму оптимумальною є єдина точка.
Самостійно №
Для кожного випадку
виписати ознаку (використовуючи позначення перетвореної задачі);
показати цю ознаку по симплекс-таблиці;
дати графічну ілюстрацію.

Виродженість

max Z = 2x1 + 3x2
x1 + 2x2 <= 8
x1 + x2 <= 4
x1, x2 >= 0
Приклад 2

max Z = 2x1 + 3x2
x1 + 2x2 <= 8
x1 + x2 <= 4
x1, x2 >= 0

max Z = 2x1 + 3x2
x1 + 2x2 <= 8
x1 + x2 <= 4
x1, x2 >= 0

Вырожденность
max Z = 2x1 + 3x2
x1 + 2x2 <= 8
x1 + x2 <= 4
x1, x2 >= 0

max Z = 2x1 + 3x2
x1 + 2x2 <= 8
x1 + x2 <= 4
x1, x2 >= 0
Відповідь:
z = 12, x1 = 0, x2 = 4
(розв’язок є виродженим)

Необмеженість ЦФ

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

Необмежена ЦФ

max z = x1 + x2
-2x1 + x2 <= 2
2x1 – 3x2 <= 6
x1, x2 >= 0
Приклад 3

max z = x1 + x2
-2x1 + x2 <= 2
2x1 – 3x2 <= 6
x1, x2 >= 0
Відповідь:
Задача не має розв’язку,
оскільки ЦФ не обмежена
зверху

Альтернативний оптимум –необмежена множина

max z = -2x1 + x2
-2x1 + x2 <= 2
4x1 – 6x2 <= 12
x1, x2 >= 0
Відповідь
Приклад 4

max z = -2x1 + x2
-2x1 + x2 <= 2
4x1 – 6x2 <= 12
x1, x2 >= 0
Відповідь

max z = -2x1 + x2
-2x1 + x2 <= 2
4x1 – 6x2 <= 12
x1, x2 >= 0
Відповідь
Відповідь

Приклади 5 - 9

Приклад 5

Приклад 5

Приклад 5 (ДБР1)

Приклад 5

Приклад 5

Приклад 5

Приклад 5

Приклад 5

Приклад 5

Приклад 5 (ДБР2)

Приклад 5

Приклад 5

Приклад 5

Приклад 5

Приклад 5

Приклад 5

Приклад 5 (ДБР3)

Приклад 5

Приклад 5
Відповідь:
Задача не має розв’язку,
оскільки ЦФ не обмежена
зверху

Приклад 5
Усі виконані ітерації СМ можна було не робити, оскільки вже для першого ДБР виконувалась ознака необмеженості ЦФ!!!
Відповідь:
Задача не має розв’язку,
оскільки ЦФ не обмежена
зверху

Приклад 6

Приклад 6

Приклад 7

Приклад 7

Приклад 7 Відповідь:

Приклад 7

Приклад 8

Приклад 8

Приклад 8

Приклад 8
ДБР2

Приклад 8
ДБР3

Приклад 9 (три оптимальні вершини)

Приклад 9

Приклад 9

Приклад 9 ДБР2

Приклад 9 ДБР2

Приклад 9

Приклад 9

Відсутність допустимих розв’язків

max Z = 2x1 + 5x2
3x1 + 2x2 >= 6
2x1 + x2 <= 2
x1, x2 >= 0
Приклад 11

max Z = 2x1 + 5x2
3x1 + 2x2 >= 6
2x1 + x2 <= 2
x1, x2 >= 0

max Z = 2x1 + 5x2
3x1 + 2x2 >= 6
2x1 + x2 <= 2
x1, x2 >= 0

max Z = 2x1 + 5x2
3x1 + 2x2 >= 6
2x1 + x2 <= 2
x1, x2 >= 0
Отримали оптимальний розв’язок допоміжної задачі, але в її оптимальному ДБР штучні змінні мають додатні значення. Відповідно, вихідна ЗЛП не має допустимих розв’язків

Приклад 12