Практичне завдання з математичного програмування
Будування математичної моделі економічної задачі і розв'язання її за допомогою графічного метода, методів Жордана-Гаусса, потенціалу та симплекс-метода
Завдання 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 0 1 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. Це й є графічний розв'язок задачі. При цьому цільова функція буде мати таке значення:--PAGE_BREAK--
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 продолжение
--PAGE_BREAK----PAGE_BREAK----PAGE_BREAK----PAGE_BREAK--
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) — розмірність об'ємів виробництва цих продуктів. Отже, за розв'язком прямої задачі оптимізації ми знаємо, як зміна об'єму виробництва того чи іншого продукту вплине на виручку підприємства.