Практичне завдання з математичного програмування

Будування математичної моделі економічної задачі і розв'язання її за допомогою графічного метода, методів Жордана-Гаусса, потенціалу та симплекс-метода

Завдання 1

Два вироби В₁ і В₂ обробляються послідовно на двох верстатах. Кожен виріб типу В₁ потребує 1 год. для обробки на І-му верстаті, 2 год. — на ІІ-му і А = 5^(1/2) = 2,236068 год. — на ІІІ-му. Кожен виріб типу В₂ потребує 2 год. для обробки на І-му верстаті, А = 5 год. — на ІІ-му і 3 год. — на ІІІ-му. Час роботи на І-му верстаті не повинен перевищувати 10*5 = 50 год., на ІІ-му — 15*5 = 75 год., на ІІІ-му — 50 год.

Необхідно:

Скласти план виробництва при максимальному прибутку, якщо відомо, що продаж одного виробу типу В₁ приносить прибуток 5 грн, а типу В₂ — 3 грн.

Для цього:

1). Побудувати математичну модель задачі лінійного програмування.

2). Звести дану задачу до канонічного вигляду.

Розв'язок

Введемо умовні позначення:

· кількість змінних задачі (типів виробів) — n = 2;

· змінні задачі оптимізації: х₁ — кількість виробів типу В₁, х₂ — кількість виробів типу В₂;

· кількість обмежень-нерівностей (верстатів) — m = 3;

· коефіцієнти а_ij обмежень-нерівностей (час обробки виробів j на верстатах i): а₁₁ = 1, а₂₁ = 2, а₃₁ = 2,236068; а₁₂ = 2, а₂₂ = 5, а₃₂ = 3;

· праві частини b_і обмежень-нерівностей (максимальний час роботи і-го верстату) — b₁ = 50, b₂ = 75, b₃ = 50;

· коефіцієнти с_j цільової функції Z (прибуток), що максимізується — с₁ = 5, с₂ = 3.

Одиниці вимірювання ті самі, що й в умові завдання.

1. Отже, використовуючи наведені вище дані, сформулюємо вихідну математичну модель задачі лінійного програмування: знайти кількості х₁, х₂ виробів В₁, В₂ такі, що максимізували б прибуток (цільову функцію)

Z = с₁х₁ + с₂х₂ → max

за обмежень на час роботи верстатів

а₁₁х₁ + а₁₂х₂ ≤ b₁

а₂₁х₁ + а₂₂х₂ ≤ b₂

а₃₁х₁ + а₃₂х₂ ≤ b₃

і, звісно, додатних значеннях змінних задачі — х_і ≥ 0, і = 1, 2.

Підставляючи сюди вихідні дані, отримаємо шукану модель (1):

х₁ + 2х₂ ≤ 50,

2х₁ + 5х₂ ≤ 75, (1)

2,236068х₁ + 3х₂ ≤ 50;

Z = 5х₁ + 3х₂ → 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 = 3x₁ + 2x₂ → max

2х₁ + х₂ ≤ 4,

х₁ + 2х₂ ≤ 5, (1)

х₁ ≥ 0, х₂ ≥ 0.

Розв'язок

Використовуючи крайні значення знаків ≤ обмежень несуворих нерівностей, тобто знаки =, побудуємо такі три графіки:

1) х₁ = - x₂/2 + 2,

2) х₁ = -2x₂ + 5,

3) x₁ = Z - 2x₂/3

Ці графіки показані на рис. 1, на якому многокутник розв’язків, як видно, обмежений знизу (оскільки в системі обмежень (1) фігурують знаки ≤) тільки додатною чвертю декартової системи х_1,2 ≥ 0.

На цьому рисунку цільова функція показана штриховою лiнiєю, яка, залежно від величини Z, може переміщуватися паралельно сама собі. Стрілкою з буквою n на рис. 1 позначений напрямок градієнта цільової функції (тобто напрямок збільшення Z). Зрозуміло, що її максимум знаходиться в точці перетину ліній обмежень 1) і 2), в якій х₁ = 1 > 0, х₂ = 2 > 0. Це й є графічний розв'язок задачі. При цьому цільова функція буде мати таке значення:

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

Рисунок 1. Графік до розв’язання Завдання 2

Завдання 3

Розв'язати систему лінійних рівнянь методом повного виключення змінних (метод Гаусса) з використанням розрахункових таблиць:

2х₁ + х₂ - х₃ - х₄ = 2

4х₁ + х₃ - 7х₄ = 3

2х₁ - 3х₂ + х₄ = 1

Розв'язок

Взагалі кажучи, ця недовизначена система може або мати безліч розв'язків, або не мати жодного (тобто бути несумісною). Для з'ясування цього застосуємо метод Гаусса (точніше, Жордана-Гаусса), який реалізуємо у вигляді таблиць 2 – 4. В таблиці 1 вміщені вихідні дані.

Таблиця 1. Вихідна матриця системи

А1	А2	А3	А4	В
2	1	-1	-1	2
4	0	1	-7	3
2	-3	0	1	1

Згідно методу Жордана-Гаусса, провідний елемент a_rs замінюємо одиницею, решту елементів провідного (r-го) рядка ділимо на провідний елемент a_rs, а решту елементів провідного (s-го) стовпчика замінюємо нулями. Елементи, які не належать до провідного рядка або стовпчика, обчислюються за правилом прямокутника:

a'_ij = a_ij - a_isa_rj / a_rs, (1)

b'_i = b_i - a_isb_r / a_rs, (2)

j = 1, …, n = 4, і № r,

i = 1, …, m = 3, j № s,

де a_rs — провідний елемент (у наших таблицях підкреслений). Розрахунки за формулами (1), (2) зведемо в наступні таблиці, послідовно вибираючи провідними діагональні елементи матриці А.

На першому кроці провідним вибираємо елемент а₁₁.

Таблиця 2. Перший крок методу

А1	А2	А3	А4	В
1	0,5	-0,5	-0,5	1
0	-2	3	-5	-1
0	-4	1	2	-1

На другому кроці провідним вибираємо елемент а₂₂ = -2.

Таблиця 3. Другий крок методу

А1	А2	А3	А4	В
1	0	0,25	-1,75	0,75
0	1	-1,5	2,5	0,5
0	0	-5	12	1

Далi, в третьому рiвняннi провідним вибираємо елемент а₃₃ = -5.

Таблиця 4. Третій крок методу з провідним а₃₃

А1	А2	А3	А4	В
1	0	0	-1,15	0,8
0	1	0	-1,1	0,2
0	0	1	-2,4	-0,2

Якщо покласти х₄ = 0, то отримаємо рішення х₁ = 0,8, х₂ = 0,2, х₃ = -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 провідним вибрати елемент а₃₄ = 12, то отримаємо таке рішення:

Таблиця 5. Третій крок методу з провідним а₃₄

А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

Якщо тут покласти х₃ = 0, то отримаємо рішення х₁ = 0,89583, х₂ = 0,29167, х₄ = 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 = 3x₁ + 2x₂ → max

2х₁ + х₂ ≤ 4,

х₁ + 2х₂ ≤ 5, (1)

х₁ ≥ 0, х₂ ≥ 0.

1. Для застосування симплекс-методу потрібно привести вихідну систему (1) до канонічного (стандартного) вигляду шляхом введення двох m = 2 нових змінних х₃ та х₄:

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

х₁ + 2х₂ + х₄ = 5, (2)

х_1,2,3,4 ≥ 0.

Також треба знайти початкове базисне рішення, тобто будь-яке рішення, що не порушує обмежень задачі (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
			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

Оскільки ми шукаємо максимум цільової функції, то треба знайти саму мінімальну симплексну різницю 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
			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

Видно, що до базису "проситься" вектор А₁. Оскільки О_о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
			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 значення 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	Б	Вб	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. Оскільки ми шукаємо саме мінімум цільової функції, а максимальним за абсолютною величиною (модулем) є 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	Б	Вб	bk	4	5	0	0
			A0	AТ1	AТ2	AТ3	AТ4
1	AТ2	5	3	2	1	1	0
2	AТ4	0	-4	-3	0	-2	1
Dk			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	Б	Вб	bk	4	5	0	0
			A0	AТ1	AТ2	AТ3	AТ4
1	AТ2	5	0,33333	0	1	-0,33333	0,66667
2	AТ1	4	1,33333	1	0	0,66667	-0,33333
Dk			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 = СХ (в грн) мають розмірність вартості (в грн) одиниць продукції типів І та ІІ, а змінні Х = (у₁, у₂) — розмірність об'ємів виробництва цих продуктів. Отже, за розв'язком прямої задачі оптимізації ми знаємо, як зміна об'єму виробництва того чи іншого продукту вплине на виручку підприємства.