ЗМІСТ
Глава 1. Завдання
Мета курсової роботиВихідні дані
Глава 2. Ознайомчий курс дослідження операцій
Введення
Лінійне програмування
Динамічне програмування
Глава 3.Практіческое обгрунтування теорії
Список використаної літератури
ГЛАВА I. ЗАВДАННЯ
Мета курсової роботи
МЕТА - навчитися:
- Самостійно розробляти математичні моделі задач з визначення оптимальних планів виробництва продукції для підприємств і фірм;
- Вирішувати отримані математичні задачі на ЕОМ з використанням пакетів прикладних програм для вирішення завдань лінійного програмування;
- Давати послеоптімізаціонную оцінку і економічну інтерпретацію отриманого розв'язку.
1.2 Вихідні дані
Завдання: ВАТ «Красногорсклексредства» є щомісячним постачальником наступних лікарських зборів аптеці «Ескулап»:
- «Немовля збір № 4»
- «Жовчогінний збір № 3»
- «Елекасол» (протимікробний препарат)
Передбачається, що підприємство має 560 000 тисяч рублів на розвиток виробництва протягом п'яти років. У початковий момент підприємство має в своєму розпорядженні ресурсами:
b1 - квітки ромашки аптечної
b2 - квітки календули
b3 - листя м'яти перцевої
b4-листя евкаліпта
Ціни на використовувані ресурси змінюються протягом п'яти років:
| Види ресурсів протягом п'яти років | 1-ий рік | 2-ий рік | 3-й рік | 4-ий рік | 5-й рік |
| в рублях на одиницю ресурсу | |||||
| b1 | 10 | 9 | 9,4 | 8 | 8,4 |
| b2 | 7 | 10 | 8 | 9 | 9,1 |
| b3 | 8 | 7 | 9 | 8 | 8,1 |
| b4 | 10 | 8 | 8,2 | 8 | 7 |
х2-кількість одиниць другого продукції
х3-кількість одиниць третього продукції. Прибуток від реалізації одиниці продукції кожного виду дорівнює
| Вид продукції | 1-ий рік | 2-ий рік | 3-й рік | 4-ий рік | 5-й рік |
| в рублях на одиницю продукції | |||||
| х1 | 52 | 50 | 55 | 53 | 54 |
| х2 | 41,20 | 42 | 44 | 45 | 43 |
| х3 | 49,09 | 52 | 54 | 49,90 | 50 |
При наступній системі обмежень:
При чому:
Розподіл грошових коштів на п'ять років (в рублях): 80 000, 100 000, 110 000, 120 000, 150 000.
РОЗДІЛ 2. Ознайомлювальний курс ДОСЛІДЖЕННЯ ОПЕРАЦІЙ
Введення
У світі діяльність практично завжди не просто усвідомлена, а цілеспрямована, якась робота відбувається заради досягнення певної мети. Звичайно, практично завжди ресурси, необхідні для виконання даної роботи, обмежені. Досить часто існує кілька можливостей розпорядиться ресурсами, і хотілося б зробити це якомусь сенсі «краще». Дослідження операцій як раз і займається цим колом питанням: мета роботи - обмеженість необхідних ресурсів - пошук варіантів можливих рішень - визначення способу дій. Мета - це бажаний результат діяльності.Лінійне програмування
Економіко-математична модель є математичний опис, закономірності досліджуваного економічного процесу або об'єкта.Завданнями лінійного програмування (ЛП) є такі оптимізаційні задачі, в яких цільова функція і функціональні обмеження - лінійні функції щодо змінних, що приймають будь-які значення з деякої множини значень.
Стандартна задача лінійного програмування записується у вигляді:
У задачі лінійного програмування несуворі функціональні нерівності можна перетворити в строгі рівності, додавши невідомі невід'ємні додаткові змінні. Звичайно, число невідомих і число рівнянь в системі можуть бути різними. Але і в цьому випадку з курсу лінійної алгебри для системи рівнянь відомі варіанти: система може бути несумісною, тобто не мати рішень взагалі; рішення може бути одне, але (!) Це єдине рішення може виявитися неприпустимим з-за наявності негативних компонентів у вирішенні ; рішень може бути нескінченно багато. Взагалі ж для єдиності рішення задачі ЛП не потрібно рівності числа змінних та числа обмежень (несуворих нерівностей). Для задач ЛП розроблені численні ефективні методи вирішення і відповідне математичне забезпечення для різноманітних ситуацій.
Еквівалентність завдань лінійного програмування
1. Завдання максимізації можна звести до задачі мінімізації та навпаки:
2. Будь-яке нерівність можна представити у вигляді рівності шляхом введення додаткової негативної змінної.
3. Зміну, не обмежену умовою невід'ємності можна замінити різницею двох невід'ємних змінних:
4. Будь-яке рівність можна представити як систему двох нерівностей:
Геометрична інтерпретація задач ЛП
Будь-яке нерівність визначає півпростір. Система нерівностей визначає перетин багатьох просторів. У результаті з урахуванням умов невід'ємності змінних область допустимих рішень - ОДР представляє собою багатогранник. Будь-яка точка багатогранника є допустимим рішенням ЗЛП. Лінійна цільова функція досягає екстремуму на опуклому множині (многограннику) тільки на кордоні. Будь-які змінні площині цільової функції, паралельно самій собі, є лише зміна значень цільової функції. Два крайніх положення цієї площини в ОДР є точками екстремуму.
Алгоритм симплекс-методу
Симплекс - найпростіший багатогранник. Метод складається з двох основних етапів:
1. Знаходження допустимого рішення.
2. Знаходження оптимального рішення серед допустимих рішень.
Рішення симплекс-методом супроводжується так званої симплекс-таблиці. На основі аналізу таких таблиць визначається необхідність поліпшення рішення або відсутність рішення або знаходження оптимального рішення.
Насамперед необхідно отримати канонічну завдання. Перетворення загальної і стандартною ЗЛП виробляється на основі властивостей еквівалентності цих завдань. При цьому нерівність перетворюється в рівність шляхом введення додаткової неотрицательной змінної. У результаті система обмежень буде записана у вигляді системи лінійних рівнянь, де кількість невідомих більше, ніж кількість рівнянь.
Складання першого симплекс-таблиці
У канонічній завданню за кількістю обмежень рівностей виділяються базисні змінні. Інші змінні називаються вільними. У системі рівнянь всі члени з вільними змінними переносяться вправо і вирішуються.На підставі отриманих виразів для базисних змінних з цільової функції виключаються всі базисні змінні. Складається симплекс-таблиця за такими правилами:
1. Перший стовпець включає базисні змінні.
2. Складається другий стовпець з вільних членів.
3. Наступні стовпці складаються з коефіцієнтів при вільних змінних з протилежними знаками.
4. Останньою рядком цієї таблиці є рядок цільової функції.
| Базисні перемінні | Вільні члени | Вільні змінні | |||||
| x 1 | x 2 | ... | x j | ... | x n | ||
| X n +1 | b 1 | A 11 | A 12 | ... | A 1j | ... | A 1n |
| X n +2 | b 2 | A 21 | A 22 | ... | A 2j | ... | A 2n |
| ... | ... | ... | ... | ... | ... | ... | ... |
| X n + i | bi | A i1 | Ai2 | ... | A ij | ... | A in |
| ... | ... | ... | ... | ... | ... | .... | ... |
| X n + m | b m | A m1 | A m2 | ... | A mj | ... | A mn |
| z | 0 | -C 1 | -C 2 | .... | -C j | ... | -C n |
Ознака допустимості базисних рішень
- Базисна рішення припустиме, якщо воно невід'ємне;
- Базисна рішення допустиме, якщо у стовпці вільних членів немає жодного негативного елементу (крім рядка цільової функції).
Ознака несумісності обмежень
Обмеження несумісні, якщо в кожному рядку, що має негативний вільний член, немає жодного негативного елементу (Ця ознака використовується, якщо рішення неприпустиме).
Ознака оптимальності
Якщо в рядку цільової функції всі елементи одного знака (крім вільного члена), то цільова функція приймає екстремальне значення, при чому, якщо всі елементи позитивні, то - max, якщо негативні - min.
Ознака необмеженості цільової функції
Цільова функція необмежена, якщо в будь-якому стовпці, не задовольняє ознакою оптимальності, немає жодного позитивного елементу, при чому не обмежена зверху при знаходженні максимуму; і цільова функція не обмежена знизу при знаходженні мінімуму, якщо в будь-якому стовпці, що має позитивний елемент у рядку цільової функції, немає жодного негативного елементу.Ознака існування альтернативного (неєдиного) рішення
Оптимальне рішення має альтернативу, якщо в рядку цільової функції є нульові елементи (крім вільних членів).
Знаходження дозволяють елементів
Дозволяє елемент знаходиться на перетині роздільної рядки і що дозволяє стовпця. Роздільна рядок вказує на базисну змінну, що переходить у вільну. Дозволяє стовпець вказує на вільну змінну, що переходила в базисну.1. Дозволяється стовпець.
a) рішення неприпустиме: у будь-якому рядку, що має негативний вільний член, знаходиться негативний елемент. Цей елемент знаходиться у вирішуючому стовпці.
b) рішення припустиме, неоптимальний: будь-який стовпець, що не задовольняє ознакою оптимальності, є що дозволяє стовпцем.
2. Роздільна рядок.
Знаходяться позитивні відносини вільних членів до елементів дозволяє стовпця. Мінімальне відношення відповідає роздільній рядку.
Правила перетворення симплекс-таблиці
1. У новій таблиці міняються місцями за дозволяючим елементу вільні і базисні змінні:
2.Ячейка дозволяє елемента заповнюється зворотним знаком:
3. Роздільна рядок ділиться на дозволяючий елемент:
4. Елементи дозволяє стовпця діляться на дозволяючий елемент з протилежним знаком:
5. З інших осередків обчислюється твір елементів, що стоїть на відповідному вирішуючому стовпці і відповідної роздільної рядку, поділені на дозволяючий елемент:
Динамічне програмування
Динамічне програмування використовується для дослідження багатоетапних процесів. Стан керованої системи характеризується певним набором параметрів (фазовими координатами). Процес переміщення в фазовому просторі поділяють на ряд послідовних етапів і виробляють послідовну оптимізацію кожного з них, починаючи з останнього. На кожному етапі знаходять умовне оптимальне управління при всіляких припущеннях про результати попереднього кроку. Коли процес доходить до вихідного стану, знову проходять всі етапи, але вже з безлічі умовних оптимальних управлінь обирається одне найкраще. Виходить, що одноразове рішення складної задачі замінюється багаторазовим рішенням простий. Важливо, що значення критерію - сума приватних значень, досягнутих на окремих кроках, і передісторія не мають значення при визначенні майбутніх дій.
Особливості методів і моделей динамічного програмування
1. Прийняття оптимального рішення розглядається як процес багатоетапний.
2. Показник ефективності всього процесу управління є адитивною функцією показників ефективності кожного кроку.
3. Вибір управління на k-тому кроці залежить тільки від стану системи до цього кроку і не впливає на попередні кроки.
4. Стан S k залежить тільки від стану попереднього кроку та управління x k.
5. На кожному кроці управління залежить від кінцевої кількості змінних, а стан системи від кінцевої кількості параметрів.
Принцип оптимальності Беллмана
Властивості динамічного програмування є наслідком загального принципу, сформульованого Р. Беллманом і званого принципом оптимальності: оптимальна політика має тим властивістю, що які б не були початкові стану і початкові рішення, наступні рішення повинні засновувати оптимальну політику щодо стану, отриманого в результаті отриманого рішення.
Знання принципу оптимальності корисно вже хоча б тому, що формує правильну професійну психологію. Але, звичайно, не тільки тому: рішення багатьох задач базується на ньому.
Формули Беллмана для динамічного програмування
РОЗДІЛ 3. ПРАКТИЧНЕ ОБГРУНТУВАННЯ ТЕОРІЇ
Лінійне програмування з використанням пакету прикладних програм Math Cad.
Знаходження оптимального плану виробництва в перший рік здійснюється за допомогою прикладної програми Math Cad.
У другій рік:
У третій рік:
У четвертий рік:
У п'ятий рік оптимальний план виробництва:
Динамічне програмування за допомогою програми Microsoft Excel
| x | Показник ефективності підприємства | |||||||||
| f (x1) | f (x2) | f (x3) | f (x4) | f (x5) | z1 | z2 | z3 | z4 | z5 | |
| 0,0 | 0,0 | 0,0 | 0,0 | 0,0 | 0,0 | 0,0 | 0,0 | 0,0 | 0,0 | 0,0 |
| 80000,0 | 15206,1 | 15671,5 | 16246,9 | 16514,4 | 16653,6 | 15206,1 | 15671,4 | 16246,9 | 16514,4 | 16653,6 |
| 100000,0 | 19815,5 | 20769,5 | 21384,9 | 21590,6 | 21737,7 | 19815,5 | 30877,6 | 31918,4 | 32761,3 | 21737,7 |
| 110000,0 | 22120,2 | 23318,5 | 23953,8 | 24128,6 | 24279,7 | 22120,2 | 35975,6 | 37056,3 | 37899,3 | 33168,1 |
| 120000,0 | 24424,9 | 25867,6 | 26522,8 | 26666,7 | 26821,7 | 24424,9 | 40585,04 | 42154,4 | 43037,3 | 43328,2 |
| 150000,0 | 31389,0 | 33514,6 | 34229,8 | 34280,9 | 34447,8 | 31389,0 | 43134,06 | 44723,4 | 45544,4 | 45870,2 |
СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ
1. В. М. Трояновський. Математичне моделювання в менеджменті, уч. посібник. 2-е вид., Испр. і доп. - М.: Видавництво РДЛ. 2002. - 256 с.
2. Теоретичні лекції під керівництвом Смирнова Ю.М.
3. Методичні посібники.
4. Пакети прикладних програм Math Cad, Microsoft Excel, Microsoft Word.