Заповнення першої симплекс-таблиці

Після знаходження ДБР складається перша симплекс-таблиця.

1-ша симплекс-таблиця.

і

х баз

с баз

с 1

…

с r

…

с m

с m+1

…

с k

…

с n

В

q

x 1

…

x r

…

x m

x m+1

…

x k

…

x n

x 1

с 1

…

…

a 1,m+1

…

a 1k

…

a 1n

b 1

…

…

…

…

…

…

…

…

…

…

…

…

…

…

r

x r

с r

…

…

a r,m+1

…

a rk

…

a r n

b r

…

…

…

…

…

…

…

…

…

…

…

…

…

...

m

x m

с m

…

…

a m,m+1

…

a mk

…

a mn

b m

m+1

D j

…

…

Dm+1

…

Dk

…

Dn

z 0

 

Значенння граф (стовбчикiв) симплекс таблицi:

i – номер рядка,

x _баз – базиснi змiннi в i -му рiвняннi,

c _баз – коефiцiєнти функцii мети при базисних змiнних в i -тих рівняннях,

a_ij – коефіцієнти при невідомих системи рівнянь (1),

B – стовбчик вiльних членiв системи рiвнянь (1).

В (m +1)-му рядку записуються значення індексних елементів .

де – коефіціенти при j -й змінній в функції мети, а с_i – коефіцієнти функції мети при базисних змінних.

Так,

.

В (m +1)-му рядку стовбчика В записуються значення функції мети для даного ДБР:

Перевірка отриманого ДБР на оптимальність

Критерій оптимальності. При розв’язуванні задачі максимізації план оптимальний, якщо в індексному рядку немає від'ємних елементів, тобто .

В цьому випадку ДБР є оптимальний розв'язок, а значення – максимальне.

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

В цьому випадку ДБР є оптимальний розв'язок, а значення – мінімальне.

В випадках, коли не всі () необхідно перейти до наступного допустимого базисного розв'язку або встановити, що задача не має оптимального розв’язку.

 

Перехід до наступної ітерації

Для переходу до наступного (кращого) розв'язку необхідно визначити, яку змінну ввести в базис і яку змінну вивести з базису.

В базис вводиться змінна з мінімальним від'ємним індексним елеменом .

Нехай – в базис вводимо x_k.

З базису виводиться змінна з мінімальним симплексним відношенням

.

Нехай – мінімальне. Це значить, що з базису виводимо змінну x_r.

Елементи 2-ї симплекс-таблиці визначаються перерахунком 1-ї симплекс таблиці з вирішальним елементом а_rk по правилу Жорданових виключень. При цьому в стовбчику x _баз в рядку r замість x_r записується x_k, а в стовбчику c _баз замість c_r записується c_k.

Зауваження 1. Якщо є і в стовбчику x_k всі елементи a_ik 0, то функція мети не обмежена зверху на ОДР (області допустимих розв’язків).

Зауваження 2.

1. При розв'язку задачі мінімізації в базис вводиться змінна x_k, яка відповідає максимальному невід'ємному елементу .

2. План оптимальний, якщо в рядку немає додатніх елементів.

Варіанти завдань

 

 

1. 2.

 

3. 4.

5. 6.

7. 8.

9. 10.

11. 12.

13. 14.

15. 16.

17. 18.

19. 20.

21. 22.

23. 24.

25. 26.

27. 28.

29. 30.

31. 32.

33. 34.

35. 36.

37. 38.

39. 40.

41. 42.

43. 44.

45. 46.

47. 48.

49. 50.

 

Приклад виконання завдання.

z= 3 x ₁ + x ₂ ® max

Розв’язок.

 

1. Приведемо задану модель до канонічного вигляду.

Для перетворення обмежень-нерівностей в рівняння:

а) оскільки права частина третього обмеження від’ємна, домножаємо обидві

частини рівняння на (–1);

б) до лівої частини перших трьох нерівностей додаємо додаткові змінні , , відповідно, а від лівої частини четвертої нерівності віднімемо , які ввійдуть у функцію мети з коефіцієнтом 0;

 

z= 3 x ₁ + x ₂ + 0 х ₃ + 0 х ₄ + 0 х ₅ + 0 х ₆ ® max

 

2. Знайдемо допустимий базисний розв’язок.

Оскільки в четвертому обмеженні немає базисних змінних (немає змінних з коефіцієнтом +1, яких немає в інших рівняннях), то до лівої частини додаємо штучну невід’ємну зміну х₇.

 

z= 3 x ₁ + x ₂ + 0 х ₃ + 0 х ₄ + 0 х ₅ + 0 х ₆ – M x ₇ ® max

 

ДБР х ₁ = 0, х ₂ = 0, х ₆ = 0 – вільні змінні,

х ₃ = 1, х ₄ = 7, х ₅ = 4, х ₇ = 6 – базисні змінні.

 

3. Заповнення першої симплекс-таблиці.

 

i	x баз	с баз							–М	b	q
х 1	х 2	х 3	х 4	х 5	х 6	х 7
	х 3			–1
	х 4										7/2
	х 5		–1								4/2
	х 7	–М						–1			6/6
		–3	–1
	–2М	–6М				М		–6М

 

 

4. Перевірка отриманого ДБР на оптимальність

План х ₃ = 1, х ₄ =7, х ₅ = 4, х ₇ = 6 не оптимальний, оскільки D₁ = –2М – 3 < 0,

D₂ = –6М – 1 < 0. Вводимо в базис х ₂, оскільки D₂ найменше від’ємне. Виводимо

з базису х ₇, оскільки q₄ = 1 найменше додатнє.

5. Перехід до наступної ітерації

Заповнюємо наступну симплекс-таблицю, перераховуючи її елементи за правилами Жорданових виключень з головним елементом а_rk (a_rk = а₄₂ = 6).

Зауваження. Після виведення з базису штучної змінної х ₇ можна стовбчик при змінній х ₇ не обчислювати.

i	x баз	с баз							–М	b	q
х 1	х 2	х 3	х 4	х 5	х 6	х 7
	х 3		8/6					–1/6			12/8
	х 4		2/6					2/6			30/2
	х 5		–10/6					2/6
	х 2		2/6					–1/6			6/2
		–16/6					–1/6

 

План х ₃ = 2, х ₄ = 5, х ₅ = 2, х ₂ = 1 не оптимальний, оскільки D₁ = –16/6 < 0,

D₆ = –1/6 < 0. Вводимо в базис х ₁, оскільки D₁ найменше від’ємне. Виводимо з базису х ₃, оскільки q₁ = 12/8 найменше додатнє.

Заповнюємо наступну симплекс-таблицю, перераховуючи її елементи за правилами Жорданових виключень з головним елементом а_rk (a_rk = а ₁₁= 8/6).

i	x баз	с баз							–М	b	q
х 1	х 2	х 3	х 4	х 5	х 6	х 7
	х 1				6/8			–1/8		12/8
	х 4				–2/8			3/8		36/8
	х 5				–10/8			1/8		36/8
	х 2				–2/8			–1/8		4/8
				16/8			–4/8		40/8

 

План х ₁ =12/8, х ₂ = 4/8, х ₄ = 36/8, х ₅ = 36/8 не оптимальний, оскільки

D₆ = –4/8 < 0. Вводимо в базис х ₆, оскільки D₆ від’ємне. Виводимо з базису х ₄, оскільки найменьше додатнє.

Заповнюємо наступну симплекс-таблицю, перераховуючи її елементи за правилами Жорданових виключень з головним елементом а_rk (a_rk = а ₂₆= 3/8).

i	x баз	с баз							–М	b	q
х 1	х 2	х 3	х 4	х 5	х 6	х 7
	х 1				2/3	1/3
	х 6				–2/3	8/3
	х 5				4/3	–1/3
	х 2				–1/3	1/3
				5/3	4/3

 

План х ₁ = 3, х ₂ = 2, х ₃ = 0, х ₄ = 0, х ₅ = 3, х ₆ = 12 оптимальний, оскільки

D _j ³ 0, j = . Z _max = 11.

 

 

ЛАБОРАТОРНА РОБОТА № 7