Практичнезавдання з математичного програмування
Будуванняматематичної моделі економічної задачі і розв'язання її за допомогою графічногометода, методів Жордана-Гаусса, потенціалу та симплекс-метода
Завдання1
Два вироби В1і В2 обробляються послідовно на двох верстатах. Кожен виріб типу В1потребує 1 год. для обробки на І-му верстаті, 2 год. — на ІІ-му і А = 5^(1/2) =2,236068 год. — на ІІІ-му. Кожен виріб типу В2 потребує 2 год. дляобробки на І-му верстаті, А = 5 год. — на ІІ-му і 3 год. — на ІІІ-му. Час роботина І-му верстаті не повинен перевищувати 10*5 = 50 год., на ІІ-му — 15*5 = 75год., на ІІІ-му — 50 год.
Необхідно:
Скласти планвиробництва при максимальному прибутку, якщо відомо, що продаж одного виробутипу В1 приносить прибуток 5 грн, а типу В2 — 3 грн.
Для цього:
1). Побудуватиматематичну модель задачі лінійного програмування.
2). Звести данузадачу до канонічного вигляду.
Розв'язок
Введемо умовніпозначення:
кількість змінних задачі(типів виробів) — n = 2;
змінні задачі оптимізації:х1 — кількість виробів типу В1, х2 — кількістьвиробів типу В2;
кількість обмежень-нерівностей(верстатів) — m = 3;
коефіцієнти аijобмежень-нерівностей (час обробки виробів j на верстатах i): а11 =1, а21 = 2, а31 = 2,236068; а12 = 2, а22= 5, а32 = 3;
праві частини bі обмежень-нерівностей(максимальний час роботи і-го верстату) — b1 = 50, b2 =75, b3 = 50;
коефіцієнти сj цільовоїфункції Z (прибуток), що максимізується — с1 = 5, с2 = 3.
Одиницівимірювання ті самі, що й в умові завдання.
1. Отже, використовуючинаведені вище дані, сформулюємо вихідну математичну модель задачі лінійногопрограмування: знайти кількості х1, х2 виробів В1,В2 такі, що максимізували б прибуток (цільову функцію)
Z = с1х1+ с2х2 → max
за обмежень начас роботи верстатів
/>а11х1 + а12х2≤ b1
а21х1+а22х2 ≤ b2
а31х1+а32х2 ≤ b3
і, звісно, додатнихзначеннях змінних задачі — хі ≥ 0, і = 1, 2.
Підставляючи сюдивихідні дані, отримаємо шукану модель (1):
/>х1 +2х2≤ 50,
2х1 +5х2 ≤ 75, (1)
2,236068х1 +3х2 ≤ 50;
Z = 5х1+ 3х2 → max.
2. Аби звести дану задачу доканонічного (стандартного) вигляду
Z = СХ → mах;АХ = В; Х ≥ 0, (2)
введемо допоміжні(балансові) змінні х3,4,5 ≥ 0, які представляють собою різниціміж максимальним і фактичним (знайденим в результаті розв'язку задачіоптимізації) часом роботи кожного з трьох верстатів. Тоді й отримаємо нашу задачув канонічному вигляді (2), де:
Х = { хі}, і = 1 ÷ n = 5,
С = (5, 3, 0, 0,0),
/>1 2 1 0 0
А = 2 5 01 0
2,236068 3 0 0 1
В = (50, 75, 50).
Як бачимо, вихідназадача максимізації цільової функції Z в нормальній формі (1) набула канонічноговигляду (2) за рахунок перетворення обмежень-нерівностей на обмеження-рівностішляхом введення балансових змінних.
Завдання2
Розв'язати задачулінійного програмування, сформульовану в Завданні 1, графічним методом:
Z = 3x1+ 2x2 → max
/>2х1 + х2 ≤4,
х1 +2х2 ≤ 5, (1)
х1 ≥0, х2 ≥ 0.
Розв'язок
Використовуючи крайнізначення знаків ≤ обмежень несуворих нерівностей, тобто знаки =, побудуємотакі три графіки:
1) х1= — x2/2 + 2,
2) х1= -2x2 + 5,
3) x1= Z — 2x2/3
Ці графіки показаніна рис. 1, на якому многокутник розв’язків, як видно, обмежений знизу (оскількив системі обмежень (1) фігурують знаки ≤) тільки додатною чвертюдекартової системи х1,2 ≥ 0.
На цьому рисунку цільовафункція показана штриховою лiнiєю, яка, залежно від величини Z, можепереміщуватися паралельно сама собі. Стрілкою з буквою n на рис. 1 позначений напрямокградієнта цільової функції (тобто напрямок збільшення Z). Зрозуміло, що їїмаксимум знаходиться в точці перетину ліній обмежень 1) і 2), в якій х1= 1 > 0, х2 = 2 > 0. Це й є графічний розв'язок задачі. Прицьому цільова функція буде мати таке значення:
Z = 3*1 + 2*2 =7.
/>
Рисунок 1. Графікдо розв’язання Завдання 2
Завдання3
Розв'язати системулінійних рівнянь методом повного виключення змінних (метод Гаусса) звикористанням розрахункових таблиць:
/>2х1 + х2 — х3 — х4 = 2
4х1 +х3 — 7х4 = 3
2х1 — 3х2 + х4 = 1
Розв'язок
Взагалі кажучи,ця недовизначена система може або мати безліч розв'язків, або не матижодного (тобто бути несумісною). Для з'ясування цього застосуємо метод Гаусса(точніше, Жордана-Гаусса), який реалізуємо у вигляді таблиць 2 – 4. В таблиці 1вміщені вихідні дані.
Таблиця 1. Вихіднаматриця системи
А1
А2
А3
А4 В
2 1 -1 -1 2 4 1 -7 3 2 -3 1 1
Згідно методуЖордана-Гаусса, провідний елемент ars замінюємо одиницею, решту елементівпровідного (r-го) рядка ділимо на провідний елемент ars, а решту елементівпровідного (s-го) стовпчика замінюємо нулями. Елементи, які не належать до провідногорядка або стовпчика, обчислюються за правилом прямокутника:
a'ij =aij — aisarj / ars, (1)
b'i =bi — aisbr / ars, (2)
j = 1, …, n = 4, і¹ r,
i = 1, …, m = 3, j¹ s,
де ars— провідний елемент (у наших таблицях підкреслений). Розрахунки за формулами(1), (2) зведемо в наступні таблиці, послідовно вибираючи провіднимидіагональні елементи матриці А.
На першому кроціпровідним вибираємо елемент а11.
Таблиця 2. Першийкрок методу
А1
А2
А3
А4 В 1 0,5 -0,5 -0,5 1
-2 3 -5 -1 -4 1 2 -1
На другому кроці провіднимвибираємо елемент а22 = -2.
Таблиця 3. Другийкрок методу
А1
А2
А3
А4 В 1 0,25 -1,75 0,75 1 -1,5 2,5 0,5
-5 12 1
Далi, в третьомурiвняннi провідним вибираємо елемент а33 = -5.
Таблиця 4. Третійкрок методу з провідним а33
А1
А2
А3
А4 В 1 -1,15 0,8 1 -1,1 0,2 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,47917 0,89583 1 -0,45833 0,29167 -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
A0
A1
A2
A3
A4 1
A3 4 2 1 1 2
A4 5 1
2 1
Dk -6
-4
Оскільки мишукаємо максимум цільової функції, то треба знайти саму мінімальнусимплексну різницю Dk серед від'ємних симплекс-різниць, тобто мінімальну заабсолютною величиною (модулем). Такою є симплексна різниця D2 включитивектор 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
A0
A1
A2
A3
A4 1
A3 1,5
1,5 1 -0,5 2
A2 2 2,5 0,5 1 0,5
Dk 5
-5 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
A0
A1
A2
A3
A4 1
A1 3 1 1 0,666667 -0,33333 2
A2 2 2 1 -0,33333 0,66667
Dk 7 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
A0
AТ1
AТ2
AТ3
AТ4 1
AТ3 3 2
1 1 2
AТ4 2 1 2 1
Dk -8
-10
При розв'язкузадачі мінімізації цільової функції в базис вводиться вектор з найбільшоюза модулем від'ємною симплексною різницею D. Оскільки ми шукаємо саме мінімумцільової функції, а максимальним за абсолютною величиною (модулем) є D2 максимальномузначенню Ооб = mах Ообі, оскільки в даному випадку D2 = -10
Так як Ообі= ai0 / ai2, Ооб = mах (3/1 = 3; 2/2 = 1) = 3,то j = 3 і з базису виключається вектор AТ3. Тепер намісце вектора АТ3 вводимо до базису вектор АТ2та робимо перерахунок системи в таблиці 4 за методом Жордана-Гаусса, взявши за провіднийелемент а12 = 1.
Таблиця 5. Другийкрок симплекс-методуi Б
Вб
bk 4 5
A0
AТ1
AТ2
AТ3
AТ4 1
AТ2 5 3 2 1 1 2
AТ4 -4 -3 -2 1
Dk 15
2 5
Як бачимо, тепердо базису «проситься» вектор АТ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. Третійкрок симплекс-методуi Б
Вб
bk 4 5
A0
AТ1
AТ2
AТ3
AТ4 1
AТ2 5 0,33333 1 -0,33333 0,66667 2
AТ1 4 1,33333 1 0,66667 -0,33333
Dk 7 1 2
Таким чином, наданому кроці симплекс-метода всі значення 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)— розмірність об'ємів виробництва цих продуктів. Отже, за розв'язком прямоїзадачі оптимізації ми знаємо, як зміна об'єму виробництва того чи іншогопродукту вплине на виручку підприємства.