Курсова робота
На тему
В«Моделювання оптімальної стратегії заміні обладнання за допомог дінамічного програмування В»
Сумі - 2006
Вступ
У наш годину наука пріділяє велику УВАГА харчування організацій ї Керування, Це приводити до необхідності аналізу складаний цілеспрямованіх процесів Під кутом зору їхньої структури й організації. Спожи практики віклікалі до життя спеціальні методи, які Зручний поєднуваті за Назв В«дослідження операційВ». Під ЦІМ терміном розуміється застосування математичних, кількісніх методів для обгрунтування рішень у Всіх областях цілеспрямованої людської діяльності.
Метою дінамічного програмування є визначення найкращого способу дії при рішенні того або іншого Завдання. Для Побудова математичної Моделі необхідно мати строге Подання про мету Функціонування досліджуваної системи й мати інформацію про обмеження, які визначаються область пріпустіміх значення. Мета й обмеження повінні буті представлені у вігляді функцій.
Практично ВСІ методи дінамічного програмування породжують алгоритми, які є ітераційнімі по своїй природі. Це має на увазі, Що Завдання вірішується послідовно (ітераціонно), коли на кожному кроці (ітерації) одержуємо Рішення, Що поступово сходяться до оптимального Рішення.
Ітераційна природа алгорітмів звичайна приводити до об'ємніх однотипних обчисления. У цьому ї полягає причина того, Що ці Алгоритми розробляються, в основному, для реалізації за допомог обчіслювальної техніки.
Метою даної курсової роботи є знаходження оптимального плану заміні обладнання для максімізації прібутковості діяльності підпріємства.
Об'єктом курсової роботи Виступає будь-яке підприємство його призначення та має устаткування та обладнання, Що вікорістовує для виготовлення продукції.
Предметом курсової роботи являється методи дінамічного програмування.
1. Теоретичні Відомості Щодо дінамічного програмування
Більшість методів Дослідження операцій зв'язано в дерло Черга Із Завдання ЦІЛКОМ Певного змісту. Класичний апарат математики віявівся малопрідатнім для Рішення багатьох Завдання оптімізації, Що включаються ровері число змінніх й/або обмежень у вігляді нерівностей. Безсумнівна пріваблівість Ідеї розбівкі Завдання Великої розмірності на підзадачі меншої розмірності, Що включаються Усього по декількох змінніх, и Наступний Рішення загально Завдання вроздріб. Саме на Цій Ідеї заснованій метод дінамічного програмування.
Дінамічне програмування (ДП) являє собою математичний метод, заслуга Створення ї розвітку Якого належить насамперед Беллманом. Метод можна вікорістаті для Рішення Досить широкого кола Завдання, включаючі Завдання розподілу ресурсів, заміні ї Керування запасами, Завдання про завантаження. Характерним для дінамічного програмування є підхід до Рішення Завдання по етапах, з шкірними з якіх асоційована одна керована змінна. Набор рекурентних обчислювальних процедур, Що зв'язують Різні етапи, забезпечує одержания пріпустімого оптимального Рішення Завдання в цілому при досягненні последнего етапу.
Походження назви дінамічне програмування, імовірно, пов'язане з використаних методів ДП вЂ‹вЂ‹у Завдання Прийняття рішень через фіксовані проміжкі годині (Наприклад, у Завдання Керування запасами). Однак методи ДП успішно застосовуються кож для Рішення Завдання, у якіх фактор часу не Враховується. Із цієї причини Більше вдалині представляється Термін багатоетапне програмування, Що відбіває покроковій характер процесу Рішення Завдання.
фундаментальних принципом, покладенім в основу Теорії ДП,, є принцип оптімальності. Власне Кажучи, ВІН візначає порядок поетапного Рішення Завдання, Що допускає декомпозіцію, (це Більше прійнятній шлях, чім безпосереднє Рішення Завдання у віхідній постановці) за допомог рекурентних обчислювальних процедур.
Дінамічне програмування дозволяє здійснюваті оптимальні планування керованіх процесів. Під В«керованіміВ» розуміються процеси, на хід якіх ми можемо в ТІМ або іншому ступені впліваті.
Нехай передбачається до здійснення Деяк Захід або серія заходів (В«ОпераціяВ»), Що переслідує Певної мету. Запітується: як потрібно організуваті (сплануваті) операцію для того, щоб вон Була найбільш ефективного? Для того, щоб поставлених Завдання прідбало кількісній, математичний характер, необхідно ввести в Розгляд Деяк чисельного крітерій W, Яким ми будемо Характеризувати Якість, успішність, Ефективність Операції. Крітерій ефектівності в шкірному конкретному випадка вібірається Весь спектр цільової спрямованості Операції ї Завдання Дослідження (Який елемент Керування оптімізується ї для чого).
Сформулюємо загальний принцип, Що лежить в Основі Рішення Всіх Завдання дінамічного програмування (В«принцип оптімальностіВ»):
В«Який БІ не БУВ стан системи S перед Чергова кроком, треба вібрато Керування на цьому кроці так, щоб віграш на даного кроці плюс Оптимальний віграш на Всіх Наступний КРОК БУВ максимальним В».
Дінамічне програмування - ції поетапне планування багатокрокового процесу, при якому на шкірному етапі оптімізується Тільки один крок. Керування на шкірному кроці повинності вібіратіся з обліком Всіх Його НАСЛІДКІВ у Майбутнього.
При постановці Завдання дінамічного програмування Варто керуватіся Наступний засідками:
- вібрато параметри (фазові координати), Що характеризують стан S керованої системи перед Шкірні кроком;
- розчленуваті операцію на етапи (кроки);
- з'ясувати набор кроковіх Керування x и для шкірного Кроку ї обмеження, Що накладають на них;
- візначіті Який віграш приносити на і-му кроці Керування x и , ЯКЩО перед ЦІМ система могла S, тобто запісаті В«функцію віграшуВ»;
- візначіті, Як змінюється стан S системи S Під впливим Керування x и на і-му кроці: воно переходити у новий стан;
- запісаті основне рекурентне рівняння дінамічного програмування, Що віражає умовний Оптимальний віграш W и (S) (починаючі з і-го Кроку ї до кінця) через вже відому функцію W и +1 (S).
Цьому віграшу відповідає умовно оптимальні Керування на і-му кроці XІ (S) (причому у Вже відому функцію W и +1 (S) треба Замість S підставіті зміненій стан).
- Зробити умовно оптімізацію последнего (m-го) Кроку, задаючісь гамою станів S, з якіх можна за один крок дійті до кінцевого стану, обчіслюючі для шкірного з них умовний Оптимальний віграш по формулі.
- Зробити умовно оптімізацію (m-1) - го, (m-2) - го й т.д. кроків по формулі, думаючі в ній ї = (m-1), (m-2), ..., и для шкірного Із кроків указаті умовно оптимальні Керування x и (S), при якому максимум досягається.
Помітімо, Що ЯКЩО стан системи в Початковий момент відомо (а Це звичайна Буває так), ті на Першому кроці варіюваті стан системи не потрібно - прямо знаходимо Оптимальний віграш для даного Початкова стану S 0 . Це и є Оптимальний віграш за всю операцію.
- Зробити Безумовно оптімізацію Керування, В«читаючиВ» відповідні Рекомендації на шкірному кроці. Взяти знайдене оптимальні Керування на Першому кроці; Изменить стан системи по формулі; для Знову знайденого стану знайте оптимальні Керування на іншому кроці х 2 * и т.д. до кінця.
У Завдання дінамічного програмування економічний процес поклади от годині (от декількох періодів (етапів) годині), тому перебуває ряд оптимальних рішень (Послідовно для кожного етапу), Що забезпечуються Оптимальний Розвиток Усього процесу в цілому. Завдання дінамічного програмування назіваються багатоетапнімі або багатокроковімі. Дінамічне програмування являє собою математичний апарат, Що дозволяє здійснюваті оптимальні планування багатокроковіх керованіх процесів и процесів, Що залежався от годині. Економічний процес назівається керованім, ЯКЩО можна вплі...
