Лабораторна робота №3.

 Аналіз лінійних оптимізаційних задач: аналіз оптимального розв’язку; параметричний аналіз; графічне представлення результатів аналізу.

Мета роботи: Вивчити методи аналізу задач лінійного програмування засобами Solver та графічного представлення отриманих результатів засобами Exсel

1.1.Теоретичні відомості.

1.Якщо рішення нема

При рішенні задачі лінійного програмування достатньо часто оптимального рішення отримати не вдається. Це виникає по двом причинам.

Причину 1 проілюструємо на наступному прикладі.

Про таку систему кажуть, що обмеження несумісні. Нажаль, це дуже часто зустрічається на практиці, а не тількі теоретично можливий варіант. В таких випадках Excel буде видавати повідомлення Пошук не може знайти відповідного рішення. В загальному випадку несумісність може бути наслідком двох причин:

• Неправильна математична модель;

• Неправильні початкові дані.

Способи подалання несумісності ми розглянемо після того, як навчимося рішати задачі лінійного програмування в Excel.

Причину 2 розглянемо на наступному прикладі.

В такому випадку при максимізації цільової функції

F=x₁max

рішення отримане бути не може, так як цільова функція, як і ОДР, не обмежена з верху. Якщо в задачі ОДР не обмежена, тоді Excel буде видавати повідомлення “значення цільової комірки не співпадають.”

Необмеженність цільової функції – це наслідок помилки в математичній моделі. Щоб уникнути таких помилок, треба виконувати наступні правила:

При максимізації цільової функції вона повинна бути обмеженна зверху або з допомогою обмежень, або з допомогою граничних умов.

При мінімізації цільової функції вона, відповідно, повинна бути обмеженна знизу.

2.Двійковість в задачах лінійного програмування

Ще трохи теорії. Розглянемо тепер поняття про двійковість.

Кожній задачі лінійного програмування, яку будемо називати початковою відповідає двійкова задача. Правила запису двійкової задачі розглянемо на такому прикладі. Нехай є початкова задача

F=4x₁+5x₂+9x ₃max

x₁+x₂+2x ₃16 (a)

7x₁+5x₂+3x ₃ 25 (b)  (5)

 Двійкова задача формулюється по наступним правилам:

1. Кожному i-ому обмеженню початкової задачі відповідає зміна двійкової задачі, яку будемо називати двійковою змінною і позначати z_і. В системі (5) обмеженню (а) відповідає змінна z₁, обмеженню (б) – зміна z_2.

2. Кожній змінній початкової задачі відповідає обмеження двійкової задачі. В системі (5) три змінних x₁,x₂,x _3.  Значить, двійкова задача повинна мати три обмеження.

3. Матриця коефіціентів при двійкових змінних в обмеженнях двійкової задачі являється транспонованою матрицею коефіціентів при змінних в обмеженнях початкової задачі (5).

4. Якщо в початковій задачі обмеження мають знаки нерівностей , тоді в двійковій вони будуть  .

5. Праві частини обмежень в двійковій задачі дорівнюють коефіціентам при змінних в цільовій функції початкової задачі.

6. Коефіціенти при двійкових змінних в цільовій функції двійкової задачі дорівнюють правим частинам обмежень початкової задачі.

7. Максимізація цільової функції початкової задачі заміняється мінімізацією цільової функції двійкової задачі.

Таким чином, для початкової задачі (5) можна записати двійкову задачу

F_д=16z₁+25z₂min

 z₁ +7z₂4; z₁ +5z₂5

 2z₁ +3z₂9;  z_i0;   i=...;   (6)

Важлива властивість двійкової задачі заключається в тому, що

MaxF=minF_Д.

Двійкова змінна z_i являється коефіціентом при b_i і отже, показує, як зміниться цільова функція при зміні ресурса b_i на одиницю. В літературі по оптимізації двійкові змінні принято називати двійковими оцінками. У звітах Excel двійкова оцінка називається тіньовою ціною.

Дуже важливо, що для знаходження двійкових оцінок двійкову задачу вирішувати не потрібно. Їх значення вже знаходяться в симплекс-таблиці оптимального рішення початкової задачі, яка приведена для розглядаємого прикладу на мал.3 (лабораторна №2).

Визначити значення двійкових оцінок можна наступним чином. Якщо деякий i-ий ресурс використовується не повністью, тобто має резерв, значить, додаткова змінна в обмеженні для даного ресурсу буде більша нуля. В нашому прикладі таким ресурсом є сировина, оскільки b₂=110 і його резерв y₂=26. Цілковито очевидно, що якщо би сировини було не 110 одиниць, а 111, то резерв був би рівен не 26, а 27. При цьому не виникло би збільшення цільової функції. Отже, для другого обмеження двійкова змінна z₂=0. Таким чином, якщо по даному ресурсу є резерв, тоді додаткова змінна буде більше нуля, двійкова оцінка цього обмеження рівна нулю.

В прикладі, що розглядається, трудові ресурси і фінанси використовувались повністью, тому їх додаткові змінні рівні нулю. В таблиці на мал.3 змінні y₁ і y₃ являються вільними, значить y₁=y₃=0. Якщо ресурс використовується повністью, то його збільшення або зменшення вплине на об’єм випускаємої продукції і, отже, на величину цільової функції.

Значення двійкової оцінки при цьому знаходиться в симплек-таблиці (мал.3 лабораторної №2) на перетині стрічки цільової функції зі стовпцем данної додаткової змінної. Для трудових ресурсів при y₁=0 двійкова оцінка z_i=20, а для фінансів при y₃=0 двійкова оцінка z₃=10.

Результати рішення задачі, що приведені на мал.3 (лаб.№2), зведені до таблиці, яка показана на мал.3.

Мал.3.

З цієї таблиці видно, що при збільшенні (зменьшенні) трудових ресурсів на одиницю, цільова функція збільшиться (зменьшиться) на 20 одиниць і буде рівна

при збільшенні - F=1320+20*1=1340,

при зменьшенні - F=1320-20*1=1300.

Аналогічно постає справа і з фінансами. При збільшенні (зменьшенні) фінансів на одиницю цільова функція буде рівна

при збільшенні - F=1320+10*1=1330,

при зменьшенні - F=1320-10*1=1310.

Для задачі розподілення ресурсів (із лаб.№2 мал.3) по приведеним вище правилам складемо двійкову задачу:

F_Д=16z₁+110z₂+100z₃min

z₁+6z₂+4z₃60

z₁+5z₂+6z₃70

z₁+4z₂+10z₃120 (9)

z₁+3z₂+13z₃130

По аналогії з вводом додаткових змінних y_i (9) введемо додаткові двійкові змінні v_j.

F_Д=16z₁+110z₂+100z₃min

z₁+6z₂+4z₃-v₁=60

z₁+5z₂+6z₃-v₂=70

z₁+4z₂+10z₃-v₃=120  (10)

z₁+3z₂+13z₃-v₄=130

v_j;z_i0;

Значення додаткових двійкових змінних спеціально обчислювати не треба. Їх значення вже визначенні в симплекс-таблиці, приведеної на мал.3 (лаб.№2). Фрагмент цієї таблиці з позначеннями основних і додаткових двійкових змінних показан на мал.4, а їх значення – на мал.5.

мал.4 і мал.5.

Який же зміст додаткових двійкових змінних?

Якщо основні змінні (в нашому прикладі x₁=10, x₃=6) увійшли в оптимальне рішення, тоді їх додаткові змінні рівні нулю (v₁=0, v₃=0). Якщо основні змінні не увійшли в оптимальне рішення, тобто рівні нулю (в прикладі x₂=x₄=0), тоді відповідні їм додаткові змінні мають додатні значення (v₂=10, v₄=20). Ці величини показують, наскільки зменьшиться цільова функція при примусовому випуску одиниці данної продукції. Отже, якщо ми захочемо примусово випустити одиницю продукції Прод3, то цільова функція F зменшиться на 10 одиниць і буде рівна 1320-10*1=1310.

3. Аналіз оптимального рішення.

Початкові данні, для яких знаходилось оптимальне рішеня, можуть змінюватись. Чи зміниться при цьому отримане оптимальне рішення? Щоб відповісти на це питання, звернемося до нашої моделі (мал.3 лаб.№2).

В математичній моделі (мал.3 з лаб.№2) цільова функція рівна

F=60x₁+70x₂+120x₃+130x₄max.

Припустимо, прибуток від продажу Прод1 с₁=60 зміниться на величину с₁ і стане

с₁=60+с₁                 

Мал.6

При цьому стрічка цільової функції в початковій симплекс-таблиці (мал.2 лаб.№2) прийме такий вигляд, як на мал.6.

В результаті пошуку оптимального рішення фрагмент останньої симплекс-таблиці буде мати вигляд, представленний на мал.7. звідси можна зробити висновок, що до величин, що знаходяться в таблиці на мал.3 (лаб.№2), додаються величини в стрічці x_j (ячейки В3:F3), помножені на с_1.

Мал.7.

Згідно до признаку 2а, сформульованому в лаб.№2, при максимізації цільової функції рішення буде оптимальним в тому випадку, коли в стрічці цільової функції всі елементи, крім вільного члена, будуть невідємними.

Значить, рішення буде оптимальним при умові

20+1,67с₁0

10+0,67с₁0

10-0,17с₁0

20-0,5 с₁0 (12).

Перетворюючи (12), запишимо:

с₁-20/1,67=-12

с₁-10/0,67=-15

с₁-10/0,17=60

с₁-20/0,5=40

і остаточно

-12с₁40.

Умова (12) визначає межі зміни с₁ при яких зберігається структура оптимального плана, тобто буде вигідно як завжди випускати продукцію x₁.

У звітах Excel нижня границя (в прикладі рівний 12) називається припустиме зменшення, верхня межа, рівна 40, - припустиме збільшення.

Якщо від меж прирощувань с₁ перейти до меж значення величини с_1, то можна записати

minс₁ =с₁ +minс₁=60-12=48

maxс₁=с₁+maxс₁=60+40=100 (13).

Таким чином, при зміні с₁ в межах

minс₁ с₁ maxс₁

maxс₁с₁100 (14)

буде вигідно випускати продукцію x₁. При цьому значення цільової функції буде:

F=1320+10с_1.

І далі по залежностям, аналогічним (13), не важко перейти до меж значень с₂, с₃, с_4.

Аналіз впливу зміни b_i

Розглянемо впли зміни ресурсів на прикладі зміни наявної кількості сировини. При зміні трудових ресурсів на b_i обмеження для них будуть мати вигляд:

x₁+x₂+x₃+x₄16b₁,

що запишимо у вигляді:

y₁=(16+b₁)-( x₁+x₂+x₃+x₄).

При цьому стовпець вільних членів в симплекс-таблиці буде мати вигляд показаний на мал.8, а фрагмент симплекс-таблиці з оптимальним рішенням – на мал.9, з якого видно правило формування вільних членів, аналогічне правилу формуванню стрічки цільової функції.

Мал.8

Мал.9

У відповідності до признака 1 рішення буде припустимим в тому випадку, якщо всі елементи в стовбці вільних членів будуть невідємними. Значить, з мал.9 випливає

10+1,67b₁0

26-7,73b₁0

6-0,67b₁0

звідки

b_i-10/1.67=-6

b_i26/7.33=3.55

b_i6/0.67=9.

Тоді для зберігання структури оптимального плана зміни трудових ресурсів повинно бути в межах

-6b₁3,55.

Аналогічно можна отримати значення для b_2, b₃ і записати

-6b₁3,55

26b₂    необмеж.

-36b₃60 (16)

Перехід від b_i до меж b_i виконується по залежностям

min b_i= b_i+min b_i

max b_i= b_i+max b_i (17)

min b_ib_imax b_i     в результаті отримаємо

minb₁=16-6=10

maxb₁=16+3.55=19.55

10b₁19.55 (18)

84b₂   необмеж.

64b₃160.

Знайдені межі показують границі, в яких можуть змінюватись ресурси, щоб структура оптимального рішення, тобто номенклатура випускаємої продукції, залишились без змін. А це означає, що при зміні трудових ресурсів в знайдених межах оптимальним, тобто забезпечуючим найбільший прибуток, являється випуск тієї ж продукції x₁  і x₃ , але інших кількостях. При цьому необхідно буде випускати

x₁=10+1,67b₁,

x₂=6-0,67b₁.

При цьому цільова функція буде

F=1320+20b_1.

Аналогічно отримані залежності для фінансів будуть мати вигляд:

x₁=10-0.17b₃

x₃=6+0.17b₃

F=1320+10b₃

Пояснимо ці залежності на наступному прикладі. Нехай збільшення фінансів складають

b₃=10

При цьому отримаєм

x₁=10-0.17*10=8,3,

x₃=6+0.17*10=7,7.

В данному випадку цільова функція буде

F=1320+10*10=1420.

Було важко представити, що при збільшення фінансів для забезпечення максимізації прибутку випуск продукції  x₁ доцільно зменьшити, а випуск продукції x₃  - збільшити. Таке рішення пояснюється наступним. Як видно з умов задачі  (мал.1 з лаб.№2), прибуток з одиниці продукції с₃=120, тобто одиниця продукції Прод3 в 120/60=2 рази дає більше прибутку порівняно з одиницею продукції виду Прод1. У зв’язку з тим виявилось доцільним такий перерозподіл випуску продукції.

Ми припускаємо, що наведених прикладів достатньо, щоб показати, на які важливі питання можна отримати відповіді з допомогою математичної моделі. Слід підкреслити, що всі ці відповіді можуть бути отримані без додатковорго рішення задачі, а тількі використовуючи симплекс-таблицю основної задачі (мал.3 з лаб.№2).

4. Варіантний аналіз

Для задачі розподілу ресурсів найбільший інтерес представляє рішення двох задач варіантного аналізу:

• Параметричного аналізу, в продовж якого вирішуються задачі при різноманітних значеннях одного з параметрів;

• Пошук рішень по декільком цільовим функціям.

При рішенні задач розподілу ресурсів по декільком ціловим функціям можлива одна з двох постановок задачі: при заданих ресурсах максимізувати отриманний результат; або при заданому результаті мінімізувати використовувані ресурси.

Якщо позначити Q – ресурси, R – результат їх застосуваня, то при заданих залежностях результата R=f₁(x_j) і потрібних ресурсів Q=f₂(x_j) від кількості випускаємої продукції ці постановки можуть бути записані так:

Перша постановка

F₁=Rmax

R=f₁(x_j)

Q=f₂(x_j)

QQ_зад  (19)

d_jx_jD_j

j=

Друга постановка

F₂=Qmin

R=f₁(x_j)

Q=f₂(x_j)

RR_зад (20)

d_jx_jD_j

j=

Рішення задачі розподілу ресурсів в цих двох постановках розглянемо на прикладі задачі, приведенної на мал.10.

Мал.10

Цей приклад відрізняється від розглянутого раніше (мал.6) введенням граничних умов на змінні і зміною деяких норм витрат. На відміну від попередньої задачі тут присвоїні імена Вид1, Вид2, Вид3, Вид4 типам випускаємої продукції. У вирішуванній задачі обмеження і граничні умови мають вигляд:

x₁+2x₂+3x₃+4x₄40

6x₁+5x₂+4x₃+3x₄110

4x₁+6x₂+8x₃+12x₄100 (21)

1 x₁12; x₃2;

x₂0; x₄=3

будемо вирішувати цю задачу в двох приведенних вище постановках.

В першій постановці – максимізація результата – цільова функція буде мати вигляд:

F₁= 60x₁+70x₂+120x₃+130x₄max (22)  

Для рішення задачі у другій постановці – мінімізація використовуваних ресурсів – введемо в (21) додаткові змінні y₁, y₂, y₃.

x₁+2x₂+3x₃+4x₄+ y₁=40

6x₁+5x₂+4x₃+3x₄ +y₂=110

4x₁+6x₂+8x₃+12x₄ +y₃=100 (23)

Змінні y₁, y₂, y₃ показують величину невикористаного ресурсу. Значить, якщо ми хочемо мінімізувати використовуваний ресурс, тоді потрібно максимізувати невикористаний ресурс, тоді у другій постановці цільова функція буде

F₂= y₁+y₂+y₃max.  (24)

В цій постановці, як і при будь-якій мінімізації, повинен бути задан мінімально припустимий результат. В якості такого заданого результата приймаємо нижні значення граничних умов для змінних, приведені на мал.10 і в (21).

Аналіз оптимального рішення за допомогою надбудови  Прийняття рішення

Аналіз оптимального рішення виконується на основі застосування тих положень симплекс-методу, які були достатньо розглянуті вище і починається після успішного рішення задачі, коли на екрані появляється діалогове вікно Результат знайдено. З допомогою цього діалового вікна можна викликати звіти трьох типів:

• результати;

• стійкість;

• межі.

Звіти кожного типу можуть бути викликані по наступному алгоритму.

Алгоритм 1. Виклик звітів аналізу

На екрані: діалогове вікно Результат пошуку рішення.

1. Курсор на тип звіту, який потрібно викликати. Почнемо зі Звіту по результатам.

2. ОК.

На екрані: викликаний звіт на новому листі, на ярличку якого вказана назва звіту.

1. Курсор на ярличок з назвою звіту.

2. М1.

Звіт по результатам

Звіт складається з трьох таблиць:

Таблиця 1 приводить відомості про цільову функцію.

В стовпчику Початково приведені значення цільової функції до початку обчислень.

Таблиця 2 приводить значення шуканих змінних, що отримані в результаті рішення задачі.

Таблиця 3 показує результати оптимального рішення для обмежень і для граничних умов.

Для Обмежень в графі Формула приведені залежності, які були введені в діалогове вікно Пошук рішення; в графі Значення приведені велечини використаного ресурсу; в графі Різниця показана кількість невикористаного ресурсу. Якщо ресурс використовується повністю, то в графі Стан вказується зв’язане; при неповному використанні ресурсу в цій графі вказується не зв’язан.

Мал.11.

Для Граничних умов приводяться аналогічні величини з тією ж різницею, що замість величини невикористаного ресурсу показана різниця між значенням змінної в знайденному оптимальному рішенні і заданою для неї граничною умовою.

Звіт по стійкості

Звіт по стійкості (мал.12) складається з двох таблиць.

Мал.12.

В таблиці 1 приводяться наступні значення для змінних:

• Результат рішення задачі;

• Редуц.вартість, тобто додаткові двійкові змінні v_j, які показують, наскількі змінюється функція мети при примусовому включенні одиниці цієї продукції в оптимальне рішення;

• Коефіціент цільової функції;

• Граничні значення прирощування коефіціентів с_j функції мети, при яких зберігається набір змінних, що входять в оптимальне рішення.

В таблиці 2 приводяться значення для обмежень:

• Величина використаних ресурсів;

• Тіньова ціна, тобто двійкові оцінки z_i , які показують, як змінюється функція мети при зміні ресурсів на одиницю;

• Значення прирощування ресурсів b_i, при яких зберігається оптимальний набір змінних, що входять в оптимальне рішення.

Задачі аналізу, які можна вирішувати з допомогою приведених величин с_j і b_i, були докладно розглянуті вище.

Звіт по межам

Цей звіт приведен на мал.13. в ньому показано, в яких межах може змінюватись випуск продукції, що увійшла в оптимальне рішення, при збереженні структури оптимального рішення.

• Приводяться значення x_j в оптимальному рішенні;
• Приводяться нижні меже зміни значення x_j.

Мал.13.

Крім того, в звіті вказані значення цільової функції при випуску даного типу продукції на нижній межі. Так, при значенні 720 видно, що F=c₁x₁+c₃x₃=60*0+120*6=720. Далі приводяться межі зміни x_j і значення функції мети при випуску продукції, яка увійшла в оптимальне рішення на верхніх межах.

Тому всюди F=60*10+120*6=1320.

На цьому ми закінчуємо опис  звітів аналізу оптимального рішення.

Параметричний аналіз

Під параметричним аналізом будемо розуміти рішення задачі оптимізації при різних значеннях того параметра, який обмежує поліпшення функції мети.

Параметричний аналіз будемо виконувати для задачі, яка приведена на мал.14, вирішуючи її при різних значеннях наявних фінансів.

Алгоритм 2. Виконання параметричних розрахунків

1. Підготовчі роботи.

1.1. Скласти таблицю варіантів (мал.14).

Мал.14.

1.2. Викликати на екран таблицю з результатом рішення задачі.

1.3. Вилучити результат рішення, що знаходиться в В3:Е3:

• Виділити В3:Е3.
• <Delete>.
• Забрати виділення.

2. Рішення задачі для першого варіанту.

2.1. Ввести в комірку H11=50.

2.2. Сервіс, Пошук рішення…

2.3. Виконати.

На екрані: діалогове вікно Результати пошуку рішення .

2.4. Зберігти сценарій…

2.5. Ввести ім’я сценарію фінанси=50.

2.6. ОК.

На екрані: діалогове вікно Результати пошуку рішення .

2.7.  ОК.

На екрані: результат рішення задачі для даного варіанта фінанси=50 (мал.16).

Мал.16.

3. Рішення задачі для наступних варіантів.

3.1. Ввести в H11 значення фінансів з мал.14 для наступного варіанту.

3.2. Виконати п.2.2 – п.2.7, при цьому в п.2.5 вводити ім’я сценарію, відповідне значення фінансів.

4. Представлення результатів рішення.

4.1. Сервіс, Сценарії…

4.2. Звіт…

4.3. Структура.

4.4. ОК.

На екрані: звіт Підсумковий сценарій (мал.19).

Мал.19.

На цьому малюнку приведені результати рішеня задачі для всіх значень фінансів, прийнятих в таблиці варіантів (мал.14).

Для зручнсті подальшої праці виконаємо редакування Підсумкового сценарію.

Алгоритм 3. Редакування Підсумкового сценарію.

1. Для розміщення на екрані всього звіту Підсумковий сценарій у вікні масштаба призначити 50%.
2. Вилучити стовпці B і D.
3. Вилучити стрічки 5 і 10.
4. Ввести:

• Прод1:Прод4 в комірки С5:С8.
• Прибуток в С9.
• Види ресурсів: трудові, сировина, фінанси в комірках С10:с12.

1. Збільшити ширину стовпця С.
2. Для наглядного представлення даних на діаграмах:

• В дрібних значеннях Прод1:Прод4 призначити два знака після коми.
• Дрібні значення в стрічках Прибуток, трудові, сировина і фінанси округлити до цілих чисел.

1. Забрати примітку.

Після того звіт Підсумковий сценарій буде виглядати так, як показано на мал.20.

Мал.20.

Для наглядного представлення результатів параметричного аналізу на основі відредакування таблиці (мал.20) побудуємо графіки.

Алгоритм 4. Побудова гістограми для шукаих змінних.

1. Виділити С3:H3.

2. Побудувати гістограму.

3. Виконати форматування гістограми.

На екрані: мал.11, на основі якого можна зробити наступні виводи:

• При різноманітному фінансуванні в план входить продукція різноманітних видів, проте ні в один варіант не входить випуск продукції Прод2. Це пояснюється тим, що при високому споживанні ресурсів прибуток від її виробництва нижче, ніж від виробництва інших видів продукції.

Для значень фінансів 50, 150, 200 величина випускаємої продукції являється дрібною. Таке положення припустиме при плануванні, наприклад, випуску тканини, добування нафти і т.д. при випуску поштучної продукції очевидно, що в плані повинні бути цілі числа. Для отримання такого плану слід вирішити задачу цілочисельного програмування, яка розглянута в лаб.№9.

Алгоритм 5. Побудова змішанної діаграми для цільової функції і сировини.

1. Виділити C3:H3, C9:H9, C11:H11.

2. Побудувати змішану діаграму.

3. Виконати форматування діаграми по алгоритму.

На екрані: діаграма (мал.12), на основі якої можна зробити наступні висновки:

• Збільшення фінансування дає збільшення прибутку, що цілком природньо.

• При збільшенні фінансування, починаючи з 150, виникає зменьшення споживаної сировини. Такий результат є несподіваним, але це не помилка. Це наслідок того, що випуск Прол3, Прод4, що забеспечують збільшення прибутку, вимагає при цьому меньшого споживання сировини.

1.2. Порядок виконання роботи.

• Отримати результати розв’язання задачі оптимального розподілу ресурсів; сформулювати та знайти розв’язок двоїстої до заданої задачі;

• Отримати звіт за результатами розв’язання задачі;

• Проаналізувати чутливість до зміни значень коефіцієнтів функції мети, значень правих частин обмежень;

• Сформувати звіт по стійкості отриманого роз’язку;

• Сформувати звіт за межами випуску продукції при збереженні структури оптимального розв’язку;

• Визначити припустимі межі зміни вищеперерахованих величин;

• Здійснити параметричний аналіз отриманих результатів;

• Побудувати ґістоґраму за результатами аналізу;

• Оформити звіт про роботу.

З повагою ІЦ "KURSOVIKS"!