Поняття динамічного програмування

Динамічне програмування (динамічне планування) - особливий метод оптимізації рішень, який застосовується, коли для максимізації загального критерію якості системи необхідно багаторазово обирати управління, при чому система є такою, що в ній можна виділити окремі етапи, а управління, які здійснюються на наступних етапах, не впливають на величину показника якості, досягнутого на попередніх етапах. [1]

Динамічне програмування визначає оптимальне рішення n-мірної задачі шляхом її декомпозиції на n етапів, кожен з яких представляє собою підзадачу однієї змінної. Обчислювальна перевага такого підходу полягає в вирішенні одновимірних оптимізаційних задач замість великої n-мірної задачі. [16]

Характерним для динамічного програмування є те, що змінні розглядаються не разом, а послідовно - одна за одною. При цьому обчислювальна система будується таким чином, що замість одного завдання з n змінними вирішується серія завдань з невеликим числом, а найчастіше з однією змінною.

Основні властивості задач, до яких можливе застосування методу динамічного програмування:

1. задача повинна бути представлена як n -кроковий процес прийняття рішень;

2. задача повинна бути визначена для будь-якого числа кроків і мати структуру, незалежну від їх числа

3. має бути задане деяка множина параметрів, що описують стан системи (під параметрами стану розуміються параметри, від яких залежать оптимальні значення керуючих змінних), на цю множину накладається умова незмінності її при збільшенні числа кроків.[15]

На кожному кроці, з метою покращення результату в цілому, здійснюється управління u. Ефективність операції в цілому характеризується показником W, який залежить від всієї сукупності управлінь на кожному кроці

Управління, при якому показник W досягає оптимуму (максимуму або мінімуму), називається оптимальним управлінням , яке складається із сукупності оптимальних крокових управлінь

Завдання динамічного програмування - визначити оптимальне управляння (яке може бути числом, вектором, функцією) на кожному кроці, i = 1, 2,... n, і тим самим знайти оптимальне управляння для всієї системи.

Дата добавления: 2015-08-17