Додавання нового обмеження

Після отримання оптимального розв’язку можлива ситуація, коли необхідно врахувати нове обмеження. Введення додаткового обмеження може привести до однієї з таких ситуацій:

1. Нове обмеження при поточному розв’язку виконується. Це означає, що дане обмеження або незв’язуюче, або зайве, і тому його додавання не змінить отриманий розв’язок.

2. Нове обмеження при поточному розв’язку не виконується. У цьому разі за допомогою двоїстого симплекс-методу знаходиться новий розв’язок.

Приклад 2. Нехай до задачі (6.8) — (6.12) додано додаткове обмеження
(рис. 6.2):

x ₁ – x ₂ ³ 1.

Розв’язок (⁴/₃, ⁴/₃) не задовольняє це обмеження. Для його врахування потрібно виконати такі дії:

1) перетворити обмеження до вигляду ”£”:

- x ₁ + x ₂ £ -1;

2) звести його до канонічної форми:

- x ₁ + x ₂ + s ₄ = -1;

3) виразити всі базисні змінні, що входять до складу обмеження, через небази­сні (за оптимальною симплекс-таблицею):

x ₁ = ²/₃ s ₁ — ¹/₃ s ₂ + ⁴/_3; x ₂ = - ¹/₃ s ₁ + ²/₃ s ₂ + ⁴/₃ ;

4) підставити ці значення в обмеження і після скорочення отримати:

- s ₁ + s ₂ + s ₄ = -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 ₁ ³ 12.

Розв’язок (⁴/₃, ⁴/₃) не задовольняє це обмеження. Для того, щоб ввести це обмеження в симплекс-таблицю треба виконати такі дії:

1) перетворити обмеження до вигляду ”£”:

- x ₁ £ -12;

2) привести це обмеження до канонічної форми:

- x ₁ + s ₅ = -12;

3) виразити всі базисні змінні, що входять до складу обмеження, через неба­зисні (за оптимальною симплекс-таблицею):

x ₁ = ²/₃ s ₁ - ¹/₃ s ₂ + ⁴/_3;

4) підставити ці значення в обмеження і скоротити:

- ²/₃ s ₁ + ¹/₃ s ₂ + s ₅ = - ³²/_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 ₃ – рядок має вигляд x ₂ + s ₃ + s ₅ = -2. Оскільки всі коефіцієнти лівої частини невід’ємні, а правої – від’ємні (s ₃ = -2), то ні при яких допустимих значеннях змінних це рівняння не може виконуватися. Отже, задача не має розв’язку.

Приклад 4. Нехай до задачі (6.8) — (6.12) добавлено додаткове обмеження:

3 x ₁ + 2 x ₂ £ 6.

Розв’язок (⁴/₃,⁴/₃) не задовольняє це обмеження. Для його врахування потрібно виконати такі дії:

1) привести обмеження до канонічної форми:

3 x ₁ + 2 x ₂ + s ₅ = 6;

2) виразити всі базисні змінні, що входять до складу обмеження, через небазисні (за оптимальною симплекс-таблицею):

x ₁ = ²/₃ s ₁ - ¹/₃ s ₂ + ⁴/_3; x ₂ = - ¹/₃ s ₁ + ²/₃ s ₂ + ⁴/_3.

3) підставити ці значення в обмеження й скоротити:

⁴/₃ s ₁ + ¹/₃ s ₂ + s ₅ = - ²/_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.