Графічний метод розв язання задачі лінійного програмування Основи аналізу моделі на чутливість

Пошукова робота на тему: Графічний метод розв’язання задачі лінійного програмування. Основи аналізу моделі на чутливість 1.         Знаходження оптимального розв’язку ЗЛП графічним методом.  Оскільки розглянута в темі 1 модель містить тільки дві змінні, задачу можна розв’язати графічно. У випадку трьох змінних графічний розв’язок стає менш наочним, а при більшому числі змвнних – взагалі неможливим. Незважаючи на це, розгляд графічного методу дасть змогу зробити висновки, що послужать основою для розробки загального методу розв’язання задач ЛП . Перший крок при використанні графічного методу полягає в поданні області допустимих розв’язків, у якій водночас задовольняються всі обмеження моделі. Шукана область (простір) розв’язків задачі прикладу 1.1. показана на рис. 2.1. Умови невід’ємності змінних обмежують область їх допустимих значень першим квадрантом координатної площини (частина площини над віссю x1 і справа від осі x2). Інші межі простору розв’язків зображені прямими лініями, побудованими по рівняннях, що отримані заміною знака “” знаком “=" в обмеженнях. Області, в яких відповідні обмеження виконуються як нерівності ( в нашому випадку – нерівності із знаком “”), указуються стрілками, спрямованими вбік допустимих значень змінних. Отриманий простір розв’язків задачі про фарби – багатокутник АВСDЕF (рис. 2.1). У кожній точці, що належить внутрішній області або межам багатокутника розв’язків АВСDЕF, всі обмеження виконуються, тому розв’язки, що відповідають цим точкам, є допустимими. Серед безкінечногочисла таких точок можна знайтиточку оптимальнного розв’язку, якщо з’ясувати, в якому напрямку зростає цільова функція.   Рис. 2.1. Простір допустимих розв’язків задачі “про фарби”. На рис. 2.2   показано, як здійснюється така операція.  Рис. 2.2. Знаходження оптимального розв’язку ЗЛП графічним методом. На графік наносять лінію рівня цільової функції c1x1+c2x2=z0, де z0 – довільне значення z. Будують вектор N (c1, c2), що є нормальним до ліній рівня цільової функції й визначає напрямок оптимізації z. Лінію рівня зрушують паралельно самій собі вздовж вектора N доти, поки вона не вийде за межі області допустимих розв’язків. Остання точка цієї області й буде точкою оптимуму.  Очевидно, що оптимальному розв’язку відповідає точка С- точка перетину прямих (1) і (2). Значення x1 та x2   в точці С визначаються шляхом розв’язання системи рівнянь: Розв’язком цієї системи є x1=3 ; x2 =1 . Отриманий у цьому випадку прибуток складе: z=3×1+2×2 =33 +21 =12 (тис. г.о.) Зазначимо, що у випадку, коли лінії рівня z мають такий самий нахил, як пряма зв’язуючого обмеження (тобто такого, що проходить через оптимальну точку), матимемо безліч оптимумів на відрізку. 2. Аналіз моделей ЗЛП на чутливість: мета і задачі.  Після одержання оптимального розв’язку задачі ЛП часто виникає потреба виявити чутливість цього розв’язку до певних змін параметрів вихідної моделі. Наприклад, в задачі про фарби може становити інтерес питання про те, як вплине на оптимальний розв’язок збільшення або зменшення попиту, зміна запасів ресурсів, а також ринкових цін на товари. При такому аналізі завжди розглядається деяка сукупність лінійних оптимізаційних моделей, що надає моделі динамічність, властиву реальним процесам. Відсутність методів, що дозволяють виявити вплив можливих змін параметрів моделі на оптимальний розв’язок, може призвести до того, що отриманий (статичний) розв’язок застаріє ще до своєї реалізації. В рамках аналізу на чутливість розв’язку, отриманого графічним методом, розв’язуються такі три задачі: 1) аналіз на чутливість до зміни правих частин обмежень; 2) аналіз ступеня дефіцитності ресурсів; 3) аналіз розв’язку ЗЛП на чутливість до зміни коефіцієнтів цільової функції. 3. Перша задача аналізу на чутливість: аналіз на чутливість  до зміни правих частин обмежень.  Дана задача дозволяє дати відповідь на питання: на скільки доцільно збільшити або скоротити запаси ресурсів? Особливо важливо проаналізувати такі два аспекти. 1. На яку величину можна збільшити запас деякого ресурсу для поліпшення отриманого оптимального значення цільової функції? 2. На яку величину можна зменшити запас деякого ресурсу при збереженні отриманого оптимального значення цільової функції? Оскільки величина запасу кожного з ресурсів фіксується в правих частинах обмежень, цей вид аналізу часто називають аналізом начутливістьдо правих частин(обмежень). Перед тим , як відповісти на поставлені запитання, класифікуємо обмеження лінійної моделі на зв’язуючі (активні) та незв’язуючі (неактивні). Пряма, що відповідає зв’язуючому обмеженню, повинна проходити через оптимальну точку. На рис. 2.1 зв’язуючими є тільки обмеження (1) і (2), тобто ті, що лімітують запаси ресурсів А і В. Якщо деяке обмеження є зв’язуючим, то ресурс, що йому відповідає, слід віднести до розрядудефіцитних ресурсів, оскільки він витрачається повністю. Ресурс, з яким асоційоване   незв’язуюче обмеження, варто віднести до розряду недефіцитних ресурсів (тобто наявних у деякому надлишку). Таким чином, у ході аналізу моделі на чутливість до правих частин обмежень визначаються такі величини: 1) гранично допустиме збільшення запасу дефіцитного ресурсу, що дозволяє поліпшити знайдений раніше оптимальний розв’язок; 2) гранично допустиме зниження запасу недефіцитного ресурсу, що не змінює знайденого раніше значення цільової функції. Інформація, отримана в останньому випадку, особливо корисна в тих ситуаціях, коли надлишки недефіцитного ресурсу можуть бути використані для інших цілей.   Може виникнути питання: чи не варто проаналізувати, як вплине на оптимум збільшення обсягу ресурсів,  які є в надлишку, і скорочення обсягу дефіцитних ресурсів. Відповідь на першу частину запитання є очевидною, тому що в цьому випадку ми спробували б зробити й без того надлишковий ресурс ще більш надлишковим, що ніяк не вплине на отриманий раніше розв’язок. Друга частина питання заслуговує особливої уваги, оскільки при можливих недопоставках дефіцитного ресурсу важливо знати, як це позначиться на результатах розв’язання задачі. Звернемося знову до конкретного прикладу. В задачі «про фарби» продукти А и В (обмеження (1) і (2)) є дефіцитними ресурсами. Розглянемо спочатку ресурс А. На рис. 2.3 видно, що при збільшенні запасу цього ресурсу пряма (1) (або відрізок СD) переміщується вгору паралельно самій собі, поступово «стягуючи» у точку трикутник СD. Сторони CK і DK цього трикутника являють собою продовження прямих, що відповідають обмеженням (2) і (4). У точці К обмеження (2) і (4) стають зв’язуючими; оптимальному розв’язку при цьому відповідає точка К, а простором (допустимих) розв’язків стає багатокутник АВKЕF. У точці К обмеження (1) (для ресурсу А) стає надлишковим, оскільки будь-яке подальше зростання запасу відповідного ресурсу не вплине ні на простір розв’язків, ні на оптимальний розв’язок. Таким чином, обсяг ресурсу А не варто збільшувати зверх тієї межі, що відповідає точці, в якій обмеження (1) стає надлишковим.   Рис. 2.3. Визначення максимально допустимого збільшення запасу ресурсу А.  Цей граничний рівень визначається наступним чином. По-перше, встановлюються координати точки, в якій перетинаються прямі (2) і (4), тобто знаходиться розв’язок системи рівнянь: В результаті одержимо x1=3 і x2=2. Підставляючи координати точки К в ліву частину обмеження (1), визначаємо максимально допустимий запас ресурсу А: x1+2 x2=2=3+2 2=7 т. Рис. 2.4 ілюструє ситуацію, коли розглядається питання про доцільність збільшення запасу дефіцитного ресурсу (2) (вихідного продукту В). Новою оптимальною точкою стає точка J, де перетинаються прямі (6) і (1), тобто x2=0, x1+2×2=6. Звідси випливає, що x1=6, x2=0, причому запас продукту В можна збільшити до значення, рівного 2×1+x2=26+10=12 т. Рис. 2.4. Визначення максимально допустимого збільшення запасу ресурсу В. Розглянемо тепер питання про зменшення правої частини незв’язуючих обмежень. Обмеження (4), x2 2 фіксує граничний рівень попиту на фарбу другого виду. На рис. 2.2. видно, що, не змінюючи оптимального розв’язку, пряму (4) (ЕD) можна опускати донизу до перетину з оптимальною точкою С. Оскільки точка С має координати x1 = і x2=то, зниження попиту на фарбу 2 до величини x2= ніяк не вплине на оптимальність раніше отриманого розв’язку. Розглянемо обмеження (3), -x1+ x2 1, що описує співвідношення між попитом на фарбу 2 і попитом на фарбу 1. У цьому випадку праву частину обмеження можна зменшувати доти, поки пряма (3) (ЕF) не досягне точки С, При цьому права частина обмеження (3) стане рівною -x1+ x2=(- )+( )= -2, що дозволяє записати це обмеження у вигляді: -x1+ x2 -2, або в еквівалентній формі: x1- x2. Цей результат показує, що раніше отриманий оптимальний розв’язок не зміниться, якщо попит на фарбу 1 перевищить попит на фарбу 2 не більше, ніж на 2 т. Результати проведеного аналізу можна звести в таку таблицю. Таблиця 2.1 Ресурс Тип ресурсу Максимальна зміна запасу ресурсу, т Максимальна зміна доходу від реалізації, тис. г.о. 1 Дефіцитний 7-6=+1 13 – =+ 2 Дефіцитний 12-8=+4 18- 3 Недефіцитний -2-1=-3 4 Недефіцитний -2= 4.  Друга задача аналізу на чутливість: оцінка дефіцитності ресурсів. За допомогою методів лінійного програмування вдається відповісти на запитання: збільшення обсягу якого з ресурсів є найбільш вигідним? Для цього вводиться характеристика цінності кожної додаткової одиниці дефіцитного ресурсу, що виражається через відповідне збільшення оптимального значення цільової функції. Таку характеристику для аналізованого прикладу можна одержати безпосередньо з таблиці з результатами розв’язання першої задачі аналізу на чутливість. Позначимо цінність додаткової одиниці ресурсу i через yi . Величину yi  визначимо із співвідношення: де bі – приріст запасу і-го ресурсу,  z i ­­­ ­­­- приріст цільової функції, зумовлений збільшенням і-го ресурсу на величину bі. Скориставшись даними зазначеної таблиці, для обмеження (1) (продукт А), одержимо  тис. г.о./ т продукту А. Аналогічно визначається цінність одиниці будь-якого іншого ресурсу (результати розрахунку представлені в табл. 2.2. Значення величин yi свідчать про те, що додаткові вкладення в першу чергу варто направити на збільшення запасу ресурсу 2 (продукт В) і лише потім – на збільшення ресурсу 1 (продукт А). Щодо недефіцитних ресурсів, то їхній обсяг, як і слід було очікувати, збільшувати недоцільно. Таблиця 2.2. Ресурс Тип ресурсу yi, тис. г.о. /т 1 2 3 4 Дефіцитний Дефіцитний Недефіцитний Недефіцитний   y1 =1/3 y2 =4/3 y3=0 y4=0 2.5. Третя задача аналізу на чутливість: аналіз на чутливість до зміни коефіцієнтів цільової функції. Дозволяє відповісти на запитання: в яких межах є допустимою зміна коефіцієнтів цільової функції? Зміна коефіцієнтів цільової функції впливає на нахил прямої, що описує цю функцію в прийнятій системі координат. Раніше було показано, що ідентифікація конкретної кутової точки в якості оптимуму залежить насамперед від нахилу цієї прямої. Це означає, що варіація коефіцієнтів цільової функції може призвести до зміни сукупності зв’зуючих обмежень і, отже, статусу того чи іншого ресурсу (тобто зробити недефіцитний ресурс дефіцитним і навпаки). Таким чином, у рамках аналізу моделі на чутливість до змін коефіцієнтів цільової функції можуть досліджуватися такі питання: 1. Яким є діапазон зміни (збільшення або зменшення) того або іншого коефіцієнта цільової функції, при якому не відбувається зміни оптимального розв’язку? 2. Наскільки варто змінити той або інший коефіцієнт цільової функції, щоб зробити деякий недефіцитний ресурс дефіцитним і, навпаки, дефіцитний ресурс зробити недефіцитним?  Обговоримо поставлені питання на прикладі задачі «про фарби». Розглядаючи перше питання, позначимо через C1 і С2 прибутки фірми від продажу 1 т відповідно фарби 1 і фарби 2. Тоді цільову функцію можна подати в такому вигляді:  Z=C1x1+C2x2.  На рис. 2.5 видно, що при збільшенні C1 або зменшенні C2 пряма, що описує цільову функцію , обертається (навколо точки С) за годинниковою стрілкою. Якщо ж C1 зменшується або C2 збільшується, ця пряма обертається проти годинникової стрілки. Таким чином, точка С буде залишатися оптимальною точкою доти, поки нахил прямої не вийде за межі, обумовлені нахилами прямі для обмежень (1) і (2).  Рис. 2.5. Визначення граничних значень коефіцієнтів цільової функції.  Як тільки нахил прямої Z стане рівним нахилу прямої обмеження (1), отримаємо альтернативні оптимальні кутові точки С і D. Аналогічно, якщо нахил прямої Z стане рівним нахилу прямої для обмеження (2), матимемо дві альтернативні оптимальні кутові точки В і С. (Наявність альтернативних оптимумів свідчить про те, що одне й те саме оптимальне значення Z може досягатись при різноманітних значеннях змінних. Як тільки нахил прямої 2 вийде за межі зазначеного вище інтервалу C1,одержимо деякий новий оптимальний розв’язок (точка В або точка D). Щоб проілюструвати цю процедуру обчислень, розглянемо, яким чином можна знайти допустимий інтервал зміни C1, при якому точка С залишається оптимальною. Вихідне значення коефіцієнта C2=2 залишимо незмінним. З рис. 2.5 видно, що значення C1можна збільшувати доти, поки пряма Z не співпаде з прямою (2), або зменшувати, поки пряма Z не співпаде з прямою (1). Ці граничні значення коефіцієнту C1можна визначити з рівності нахилів прямої Z і прямої (2) (максимальне значення C1)і рівності нахилів прямої Z і прямої (1) (мінімальне значення). Оскільки тангенс кута нахилу для прямої Z дорівнює C1/2, а для прямих (1) і (2) відповідно 1/2 і 2/1, мінімальне значення C1 визначимо з рівності: C1=1/2, звідки C1 min =1, а максимальне з рівності: C1/2=2/1, звідки C1 max=4. Інтервал зміни C1, у якому точка С як і раніше залишається єдиною оптимальною точкою, визначається нерівністю 1C14. При C1=1 оптимальними кутовими точками будуть В і С. Як тільки коефіцієнт C1 стає меншим від 1, оптимум зміщається в точку D. Аналогічну інтерпретацію можна дати й у тому випадку, коли коефіцієнт C1 4. Можна зауважити, що як тільки C1 виявляється меншим 1, ресурс 2 стає недефіцитним, а ресурс 4 – дефіцитним. Такий самий аналіз можна виконати і для коефіцієнта С2, зафіксувавши при цьому С1 на рівні С1=3 тис. г.о./т. Тепер уявімо, що коефіцієнти цільової функції співпадають з відповідними коефіцієнтами одного із зв’язуючих обмежень або є пропорційними їм. Наприклад, нехай у задачі про фарби сумарний прибуток фірми описується функцією z= 4×1+2×2 . У цьому випадку лінії рівня цільової функції будуть паралельними до прямої обмеження (2). Таким чином, оптимальному розв’язку відповідатиме нескінченна  множина точок, що належать відрізку ВС. Резюме: 1. Графічний метод розв’язання ЗЛП є ефективним лише при двох змінних і взагалі можливим – при числі змінних не більше трьох. 2. Аналіз моделі на чутливість – обов’язковий етап розв’язання будь-якої оптимізаційної задачі, необхідний для розробки обгрунтованих рішень в умовах , що постійно змінюються. 3. В ході аналізу моделей ЗЛП на чутливість було показано, що оптимальному розв’язку задачі лінійного програмування завжди відповідає хоча б одна з граничних (кутових) точок області її допустимих розв’язків. У розглянутому прикладі такими точками, в залежності від вихідних даних, були B, K, J, C, D. У випадку, коли коефіцієнти цільової функції є пропорційними коефіцієнтам деякого зв’язуючого обмеження, матимемо нескінченну множину альтернативних оптимумів на відрізку.