Стисла теоретична довідка. Метод динамічного програмування розроблений американським вченим Р

Метод динамічного програмування розроблений американським вченим Р. Беллманом для оптимізації багатокрокових процесів прийняття рішень та побудований на, так званому, принципі оптимальності: оптимальній поведінці властиво те, що яким би не був початковий стан та рішення у початковий момент, наступні рішення повинні складати оптимальну поведінку відносно стану, що одержано в результаті першого рішення.

Загальну задачу оптимізації можна описати моделлю динамічного програмування при виконанні наступних умов:

1) задача може інтерпретуватись як n -кроковий процес управління, а загальний показник ефективності може бути поданий як сума показників ефективності на кожному кроці;

2) структура задачі повинна бути визначена для будь-якої кількості кроків n і не залежати від цієї кількості.

3. На кожному кроці стан системи визначається скінченою кількістю m параметрів стану та управляється скінченою кількістю r змінних, причому m та r не залежать від кількості кроків n.

4. Вибір управління на k -му кроці не має впливу на попередні кроки, а стан на початку цього кроку є функція тільки попереднього кроку та обраного на ньому управління.

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

1) вибирають спосіб поділу процесу на кроки;

2) вводять параметри стану та змінні управління на кожному кроці процесу;

3) записують рівняння стану для кожного кроку

,

де – стан процесу на попередньому (k– 1)-му кроці;

– управління на даному k -му кроці;

4) вводять показники ефективності на k -му кроці та сумарний показник – цільову функцію в одній із форм в залежності від умов задачі:

а) в адитивній формі у вигляді суми показників ефективності на окремих кроках

;

б) в мультиплікативній формі у вигляді добутку показників ефективності на окремих кроках

;

5) вводять у розгляд умовні максимуми (мінімуми) показника ефективності від k -го кроку (включно) до кінця процесу та умовні оптимальні управління на k -му кроці ;

6) із обмежень задачі визначають для кожного кроку множини D_k припустимих управлінь на цьому кроці;

7) записують основні для обчислювальної схеми функціональні рівняння Беллмана:

а) для адитивної цільової функції

,

;

б) для мультиплікативної цільової функції

,

.