арактерним для дінамічного програмування є підхід до решение Завдання по етапах, з шкірними з якіх асоційована одна керована змінна. Набір рекурентних обчислювальних процедур, что зв'язують Різні етап, Забезпечує одержании Припустиме оптимального решение Завдання в цілому при досягненні последнего етапу.
Походження назви дінамічне програмування, імовірно, пов'язане з використаних методів ДП вЂ‹вЂ‹у Завдання Прийняття РІШЕНЬ через фіксовані проміжкі годині (Наприклад, у Завдання Керування запасами). Однак метод ДП успішно застосовуються такоже для решение Завдання, у якіх фактор часу не Враховується. Із цієї причини больше вдалину представляється Термін багатоетапності програмування, что відбіває покроковий характер процеса решение Завдання.
фундаментальності принципом, Покладення в основу Теорії ДП, є принцип оптімальності. Власне Кажучи, ВІН візначає порядок поетапна решение Завдання, что допускає декомпозіцію, (це больше Прийнятних шлях, чім безпосереднє решение Завдання у віхідній постановці) помощью рекурентних обчислювальних процедур.
Дінамічне програмування дозволяє Здійснювати оптімальне планування керованих процесів. Під В«керованогоВ» розуміються Процеси, на Хід якіх ми можемо в ТІМ або Іншому Ступені впліваті.
Нехай передбачається до Здійснення Деяк Захід або серія ЗАХОДІВ (В«ОпераціяВ»), что переслідує ПЄВНЄВ мету. Запітується: як нужно організуваті (спланувати) операцію для того, щоб вона булу найбільш ефективного? Для того, щоб поставлених Завдання Придбай кількісній, математичний характер, звітність, ввести в Розгляд Деяк чисельного крітерій W, Яким ми будемо Характеризувати Якість, успішність, ефективність Операції. Крітерій ефектівності в шкірному конкретному випадка вібірається віходячі Із цільової спрямованості Операції ї Завдання Дослідження (Який елемент Керування оптімізується ї для чого). p> Сформулюємо загальний принцип, что лежить в Основі решение всех Завдання дінамічного програмування (В«принцип оптімальностіВ»):
В«Який бі НЕ БУВ стан системи S перед Чергова кроком, треба вібрато Керування на цьом кроці так, щоб виграш на даним кроці плюс оптимальний виграш на всех Наступний кроках БУВ максимальним В».
Дінамічне програмування - це поетапна планування багатокрокового процеса, при якому на шкірному етапі оптімізується Тільки один крок. Керування на шкірному кроці повинною вібіратіся з обліком всех его НАСЛІДКІВ у Майбутнього.
При постановці Завдання дінамічного програмування Варто Керувати Наступний засідками:
- вібрато параметри (фазові координати), что характеризують стан S керованої системи перед Шкірні кроком;
- розчленуваті операцію на етап (кроки);
- з'ясувати набор Кроковеє Керування x и для шкірного Кроку ї обмеження, что накладають на них;
- візначіті Який виграш приносити на і-му кроці Керування x и , ЯКЩО перед ЦІМ система могла S, тоб записатися В«функцію виграшВ»;
...
