WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

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

ГоловнаМатематика, Геометрія, Статистика → Графічний метод розв’язання задачі лінійного програмування. Основи аналізу моделі на чутливість(пошукова робота) - Реферат

Графічний метод розв’язання задачі лінійного програмування. Основи аналізу моделі на чутливість(пошукова робота) - Реферат

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=
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= 4x1+2x2 . У цьому випадку лінії рівня цільової функції будуть паралельними до прямої обмеження (2). Таким чином, оптимальному розв'язку відповідатиме нескінченна множина точок, що належать відрізку ВС.
Резюме:
1. Графічний метод розв'язання ЗЛП є ефективним лише при двох змінних і взагалі можливим - при числі змінних не більше трьох.
2. Аналіз моделі на чутливість - обов'язковий етап розв'язання будь-якої оптимізаційної задачі, необхідний для розробки обгрунтованих рішень в умовах , що постійно змінюються.
3. В ході аналізу моделей ЗЛП на чутливість було показано, що оптимальному розв'язку задачі лінійного програмування завжди відповідає хоча б одна з граничних (кутових) точок області її допустимих розв'язків. У розглянутому прикладі такими точками, в залежності від вихідних даних, були B, K, J, C, D. У випадку, коли коефіцієнти цільової функції є пропорційними коефіцієнтам деякого зв'язуючого обмеження, матимемо нескінченну множину альтернативних оптимумів на відрізку.
Loading...

 
 

Цікаве