2. 2. Аналіз моделей ЗЛП на чутливість: мета і задачі.

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

В рамках аналізу на чутливість розв’язку, отриманого графічним методом, розв’язуються такі три задачі:

1) аналіз на чутливість до зміни правих частин обмежень;

2) аналіз ступеня дефіцитності ресурсів;

3) аналіз розв’язку ЗЛП на чутливість до зміни коефіцієнтів цільової функції.

 

2.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+2x2=6. Звідси випливає, що x1=6, x2=0, причому запас продукту В можна збільшити до значення, рівного 2x1+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=       

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 
25 26 27 28 29  Наверх ↑