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

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