Принцип оптимальности и уравнения Беллмана

 

Принцип оптимальности впервые был сформулирован Ричардом Эрнестом Беллманом в 1953 г. (в трактовке Е.С. Вентцель):

Каково бы ни было состояние системы в результате какого-либо числа шагов, на ближайшем шаге нужно выбирать управление таким образом, чтобы оно в совокупности с оптимальным управлением на всех последующих шагах приводило к оптимальному выигрышу на всех оставшихся шагах, включая данный.

Р.Э. Беллманом были сформулированы и условия, при которых принцип верен. Основное требование ­– процесс управления должен быть без обратной связи, т.е. управление на данном шаге не должно оказывать влияния на предшествующие шаги.

Рассмотрим общую задачу динамического программирования, приведенную выше. На каждом шаге кроме последнего для любого состояния системы s_k-1 управленческое решение X_k необходимо выбирать «с оглядкой», так как этот выбор влияет на последующее состояние системы s_k.

На последнем шаге исходя из состояния системы s_n-1 управленческое решение X_n можно планировать локально-оптимально, т.е. исходя только из соображений этого шага.

Рассмотрим последний n-й шаг:

s_n-1 – состояние системы к началу n-го шага;

s_n – конечное состояние системы;

X_n – управление на n-ом шаге;

f_n(s_n-1, X_n) – целевая функция (выигрыш) n-го шага.

Согласно принципу оптимальности, X_n нужно выбирать таким образом, чтобы для любых состояний системы s_n-1 получить оптимум целевой функции на этом шаге.

Обозначим через оптимум (для определенности примем максимум) целевой функции – показатель эффективности n-го шага при условии, что к началу последнего шага система S была в произвольном состоянии s_n-1 , а на последнем шаге управление было оптимальным.

называют условным максимумом целевой функции на n-ом шаге, и определяют по следующей формуле:

. (11.5)

Максимизация ведется по всем допустимым управлениям X_n.

Решение X_n, при котором достигается , также зависит от s_n-1 и называется условным оптимальным решением на n-ом шаге. Обозначим его через .

Решив одномерную задачу локальной оптимизации по уравнению (11.5), определим для всех возможных состояний s_n-1 две функции и .

Рассмотрим двухшаговую задачу: присоединим к n-му шагу (n–1)-й.

Для любых состояний s_n-2, произвольных управленческих решений X_n-1 и оптимальном управлении на n-ом шаге значение целевой функции на двух последних шагах вычисляется по формуле:

. (11.6)

Согласно принципу оптимальности Беллмана для любых s_n-2 решение нужно выбирать так, чтобы оно вместе с оптимальным управлением на последнем (n-ом) шаге приводило бы к оптимуму целевой функции на двух последних шагах. Следовательно, необходимо отыскать оптимум выражения (11.6) по всем допустимым управленческим решениям X_n-1:

. (11.6)

– называют условным максимумом целевой функции при оптимальном управлении на двух последних шагах. Необходимо отметить, что выражение в фигурных скобках в формуле (11.6), зависит только от s_n-2 и X_n-1, так как s_n-1 можно найти из уравнения состояний (11.1) при :

. (11.7)

Соответствующее управление X_n-1 на (n–1)-ом шаге обозначается через и называют условным оптимальным управлением на (n–1)-ом.

Аналогично определяются условные оптимумы целевой функции при оптимальном управлении на (n–k+1) шагах, начиная с k-го до конца, при условии, что к началу k-го шага система находилась в состоянии s_k-1:

. (11.8)

Управление X_k на k-ом шаге, при котором достигается максимум по (11.8), обозначается и называется условным оптимальным управлением на k-ом шаге.

Уравнения (11.5) и (11.8) называют рекуррентными уравнения Беллмана (обратная схема). Процесс решения данных уравнений называют условной оптимизацией.

В результате условной оптимизации получаются две последовательности:

, , …, , – условные максимумы целевой функции на последнем, двух последних, …, на n шагах;

, , …, , – условные оптимальные управления на n-ом, (n–1)-ом, …, на 1-ом шагах.

Используя данные последовательности, можно найти решение задачи динамического программирования при данных n и s₀:

В результате получаем оптимальное решение задачи динамического программирования: .

Аналогично рассуждая, можно выстроить и прямую схему условной оптимизации:

, (11.9)

. (11.10)

Оптимальное решение задачи в данном случае находится по следующей схеме:

Таким образом, построение модели динамического программирования и решение задачи на ее основе в общем виде можно представить в виде следующих этапов:

1. Выбирают способ деления процесса управления на шаги.

2. Определяют параметры состояния s_k и переменные управления X_k на каждом шаге, записывают уравнения состояний.

3. Вводят целевые функции k-ого шага и суммарную целевую функцию, а также условные оптимумы и условное оптимальное управление на k-ом шаге ( ).

4. Записывают в соответствии с обратной или прямой схемой рекуррентные уравнения Беллмана и после выполнения условной оптимизации получают две последовательности: { } и { }.

5. Определяют оптимальное значение целевой функции и оптимальное решение .