Рішення задачі лінійного програмування графічним методом

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

Міністерство освіти Російської Федерації
МІНІСТЕРСТВО ОСВІТИ УНІВЕРСИТЕТ
СИСТЕМ УПРАВЛІННЯ ТА РАДІОЕЛЕКТРОНІКИ (ТУСУР)
Пояснювальна записка до курсового проекту з дисципліни

«СПЕЦКУРС-3. ДОСЛІДЖЕННЯ ОПЕРАЦІЙ »

Варіант № 3

28 березня 2008 р .

ТОМСЬК 2008

Зміст.
ВСТУП
3
1. ПОСТАНОВКА ЗАВДАННЯ
6
1.1 Математичне програмування
6
1.2 Коротко про лінійному програмуванні
6
1.3 Основне завдання лінійного програмування
8
2. ГРАФІЧНИЙ МЕТОД РОЗВ'ЯЗУВАННЯ ЗАДАЧІ лінійного програмування
10
2.1 Теоретичне введення
10

2.2 Методика розв'язування задач ЛП графічним методом

12

3.Застосування ГРАФІЧНОГО МЕТОДУ РОЗВ'ЯЗАННЯ ЗАДАЧІ лінійного програмування НА ПРАКТИЦІ

13

3.1 Економічна постановка задачі лінійного програмування

13

3.2 Побудова математичної моделі

14
3.3 Знаходження оптимального рішення задачі за допомогою лінійного методу.
16
4. АНАЛІЗ ЧУТЛИВОСТІ ОПТИМАЛЬНОГО розв'язання задач лінійного програмування
18
4.1 Теоретичне введення
18
4.2 Методика графічного аналізу чутливості оптимального рішення
19

4.2.1 Перша задача аналізу на чутливість (аналіз на чутливість до правої частини обмежень)

19

4.2.2 Друга задача аналізу на чутливість (збільшення запасу якого із ресурсів найбільш вигідно)

25

4.2.3 Третя задача аналізу на чутливість (у яких межах допустимо зміна коефіцієнтів цільової функції)

26
ВИСНОВОК
30
Список літератури
32

ВСТУП
Дослідження операцій - це математична дисципліна, що займається розробкою та застосуванням методів знаходження найкращих рішень в різних областях людської діяльності.
Термін "Дослідження операцій" ("Operation Research") запозичений із західної літератури. Зараз, мабуть, не можна точно назвати, ні дату його виникнення, ні автора, та й навряд чи знайдеться вичерпне визначення цього поняття.
Під операціями звичайно розуміють цілеспрямовані керовані процеси. Природа їх може бути різною - це можуть бути військові дії, виробничі процеси, комерційні заходи, адміністративні рішення, і т.д. Що цікаво - операції ці (абсолютно несхожі за своєю природою) можуть бути описані одними і тими ж математичними моделями, більше того, аналіз цих моделей дозволяє краще зрозуміти суть того чи іншого явища і навіть передбачити його подальший розвиток. Світ, як виявилося, влаштований надзвичайно компактно (в інформаційному сенсі), оскільки одна і та ж інформаційна схема реалізується в самих різних фізичних (і не тільки фізичних) проявах. У кібернетиці це називається терміном "ізоморфізм моделей".
Якщо б не ізоморфізм моделей, для кожної конкретної ситуації довелося б відшукувати власний, унікальний метод рішення, і дослідження операцій як науковий напрямок не сформувалося б. На щастя, справа йде інакше. Завдяки наявності загальних закономірностей у розвитку самих різних систем можливе дослідження їх математичними методами. Дослідження операцій як математичний інструментарій, що підтримує процес прийняття рішень в самих різних областях людської діяльності, як сукупність засобів, що дозволяють забезпечити особа, яка приймає рішення, необхідної кількісної інформацією, отриманої науковими методами, сформувалося на стику математики і різноманітних соціально-економічних дисциплін. Свій внесок у його становлення внесли представники самих різних галузей науки.
Історія виникнення дослідження операцій сягає корінням у далеке минуле. Так, ще в 1885 році Фредерік Тейлор прийшов до висновку про можливість застосування наукового аналізу в сфері виробництва. Проблема, розглянута їм, на перший погляд, здається тривіальної: "як оптимальним чином організувати роботу землекопів?" Здавалося б, відповідь давно відомий - "Бери більше, кидай далі, відпочивай, поки летить". Однак застосування математичного апарату показало неспроможність цього принципу. Виявилося, що оптимальна вага вантажу, що дозволяє максимізувати кількості перекидати матеріалу (при розумній економії робочої сили) значно менше того, що може підняти людина при максимальному навантаженні.
Піонером у галузі перекладу складних військово-стратегічних завдань на мову математики став Фредерік Ланчестер. Одним з найбільш значних результатів, отриманих вченим, стало відкриття в 1916 р . так званого квадратичного закону, кількісно зв'язує досягнення перемоги з двома основними факторами: чисельною перевагою живої сили і ефективністю зброї. Було показано, що при одночасному вступі до бій чисельну перевагу в живій силі більш важливо, ніж застосування більш досконалого озброєння, оскільки головну роль грає зосередження власних військ та розчленування сил противника. Класичним прикладом використання квадратичного закону Ланчестер є тактика Нельсона в битві при Трафальгарі.
У 1917 році датський математик А. К. Ерланг, який працював у телефонній компанії, поставив завдання мінімізації втрат часу на встановлення телефонного зв'язку. Отримані ним результати стали основоположними принципами в теорії телефонного зв'язку. Формули Ерланга (середній час очікування виклику та ін) були прийняті міністерством зв'язку Англії в якості стандартів для розрахунку ефективності телефонних ліній. Ідеї ​​Ерланга майже на півстоліття передбачили сучасні теорії розрахунку телефонних вузлів.
У 1930 р . Г. Левінсон почав застосовувати науковий аналіз до вирішення завдань, що виникають у торгівлі. Методика дослідження операцій була використана для дослідження ефективності реклами, розміщення товарів, впливу кон'юнктури на номенклатуру і кількість проданих товарів.
У роки другої світової війни дослідження операцій широко застосовувалося для планування бойових дій. Так, фахівці з дослідження операцій працювали в командуванні бомбардувальної авіації США, дислокованому в Англії. Ними досліджувалися численні фактори, що впливають на ефективність бомбометання. Були вироблені рекомендації, що призвели до 4-х-кратного підвищення ефективності бомбометання.
На початку війни бойове патрулювання літаків союзників для виявлення кораблів і підводних човнів супротивника носило неорганізований характер. Залучення до командування фахівців з дослідження операцій дозволило встановити такі маршрути патрулювання й такий розклад польотів, при яких імовірність залишити об'єкт непоміченим була зведена до мінімуму. Отримані рекомендації були застосовані для організації патрулювання над Південною частиною Атлантичного океану з метою перехоплення німецьких кораблів з військовими матеріалами. З п'яти ворожих кораблів, що прорвали блокаду, три були перехоплені на шляху з Японії до Німеччини, один був виявлений і знищений у Біскайській затоці і лише одному вдалося зникнути завдяки ретельному маскуванню.
Ми навели лише два приклади використання методів дослідження операцій у військовій практиці. Кількість їх дуже велике. У роки війни всі ці роботи із застосування були абсолютно секретними, надалі багато з них знайшли своє відображення у спеціальній літературі.
Після закінчення другої світової війни групи фахівців з дослідження операцій продовжили свою роботу в збройних силах США і Великобританії. Публікація ряду результатів у відкритій пресі викликала сплеск суспільного інтересу до цього напрямку. Виникає тенденція до застосування методів дослідження операцій у комерційній діяльності, з метою реорганізації виробництва, перекладу промисловості на мирні рейки. На розвиток математичних методів дослідження операцій в економіці асигнуються.
У Великобританії націоналізація деяких видів промисловості створила можливість для проведення досліджень економічних на базі математичних моделей у загальнодержавному масштабі. Дослідження операцій стало застосовуватися при плануванні і проведенні деяких державних, соціальних і економічних заходів. Так, наприклад, дослідження, проведені для міністерства продовольства, дозволили пророчити вплив політики урядових цін на сімейний бюджет.
У США впровадження методів дослідження операцій у практику керування економікою відбувалося трохи повільніше - але і там багато концернів незабаром стали залучати фахівців такого роду для рішення проблем, пов'язаних з регулюванням цін, підвищенням продуктивності праці, прискоренням доставки товарів споживачам та ін Лідерство в області застосування наукових методів управління належало авіаційної промисловості, яка не могла не йти в ногу зі зростаючими вимогами до ВПС. У 50-ті-60-і роки на Заході створюються суспільства та центри дослідження операцій, що випускають власні наукові журнали, ряд американських університетів включає цю дисципліну в свої навчальні плани.
В даний час у рамках дослідження операцій сформовані окремі самостійні напрями - лінійне програмування, опукле програмування, теорія ігор, теорія масового обслуговування, та ін

1. ПОСТАНОВКА ЗАВДАННЯ
Метою нашого курсового проекту є вирішення задачі лінійного програмування графічним методом.
1.1 Математичне програмування.
Математичне програмування ("планування")   - Це розділ математики, що займається розробкою методів відшукання екстремальних значень функції, на аргументи якої накладено обмеження. Методи математичного програмування використовуються в економічних, організаційних, військових та ін системах для рішення так званих розподільчих завдань. Розподільні завдання (РЗ) виникають у разі, коли є в наявності ресурсів не вистачає для виконання кожної з намічених робіт ефективним чином і необхідно найкращим чином розподілити ресурси по роботах у відповідності з обраним критерієм оптимальності.
1.2 Коротко про лінійному програмуванні.
Що ж таке лінійне програмування? Це один з перших і найбільш детально вивчених розділів математичного програмування. Саме лінійне програмування стало тим розділом, з якого почала розвиватися сама дисципліна «математичне програмування». Термін «програмування» в назві дисципліни нічого спільного з терміном «програмування (тобто складання програм) для ЕОМ» не має, оскільки дисципліна «лінійне програмування» виникла ще до того часу, коли ЕОМ стали широко застосовуватися при вирішенні математичних, інженерних , економічних та інших завдань. Термін «лінійне програмування» виник в результаті неточного перекладу англійського «linear programming». Одне зі значень слова «programming» - складання планів, планування. Отже, правильним перекладом «linear programming» було б не «лінійне програмування», а «лінійне планування», що більш точно відображає зміст дисципліни. Однак, термін лінійне програмування, нелінійне програмування і т.д. в нашій літературі стали загальноприйнятими.
Отже, лінійне програмування виникло після Другої світової війни і став швидко розвиватися, привертаючи увагу математиків, економістів та інженерів завдяки можливості широкого практичного застосування, а так само математичної «стрункості».
Можна сказати, що лінійне програмування застосовується для побудови математичних моделей тих процесів, в основу яких може бути покладена гіпотеза лінійного представлення реального світу: економічних завдань, завдань управління та планування, оптимального розміщення устаткування і пр.
Завданнями лінійного програмування називаються завдання, в яких лінійні як цільова функція, так і обмеження у вигляді рівностей та нерівностей. Коротко задачу лінійного програмування можна сформулювати наступним чином: знайти вектор значень змінних, що доставляють екстремум лінійної цільової функції при m обмеженнях у вигляді лінійних рівностей або нерівностей.
Лінійне програмування є найбільш часто використовуваний метод оптимізації. До завдань лінійного програмування можна віднести завдання:
· Раціонального використання сировини та матеріалів; завдання оптимізації розкрою;
· Оптимізації виробничої програми підприємств;
· Оптимального розміщення і концентрації виробництва;
· Складання оптимального плану перевезень, роботи транспорту;
· Управління виробничими запасами;
· І багато інших, що належать сфері оптимального планування.
Так, за оцінками американських експертів, близько 75% від загального числа застосовуваних оптимізаційних методів припадає на лінійне програмування. Близько чверті машинного часу, витраченого в останні роки на проведення наукових досліджень, було відведено рішенням завдань лінійного програмування та їх численних модифікацій.
Перші постановки завдань лінійного програмування були сформульовані відомим радянським математиком Л. В. Канторовичем, якому за ці роботи була присуджена Нобелівська премія з економіки.
В даний час лінійне програмування є одним з найбільш вживаних апаратів математичної теорії оптимального прийняття рішення.
Отже, лінійне програмування - це наука про методи дослідження і відшукання найбільших і найменших значень лінійної функції, на невідомі якої накладено лінійні обмеження. Таким чином, завдання лінійного програмування відносяться до завдань на умовний екстремум функції.

1.3 Основне завдання лінійного програмування
Основне завдання лінійного програмування (ОЗЛП) ставиться таким чином: Є ряд змінних . Потрібно знайти такі їх невід'ємні значення, які задовольняли б системі лінійних рівнянь:

{1.1}


і, крім того, звертали б у мінімум лінійну цільову функцію (ЦФ)

Очевидно, випадок, коли ЦФ потрібно звернути не в мінімум, а в максимум, легко зводиться до попереднього, якщо змінити знак функції і розглянути замість неї функцію

Допустимим рішенням ОЗЛП називають будь-яку сукупність змінних , Що задовольняє рівнянь (1.1).
Оптимальним рішенням називають те з допустимих рішень, при якому ЦФ звертається до мінімум.
На практиці обмеження в задачі лінійного програмування часто задані не рівняннями, а нерівностями. У цьому випадку можна перейти до основної задачі лінійного програмування.
Розглянемо задачу лінійного програмування з обмеженнями-нерівностями, які мають вигляд
{1.2}
і є лінійно-незалежними. Останнє означає, жодне з них не можна представити у вигляді лінійної комбінації інших. Потрібно знайти , Які задовольняють нерівності і звертають в мінімум



Введемо рівняння:
{1.3}

де - Додаткові змінні, які також як і є невід'ємними.
Таким чином, маємо спільну задачу лінійного програмування - знайти невід'ємні , Щоб вони задовольняли системі рівнянь (1.3) і звертали в мінімум .
Коефіцієнти у формулі (1.3) перед дорівнюють нулю.

2. ГРАФІЧНИЙ МЕТОД РОЗВ'ЯЗУВАННЯ ЗАДАЧІ лінійного програмування
2.1. Теоретичне введення
Графічний метод досить простий і наочний для вирішення завдань лінійного програмування з двома змінними. Він заснований на геометричному представленні допустимих рішень і ЦФ завдання.
Кожне з нерівностей завдання лінійного програмування (1.2) визначає на координатній площині деяку полуплоскость (рис.2.1), а система нерівностей в цілому - перетин відповідних площин. Безліч точок перетину даних півплощин називається областю допустимих рішень (ОДР). ОДР завжди являє собою опуклу фігуру, тобто володіє наступною властивістю: якщо дві точки А і В належать цій особі, то і весь відрізок АВ належить їй. ОДР графічно може бути представлена ​​опуклим багатокутником, необмеженої опуклої багатокутної областю, відрізком, променем, однією точкою. У разі несумісності системи обмежень задачі (1.2) ОДР є порожнім безліччю.
Все вищесказане відноситься і до випадку, коли система обмежень (1.2) включає рівності, оскільки будь-яке рівність

можна представити у вигляді системи двох нерівностей (див. рис.2.1)

ЦФ при фіксованому значенні визначає на площині пряму лінію . Змінюючи значення L, ми отримаємо сімейство паралельних прямих, званих лініями рівня.
Це пов'язано з тим, що зміна значення L спричинить зміну лише довжини відрізка, який відсікається лінією рівня на осі (Початкова ордината), а кутовий коефіцієнт прямої залишиться постійним (см.ріс.2.1). Тому для вирішення буде досить побудувати одну з ліній рівня, довільно обравши значення L.
Вектор з координатами з коефіцієнтів ЦФ при і перпендикулярний до кожної з ліній рівня (див. рис.2.1). Напрямок вектора   збігається з напрямком зростання ЦФ, що є важливим моментом для вирішення завдань. Напрямок убування ЦФ протилежно напрямку вектора .
Суть графічного методу полягає в наступному. По напрямку (проти напрямку) вектора в ОДР здійснюється пошук оптимальної точки . Оптимальною вважається точка, через яку проходить лінія рівня , Відповідна найбільшому (найменшому) значенню функції . Оптимальне рішення завжди знаходиться на кордоні ОДР, наприклад, в останній вершині багатокутника ОДР, через яку пройде цільова пряма, або на всій його боці.
При пошуку оптимального рішення задач лінійного програмування можливі наступні ситуації: існує єдине рішення задачі; існує нескінченна безліч рішень (альтернативний оптіум); ЦФ не обмежена; область допустимих рішень - єдина точка; завдання не має рішень.

Малюнок 2.1 Геометрична інтерпретація обмежень і ЦФ завдання.

2.2. Методика розв'язування задач ЛП графічним методом.

I. У обмеженнях задачі (1.2) замінити знаки нерівностей знаками точних рівностей і побудувати відповідні прямі.
II. Знайти і заштрихувати півплощини, дозволені кожним з обмежень-нерівностей завдання (1.2). Для цього потрібно підставити в конкретний нерівність координати будь-якої точки [наприклад, (0, 0)], і перевірити істинність отриманого нерівності.
Якщо    нерівність істинне,
то треба заштрихувати полуплоскость, що містить дану точку;
інакше (нерівність помилкове) треба заштрихувати полуплоскость, не містить цю точку.
Оскільки і повинні бути невід'ємними, то їх допустимі значення завжди будуть знаходитися вище осі і правіше осі , Тобто в I-му квадранті.
Обмеження-рівності дозволяють тільки ті точки, які лежать на відповідній прямій. Тому необхідно виділити на графіку такі прямі.
III. Визначити ОДР як частина площини, що належить одночасно всім дозволеним областям, і виділити її. При відсутності ТДР завдання не має рішень.
IV. Якщо ОДР - не порожня множина, то потрібно побудувати цільову пряму, тобто будь-яку з ліній рівня (Де L - довільне число, наприклад, кратне і , Тобто зручне для проведення розрахунків). Спосіб побудови аналогічний побудові прямих обмежень.
V. Побудувати вектор , Який починається в точці (0; 0) і закінчується в точці . Якщо цільова пряма і вектор побудовані вірно, то вони будуть перпендикулярні.
VI. При пошуку максимуму ЦФ необхідно пересувати цільову пряму в напрямку вектора , При пошуку мінімуму ЦФ - проти напрямку вектора . Остання по ходу руху вершина ОДР буде точкою максимуму чи мінімуму ЦФ. Якщо такої точки (точок) не існує, то можна зробити висновок про необмеженість ЦФ на безлічі планів зверху (при пошуку максимуму) або знизу (при пошуку мінімум).
VII. Визначити координати точки max (min) ЦФ і обчислити значення ЦФ . Для обчислення координат оптимальної точки необхідно вирішити систему рівнянь прямих, на перетині яких знаходиться .

3. П РІМЕНЕНІЕ ГРАФІЧНОГО МЕТОДУ РОЗВ'ЯЗАННЯ ЗАДАЧІ лінійного програмування НА ПРАКТИЦІ.
3.1 Економічна постановка задачі лінійного програмування
Підприємство електронної промисловості випускає дві моделі радіоприймачів, причому кожна модель виробляється на окремі технологічні лінії. Добовий обсяг першої лінії - 60 виробів, другої лінії - 80 виробів. На радіоприймач першої моделі витрачається 15 однотипних елементів електронних схем, на радіоприймач другої моделі - 10 таких же елементів. Максимальний добовий запас використовуваних елементів дорівнює 950 одиниць. Прибутки від реалізації одного радіоприймача першої та другої моделей рівні 40 $ і 20 $ відповідно. Визначте оптимальні добові обсяги виробництва першої та другої моделей на основі графічного рішення задачі.
3.2 Побудова математичної моделі.
Змінні завдання
У задачі потрібно встановити, скільки радіоприймачів першої та другої моделі треба виробляти. Тому шуканими величинами, а значить, і змінними задачі є добові обсяги виробництва кожного типу радіоприймачів:
- Добовий обсяг виробництва радіоприймачів першої моделі, [шт / добу];
- Добовий обсяг виробництва радіоприймачів другої моделі, [шт / добу];
Цільова функція
Мета завдання - домогтися максимального доходу від реалізації продукції. Тобто критерієм ефективності служить параметр добового доходу, який повинен прагнути до максимуму. Щоб розрахувати величину добового доходу від продажу радіоприймачів обох моделей, необхідно знати:
· Їхні обсяги виробництва, тобто і радіоприймачів в добу;
· Прибуток від їх реалізації - згідно з умовою, відповідно 40 і 20 $.
Таким чином, дохід від продажу добового обсягу виробництва радіоприймачів першої моделі дорівнює $ На добу, а від продажу радіоприймачів другої моделі - $ На добу. Тому запишемо ЦФ у вигляді суми доходу від продажу радіоприймачів першої та другої моделі:
[$ / Добу]
Обмеження
Можливі обсяги виробництва радіоприймачів і обмежуються наступними умовами:
· Кількість елементів електронних схем, витрачений на протязі доби на виробництво радіоприймачів обох моделей, не може перевищувати добового запасу цих елементів на складі;
· Добовий обсяг першої технологічної лінії (виробництво радіоприймачів першої моделі) не може перевищувати 60 шт на добу, другий (виробництво радіоприймачів другої моделі) - 80 шт;
· Обсяги виробництва радіоприймачів не можуть бути негативними.
Таким чином, всі обмеження задачі діляться на 3 групи, зумовлені:
1) витратою елементів електронних схем;
2) добовим обсягом технологічних ліній;
3) неотрицательности обсягів виробництва.
Запишемо ці обмеження в математичній формі:
1) Оскільки з умови на радіоприймачі першої та другої моделі необхідно 15 і 20 елементів відповідно, то це обмеження має вигляд:
[Шт / добу]
2) Обмеження по добовому обсягу першої та другої технологічних ліній мають вигляд:
[Шт / добу]
3) неотрицательности обсягів виробництва задається як
.
Таким чином, математична модель цієї задачі має вигляд


3.3 Знаходження оптимального рішення задачі за допомогою лінійного методу.
Математичну модель задачі про радіоприймачах ми знайшли на попередньому кроці:


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

пряма (1) - точки (0; 95) та (63, (3); 0), пряма (2) проходить через точку паралельно осі , Пряма (3) проходить через точку паралельно осі .

Рис.3.1. Графічне рішення задачі про виробництво радіоприймачів.
Визначимо ОДР. Наприклад, підставимо точку (0; 0) в вихідне обмеження (1), отримаємо , Що є істинним нерівністю, тому стрілкою позначимо полуплоскость, що містить точку (0; 0), тобто розташовану правіше і нижче прямої (1). Аналогічно визначимо допустимі півплощині для інших обмежень і вкажемо їх стрілками у відповідних прямих обмежень (див. рис.3.1). Загальною областю, дозволеної усіма обмеженнями, тобто ОДР є багатокутник ABCDE.
Цільову пряму можна побудувати за рівнянням

Точки перетину з осями - (0; 75) і (37,5; 0)
Будуємо вектор з точки (0; 0) в точку (40; 20). Точка D - це остання вершина многокутника допустимих рішень ABCDE, через яку проходить цільова пряма, рухаючись у напрямку вектора . Тому D - це точка максимуму ЦФ. Визначимо координати точки D з системи рівнянь прямих обмежень (1) і (2)

Отримали точку D (60; 5) [шт / добу].
Максимальне значення ЦФ одно [$ / Добу].
Таким чином, найкращим режимом роботи підприємства є щодобове виробництво радіоприймачів першої моделі у кількості 60 штук і радіоприймачів другої моделі в кількості 5 штук. Дохід від продажу складе 2500 $ в добу.

4. АНАЛІЗ чутливості оптимальних рішень ЗАВДАНЬ ЛІНІЙНОГО П РОГРАММІРОВАНІЯ

4.1. Теоретичне введення

Неминуче коливання значень таких економічних параметрів, як ціни на продукцію і сировину, запаси сировини, попит на ринку і т.д. може призвести до неоптимальності або непридатність колишнього режиму роботи. Для обліку подібних ситуацій проводиться аналіз чутливості, тобто аналіз того, як можливі зміни параметрів початкової моделі вплинуть на отримане раніше оптимальне рішення задачі ЛП.
Для вирішення завдань аналізу чутливості обмеження лінійної моделі класифікуються наступним чином. Зв'язуючі обмеження проходять через оптимальну точку. Несвязивающіе обмеження не проходять через оптимальну точку. Аналогічно ресурс, що представляється зв'язує обмеженням, називають дефіцитним, а ресурс, що представляється несвязивающім обмеженням - недефіцитних. Обмеження називають надлишковим в тому випадку, якщо його виключення не впливає на ОДР і, отже, на оптимальне рішення. Виділяють такі три завдання аналізу на чутливість.
1. Аналіз скорочення або збільшення ресурсів:
· На скільки можна збільшити (обмеження типу ) Запас дефіцитного ресурсу для поліпшення оптимального значення ЦФ?
· На скільки можна зменшити (обмеження типу ) Запас недефіцитних ресурсу при збереженні оптимального значення ЦФ?
2. Збільшення (обмеження типу ) Запасу якого із ресурсів найбільш вигідно?
3. Аналіз зміни коефіцієнтів ЦФ: який діапазон зміни коефіцієнтів ЦФ, при якому не змінюється оптимальне рішення?

4.2. Методика графічного аналізу чутливості оптимального рішення.

4.2.1. Перша задача аналізу на чутливість (аналіз на чутливість до правої частини обмежень)

Проаналізуємо чутливість оптимального рішення задачі про виробництво радіоприймачів. ОДР завдання (рис.3.1) - багатокутник ABCDE. У оптимальної точці D перетинаються прямі (1) і (2). Тому обмеження (1) і (2) є зв'язуючими, а відповідні їм ресурси (добовий обсяг елементів електронних схем і продуктивність першої технологічної лінії) - дефіцитними.
Розглянемо економічний зміст цих понять. Точка максимуму ЦФ D відповідає добовому виробництва 60 шт радіоприймачів першої моделі та 5 шт радіоприймачів другої моделі. У виробництві радіоприймачів використовуються однотипні елементи електронних схем. Добовий запас на складі цих елементів - це права частина зв'язує обмеження (1) (950 шт / добу). Згідно з цим обмеження, на виробництво в точці D витрачається
[Шт елементів / добу] (1).
Аналогічно бачимо, що продуктивність першої технологічної лінії - це права частина зв'язує обмеження (2) (60 шт / добу). Згідно з цим обмеження в точці D дана лінія виробляє 60 радіоприймачів першої моделі на добу.
Таким чином, поняття "зв'язують обмеження" (1) і (2) означає, що при виробництві радіоприймачів в точці D (60; 5) запаси елементів електронних схем витрачаються повністю, а так само продуктивність першої технологічної лінії використовується в повному обсязі. З цієї причини неможливо подальше нарощування виробництва. У цьому полягає економічний зміст поняття дефіцитності ресурсів, тобто якщо підприємство зможе збільшити добові запаси елементів електронних схем або продуктивність першої технологічної лінії, то це дозволить збільшити випуск радіоприймачів. У зв'язку з цим виникає питання: до якого рівня доцільно збільшити дані ресурси, і на скільки при цьому збільшиться оптимальне виробництво радіоприймачів?
Правило № 1
Щоб графічно визначити максимальне збільшення запасу дефіцитного ресурсу, що викликає поліпшення оптимального рішення,
необхідно пересувати відповідну пряму в напрямку поліпшення ЦФ до тих пір, поки це обмеження не стане надмірною.
При проходженні прямий (1) через точку К (рис.4.1) багатокутник ABKE стає ОДР, а обмеження (1) - надлишковим. Дійсно, якщо видалити пряму (1), що проходить через точку К, то ОДР ABKE не зміниться. Точка До стає оптимальною, в цій точці обмеження (2) та (3) стають зв'язуючими.

Рис.4.1. Аналіз збільшення добового запасу елементів електронних схем
Правило № 2
Щоб чисельно визначити максимальну величину запасу дефіцитного ресурсу, що викликає поліпшення оптимального рішення,
необхідно:
1) визначити координати точки , В якій відповідне обмеження стає надмірною;
2) підставити координати в ліву частину відповідного обмеження.
Координати точки К (60; 80) знаходяться шляхом рішення системи рівнянь прямих (2) і (3). Тобто в цій точці підприємство буде виробляти 60 шт радіоприймачів першої моделі і 80 шт радіоприймачів другої моделі. Підставимо і в ліву частину обмеження (1) і отримаємо максимально допустимий запас елементів електронних схем
[Шт ел / добу].
Подальше збільшення запасу елементів електронних схем недоцільно, тому що це не змінить ОДР і не призведе до іншого оптимального рішення (див. рис.4.1). Дохід від продажу радіоприймачів в обсязі, відповідному точці К, можна розрахувати, підставивши її координати у вираз ЦФ
[$ / Добу].
Розглянемо питання про доцільність збільшення продуктивності першої технологічної лінії. Згідно з правилом № 1, відповідне обмеження (2) стає надлишковим в точці J, в якій перетинаються пряма (1) і вісь змінної (Рис.4.2). Багатокутник ABCJ стає ОДР, а точка J (63,33; 0) (або (63; 0)-цілочисельне рішення) - оптимальним рішенням.

Рис.4.2. Аналіз збільшення продуктивності першої технологічної лінії
У точці J вигідно робити тільки радіоприймачі першої моделі (63 шт в добу). Дохід від продажу при цьому складе
[$ / Добу]
Щоб забезпечити такий режим роботи, згідно з правилом № 2, продуктивність першої технологічної лінії треба збільшити до величини
  [Шт / добу].
Обмеження (3) є несвязивающім, тому що не проходить через оптимальну точку D (див. рис.4.3). Відповідний йому ресурс (продуктивність другої технологічної лінії) є недефіцитних. З економічної точки зору це означає, що в даний момент рівень продуктивності другої технологічної лінії безпосередньо не визначає обсяги виробництва. Тому деяке його коливання може ніяк не вплинути на оптимальний режим виробництва в точці D.
Наприклад, збільшення (зменшення) добового обсягу другої технологічної лінії буде відповідати переміщенню прямий обмеження (3) вгору (вниз). Переміщення прямий (3) вгору ніяк не може змінити точку D максимуму ЦФ. Переміщення ж прямий (3) вниз не впливає на існуючий оптимальне рішення тільки до перетину з точкою D (див. нижче правило № 3). З рис.4.3 видно, що подальше переміщення (3) призведе до того, що точка D буде за межами нової ОДР, виділеної більш темним кольором. Крім того, будь-яке оптимальне рішення для цієї нової ОДР буде гірше точки D.

Рис.4.3. Аналіз зменшення продуктивності другої технологічної лінії
Правило № 3
Щоб визначити максимальне зменшення запасу недефіцитних ресурсу, не змінює оптимальне рішення,
необхідно пересувати відповідну пряму до перетину з оптимальною точкою.
Правило № 4
Щоб чисельно визначити мінімальну величину запасу недефіцитних ресурсу, не міняє оптимальне рішення,
необхідно підставити координати оптимальної точки в ліву частину відповідного обмеження.
Щоб з'ясувати, до яких меж зменшення продуктивності другої технологічної лінії не вплине на виробництво в точці D, використовуємо правило № 4 Підставляємо в ліву частину обмеження (3) координати точки D, отримуємо
[Шт / добу].
Робимо висновок: граничний рівень, до якого може зменшитися обсяг другої технологічної лінії, і при якому не зміниться оптимальність отриманого раніше рішення, дорівнює 5 шт радіоприймачів на добу.
Результати вирішення першого завдання аналізу оптимального рішення на чутливість представлені в табл.4.1.
Таблиця 4.1

Тип ресурсу
Max
зміна ресурсу,
, Шт / добу
Max
зміна
доходу,
,
$ / Добу
Цінність
додаткової
одиниці ресурсу
, $ / Шт
(1)
Дефіцитний
1700-950 = +750
4000-2500 = +1500

(2)
Дефіцитний
63-60 = +3
2520-2500 = +20

(3)
Недефіцитних
5-80 =- 75
2500-2500 = 0

4.2.2. Друга задача аналізу на чутливість (збільшення запасу якого із ресурсів найбільш вигідно)

Аналіз табл.4.1 показує, що до покращення оптимального рішення, тобто до збільшення добового доходу призводить збільшення дефіцитних ресурсів. Для визначення вигідності збільшення цих ресурсів використовують поняття цінності додаткової одиниці i-го ресурсу  

де - Максимальне збільшення оптимального значення ЦФ; - Максимально допустимий приріст обсягу i-го ресурсу.
Наприклад, з табл.4.1 випливає, що збільшення добового запасу елементів електронних схем (обмеження (1)) на 1 шт дозволить отримати додатковий дохід, що дорівнює 2 $ / добу, в той час як збільшення продуктивності першої технологічної лінії (обмеження (2)) на 1 шт принесе 6,7 $ / добу. Недефіцитні ресурси мають нульові цінності, оскільки зміна цих ресурсів не призводить до збільшення доходу.
Висновок: додаткові вкладення в першу чергу необхідно направляти на збільшення добового обсягу першої технологічної лінії, а лише потім на збільшення добового запасу елементів електронних схем. Змінювати недефіцитні ресурси немає необхідності.
4.2.3. Третє завдання аналізу на чутливість (у яких межах допустимо зміна коефіцієнтів цільової функції)
Зміна цін на продукцію, тобто зміна коефіцієнтів ЦФ, представляється на графіку обертанням цільової прямий навколо оптимальної точки. Так, при збільшенні коефіцієнта ЦФ або зменшенні цільова пряма обертається за годинниковою стрілкою. При зменшенні або ж збільшенні цільова пряма обертається проти годинникової стрілки (рис.4.4).
За таких поворотах точка D буде залишатися оптимальною до тих пір, поки нахил цільової прямій не вийде за межі, обумовлені нахилами прямих обмежень (1) і (2). Так, наприклад, якщо нахил цільової прямий співпаде з нахилом прямої (1), то оптимальним рішенням будуть точки відрізка СD. При збігу c прямий (2) оптимальним рішенням будуть точки відрізка DE.

Рис.3.4. Аналіз зміни цін
Наявність альтернативних оптимумів свідчить про те, що одне і те ж оптимальне значення може досягатися при різних значеннях змінних. Якщо цільова пряма вийде за межі нахилу (1), то оптимальною точкою стане точка C. Припустимо, що ціна на радіоприймачі другої моделі не змінюється, тобто зафіксуємо значення цільового коефіцієнта . Проаналізуємо графічно результати зміни значення цільового коефіцієнта , Тобто ціни на радіоприймачі першої моделі. Оптимальне рішення в точці D не буде змінюватися при збільшенні до тих пір, поки цільова пряма не співпаде з прямою (2). Аналогічно, оптимальне рішення в точці D не буде змінюватися при зменшенні до тих пір, поки цільова пряма не співпаде з прямою (1).
Збіг в процесі обертання цільової прямий з прямою обмеження означає, що кути їх нахилу щодо горизонтальної осі зрівнялися, а значить, стали рівні тангенси кутів нахилу цих прямих.
Правило № 5
Щоб визначити межі допустимого діапазону зміни коефіцієнта ЦФ, наприклад і ,
необхідно прирівняти тангенс кута нахилу цільової прямий по черзі до тангенсам кутів нахилу прямих зв'язуючих обмежень, наприклад і (Рис.4.5 і 4.6).

Рис.4.5. Визначення

Рис.4.6. Определеніе
Визначимо, наскільки максимально може знизитися ціна на радіоприймачі першої моделі, не змінюючи оптимальну точку D. Для цього застосуємо правило № 5.
Тангенси кута нахилу для прямих L (x) і (1) відповідно рівні:
і
Тоді з рівності знаходимо [$ / Шт]
Тепер спробуємо визначити, наскільки максимально може збільшитися ціна на радіоприймачі першої моделі, щоб не змінилася оптимальна точка D.
На рис 4.6 видно, що значення c 1 можна збільшувати безмежно, тому що пряма L (x) при c 2 = 20 і ніколи не збігається з прямою (2). Отже, точка D при всіх значеннях коефіцієнта буде єдиною оптимальною.
З наведених вище розрахунків та графічної їх ілюстрації випливає, що якщо ціна на радіоприймачі першої моделі стане менше 30 $ / шт, то найбільш вигідним буде виробництво радіоприймачів в точці C (див. рис.4.5). При цьому продуктивність першої технологічної лінії буде використовуватися не в повному обсязі, що призведе до недефицитности даного ресурсу (2), а дефіцитними будуть ресурси (1) і (3).
Проведемо ті ж самі дослідження для радіоприймачів другої моделі. Для цього зафіксуємо значення . Шукаємо :

Тоді з рівності знаходимо [$ / Шт]
На рис 4.6 видно, що значення c 2 можна зменшувати до нуля, тому що пряма L (x) при c 1 = 40 і збігається з прямою (2). Отже, точка D при всіх значеннях коефіцієнта буде оптимальною.
Аналогічно робимо висновок, що якщо ціна на радіоприймачі другої моделі стане вище 26,67 $ / шт, то найбільш вигідним буде виробництво радіоприймачів в точці C.
З економічної точки зору виробництво радіоприймачів в точці С означає, що підприємству стане вигідніше виготовляти радіоприймачі другої моделі, використовуючи на повну потужність продуктивність другої технологічної лінії.

ВИСНОВОК.
У ході роботи над курсовим проектом була розглянута задача лінійного програмування про виробництво радіоприймачів. Для вирішення завдання використовувався графічний метод. Отримано такі результати:
Оптимальна прибуток від реалізації продукції досягається при наступному добовому виробництві радіоприймачів: 60 шт радіоприймачів першої моделі та 5 шт радіоприймачів другої моделі. При цьому прибуток від реалізації складе 2500 $ в добу.
Розглянувши три завдання аналізу отриманого рішення на чутливість до прийнятої моделі, ми можемо відповісти на наступні питання:
1. Визначте межа збільшення продуктивності першої лінії, перевищення якого вже не буде поліпшувати значення цільової функції.
- Межа збільшення продуктивності першої лінії дорівнює 63 радіоприймача на добу. Подальше збільшення продуктивності не має сенсу, тому що значення ЦФ не покращиться.
2. Визначте межу зменшення продуктивності другої лінії, при якому отримане оптимальне рішення залишиться незмінним.
- Граничний рівень, до якого може зменшитися продуктивність другої технологічної лінії, і при якому не зміниться оптимальність отриманого раніше рішення, дорівнює 5 радіоприймачів на добу.
3. Визначте межа збільшення добового запасу елементів електронних схем, при перевищенні якого поліпшити значення цільової функції виявляється неможливим.
- Межа збільшення добового запасу елементів електронних схем дорівнює 1700 шт на добу. Подальше збільшення недоцільно, тому що це не змінить ОДР і не призведе до іншого оптимального рішення.
4. Визначити дефіцитний ресурс, який має найбільший пріоритет при можливості збільшення запасів ресурсів.
- Тому що збільшення продуктивності першої технологічної лінії на 1 шт принесе 6,7 $ / добу (на відміну від 2 $ / добу від збільшення добового запасу елементів електронних схем), то саме даний ресурс (2) має пріоритет.
5. Визначте інтервал зміни прибутку від продажу радіоприймача першої моделі, в якому оптимальне рішення залишається незмінним.
- Інтервал зміни прибутку від продажу радіоприймача першої моделі, в якому оптимальне рішення залишається незмінним, визначається нерівністю $ / Шт.
6. Визначте аналогічний інтервал для приймача другої моделі.
- Інтервал зміни прибутку від продажу радіоприймача другої моделі, в якому оптимальне рішення залишається незмінним, визначається нерівністю $ / Шт.
Рішення даного завдання допомогло більш глибоко і грунтовно вивчити і зміцнити на практиці всі тонкощі і моменти графічного методу розв'язання задач лінійного програмування, а так само розібратися з основами аналізу на чутливість моделі до отриманого оптимального рішення.

Список літератури
1. АстафуровВ.Г., Колоднікова Н. - Комп'ютерне навчальний посібник, розділ "Аналіз на чутливість за допомогою двоїстої задачі", Томськ-2002.
2. Алесінская Т.В. - Завдання з дослідження операцій з рішеннями.
3. Смородинський С.С., Батін Н.В. - Оптимізація рішень на основі методів і моделей математичного програмування: Навчальний посібник.
4. Кононов В.А. - Дослідження операцій. Для просунутих математиків.
Додати в блог або на сайт

Цей текст може містити помилки.

Програмування, комп'ютери, інформатика і кібернетика | Курсова
121.1кб. | скачати


Схожі роботи:
Рішення задачі лінійного програмування симплексним методом
Рішення задачі лінійного програмування симплекс методом
Графічне рішення задачі лінійного програмування в економіці
Симплекс метод рішення задачі лінійного програмування
Рішення задач лінійного програмування симплекс методом
Рішення задачі оптимального резервування системи методом динамічного програмування
Основні поняття математичного програмування Побудова моделі задачі лінійного програмування
Розвязання задач графічним методом методом потенціалів методом множників Лангранжа та симплекс-методом
Розвязок задачі лінійного програмування
© Усі права захищені
написати до нас