Після отримання оптимального розв’язку можлива ситуація, коли необхідно врахувати нове обмеження. Введення додаткового обмеження може привести до однієї з таких ситуацій:
1. Нове обмеження при поточному розв’язку виконується. Це означає, що дане обмеження або незв’язуюче, або зайве, і тому його додавання не змінить отриманий розв’язок.
2. Нове обмеження при поточному розв’язку не виконується. У цьому разі за допомогою двоїстого симплекс-методу знаходиться новий розв’язок.
Приклад 2. Нехай до задачі (6.8) — (6.12) додано додаткове обмеження
(рис. 6.2):
x 1 – x 2 ³ 1.
Розв’язок (4/3, 4/3) не задовольняє це обмеження. Для його врахування потрібно виконати такі дії:
1) перетворити обмеження до вигляду ”£”:
- x 1 + x 2 £ -1;
2) звести його до канонічної форми:
- x 1 + x 2 + s 4 = -1;
3) виразити всі базисні змінні, що входять до складу обмеження, через небазисні (за оптимальною симплекс-таблицею):
x 1 = 2/3 s 1 — 1/3 s 2 + 4/3; x 2 = - 1/3 s 1 + 2/3 s 2 + 4/3 ;
4) підставити ці значення в обмеження і після скорочення отримати:
- s 1 + s 2 + s 4 = -1;
5) додати це рівняння до оптимальної симплекс-таблиці (табл. 6.7).
Таблиця 6.7
| Базисні змінні | x 1 | x 2 | s 1 ¯ | s 2 | s 3 | s 4 | Розв’язок |
| Z | -1/3 | -1/3 | 0 | 8/3 | |||
| x 1 | -2/3 | 1/3 | 4/3 | ||||
| x 2 | 1/3 | -2/3 | 4/3 | ||||
| s 3 | 1/3 | 1/3 | 0 | 22/3 | |||
| s 4 | -1 | 1 | -1 | ||||
| z | -2/3 | -1/3 | |||||
| x 1 | -1/3 | -2/3 | |||||
| x 2 | -1/3 | 1/3 | |||||
| s 3 | 2/3 | 1/3 | |||||
| s 1 | -1 | -1 |
Розв’язок, що є оптимальним і допустимим, відповідає точці D (2, 1).
Рис. 6.2
Приклад 3. Нехай до задачі (6.8) — (6.12) додано додаткове обмеження:
x 1 ³ 12.
Розв’язок (4/3, 4/3) не задовольняє це обмеження. Для того, щоб ввести це обмеження в симплекс-таблицю треба виконати такі дії:
1) перетворити обмеження до вигляду ”£”:
- x 1 £ -12;
2) привести це обмеження до канонічної форми:
- x 1 + s 5 = -12;
3) виразити всі базисні змінні, що входять до складу обмеження, через небазисні (за оптимальною симплекс-таблицею):
x 1 = 2/3 s 1 - 1/3 s 2 + 4/3;
4) підставити ці значення в обмеження і скоротити:
- 2/3 s 1 + 1/3 s 2 + s 5 = - 32/3.
Додамо це рівняння до оптимальної симплекс-таблиці (табл. 6.8).
Таблиця 6.8
| Базисні змінні | x 1 | x 2 | s 1¯ | s 2 | s 3 | s 5 | Розв’язок |
| z | -1/3 | -1/3 | 0 | 8/3 | |||
| x 1 | -2/3 | 1/3 | 0 | 4/3 | |||
| x 2 | 1/3 | -2/3 | 0 | 4/3 | |||
| s 3 | 1/3 | 1/3 | 0 | 22/3 | |||
| s 5 | -2/3 | 1/3 | 1 | -32/3 |
За дві ітерації отримаємо оптимальну симплекс-таблицю (табл. 6.9).
Таблиця 6.9
| Базисні змінні | x 1 | x 2 | s 1 | s 2 | s 3 | s 5 | Розв’язок |
| z | -1 | -1 | |||||
| x 1 | 3/2 | ||||||
| s 2 | -2 | -1 | |||||
| s 3 | 1 | -2 | |||||
| s 1 | -1 | -2 |
S 3 – рядок має вигляд x 2 + s 3 + s 5 = -2. Оскільки всі коефіцієнти лівої частини невід’ємні, а правої – від’ємні (s 3 = -2), то ні при яких допустимих значеннях змінних це рівняння не може виконуватися. Отже, задача не має розв’язку.
Приклад 4. Нехай до задачі (6.8) — (6.12) добавлено додаткове обмеження:
3 x 1 + 2 x 2 £ 6.
Розв’язок (4/3,4/3) не задовольняє це обмеження. Для його врахування потрібно виконати такі дії:
1) привести обмеження до канонічної форми:
3 x 1 + 2 x 2 + s 5 = 6;
2) виразити всі базисні змінні, що входять до складу обмеження, через небазисні (за оптимальною симплекс-таблицею):
x 1 = 2/3 s 1 - 1/3 s 2 + 4/3; x 2 = - 1/3 s 1 + 2/3 s 2 + 4/3.
3) підставити ці значення в обмеження й скоротити:
4/3 s 1 + 1/3 s 2 + s 5 = - 2/3.
Не додаючи це обмеження до оптимальної симплекс-таблиці, бачимо, що всі коефіцієнти в лівій частині рівняння додатні, а в правій – від’ємні. Це означає, що введене обмеження суперечить початковій системі обмежень.
Завдання до самостійної роботи
Додайте до оптимальної симплекс-таблиці додаткове обмеження згідно зі своїм варіантом (табл. 6.10).
Таблиця 6.10
| Базисні змінні | x 1 | x 2 | s 1 | s 2 | s 3 | Розв’язок |
| z | -3/5 | -4/5 | ||||
| x 1 | 1/5 | -2/5 | ||||
| x 2 | -2/5 | -1/5 | ||||
| s 3 | 2/5 | 11/5 |
Варіанти завдань
| 1) -x1 + 2x2 ³ 8; | 2) x1 – x2 ³ 1. |
| 3) x1 + x2 ³ 6; | 4) 4x1 – x2 £ -4. |
| 5) 3x1 + 2x2 £ 6; | 6) 4x1 – 3x2 ³ 3; |
| 7) x1³ x2; | 8) x1 + 3x2 £ 3; |
| 9) 3x1 – x2 ³ 9; | 10) 5x1 + 4 x2 ³ 20; |
| 11) x2 ³ 5; | 12) 4x1 + x2 £ 2; |
| 13) x1 + 3x2 ³ 12; | 14) x1 ³ 4; |
| 15) -6x1 + x2 ³ 6; | 16) x1 ³ 3. |
