Опорний конспект лекцій з курсу Дослідження операцій Тема 4 Лінійне програмування, Аналіз моделей на чутливість, НУДПСУ

Лекція №4. ЛІНІЙНЕ ПРОГРАМУВАННЯ. Аналіз моделей на чутливість

План

1. Процес аналізу моделей на чутливість.

2. Інтерпретація динамічних характеристик моделей.

3. Використання графічних методів.

4. Задача аналізу змін запасів ресурсів.

5. Задача визначення найбільш вигідного ресурсу.

6. Задача визначення меж зміни коефіцієнтів цільовій функції.

2.4. Аналіз моделей на чутливість

Аналіз моделей на чутливість – це процес, що реалізовується після отримання оптимального розв'язку. В рамках такого аналізу виявляється чутливість оптимального розв'язку до певних змін початковій моделі, тобто вплив змін у постановці задачі (запасів ресурсів, величин прибутку від випуску виробів і т.д.) на оптимальний розв'язок. У багатьох випадках аналіз на чутливість дозволяє, не вирішуючи задачі заново, знайти новий оптимальний розв'язок задачі при зміни деяких умов в її постановці.

Методи аналізу на чутливість застосовуються у випадках, коли в постановці задачі змінюється тільки одна з величин (наприклад, запас одного з ресурсів, прибуток від одного з виробів і т.д.). Якщо в постановці задачі змінюється відразу декілька величин, то для отримання нового оптимального розв'язку слід вирішувати задачу заново.

У задачі про асортимент продукції (приклад 2.2) може представляти інтерес питання про те, як вплине на оптимальний розв'язок збільшення чи зменшення попиту на продукцію або запасів початкової сировини. Можливо, також буде потрібно аналіз впливу ринкових цін на оптимальний розв'язок.

При такому аналізі завжди розглядається комплекс лінійних оптимізаційних моделей. Це додає моделі певну динамічність, що дозволяє досліднику проаналізувати вплив можливих змін початкових умов на отриманий раніше оптимальний розв'язок. Динамічні характеристики моделей фактично відображають аналогічні характеристики, що властиві реальним процесам. Відсутність методів, що дозволяють виявляти вплив можливих змін параметрів моделі на оптимальний розв'язок, може привести до того, що отриманий (статичний) розв'язок застаріє ще до своєї реалізації. Для проведення аналізу моделі на чутливість з успіхом можуть бути використані графічні методи.

Розглянемо основні задачі аналізу на чутливість на прикладі 2.9.

Задача 1. Аналіз змін запасів ресурсів

За статусом ресурси діляться на дефіцитні та недефіцитні. Якщо для реалізації оптимального розв'язку ресурс витрачається повністю, то він називається дефіцитним, якщо не повністю – недефіцитним. Статус ресурсів визначається за значеннями залишкових змінних. Збільшення запасів дефіцитних ресурсів дозволяє збільшити цільову функцію (прибуток). Зниження запасів дефіцитних ресурсів призводить до зниження прибутку. Збільшення запасів недефіцитних ресурсів завжди недоцільно, так як воно призводить тільки до збільшення невитрачених залишків. Запас недефіцитного ресурсу можна знизити на величину його залишку; це ніяким чином не впливає на оптимальний розв'язок (в тому числі на оптимальні обсяги виробництва і на прибуток), зменшується тільки невитрачений залишок ресурсу. Якщо запас недефіцитного ресурсу знизиться на величину, що перевищує його залишок, то для визначення нового оптимального плану виробництва необхідно вирішувати задачу заново.

Після знаходження оптимального розв'язку представляється цілком логічним з'ясувати, як відіб'ється на оптимальному розв'язку зміна запасів ресурсів. Для цього необхідно відповісти на два питання:

1. На скільки можна збільшити запас деякого ресурсу для поліпшення набутого оптимального значення цільової функції Z?

2. На скільки можна понизити запас деякого ресурсу при збереженні набутого оптимального значення цільової функції Z?

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

На мал. 2.5 зв'язуючими обмеженнями є обмеження (1) і (3), представлені прямими L₁ і L₃ відповідно, тобто ті, що визначають запаси початкових ресурсів. Обмеження (1) визначає запаси сировини А. Обмеження (3) визначає співвідношення попиту на продукцію, що випускається.

Якщо деяке обмеження є таким, що зв'язує, то відповідний ресурс відносять до розряду дефіцитних ресурсів, оскільки він використовується повністю. Ресурс, з яким асоційовано незв'язуюче обмеження, слід віднести до розряду недефіцитних ресурсів (тобто наявних в деякому надлишку). У нашому прикладі незв'язуючими обмеженнями є (2) і (4). Отже, ресурс – сировина В – недефіцитний, тобто є в надлишку, а попит на продукцію П₂ не буде задоволений повністю (у таблиці – ресурси 2 і 4).

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

У нашому прикладі сировина А і співвідношення попиту на продукцію П₁ і П₂, що випускається, є дефіцитними ресурсами (у таблиці – ресурси 1, 3).

Розглянемо спочатку ресурс – сировина А. На мал. 2.6 при збільшенні запасу цього ресурсу пряма L₁ переміщається вгору паралельно самій собі до точки К, в якій перетинаються лінії обмежень L₂, L₃ і L₄. У точці К обмеження (2), (3) і (4) стають такими, що зв'язують; оптимальному розв'язку при цьому відповідає точка К, а простором (допустимих) розв'язків стає багатокутник AKD0. У точці К обмеження (1) (для ресурсу А) стає надмірним, оскільки будь-яке подальше зростання запасу відповідного ресурсу не впливає ні на простір розв'язків, ні на оптимальний розв'язок.

Таким чином, об'єм ресурсу А не слід збільшувати понад ту межу, коли відповідне йому обмеження (1) стає надмірним, тобто пряма (1) проходить через нову оптимальну точку К. Цей граничний рівень визначається таким чином. Встановлюються координати точки К, в якій перетинаються прямі L₂, L₃ і L₄, тобто знаходиться розв'язок системи рівнянь.

В результаті виходить х₁ = 3 і х₂ = 1. Потім, шляхом підстановки координат точки К в ліву частину обмеження (1), визначається максимально допустимий запас ресурсу А

2x₁ + 3x₂ = 2 3 + 3 2 = 12.

Мал. 2.7 ілюструє ситуації, коли розглядається питання про зміну співвідношення попиту на продукцію П₁ і П_2.

Новою оптимальною точкою стає точка Е, де перетинаються прямі L₁ і L₂. Координати даної точки знаходяться шляхом розв'язку системи рівнянь (1) і (2) таким чином.

В результаті виходить х₁ = 4,2; х₂ = 0,2, причому добовий попит на продукцію П₁ не повинен перевищувати попит на продукцію П₂ на величину х₁ – х₂ = 4,2 – 0,2= 4 од.

Подальше збільшення розриву в попиті на продукцію П₁ і П₂ не впливатиме на оптимальний розв'язок.

Розглянемо питання про зменшення правої частини незв'язуючих обмежень. Обмеження (4) фіксує граничний рівень попиту на продукцію П₂. З мал. 2.5 витікає, що, не змінюючи оптимального рішення, пряму L₄ (АВ) можна опускати вниз до перетину з оптимальною точкою С. Так як точка С має координати х₁ = 4,2; х₂ = 1,4 зменшення попиту на продукцію П₂ до величини х₂ = 1,4 ніяк не вплине на оптимальність раніше отриманого розв'язку.

Розглянемо обмеження (2) 3x₁ + 2x₂ ≤ 13, яке є обмеженням на недефіцитний ресурс – сировина В. І в цьому випадку праву частину – запаси сировини В – можна зменшувати до тих пір, поки пряма L₂ не досягне точки С. При цьому права частина обмеження (2) стане рівною 3x₁ + 2x₂ = 3 2,4 + 2 1,4 = 10, що дозволяє записати це обмеження у вигляді: 3x₁ + 2x₂ ≤ 10. Цей результат показує, що раніше отриманий оптимальний розв'язок не зміниться, якщо добовий запас ресурсу В зменшити на 3 од.

Результати проведеного аналізу можна звести до наступної таблиці

Задача 2. Визначення найбільш вигідного ресурсу

У задачі 1 аналізу на чутливість досліджено вплив на оптимум збільшення об'єму дефіцитних ресурсів. При обмеженнях, пов'язаних з додатковим залученням ресурсів, природно поставити питання: якому з ресурсів слід віддати перевагу при вкладенні додаткових витрат? Для цього вводиться характеристика цінності кожної додаткової одиниці дефіцитного ресурсу, що виражається через відповідний приріст оптимального значення цільової функції. Таку характеристику для даного прикладу можна отримати безпосередньо з таблиці, в якій приведені результати розв'язку задачі 1 на чутливість. Позначимо цінність додаткової одиниці ресурсу i через y_i. Величина y_i визначається із співвідношення.

Результати розрахунку цінності одиниці кожного з ресурсів представлені в наступній таблиці

Отримані результати свідчать про те, що додаткові вкладення в першу чергу слід направити на збільшення ресурсу А і лише потім – на формування співвідношення попиту на продукцію П₁ і продукцію П₂. Що стосується недефіцитних ресурсів, то, як і слід було чекати, їх об'єм збільшувати не слід.

Задача 3. Визначення меж зміни коефіцієнтів цільової функції

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

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

1. Який повинен бути діапазон зміни того або іншого коефіцієнта цільової функції, при якому не відбуваються зміни оптимального розв'язку?

2. На скільки слід змінити той або інший коефіцієнт цільової функції, щоб зробити деякий недефіцитний ресурс дефіцитним, і, навпаки, дефіцитний ресурс зробити недефіцитним?

Відповімо на поставлені питання на прикладі.

Розглядаючи перше питання, позначимо через c₁ і c₂ доходи підприємства від продажу одиниці продукції П₁ і П₂ відповідно. Тоді цільову функцію можна представити в наступному вигляді:

Z = с₁х₁ + с₂х₂.

На мал. 2.5 видно, що при збільшенні c₁ або зменшенні c₂ пряма, що представляє цільову функцію Z, обертається (навколо точки С) за годинниковою стрілкою. Якщо ж c₁ зменшується або c₂ збільшується, ця пряма обертається в протилежному напрямі – проти годинникової стрілки. Таким чином, точка С залишатиметься оптимальною точкою до тих пір, поки нахил прямої не вийде за межі, визначувані нахилами прямих для обмежень (1) і (3).

Коли ж нахил прямої Z стане рівним нахилу прямої L₁, отримаємо дві альтернативні оптимальні кутові точки – С і В. Аналогічно, якщо нахил прямої Z стане рівним нахилу прямої для обмеження (3), матимемо альтернативні оптимальні кутові точки С і D. Наявність альтернативного оптимуму свідчить про те, що одне і те ж оптимальне значення Z може досягатися при різних значеннях змінних х₁ і х₂. Як тільки нахил прямої вийде за межі вказаного вище інтервалу c₁, отримаємо деякий новий оптимальний розв'язок.

Розглянемо, яким чином можна знайти допустимий інтервал зміни c₁, при якому точка С залишається оптимальною. Початкове значення коефіцієнта c₂ = 4 залишимо незмінним. На мал. 2.5 видно, що значення c₁ можна зменшувати до тих пір, поки пряма Z не співпаде з прямою L₁ (відрізок ВС).

Це крайнє мінімальне значення коефіцієнта c₁ можна визначити з рівності кутів нахилів прямої Z і прямої L₁. Оскільки тангенс кута нахилу для прямої Z дорівнює (c₁/4), а для прямої (1) дорівнює 2/3, то мінімальне значення c₁ визначимо з рівності c₁/4 = 2/3, звідки min c₁ = 8/3. На мал. 2.5 видно, що значення c₁ можна збільшувати безмежно, оскільки пряма Z при c₂ = 4 і c₁®+¥ не співпадає з прямою L₃ (відрізок DC) і, отже, точка С при всіх значеннях коефіцієнта c₁ ³ 8/3 буде єдиною оптимальною.

Інтервал зміни c₁, в якому точка С як і раніше залишається єдиною оптимальною точкою, визначається нерівністю 8/3 < c₁ < +¥. При c₁ = 8/3 оптимальними кутовими точками будуть як точка С, так і точка В. Як тільки коефіцієнт c₁ стає менше 8/3, оптимум зміщується в точку В.

Можна відзначити, що, як тільки коефіцієнт c₁ виявляється менше 8/3, ресурс 3 стає недефіцитним, а ресурс 4 – дефіцитним. Для підприємства це означає наступне; якщо дохід від продажу одиниці продукції П₁ стане менше 8/3 г.о., то найбільш вигідна виробнича програма підприємства повинна передбачати випуск максимально допустимої кількості продукції П₂ (повністю задовольняти попит на продукцію П₂). При цьому співвідношення попиту на продукцію П₁ і П₂ не лімітуватиме об'єми виробництва, що зумовить недефіцитність ресурсу (3). Збільшення коефіцієнта c₁ понад 8/3 г.о. не знімає проблему дефіциту ресурсів (1) і (3). Точка С – точка перетину прямих L₁ і L₃ – залишається весь час оптимальною.

Контрольні запитання

1. В чому полягає процес аналізу моделей на чутливість?

2. Яка інтерпретація динамічних характеристик моделей?

3. Для чого використовуються графічні методи?

4. В чому полягає задача аналізу змін запасів ресурсів?

5. В чому полягає задача визначення найбільш вигідного ресурсу?

6. В чому полягає задача визначення меж зміни коефіцієнтів цільової функції?

З повагою ІЦ “KURSOVIKS”!