2. Вибираємо направляючий стовпчик а­_р­ з умови: γ­_і­ < 0 і хоча б один елемент а­_ір­ > 0.

3. Вибираємо q-й ведучий рядок з умови: b­_q­/a­_qp­= min { b­_i/a­_ip } для a­_ip­ > 0.

4. Виконуємо перерахунок елементів q-го ведучого рядка за формулою:

a­’_qk = a­_qk / a­_qp­, (k = 0, 1, 2,…, n).

5. Обчислюємо елементи всіх інших рядків (при k≠p) за формулою:

a­’_іk = a­_іk - a­’_qk­∙ a­_іp­, (і = 0, 1, 2, …, q-1,q+1,…,r).

Перед тим як виконувати вищевказані дії, перевіряємо чи виконується теорема симплексного методу:

1. якщо в стовпчику, де γ­_і­ < 0 існує хоча б один елемент а­_ір­ > 0, то опорний план можна покращити;

2. якщо в усіх стовпчиках, де γ­_і­ < 0 немає жодного додатного елемента а­_ір­, (всі а­_ір­< 0), то функція цілі не обмежена в області допустимих розв’язків (L→max).

3. якщо γ­_і­ ≥ 0 для всіх і, то отриманий опорний план є оптимальним.

П овертаємося до прикладу. Отримана система рівнянь-обмежень сумісна, так як ранги матриці системи А та розширеної матриці Ā співпадають і рівні 3.

2 2 1 0 0 2 2 1 0 0 60

rang А = rang 3 1 0 1 0 = rang Ā = rang 3 1 0 1 0 65 = 3.

2 9 0 0 1 2 9 0 0 1 135

З того, що система сумісна і має ранг 3 випливає, що три базисні змінні можна лінійно виразити через дві вільні змінні. Виразимо, наприклад, змінні х₃, х₄, х₅ та функцію цілі через змінні х₁ та х₂, тобто приведемо систему до одиничного базису:

х ₃ = 60 – 2х₁ – 2х­₂,

х₄ = 60 – 2х­₁ – 2х­₂,

х₅ = 60 – 2х­₁ – 2х­₂.

Функція цілі L = 10 х₁ + 18 х₂ виражена через змінні х­₁ та х­₂, перепишемо її для зручності у вигляді: L - 10 х₁ - 18 х_2­ = 0.

Покладемо х₁ = 0 та х₂ = 0 і дістаємо значення решти змінних: х₃ = 60, х₄ = 65, х₅ = 135. Всі значення змінних є невід’ємними і задовольняють системі (*), а тому є допустимими. Таким чином, отримали початковий розв’язок системи (*) – початковий план: (0; 0; 60; 65; 135). При цьому L = 0.

Таблиця 2.

Базис	Вільні члени, bi­	10	18	0	0	0	bi­­ / х­i
		х­1	х­2	х­3	х4	х­5
х­3	60	2	2	1	0	0	60/2=30
х­4	65	3	1	0	1	0	65/1=65
х­5	135	2	9	0	0	1	135/9=15
L	0	-10	-18	0	0	0

Отриманий початковий план можна вдосконалити, так як в останньому рядку табл.2 є два від’ємні числа: -10, -18. Вибираємо за направляючий стовпчик - стовпчик, що містить х_2­, так як min {-18; -10} = -18. Визначаємо ведучий рядок, для цього з’ясовуємо, чи є в першому стовпці додатні числа. Їх три: 2, 1, 9. Складаємо відношення відповідних вільних членів до цих чисел, які заносимо в останній стовпчик і вибираємо серед цих відношень найменше (15), тоді ведучим рядком буде рядок, що містить х­_5­. На перетині направляючого стовпця та ведучого рядка буде число 9, цей елемент є розрахунковим. Таким чином, змінна х­_5­ виводиться з базису, тепер її значення дорівнює 0. Змінна х­₂ вводиться в базис. Виконуємо цю операцію за вищенаведеними правилами та отримуємо табл.3.

Таблиця 3.

Базис	Вільні члени, bi­	х­1	х­2	х­3	х­4	х­5	bi­­ / х­i
х­3	60 -15*2 =	2 – 2/9*2 =	2 – 1*2=	1 – 0*2=	0 – 0*2=	0 – 1/9*2=	30:14/9 ≈ 19,3
	30	14/9	0	1	0	-2/9
х­4	65 -15*1 =	3 – 2/9*1 =	1 – 1*1=	0 – 0*1=	1 – 0*1=	0 – 1/9*1=	50:25/9= 18
	50	25/9	0	0	1	-1/9
х­2	135 : 9 =	2:9 =	9:9 =	0:9 =	0:9 =	1:9 =	15:2/9= 67,5
	15	2/9	1	0	0	1/9
L	0 -15*(-18) =	-10 –2/9*(-18)=	-18 – 1*(-18)=	0 – 0*(-18)=	0 – 0*(-18)=	0 – 1/9*(-18)=
	270	-6	0	0	0	2

З цієї таблиці знаходимо новий опорний план: (0; 15; 30; 50; 0) для якого L=270.

В табл. 3 в рядку для L є одне від’ємне число –6, яке відповідає стовпцю для змінної х­₁. Отже, виконуємо наступну ітерацію – крок симплекс-метода. У визначеному стовпці є три додатні чиста: 14/9, 25/9, 2/9. З останнього стовпчика за відношенням вільних членів до цих чисел визначаємо, що ведучим рядком буде рядок, що містить змінну х­₄. Розрахунковий елемент 25/9, що означає вивід з базису змінної х­₄ (тепер х­₄ = 0) та включення до базису змінної х­₁ . Провівши відповідні розрахунки, отримуємо табл. 4.

Таблиця 4.

Базис	Вільні члени, bi­	х­1	х­2	х­3	х­4	х­5
х­3	30 -18*14/9 =	14/9 – 1*14/9=	0 – 0*14/9=	1 – 0*14/9=	0 – 9/25*14/9=	-2/9 – (-1/25)*14/9=
	2	0	0	1	-14/25	-4/25
х­1	50:25/9 =	25/9:25/9 =	0:25/9 =	0:25/9 =	1:25/9 =	-1/9:25/9 =
	18	1	0	0	9/25	-1/25
х­2	15 -18*2/9 =	2/9 – 1*2/9=	1 – 0*2/9=	0 – 0*2/9=	0 – 9/25*2/9=	1/9 – (-1/25)*2/9=
	11	0	1	0	-2/25	3/25
L	270 -18*(-6) =	(-6) – 1*(-6)=	0 – 0*(-6)=	0 – 0*(-6)=	0 – 9/25*(-6)=	2 – (-1/25)*(-6)=
	378	0	0	0	54/25	44/25

Оскільки в останньому рядку немає від’ємних чисел, то отриманий опорний план (18; 11; 2; 0; 0), L = 378 є оптимальний.

Згідно з отриманим розв’язком, щоб отримати максимальний прибуток L­_max­ = 378, необхідно випускати 18 одиниць продукції Р­_1­ та 11 одиниць продукції Р­_1­.

Змінна х­_3­ = 2, це означає, що перший ресурс використовується не повністю. Є його залишок кількістю 2 одиниці. Оскільки х­_4­ та х­_5­ дорівнюють 0, то це означає, що другий і третій ресурси використовуються повністю.

Будуємо двоїсту задачу.

При побудові двоїстої задачі користуємося правилами:

1). Двоїста задача містить стільки нових змінних, скільки основних обмежень у прямій задачі.

2). Якщо пряма задача на max, то двоїста – на min і навпаки.

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

4). Коефіцієнти, що стоять при х­_1­ у системі основних обмежень прямої задачі, стають коефіцієнтами в першому обмеженні двоїстої задачі. Аналогічно для х­_2­, і т.д.

5). Якщо змінна прямої задачі може бути будь-якою за знаком, то відповідне їй обмеження є рівнянням. І навпаки, якщо основне обмеження прямої задачі є рівнянням, то відповідна змінна двоїстої задачі може набувати будь-яких значень.

6). Якщо задача на max, то усі нерівності повинні бути виду “≤”, якщо на min, то - “≥”.

Записуємо модель двоїстої задачі з цільовою функцією F та двоїстими змінними у­_1­, у­_2­, у­_3­ (кількість обмежень у нашій задачі три).

L = 10 х1 + 18 х2 → max, 2 х1 + 2 х2 ≤ 60 ↔ у­1­, 3 х1 + х2 ≤ 65 ↔ у­2­, 2 х1 + 9 х2 ≤ 135 ↔ у­3­ х1 ≥ 0, х2 ≥ 0.

↔

F = 60 у­1­ + 65 y2 + 135 у­3­ → min, 2 у­1­ + 3 y2 + 2 у­3­ ≥ 10, 2 у­1­ + y2 + 9 у­3­ ≥ 18, ­y­1 ≥ 0, y2 ≥ 0.

Розв’язок двоїстої задачі можна знайти за допомогою останнього рядка останньої симплексної таблиці прямої задачі (табл. 4).

0 0 0 54/25 44/25

о сновні х₁, х₂ х₃, х₄, х₅ додаткові

додаткові у₄, у₅ у₁, у₂, у₃ основні

маємо: У = (0; 54/25; 44/25 | 0; 0), F­_min­ = 378.

Двоїсті змінні показують міру дефіцитності ресурсів, вони чисельно рівні зміні цільової функції при зміні відповідного ресурсу на одиницю. Відповідно, зміна другого ресурсу на одиницю призводить до збільшення обсягу реалізації на у₂ = 54/25, третього – на у₃ = 44/25. Змінна у₁ = 0 вказують, що перший ресурс у надлишку, тому його збільшення до будь-якої зміни цільової функції не призведе.

Додаткові двоїсті змінні показують міру збитковості продукції, яку, згідно з розв’язком, недоцільно випускати. З розв’язку двоїстої задачі випливає, що збиткової продукції немає.

ЗАВДАННЯ ДЛЯ САМОСТІЙНОГО ВИКОНАННЯ

№№ 201 – 300. Для виготовлення двох видів продукції Р₁ і Р₂ підприємство використовує три види сировини S₁, S₂, S₃. Запаси ресурсів, норми їх затрат і прибуток від реалізації одиниці продукції задано таблицею.