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

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

 

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

Завдання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+<sub/>а22х2 ≤ b2

а31х1+<sub/>а32х2 ≤ b3

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

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

/>х1 +<sub/>2х2≤ 50,

2х1 +<sub/>5х2 ≤ 75,                                                     (1)

2,236068х1 +<sub/>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 < 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

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<sub/>=4,

1 + 2*2 + 0<sub/>=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 < 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

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 (в грн) мають розмірність об'ємів виробництва продукції типів І<sub/>таІІ, а змінні Y = (у1, у2) — розмірність вартості (в грн) одиницьцих продуктів. Отже, тепер ми знаємо, як зміна вартості одиниці того чи іншого продуктувплине на виручку підприємства.

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