Алгоритм симплекс-методу

Записуємо робочу модель.

З’ясовуємо умови задачі і записуємо їх у вигляді обмежень.

Будуємо цільову функцію, що відображує мету розв’язання задачі і обов’язково включає до свого складу змінні.

Цільова функція нашої задачі має вигляд:

L = 10 х₁ + 18 х₂ → max,

де кожний окремий доданок означає прибуток від випуску продукції відповідного виду, а символ → max відображає вимогу максимізації функції.

Згідно з умовами прикладу запаси сировини S₁, S₂, S₃ обмежені і відповідно дорівнюють 60, 65, 135, отже, кількість ресурсів кожного типу, які використовуються для виробництва всіх видів продукції, не повинна перевищувати наявної їх кількості в розпорядженні підприємства:

2 х₁ + 2 х₂ ≤ 60,

3 х₁ + х₂ ≤ 65,

2 х₁ + 9 х₂ ≤ 135,

i, очевидно, випуск продукції повинен бути невід’ємним:

х₁ ≥ 0, х₂ ≥ 0.

L = 10 х₁ + 18 х₂ → max,

2 х₁ + 2 х₂ ≤ 60,

3 х₁ + х₂ ≤ 65,

2 х₁ + 9 х₂ ≤ 135,

х₁ ≥ 0, х₂ ≥ 0.

6. Зводимо дану задачу лінійного програмування до канонічної форми. (Детально дана задача розглянуто у прикладі 1).

Вводимо в ліві частини нерівностей виду “≤” додаткові невід’ємні змінні х₃, х₄, х₅ (балансові змінні) зі знаком “+” та отримуємо канонічну форму для заданої задачі лінійного програмування:

L = 10 х₁ + 18 х₂ → max,

2 х₁ + 2 х₂ + х₃ = 60,

3 х₁ + х₂ + х₄ = 65, (*)

2 х₁ + 9 х₂ + х₅ = 135,

х₁ ≥ 0, х₂ ≥ 0, х₃ ≥ 0, х₄ ≥ 0, х₅ ≥ 0.

1).

Зводимо систему обмежень до одиничного базису:

а функцію цілі L = γ­_0­ + γ­_r+1­x­_r+1­ + … + γ­­_j­x­_j­ + … + γ­_n­x­_n­, що виражена через вільні зміннізаписуємо у вигляді: L - γ­_r+1­x­_r+1­ - … - γ­­_j­x­_j­ - … - γ­_n­x­_n­= γ­_0­

Подаємо умову задачі лінійного програмування у вигляді таблиці:

Таблиця 1.

Базисні змінні

Вільні члени

x1

x2

…

xі

…

xr

xr+1­

…

x­j­

…

x­n­

x1

b­1

1

0

…

0

…

0

a1, r+1

…

a1, j

…

a1, n

x2

b­2

0

1

…

0

…

0

a2, r+1

…

a2, j

…

a2, n

……

…….

…

…

…

…

…

…

…

…

…

…

…

xі

b­i

0

0

…

1

…

0

ai, r+1

…

ai, j

…

ai, n

……

…….

…

…

…

…

…

…

…

…

…

…

…

xr

b­n

0

0

…

0

…

1

ar, r+1

…

ar, j

…

ar, n

L

γ­0

0

0

…

0

…

0

γ­r+1­

γ­j

γ­n

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­						bi­­ / х­i
х­1	х­2	х­3	х4	х­5
х­3							60/2=30
х­4							65/1=65
х­5							135/9=15
L		-10	-18

Отриманий початковий план можна вдосконалити, так як в останньому рядку табл.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
	14/9				-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=
	25/9				-1/9
х­2	135: 9 =	2:9 =	9:9 =	0:9 =	0:9 =	1:9 =	15:2/9= 67,5
	2/9				1/9
L	0 -15*(-18) =	-10 –2/9*(-18)=	-18 – 1*(-18)=	0 – 0*(-18)=	0 – 0*(-18)=	0 – 1/9*(-18)=
	-6

З цієї таблиці знаходимо новий опорний план: (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=
				-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 =
				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=
				-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)=
				54/25	44/25

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

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

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

Дата добавления: 2014-10-15