6.5. Додавання нового обмеження
Після отримання оптимального розв’язку можлива ситуація, коли необхідно врахувати нове обмеження. Введення додаткового обмеження може привести до однієї з таких ситуацій:
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 |
0 |
0 |
-1/3 |
-1/3 |
0 |
0 |
8/3 |
|
x1 |
1 |
0 |
-2/3 |
1/3 |
0 |
0 |
4/3 |
|
x2 |
0 |
1 |
1/3 |
-2/3 |
0 |
0 |
4/3 |
|
s3 |
0 |
0 |
1/3 |
1/3 |
1 |
0 |
22/3 |
|
s4 |
0 |
0 |
-1 |
1 |
0 |
1 |
-1 |
|
z |
0 |
0 |
0 |
-2/3 |
0 |
-1/3 |
3 |
|
x1 |
1 |
0 |
0 |
-1/3 |
0 |
-2/3 |
2 |
|
x2 |
0 |
1 |
0 |
-1/3 |
0 |
1/3 |
1 |
|
s3 |
0 |
0 |
0 |
2/3 |
1 |
1/3 |
7 |
|
s1 |
0 |
0 |
1 |
-1 |
0 |
-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 |
0 |
0 |
-1/3 |
-1/3 |
0 |
0 |
8/3 |
|
x1 |
1 |
0 |
-2/3 |
1/3 |
0 |
0 |
4/3 |
|
x2 |
0 |
1 |
1/3 |
-2/3 |
0 |
0 |
4/3 |
|
s3 |
0 |
0 |
1/3 |
1/3 |
1 |
0 |
22/3 |
|
s5 |
0 |
0 |
-2/3 |
1/3 |
0 |
1 |
-32/3 |
За дві ітерації отримаємо оптимальну симплекс-таблицю (табл. 6.9).
Таблиця 6.9
|
Базисні змінні |
x1 |
x2 |
s1 |
s2 |
s3 |
s5 |
Розв’язок |
|
z |
0 |
-1 |
0 |
0 |
0 |
-1 |
12 |
|
x1 |
1 |
0 |
0 |
0 |
0 |
3/2 |
12 |
|
s2 |
0 |
-2 |
0 |
1 |
0 |
-1 |
8 |
|
s3 |
0 |
1 |
0 |
0 |
1 |
1 |
-2 |
|
s1 |
0 |
-1 |
1 |
0 |
0 |
-2 |
20 |
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 .
Не додаючи це обмеження до оптимальної симплекс-таблиці, бачимо, що всі коефіцієнти в лівій частині рівняння додатні, а в правій – від’ємні. Це означає, що введене обмеження суперечить початковій системі обмежень.