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