Метод динамического программирования: вывод уравнения Беллмана,
замечания о методе динамического программирования
Метод динамического программирования является методом синтеза оптимального управления.
Он основан на
принципе динамического программирования,
сформулированным Беллманом.
Принцип динамического программирования:
оптимальное управление обладает тем свойством, что для любого начального состояния
и использованного начального управления последующее оптимальное управление
совпадает с исходным оптимальным управлением относительно состояния, получающегося
в результате применения начального управления.
Другими словами, пусть построена экстремальная траектория, решающая задачу
оптимизации по некоторому критерию для управляемого процесса $u(t), x(t)$,
переводящего механическую систему из заданного начального состояния $x_\text{н}$
в момент времени $t = t_\text{н}$ в некоторое конечное положение $x_\text{к}$
при $t = t_\text{к}$. Если взять в качестве новой начальной точки любую точку
$x(\tau)$ этой траектории, причём $t_\text{н} \lt \tau \lt t_\text{к}$, то
оптимальным управлением в случае $F_0(x, u, t) \geqslant 0$ будет оставшаяся часть
ранее построенного оптимального управления, отвечающая отрезку
$t \in [\tau, t_\text{к}]$. Оба вектора управления (первоначального и укороченного)
на этом отрезке совпадают.
Говорят, что второй вектор управления является сужением первого на отрезке
$t \in [\tau, t_\text{к}]$.
Рассмотрим задачу управления на конечном интервале времени:
-
уравнения движения:
\[
\tag{1}
\dot x(t) = f(t, x(t), u), \qquad t_\text{н} \leqslant t \leqslant t_\text{к}
\]
с начальными условиями $x(t_\text{н}) = x_\text{н}$;
-
критерий качества:
\[
\tag{2}
J(u)
= \int\limits_{t_\text{н}}^{t_\text{к}} F_0(t, x(t), u) dt
+ \varphi_0(x(t_\text{к}))
\limto{u \in U} \inf,
\]
-
ограничение на управление: $u \in U$.
Пусть движение системы происходит на отрезке
\[
t_\text{н} \leqslant \tau \leqslant t \leqslant t_\text{к}
\]
с начальными условиями
\[
x(\tau) = x, \qquad x \in \R^n,
\]
то есть
\[
\tag{3}
\dot x(t) = f(t, x(t), u),
\qquad \tau \leqslant t \leqslant t_\text{к},
\qquad x(\tau) = x.
\]
Для этой системы рассмотрим задачу минимизации функционала
\[
\tag{4}
\int\limits_{\tau}^{t_\text{к}} F_0(t, x(t), u) dt
+ \varphi_0(x(t_\text{к}))
\limto{u \in U} \inf.
\]
Допустимым управлением называется любая измеримая функция $u \in U$ такая,
что для всех моментов времени $\tau \in [t_\text{н}, t_\text{к}]$ и $x \in \R^n$
существует решение суженной задачи (3).
Функцией Беллмана $B(\tau, x)$ называют функцию, равную $\inf$ функционала (4)
на траекториях системы (3) по всем допустимым управлениям:
\[
\tag{5}
B(\tau, x)
= \inf_{u \in U} \left[
\int\limits_{\tau}^{t_\text{к}} F_0(t, x(t), u) dt
+ \varphi_0(x(t_\text{к}))
\right].
\]
Рассмотрим произвольные моменты времени $\tau$ и $\tau_1$:
\[
t_\text{н} \leqslant \tau \leqslant \tau_1 \leqslant t_\text{к}.
\]
На основании принципа динамического программирования запишем, что
\[
\tag{6}
\begin{aligned}
B(\tau, x)
&= \inf_{u \in U} \left[
\int\limits_{\tau}^{t_\text{к}} F_0(t, x(t), u) dt
+ \varphi_0(x(t_\text{к}))
\right] = \\
&= \inf_{u \in U} \left[
\int\limits_{\tau}^{\tau_1} F_0(t, x(t), u) dt
+
\int\limits_{\tau_1}^{t_\text{к}} F_0(t, x(t), u) dt + \varphi_0(x(t_\text{к}))
\right] = \\
&= \inf_{\substack{u \in U \\ \tau \leqslant t \leqslant \tau_1}} \left[
\int\limits_{\tau}^{\tau_1} F_0(t, x(t), u) dt
+
\inf_{\substack{u \in U \\ \tau_1 \leqslant t \leqslant t_\text{к}}} \left[
\int\limits_{\tau_1}^{t_\text{к}} F_0(t, x(t), u) dt + \varphi_0(x(t_\text{к}))
\right]
\right] = \\
&= \inf_{\substack{u \in U \\ \tau \leqslant t \leqslant \tau_1}} \left[
\int\limits_{\tau}^{\tau_1} F_0(t, x(t), u) dt
+
B(\tau_1, x(\tau_1))
\right].
\end{aligned}
\]
Здесь $x(t)$ — решение задачи (3), а управление при $t \in [\tau, \tau_1]$ влияет
на
\[
\int\limits_{\tau}^{\tau_1} F_0(t, x(t), u) dt
\]
и на величину $x(\tau_1)$.
Представим формулу (6) в виде
\[
\tag{7}
\inf_{\substack{u \in U \\ \tau \leqslant t \leqslant \tau_1}} \left[
\int\limits_{\tau}^{\tau_1} F_0(t, x(t), u) dt
+ B(\tau_1, x(\tau_1))
- B(\tau, x)
\right]
= 0.
\]
Пусть $B(\tau, x)$ непрерывно дифференцируема, тогда при
$\Delta t = \tau_1 - \tau \to 0$ с точностью до малых более высокого порядка малости
относительно $\Delta t$ выполняется равенство
\[
\tag{8}
B(\tau_1, x(\tau_1)) - B(\tau, x) = \dot B(\tau, x) \Delta t,
\]
где $\dot B(\tau, x)$ — полная производная функции $B$ вдоль траекторий системы
(1):
\[
\tag{9}
\dv{B(\tau, x)}{t} = \pd{B(\tau, x)}{t} + \pd{B(\tau, x)}{x} f(t, x, u).
\]
Разделив обе части (7) на $\Delta t$ и переходя к пределу при $\Delta t \to 0$,
получаем
\[
\inf_{u \in U} \left[
\pd{B(t, x)}{t} + \pd{B(t, x)}{x} f(t, x, u) + F_0(t, x, u)
\right] = 0,
\quad \text{где}
\quad t_\text{н} \leqslant t \leqslant t_\text{к},
\quad x \in \R^n.
\]
Уравнение
\[
\tag{10}
\inf_{u \in U} \left[
\pd{B(t, x)}{t} + \pd{B(t, x)}{x} f(t, x, u) + F_0(t, x, u)
\right] = 0,
\quad \text{где}
\quad t_\text{н} \leqslant t \leqslant t_\text{к},
\quad x \in \R^n
\]
называют уравнением Беллмана.
Заметим, что из определения функции Беллмана следует, что
\[
\tag{11}
B(t_\text{к}, x) = \varphi(x(t_\text{к})), \qquad x \in \R^n.
\]
Таким образом, если решение задачи (1),(2) оптимального управления существует, а
функция Беллмана $B(t, x)$ непрерывно дифференцируема, то справедливы соотношения
\[
\begin{gathered}
\inf_{u \in U} \left[
\pd{B(t, x)}{t} + \pd{B(t, x)}{x} f(t, x, u) + F_0(t, x, u)
\right] = 0, \\
B(t_\text{к}, x) = \varphi(x(t_\text{к})).
\end{gathered}
\]
Таким образом, решение задачи оптимального управления для системы ОДУ сводится к
решению одного уравнения в частных производных с граничными условиями
(аналогично методу Якоби для решения канонических уравнений).
