Будування математичної моделі економічної задачі і розвязання її за допомогою графічного метода (стр. 2 из 2)

х₁ = 1 > 0, х₂ = 2 > 0, х₃= х₄ = 0.)

Формально початковий базисний розв’язок можна взяти, прийнявши до уваги, що x₃ та х₄ зустрічаються в кожному рівнянні системи (2) по одному разу:

х_1,2 = 0, x₃ = 4, х₄ = 5.

Далi скористаємося алгоритмом симплекс-метода i заповнимо наступні таблиці за відомими формулами математичного програмування. Позначимо через А_k вектор, складений з коефіцієнтів а_ik при змінній х_k в i-ому обмеженні, через С_Б — вектор, складений з координат с_бi, що відповідають базисним змінним (на цьому 1-му кроці методу це — x₃, х₄). Тепер вирахуємо симплексні різниці Δ_k за формулою

Δ_k = A_k C_Б - Z_k = ∑α_ik, k = 1÷ n + m, і = 1 ÷ m (3)

де підсумовування ведеться по індексу і,

α_ik = а_ik с_бi – с_k. (4)

Отже, Δ_k дорівнює сумі добутків базисних с_бi на а_ik мінус с_k.

Таблиця 1. Перший крок симплекс-методу

i	Б	С_б	с_k	3	2	0	0
i	Б	С_б	A₀	A₁	A₂	A₃	A₄
1	A₃	0	4	2	1	1	0
2	A₄	0	5	1	2	0	1
D_k			0	-6	-4	0	0

Оскільки ми шукаємо максимум цільової функції, то треба знайти саму мінімальну симплексну різницю D_k серед від'ємних симплекс-різниць, тобто мінімальну за абсолютною величиною (модулем). Такою є симплексна різниця D₂ < 0 = -4, отже до базису треба включити вектор A₂. Тепер зробимо перевірку того, який з векторів — А₃ чи А₄ — треба виключити з базису. Для цього підрахуємо величини О_о6i = a_i0 / a_i2та знайдемо номер базисного індексу j, який відповідає мінімальному значенню О_о6= min О_о6і.

Оскільки О_о6і = a_i0 / a_i2, О_о6= min (4/1 = 4; 5/2 = 2,5) = 2,5, то j = 4 (в попередній таблиці виділений) і з базису виключається вектор A₄. Тепер на місце вектора А₄ вводимо до базису вектор А₂ та робимо перерахунок системи в таблиці 1 за методом Жордана-Гаусса (алгоритм див. у завданні 3), взявши за провідний елемент а₂₂ = 2 (який у попередній таблиці підкреслений хвилястою лінією).

Таблиця 2. Другий крок симплекс-методу

i	Б	С_б	с_k	3	2	0	0
i	Б	С_б	A₀	A₁	A₂	A₃	A₄
1	A₃	0	1,5	1,5	0	1	-0,5
2	A₂	2	2,5	0,5	1	0	0,5
D_k			5	-5	0	0	1

Видно, що до базису "проситься" вектор А₁. Оскільки О_о6= min (1,5/1,5 = 1; 2,5/0,5 = 5) = 1, то j = 3 і з базису виключається вектор A₃. Тепер на місце вектора А₃ вводимо вектор А₁ та знову робимо перерахунок системи в таблиці 2 за методом Жордана-Гаусса, взявши за провідний елемент а₁₁ = 1,5.

Таблиця 3. Третій крок симплекс-методу

i	Б	С_б	с_k	3	2	0	0
i	Б	С_б	A₀	A₁	A₂	A₃	A₄
1	A₁	3	1	1	0	0,666667	-0,33333
2	A₂	2	2	0	1	-0,33333	0,66667
D_k			7	0	0	1,33333	0,33333

Таким чином, на даному кроцi симплекс-метода всi значення D_i ≥ 0, отже ми отримали таке рішення задачі: Х = (1; 2; 0; 0;) з цільовою функцією

Z_max = 3*1 + 2*2 = 7.

Безпосередня підстановка цього рішення у вихідну систему підтверджує його правильність:

2*1 + 2 + 0 = 4,

1 + 2*2 + 0 = 5.

Між іншим, в таблиці 3 маємо також розв'язок спряженої задачі (див. далі).

2. В матрично-векторному вигляді взаємно двоїсті (пряма і спряжена) задачі лінійного програмування записуються у вигляді (5), (6):

Z = СХ Þ min (max) при АХ ≤ В, Х ≥ 0; (5)

Z' = BY Þ max (min) при А^TY ≥ C, Y ≥ 0. (6)

Враховуючи, що цільова функція Z нашої прямої задачі дослужується на максимум i всі обмеження записані у вигляді нерівностей типу ≤, двоїста спряжена задача, згідно з правилами лінійного програмування, матиме такий вигляд:

Z' = 4у₁ + 5у₂ → min

2у₁ + у₂ ≥ 3,

у₁ + 2у₂ ≥ 2, (5)

у₁ ≥ 0, у₂ ≥ 0.

В даному випадку вихідної системи (1) коефіцієнтами цільової функції Z' стають праві частини В обмежень типу ≤ ; якщо якесь обмеження мало б знак типу ≥, ми б просто змінили знаки коефіцієнтів обох частин цього обмеження. Правими частинами обмежень спряженої задачі стають коефіцієнти C цільової функції Z прямої задачі, що максимізується. Нарешті, коефіцієнтами обмежень типу ≥ спряженої задачі стають елементи векторів А_k, k = 1 ÷ m. Змінні Y = {у_j} спряженої задачі також повинні бути невід'ємними. Система обмежень спряженої задачі має розмірність n × m, на відміну від m × n у прямій задачі.

3. Після введення балансових змінних y_3,4 одразу отримаємо базовий розв'язок канонічної системи:

y_1,2= 0, y₃= 3, y₄= 2.

і можемо зробити перший крок симплекс-методу для двоїстої задачі.

Таблиця 4. Перший крок симплекс-методу

i	Б	В_б	b_k	4	5	0	0
i	Б	В_б	A₀	A^Т₁	A^Т₂	A^Т₃	A^Т₄
1	A^Т₃	0	3	2	1	1	0
2	A^Т₄	0	2	1	2	0	1
D_k			0	-8	-10	0	0

При розв'язку задачі мінімізації цільової функції в базис вводиться вектор з найбільшою за модулем від'ємною симплексною різницею D. Оскільки ми шукаємо саме мінімум цільової функції, а максимальним за абсолютною величиною (модулем) є D₂ < 0 = -10, то до базису треба включити вектор A^Т₂. Тепер зробимо перевірку того, який з векторів — А₃ чи А₄ — треба виключити з базису. Для цього підрахуємо величини О_обi = a_i0 / a_i2 та знайдемо номер базисного індексу j, який відповідає максимальному значенню О_об = mах О_обі, оскільки в даному випадку D₂ = -10 < 0.

Так як О_обі = a_i0 / a_i2, О_об= mах (3/1 = 3; 2/2 = 1) = 3, то j = 3 і з базису виключається вектор A^Т₃. Тепер на місце вектора А^Т₃ вводимо до базису вектор А^Т₂ та робимо перерахунок системи в таблиці 4 за методом Жордана-Гаусса, взявши за провідний елемент а₁₂ = 1.

Таблиця 5. Другий крок симплекс-методу

i	Б	В_б	b_k	4	5	0	0
i	Б	В_б	A₀	A^Т₁	A^Т₂	A^Т₃	A^Т₄
1	A^Т₂	5	3	2	1	1	0
2	A^Т₄	0	-4	-3	0	-2	1
D_k			15	2	0	5	0

Як бачимо, тепер до базису "проситься" вектор А^Т₁. Оскільки D₁ = 2 > 0, то в даному випадку треба шукати О_о6= mіn (3/2 = 1,5; -4/-3 = 1,3333333) = 1,3333333; отже, j = 4 і з базису виключається вектор A₄. Тепер на місце вектора А^Т₄ вводимо вектор А^Т₁ та знову робимо перерахунок системи в таблиці 5 за методом Жордана-Гаусса, взявши за провідний елемент а₁₂ = -3.

Таблиця 6. Третій крок симплекс-методу

i	Б	В_б	b_k	4	5	0	0
i	Б	В_б	A₀	A^Т₁	A^Т₂	A^Т₃	A^Т₄
1	A^Т₂	5	0,33333	0	1	-0,33333	0,66667
2	A^Т₁	4	1,33333	1	0	0,66667	-0,33333
D_k			7	0	0	1	2

Таким чином, на даному кроці симплекс-метода всі значення D_i ≥ 0, отже ми отримали таке рушення задачі: Y = (1,33333; 0,33333; 0; 0;) ≥ 0 з цільовою функцією

Z'_mіn = 4* 1,33333+ 5* 0,33333 = 7.

Безпосередня підстановка цього рішення у вихідну систему підтверджує його правильність:

2*1,33333 + 0,33333 + 0 = 3,

1,33333 + 2*0,33333 + 0 = 2.

Як бачимо, дійсно, значення цільових функцій прямої Z і двоїстої Z' задач в оптимальній точці співпадають. Крім того, розв'язок двоїстої до даної – прямої задачі (див. п. 4.1) – можна знайти за останньою симплексною таблицею 6: останні m компонентів вектора D симплекс-різниць — D₃ ≡ х₁ = 1 і D₄ ≡ х₂ = 2 — є оптимальним рішенням двоїстої (вихідної) задачі. Те саме можна сказати про рішення прямої задачі: оптимальні розв'язки двоїстої (спряженої) задачі виявилися в останніх m компонентах вектора D в таблиці3.

Економічна інтерпретація отриманого розв'язку спряженої задачі полягає в тому, що в цій задачі коефіцієнти B = (b₁, b₂) цільової функції виручки Z' = BY (в грн) мають розмірність об'ємів виробництва продукції типів І та ІІ, а змінні Y = (у₁, у₂) — розмірність вартості (в грн) одиниць цих продуктів. Отже, тепер ми знаємо, як зміна вартості одиниці того чи іншого продукту вплине на виручку підприємства.

В прямій задачі — все навпаки: коефіцієнти С = (с₁, с₂) цільової функції виручки Z = СХ (в грн) мають розмірність вартості (в грн) одиниць продукції типів І та ІІ, а змінні Х = (у₁, у₂) — розмірність об'ємів виробництва цих продуктів. Отже, за розв'язком прямої задачі оптимізації ми знаємо, як зміна об'єму виробництва того чи іншого продукту вплине на виручку підприємства.