Принцип оптимальності вперше був сформульований Річардом Ернестом Беллманом в 1953 р (в трактуванні Е.С. Вентцель):
Яке б не було стан системи в результаті якого-небудь числа кроків, на найближчому кроці потрібно вибирати управління таким чином, щоб воно в сукупності з оптимальним керуванням на всіх наступних кроках приводило до оптимального виграшу на всіх, хто лишився кроках, включаючи даний.
Р.Е. Беллманом були сформульовані і умови, при яких принцип вірний. Основна вимога - процес управління повинен бути без зворотного зв'язку, тобто управління на даному етапі не повинно впливати на попередні кроки.
Розглянемо загальну задачу динамічного програмування, наведену вище. На кожному кроці крім останнього для будь-якого стану системи sk-1 управлінське рішення Xk необхідно вибирати «з оглядкою», так як цей вибір впливає на подальший стан системи sk.
На останньому кроці виходячи зі стану системи sn-1 управлінське рішення Xn можна планувати локально-оптимально, тобто виходячи тільки з міркувань цього кроку.
Розглянемо останній n -й крок:
sn-1 - стан системи до початку n-го кроку;
sn - кінцевий стан системи;
Xn - управління на n-му кроці;
Відповідно до принципу оптимальності, Xn потрібно вибирати таким чином, щоб для будь-яких станів системи sn-1 отримати оптимум цільової функції на цьому кроці.
Позначимо через оптимум (для визначеності приймемо максимум) цільової функції - показник ефективності n -го кроку за умови, що до початку останнього кроку система S була в довільному стані sn-1. а на останньому кроці управління було оптимальним.
називають умовним максимумом цільової функції на n-му кроці, і визначають за такою формулою:
Максимізація ведеться за всіма допустимим управлінням Xn.
Рішення Xn. при якому досягається. також залежить від sn-1 і називається умовним оптимальним рішенням на n-му кроці. Позначимо його через.
Вирішивши одновимірну задачу локальної оптимізації за рівнянням (11.5), визначимо для всіх можливих станів sn-1 дві функції і.
Розглянемо двокрокового завдання: приєднаємо до n -го кроку (n- 1) -й.
Для будь-яких станів sn-2. довільних управлінських рішень Xn-1 і оптимальне управління на n-му кроці значення цільової функції на двох останніх кроках обчислюється за формулою:
Відповідно до принципу оптимальності Беллмана для будь-яких sn-2 рішення потрібно вибирати так, щоб воно разом з оптимальним керуванням на останньому (n -му) кроці призводило б до оптимуму цільової функції на двох останніх кроках. Отже, необхідно відшукати оптимум вираження (11.6) за всіма допустимим управлінським рішенням Xn-1:
- називають умовним максимумом цільової функції при оптимальному управлінні на двох останніх кроках. Необхідно відзначити, що вираз в фігурних дужках у формулі (11.6), залежить тільки від sn-2 і Xn-1. так як sn-1 можна знайти з рівняння станів (11.1) при:
Відповідне управління Xn-1 на (n- 1) -му кроці позначається через і називають умовним оптимальним керуванням на (n- 1) -ом.
Аналогічно визначаються умовні оптимум цільової функції при оптимальному управлінні на (n -k + 1) кроках, починаючи з k -го до кінця, за умови, що до початку k -го кроку система перебувала в стані sk-1:
Управління Xk на k -му кроці, при якому досягається максимум по (11.8), позначається і називається умовним оптимальним керуванням на k -му кроці.
Рівняння (11.5) і (11.8) називають рекурентними рівняння Беллмана (зворотна схема). Процес вирішення даних рівнянь називають умовною оптимізацією.
В результаті умовної оптимізації виходять дві послідовності:
. . ...,. - умовні максимуми цільової функції на останньому, двох останніх, ..., на n кроків;
. . ...,. - умовні оптимальні керування на n-ому, (n -1) -му, ..., на 1-му кроках.
Використовуючи дані послідовності, можна знайти рішення задачі динамічного програмування при даних n і s0:
В результаті отримуємо оптимальне рішення задачі динамічного програмування:.
Аналогічно розмірковуючи, можна вибудувати і пряму схему умовної оптимізації:
Оптимальне рішення задачі в даному випадку знаходиться за наступною схемою:
Таким чином, побудова моделі динамічного програмування і рішення задачі на її основі в загальному вигляді можна представити у вигляді наступних етапів:
1. Вибирають спосіб поділу процесу управління на кроки.
2. Визначають параметри стану sk і змінні управління Xk на кожному кроці, записують рівняння станів.
3. Вводять цільові функції k -ого кроку і сумарну цільову функцію, а також умовні оптимум і умовне оптимальне керування на k -му кроці ().
4. Записують відповідно до зворотного або прямий схемою рекурентні рівняння Беллмана і після виконання умовної оптимізації отримують дві послідовності: <> і <>.
5. Визначають оптимальне значення цільової функції і оптимальне рішення.