Поняття та галузь застосування
Динамічне програмування - метод оптимізації, пристосований до операцій, в яких процес прийняття рішень може бути розділений на окремі етапи (кроки). В основі методу лежить принцип оптимальності, сформульований Р.Беллманом. Оптимальне управління характеризується такими властивостями, що незалежно від початкового стану на будь-якому кроці управління і наступне управління повинно обиратися оптимальним відносно стану, до якого прийде система в кінці цього кроку.
Метод, побудований на використанні принципу оптимальності, дозволяє встановити співвідношення між екстремальними значеннями цільової функції в задачах, що характеризуються різною тривалістю процесу і різними початковими станами. При цьому необхідно враховувати наслідки реалізації знайденого оптимального рішення і для наступних рішень. Такий підхід обумовлений розробкою оптимальної стратегії. Процес прийняття рішення в цьому випадку є багатокроковим.
При цьому, якщо в задачах лінійного програмування залежності між критеріальною функцією та змінними обов'язково лінійні, то в завданнях динамічного програмування ці залежності можуть мати й нелінійний характер.
Динамічне програмування застосовується в основному для вирішення задач двох класів: планування діяльності економічної системи (підприємств) з урахуванням зміни продукції, що виготовляється в часі відповідно до зміни потреби; перерозподілу ресурсів за різними напрямками в часі.
Найбільш доцільно динамічне програмування застосувати для вирішення таких практичних задач, в яких пошук оптимального рішення вимагає поетапного підходу; наприклад, визначення часу заміни устаткування з урахуванням витрат на експлуатацію устаткування, на придбання нового, первісної вартості даного устаткування, вартості отриманої на ньому продукції.
Концептуальний підхід
Побудова моделі динамічного програмування зводиться до таких основних моментів:
1) обирають спосіб ділення процесу на кроки:
3) записують рівняння стану:
4) вводять показники ефективності на к-му кроці
і сумарний показник - цільову функцію:
5) вводять для розгляду умовні максимуми
показника ефективності від к-го кроку (включно) до кінця процесу та умовні оптимальні управління на к-му кроці
6) згідно з обмеженнями задачі визначають для кожного кроку множину Пк допустимих управлінь на цьому кроці;
7) записують основні для розрахунків функціональні рівняння Беллмана:
Незважаючи на одноманітність у загальній побудові моделі динамічного програмування, шо наведена вище, схема розрахунків видозмінюється залежно від розмірності задачі, характеру моделі (дискретна чи неперервна), виду функцій та інших характеристик моделі.
Загальні характеристики
Яким же умовам має відповідати задача оптимізації, щоб її можна було описати моделлю динамічного програмування. Ці умови такі:
1. Задача може інтерпретуватись як n- кроковий процес управління, а показник ефективності процесу може бути представлений в адитивній формі, тобто як сума показників ефективності на кожному кроці.
2. Структура задачі інваріантна відносно числа кроків п, тобто повинна бути визначена для будь-якого п і не залежати від цього числа.
3. На кожному кроці стан системи визначається кінцевим числом б параметрів стану та управляється кінцевим числом г змінних управління, причому г і в не залежать від кількості кроків п.
4. Вибір управління на К-му кроці не впливає на попередні кроки, а стан на початку цього кроку є функцією лише попереднього стану і обраного на ньому управління (умова відсутності післядії).
Зазначимо також, що виконання вказаних умов іноді є очевидним, а іноді досягається після відповідних перетворень.
Приклад застосування
Автомашина експлуатується протягом 6років. На початку кожного року може бути прийняте рішення про заміну машини новою. Вартість нової машини на к-му році експлуатації складає я^=5ооо+5оо( гривень. Після г років експлуатації машини на к-му році її можна продати за<р( і) 2-/ гривень. Вартість утримання машини протягом к-го року складає ^(О'0'1/^'*1) гривень. Знайти оптимальний спосіб експлуатації машини: коли потрібно замінити машину новою, щоб сумарні витрати (з врахуванням витрат на закупівлю нової машини на початку терміну експлуатації та компенсація за рахунок остаточного продажу) були мінімальними;
Рк - початкова вартість машини, якщо вона придбана на початку к-го року;
гк(і) - витрати на експлуатацію протягом к-го року, якщо з часу останньої заміни пройшло і років;
*0) ~~ ліквідаційна вартість устаткування віком / років, якщо воно продається на початку к-го року.
Процес експлуатації машини є б-кроковим. Стан %к_х системи на початку к-го кроку характеризується одним параметром - / - віком машини. Управління на кожному кроці полягає у виборі одного з двох рішень: цс - експлуатувати стару машину; ц3 - продати стару машину, купити нову (замінити). Рівняння стану для цього процесу має вигляд:
Показник ефективності в цій задачі-сумарні затрати на експлуатацію устаткування. Витрати на к-му кроці залежать від вибраного управління. При управлінні щ = ис ці витрати дорівнюють: 2кс = гДп, а при управлінні ик == и3 складають: Z^3 = -фк+Ри + 7"Д0).
Нехай Хк и) умовні мінімальні затрати зап - к + кроків з к-го по п-й включно, якщо на початок к-го кроку вік машини складає і років, за умови, що був обраний оптимальний режим експлуатації.
Рекурентні співвідношення для Хк (/) мають у нашому прикладі вигляд:
Для 6-го кроку відповідно отримаємо:
Запишемо останнє рівняння, враховуючи задані в умовах функції р.. Умовна оптимізація на 6-му кроці зводиться до оптимізації за рівнянням:
Поняття та галузь застосування
Приклад застосування
Література