[ Будування математичної моделі економічної задачі і розвязання її за допомогою графічного метода ] | 0,8 | |||
0 | 1 | 0 | -1,1 | 0,2 |
0 | 0 | 1 | -2,4 | -0,2 |
Якщо покласти х4 = 0, то отримаємо рішення х1 = 0,8, х2 = 0,2, х3 = -0,2. Підстановка їх у вихідну систему дає тотожне задоволення обмежень-рівностей:
2*0,8 + 0,2 + 0,2 – 0 = 2
4*0,8 – 0,2 – 7*0 = 3
2*0,8 – 3*0,2 + 0 = 1
Якщо на третьому кроці в третьому рiвняннi провідним вибрати елемент а34 = 12, то отримаємо таке рішення:
Таблиця 5. Третій крок методу з провідним а34
А1 | А2 | А3 | А4 | В |
1 | 0 | -0,47917 | 0 | 0,89583 |
0 | 1 | -0,45833 | 0 | 0,29167 |
0 | 0 | -0,41667 | 1 | 8,333E-02 |
Якщо тут покласти х3 = 0, то отримаємо рішення х1 = 0,89583, х2 = 0,29167, х4 = 0,08333. Підстановка їх у вихідну систему також дає тотожності:
2*0,89583+ 0,29167 - 0 - 0,08333 = 2
4*0,89583 + 0 - 7*0,08333 = 3
2*0,89583 - 3*0,29167 + 0,08333 = 1
Отже, ця недовизначена система має безліч розв'язків. Тому можна й далі таким же чином шукати різні розв'язки цієї системи, як завгодно "вручну" визначаючи будь-яку її змінну.
Завдання 4
1). Розв'язати симплекс-методом задачу лінійного програмування, яка представлена в завданні 2.
2). Побудувати двоїсту задачу до заданої задачі лінійного програмування.
3). Знайти розв'язок двоїстої задачі та дати економічну інтерпретацію отриманого розв'язку.
Розв'язок
Отже, наша вихідна система лінійного програмування (ЛП) із завдання 2 з n = 2 буде така:
Z = 3x1 + 2x2 → max
2х1 + х2 ≤ 4,
х1 + 2х2 ≤ 5, (1)
х1 ≥ 0, х2 ≥ 0.
1. Для застосування симплекс-методу потрібно привести вихідну систему (1) до канонічного (стандартного) вигляду шляхом введення двох m = 2 нових змінних х3 та х4:
2х1 + х2 + х3 = 4,
х1 + 2х2 + х4 = 5, (2)
х1,2,3,4 ≥ 0.
Також треба знайти початкове базисне рішення, тобто будь-яке рішення, що не порушує обмежень задачі (2). (Виходячи із тривіальності заданої системи, можна було б відразу вказати таке рішення, яке одночасно було б й оптимальним:
х1 = 1 > 0, х2 = 2 > 0, х3 = х4 = 0.)
Формально початковий базисний розв’язок можна взяти, прийнявши до уваги, що x3 та х4 зустрічаються в кожному рівнянні системи (2) по одному разу:
х1,2 = 0, x3 = 4, х4 = 5.
Далi скористаємося алгоритмом симплекс-метода i заповнимо наступні таблиці за відомими формулами математичного програмування. Позначимо через Аk вектор, складений з коефіцієнтів аik при змінній хk в i-ому обмеженні, через СБ — вектор, складений з координат сбi, що відповідають базисним змінним (на цьому 1-му кроці методу це — x3, х4). Тепер вирахуємо симплексні різниці Δk за формулою
Δk = Ak CБ - Zk = ∑αik, k = 1÷ n + m, і = 1 ÷ m (3)
де підсумовування ведеться по індексу і,
αik = аik сбi – сk. (4)
Отже, Δk дорівнює сумі добутків базисних сбi на аik мінус сk.
Таблиця 1. Перший крок симплекс-методу
i | Б | Сб | сk | 3 | 2 | 0 | 0 |
| | | A0 | A1 | A2 | A3 | A4 |
1 | A3 | 0 | 4 | 2 | 1 | 1 | 0 |
2 | A4 | 0 | 5 | 1 | 2 | 0 | 1 |
Dk | 0 | -6 | -4 | 0 | 0 |
Оскільки ми шукаємо максимум цільової функції, то треба знайти саму мінімальну симплексну різницю Dk серед від'ємних симплекс-різниць, тобто мінімальну за абсолютною величиною (модулем). Такою є симплексна різниця D2 < 0 = -4, отже до базису треба включити вектор A2. Тепер зробимо перевірку того, який з векторів — А3 чи А4 — треба виключити з базису. Для цього підрахуємо величини Оо6i = ai0 / ai2 та знайдемо номер базисного індексу j, який відповідає мінімальному значенню Оо6 = min Оо6і.
Оскільки Оо6і = ai0 / ai2, Оо6 = min (4/1 = 4; 5/2 = 2,5) = 2,5, то j = 4 (в попередній таблиці виділений) і з базису виключається вектор A4. Тепер на місце вектора А4 вводимо до базису вектор А2 та робимо перерахунок системи в таблиці 1 за методом Жордана-Гаусса (алгоритм див. у завданні 3), взявши за провідний елемент а22 = 2 (який у попередній таблиці підкреслений хвилястою лінією).
Таблиця 2. Другий крок симплекс-методу
i | Б | Сб | сk | 3 | 2 | 0 | 0 |
| | | A0 | A1 | A2 | A3 | A4 |
1 | A3 | 0 | 1,5 | 1,5 | 0 | 1 | -0,5 |
2 | A2 | 2 | 2,5 | 0,5 | 1 | 0 | 0,5 |
Dk | 5 | -5 | 0 | 0 | 1 |
Видно, що до базису "проситься" вектор А1. Оскільки Оо6 = min (1,5/1,5 = 1; 2,5/0,5 = 5) = 1, то j = 3 і з базису виключається вектор A3. Тепер на місце вектора А3 вводимо вектор А1 та знову робимо перерахунок системи в таблиці 2 за методом Жордана-Гаусса, взявши за провідний елемент а11 = 1,5.
Таблиця 3. Третій крок симплекс-методу
i | Б | Сб | сk | 3 | 2 | 0 | 0 |
|
|
| A0 | A1 | A2 | A3 | A4 |
1 | A1 | 3 | 1 | 1 | 0 | 0,666667 | -0,33333 |
2 | A2 | 2 | 2 | 0 | 1 | -0,33333 | 0,66667 |
Dk | 7 | 0 | 0 | 1,33333 | 0,33333 |
Таким чином, на даному кроцi симплекс-метода всi значення Di ≥ 0, отже ми отримали таке рішення задачі: Х = (1; 2; 0; 0;) з цільовою функцією
Zmax = 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у1 + 5у2 → min
2у1 + у2 ≥ 3,
у1 + 2у2 ≥ 2, (5)
у1 ≥ 0, у2 ≥ 0.
В даному випадку вихідної системи (1) коефіцієнтами цільової функції Z' стають праві частини В обмежень типу ≤ ; якщо якесь обмеження мало б знак типу ≥, ми б просто змінили знаки коефіцієнтів обох частин цього обмеження. Правими частинами обмежень спряженої задачі стають коефіцієнти C цільової функції Z прямої задачі, що максимізується. Нарешті, коефіцієнтами обмежень типу ≥ спряженої задачі стають елементи векторів Аk, k = 1 ÷ m. Змінні Y = {уj} спряженої задачі також повинні бути невід'ємними. Система обмежень спряженої задачі має розмірність n × m, на відміну від m × n у прямій задачі.
3. Після введення балансових змінних y3,4 одразу отримаємо базовий розв'язок канонічної системи:
y1,2 = 0, y3 = 3, y4 = 2.
і можемо зробити перший крок симплекс-методу для двоїстої задачі.
Таблиця 4. Перший крок симплекс-методу
i | Б | Вб | bk | 4 | 5 | 0 | 0 |
| | | A0 | AТ1 | AТ2 | AТ3 | AТ4 |
1 | AТ3 | 0 | 3 | 2 | 1 | 1 | 0 |
2 | AТ4 | 0 | 2 | 1 | 2 | 0 | 1 |
Dk | 0 | -8 | -10 | 0 | 0 |
При розв'язку задачі мінімізації цільової функції в базис вводиться вектор з найбільшою за модулем від'ємною симплексною різницею D. Оскільки ми шукаємо саме мінімум цільової функції, а максимальним за абсолютною величиною (модулем) є D2 < 0 = -10, то до базису треба включити вектор AТ2. Тепер зробимо перевірку того, який з векторів — А3 чи А4 — треба виключити з базису. Для цього підрахуємо величини Ообi = ai0 / ai2 та знайдемо номер базисного індексу j, який відповідає максимальному значенню Ооб = mах Ообі, оскільки в даному випадку D2 = -10 < 0.
Так як Ообі = ai0 / ai2, Ооб = mах (3/1 = 3; 2/2 = 1) = 3, то j = 3 і з базису виключається вектор AТ3. Тепер на місце вектора АТ3 вводимо до базису вектор АТ2 та робимо перерахунок системи в таблиці 4 за методом Жордана-Гаусса, взявши за провідний елемент а12 = 1.
Таблиця 5. Другий крок симплекс-методу
i | Б | Вб | bk | 4 | 5 | 0 | 0 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| | | A0 | AТ1 | AТ2 | AТ3
Як бачимо, тепер до базису "проситься" вектор АТ1. Оскільки D1 = 2 > 0, то в даному випадку треба шукати Оо6 = mіn (3/2 = 1,5; -4/-3 = 1,3333333) = 1,3333333; отже, j = 4 і з базису виключається вектор A4. Тепер на місце вектора АТ4 вводимо вектор АТ1 та знову робимо перерахунок системи в таблиці 5 за методом Жордана-Гаусса, взявши за провідний елемент а12 = -3. Таблиця 6. Третій крок симплекс-методу
Таким чином, на даному кроці симплекс-метода всі значення Di ≥ 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 симплекс-різниць — D3 ≡ х1 = 1 і D4 ≡ х2 = 2 — є оптимальним рішенням двоїстої (вихідної) задачі. Те саме можна сказати про рішення прямої задачі: оптимальні розв'язки двоїстої (спряженої) задачі виявилися в останніх m компонентах вектора D в таблиці3. Економічна інтерпретація отриманого розв'язку спряженої задачі полягає в тому, що в цій задачі коефіцієнти B = (b1, b2) цільової функції виручки Z' = BY (в грн) мають розмірність об'ємів виробництва продукції типів І та ІІ, а змінні Y = (у1, у2) — розмірність вартості (в грн) одиниць цих продуктів. Отже, тепер ми знаємо, як зміна вартості одиниці того чи іншого продукту вплине на виручку підприємства. В прямій задачі — все навпаки: коефіцієнти С = (с1, с2) цільової функції виручки Z = СХ (в грн) мають розмірність вартості (в грн) одиниць продукції типів І та ІІ, а змінні Х = (у1, у2) — розмірність об'ємів виробництва цих продуктів. Отже, за розв'язком прямої задачі оптимізації ми знаємо, як зміна об'єму виробництва того чи іншого продукту вплине на виручку підприємства. Будь ласка, не зберігайте тестовий текст. |