ими особливостями:
. Завдання оптимізації інтерпретується як n-кроковий процес управління.
. Цільова функція дорівнює сумі цільових функцій кожного кроку.
. Вибір управління на k-му кроці залежить тільки від стану системи до цього кроку, не впливає на попередні кроки (відсутність зворотного зв'язку).
. Стан sk після k-го кроку управління залежить тільки від попереднього стану sk - 1 та управління Xk («відсутність наслідки»).
. На кожному кроці управління Xk залежить від кінцевого числа керуючих змінних, а стан sk - від кінцевого числа параметрів.
2. Принцип оптимальності та рівняння Беллмана
Принцип оптимальності вперше був сформульований Річардом Ернестом Беллманом в 1953 р. (у трактуванні Е.С. Вентцель):
Яке б не був стан системи в результаті якого-небудь числа кроків, на найближчому кроці потрібно вибирати управління таким чином, щоб воно в сукупності з оптимальним керуванням на всіх наступних кроках призводило до оптимального виграшу на всіх залишилися кроках , включаючи даний.
Р.Е. Беллманом були сформульовані та умови, за яких принцип вірний. Основна вимога - процес управління повинен бути без зворотного зв'язку, тобто управління на даному кроці не повинно робити впливу на попередні кроки.
Розглянемо загальну задачу динамічного програмування, наведену вище. На кожному кроці крім останнього для будь-якого стану системи sk - 1 управлінське рішення X k необхідно вибирати «з оглядкою», так як цей вибір впливає на подальший стан системи sk.
На останньому кроці виходячи зі стану системи sn - 1 управлінське рішення X n можна планувати локально-оптимально, тобто виходячи тільки з міркувань цього кроку.
Розглянемо останній n-й крок:
sn - 1 - стан системи до початку n-го кроку;
sn - кінцевий стан системи;
X n - управління на n-му кроці;
fn (sn - 1, X n) - цільова функція (виграш) n-го кроку.
Згідно з принципом оптимальності, X n потрібно вибирати таким чином, щоб для будь-яких станів системи sn - 1 отримати оптимум цільової функції на цьому кроці.
Позначимо через оптимум (для визначеності приймемо максимум) цільової функції - показник ефективності n-го кроку за умови, що до початку останнього кроку система S була в довільному стані sn - 1, а на останньому кроці управління було оптимальним.
називають умовним максимумом цільової функції на n-му кроці, і визначають за такою формулою:
. (5)
Максимізація ведеться за всіма допустимим управлінням Xn.
Рішення Xn, при якому досягається, також залежить від sn - 1 і називається умовним оптимальним рішенням на n-му кроці. Позначимо його через.
Вирішивши одновимірну задачу локальної оптимізації за рівнянням (5), визначимо для всіх можливих станів sn - 1 дві функції і.
Розглянемо двокроковий задачу: приєднаємо до n-му кроці (n - 1) - й.
Для будь-яких станів sn - 2, довільних управлінських рішень Xn - 1 і оптимальному управлінні на n-му кроці значення цільової функції на двох останніх кроках обчислюється за формулою:
. (6)
Згідно з принципом оптимальності Беллмана для б...
