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

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

ГоловнаМатематика, Геометрія, Статистика → Дослідження операцій. Задачі та моделі заміни. Динамічне програмування - Реферат

Дослідження операцій. Задачі та моделі заміни. Динамічне програмування - Реферат

система потрапила в стан sі-1 . Оптимальною називається така стратегія и* = (и1*, и2*,..., ип*) (послідовність управ-лінь на кожному кроці процесу), що переводить систему з стану s0 в стан sn за п кроків, і для котрої . Метод динамічного програмування ґрунтується на принципі оптимальності Р. Белмана, що визначає порядок покрокового розв'язування задачі, яка може бути піддана декомпозиції, за допомогою рекурентних обчислювальних процедур. Принцип оптимальності формулюється наступним чином . Оптимальне керування маєнаступну основоположну властивість: яким не були би по-чатковий стан та прийняте початкове рішення, наступні рішення повинні утворювати оптимальне керування відносно стану, що виник в результаті попереднього рішення. Іншими словами, процес оптимальний тоді і лише тоді, коли оптима-льний кожен з процесів , і = 1,2,..., n-1 . Таким чином, динамічне програмування є поетапним плануванням багатокрокового процесу з оптимізацією на один крок , яке враховує на кожному кроці розвиток процесу загалом, тоб-то при прийнятті рішення враховується майбутнє. Безпосередньо це зробити неможливо, і власне принцип оптимальності дає нам можливість це зробити. В кожному процесі є остан-ній, п -й крок, прийняття рішення на якому не залежить від майбутнього. Здійснивши плану-вання цього кроку, до нього можна приєднати (n - 1) -й крок, до яких в свою чергу ( п - 2 ) -й, приходячи таким чином до початкового стану s0 . Процес динамічного програмування розгортається з кінця до початку - від остан-нього стану до початкового. Для того ж, щоб спланувати п -й крок, необхідно знати стан системи на (n -1) -му кроці. Якщо стан системи на (п -1) -му кроці невідомий (а так є завжди), то, виходячи з характери-стик процесу, роблять припущення про можливі стани системи на цьому кроці. Для кожного припущення визначаємо оптимальне керування на останньому, п -му кроці. Таке оптимальне керування називається умовно-оптимальним (за умови певного значення стану на попередньому кроці). Аналогічно діємо на (n - 2) -му кроці, але умовно-оптимальні керування обираємо, враховуючи вже обрані умовно-оптимальні керування на (n -1) -й крок. Для першого кроку (на відміну від інших) припущень про можливий стан системи не робимо - стан s0 відомий, і знаходимо оптимальне керування з врахуванням всіх умовно-оптимальних керувань, знайдених для другого кроку. І, нарешті, проходячи від s0 до s в пря-мому напрямку виконання процесу, отримуємо оптимальне керування для процесу загалом. У динамічному програмуванні існує проблема розмірності (або прокляття розмірності за словами Р.Белмана), суть якої полягає в наступному. В моделях динамічного програмування стани можуть бути описані за допомогою змінних, які утворюють вектор стану. Збільшення кількості змінних викликає зрос-тання числа можливих варіантів розв'язування, асоційованих з кожним з етапів. Це особливо помітно при проведенні обчислень з використанням таблиць. Оскільки при розв'язуванні задач динамічного програмування зазвичай використовуються відповідні комп'ютерні програми, зростання кількості змінних стану не лише збільшує час обчислень, але й може викликати переповнення пам'яті комп'ютера. Якщо ж говорити про складність задачі, то вона належить до класу NP -повних задач, оскіль-ки її складність експоненційно залежить від складності задачі, S = аеn , де n розмірність за-дачі. З іншого боку, кількість варіантів є значно меншою, ніж у випадку повного перебору. 3. Метод функціональних рівнянь. При застосуванні методу функціональних рівнянь знаходження оптимального розв'язку (стратегії) багатокрокового процесу отримується шляхом розв'язування функціональних рів-нянь. Проілюструємо основні ідеї методу функціональних рівнянь на прикладі простого багатое-топного процесу розподілу. Нехай наявна деяка кількість засобів х0 , які необхідно вкласти в розвиток 2-х неоднорідних підприємств. Якщо в перше підприємство вкласти у0 засобів, то для 2-го залишиться (х0 - у0 ) засобів. При цьому будуть отримані відповідні доходи g (yQ ) та h (х0 - у0) . Необхідно розподілити засоби х (тобто обрати величину у) таким чином, щоб максимізувати загальний дохід від вкладення х одиниць засобів, тобто , . (4) Нехай g та h неперервні для всіх скінчених . Тоді максимальне значення Q існує зав-жди та визначає максимальне значення доходу в одноетапному процесі. Розглянемо двохетапний процес. Припустимо, що за рахунок витрат, необхідних для отримання доходу g (у) , кількість перві-сних засобів у зменшиться до значення , . Аналогічно для отримання доходу h (х - у) кількість первісних засобів (х0 -у0 ) зменшиться до значення b (x0 - y0) , тобто , . Таким чином, після завершення 1 -го етапу залишок засобів становитиме . (5) Повторимо процес розподілу сумарного залишку на другому кроці: , . (6) При цьому дохід на другому кроці становитиме g (у1 ) + h (х1- у1) . Таким чином повний дохід за два кроки становитиме , , , (7) , . Розповсюджуючи отримані результати на N кроків, отримаємо: , (8) , , . Співставивши з загальною постановкою задачі, отримаємо: Рис. 2. Співставлення розподільчої задачі з загальною задачею динамічного програмування , . (9) Застосуємо принцип оптимальності Белмана дая розв'язування цієї задачі. На N-му кроці розподілу підлягає значення: , (10) де визначається зі співвідношення (оскільки немає майбутнього !!!) . (11) За два останні етапи найбільший прибуток визначиться, як: , , (12) , звідки . (13) Таким чином, оптимальний сумарний прибуток з і -го по N -й крок визначиться, як: , (14) або , і (15) 4. Динамічні моделі управління запасами. Однопродуктова динамічна модель. В цій моделі припускається, що хоча й попит достовірно відомий, він може змінюватися від етапу до етапу. Рівень запасу контролюється періодично. Хоч запізнення
Loading...

 
 

Цікаве