На главную   ::   Содержание



Метод динамического программирования и уравнение Беллмана

Рассмотрим

$\displaystyle x_{k+1}=f(x_k, u_k),\quad k=0,1,\ldots,N-1,\quad x_k\in \mathbb{R}^n,\;u_k\in \mathrm U \subseteq \mathbb{R}^r.
$

Такие системы часто возникают в экономике, когда планирование идет по годам, месяцам, и т. д.

Функционал качества определяется так:

$\displaystyle \mathcal J=\sum_{k=0}^{N-1}g(x_k, u_k)+\varphi(x_N).
$

В экономических терминах $ g$ -- затраты при реализации задачи управления. Заданы начальные данные $ x^0\in\mathbb{R}^n$. Задача ставится так:

$\displaystyle \mathcal J \to \min.
$

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

$\displaystyle (x^0, u_0)\; \stackrel{\text{определяется}}{\longrightarrow} \;
...
...el{u_1}{\longrightarrow} \; x_2=x_2(u_0,
u_1) \; \longrightarrow \; \ldots.
$

Если подставить, то получим выражение:

$\displaystyle \mathcal J = \mathcal J(x^0;u_0, u_1,\ldots, u_{N-1}).
$

Получили задачу оптимизации для $ N\times r$ переменных. Но, как правило, в прикладных задачах $ N$ велика. Следовательно, получили задачу большой размерности. Поэтому прямой путь неприемлем. Метод дискретного динамического программирования сводит задачу к последовательности задач оптимизации размерности $ r$.

При этом используется принцип оптимальности Беллмана. Смысл принципа оптимальности: остаток оптимальной траектории оптимален. Принцип Беллмана справедлив не всегда, но для аддитивных функционалов это справедливо.

Начнем процедуру попятного движения. Пусть мы находились в предпоследней точке $ x_{N-1}$, тогда

$\displaystyle \mathcal J_{N-1}=g(x_{N-1}, u_{N-1})+\varphi(x_N) = g(x_{N-1},
u_{N-1})+\varphi\bigl( f(x_{N-1}, u_{N-1}) \bigr).
$

Поскольку остаток оптимальной траектории оптимален, находим требуемое управление на последнем шаге:

$\displaystyle u_{N-1}:\;\min_{u_{N-1}\in\mathrm U}\mathcal J_{N-1}.
$

Но предполагаемая точка нам пока неизвестна, поэтому решение задачи будет зависить от $ x_{N-1}$.

$\displaystyle u_{N-1}=u_{N-1}(x_{N-1}),\;\min \mathcal
J_{N-1}=S_{N-1}(x_{N-1}).
$

Следующий шаг. Пусть мы в точке $ N-2$:

$\displaystyle \mathcal J_{N-2}=g(x_{N-2}, u_{N-2})+g(x_{N-1},
u_{N-1})+\varphi(x_N).
$

Находим минимум

$\displaystyle \min_{
\begin{array}{c}
\text{\small {$u_{N-2}$}} \\
\text...
...)+\min_{u_{N-1}}\Bigl[ g(x_{N-1}, u_{N-1})+\varphi(x_N)
\Bigr]
\biggr\} =
$

Скобки только так. Но мы уже решили задачу минимума в квадратных скобках. Следовательно, это выражение равно:

$\displaystyle = \min_{u_{N-2}}\bigl\{ g(x_{N-2}, u_{N-2}) + S_{N-1}(x_{N-1})
\bigr\}=
$

$\displaystyle = \min_{u_{N-2}}\bigl\{ \ldots + S_{N-1}\bigl(f(x_{N-2}, u_{N-2})\bigr)
\bigr\}.
$

Но $ x_{N-2}$ пока неизвестна.

$\displaystyle u_{N-2}=u_{N-2}(x_{N-2});\quad \mathcal J_{N-2}=S_{N-2}$    -- значение функционала.$\displaystyle $

Замечаем закономерность

$\displaystyle S_{N-k}=\min\Bigl\{ g(x_{N-k}, u_{N-k})+S_{N-k+1}\bigl( f(x_{N-k}, u_{N-k}) \bigr) \Bigr\}
$

$\displaystyle u_{N-k} = u_{N-k}(x_{N-k})$$\displaystyle \text { - оптимальное.}
$

Полученное уравнение называется рекуррентным уравнением Беллмана. $ S_i$ -- функции Беллмана.

На последнем этапе получим, что $ u_0=u_0(x^0)$. Но $ x^0$ известна по постановке задачи. Начинаем этап прямого движения: по $ x^0$ вычисляем $ u_0=u_0(x^0)$. Далее, вычисляем $ x_1=f(x_0, u_0)$ и $ u_1=u_1(x_1)$. Получили, что $ u_1$ -- известна. И так далее, узнаем $ x_1,\ldots,x_N$.

Так как $ u_{N-k}\in \mathrm U$, то это $ r$-мерные задачи оптимизации.

Но не все так хорошо. Недостаток метода: на этапе попятного движения физические точки не были известны, следовательно, мы должны хранить функции $ u_{N-k}(x_{N-k}),\; k=1,2,\ldots,N$. То есть мы должны решить при любом допустимом $ x_{N-k}$. Сейчас это уже не большая проблема, но на $ 64$Кб... Например:

$\displaystyle f(x)\to\min_{x\in \mathbb{R}^n}
$

Решать можно так: $ x_{n+1}=x_n-\alpha f'(x_n)$. Вообще говоря, здесь бесконечное число шагов. Но это намного лучше, это хранение себя оправдывает.

К дискретным задачам сводятся и непрерывные, при использовании разностных методов. Например:

$\displaystyle \begin{array}{c}
\dot x = f(x, u) \\
x(0)=x^0 \\
\display...
...r)+\int\limits_0^T f_0\bigl( x(\tau), u(\tau) \bigr) d\tau \\
\end{array}
$

Разбиваем отрезок $ [0,T]$ на $ N$ отрезков с шагом $ h=\frac{T}{N}$. Пусть $ t_k\stackrel{def}{=}kh$

$\displaystyle \frac{ x( t_{k+1} ) - x( t_k )}{h}=f\bigl( x(t_k), u(t_k) \bigr)
$

Пусть $ x_k=x(kh)$,

$\displaystyle x_{k+1}=\widetilde{f}(x_k, u_k)=x_k+h\cdot f(x_k, u_k)
$

$\displaystyle \int\limits_0^T \approx \sum_{i=0}^{N-1} f_0 ( x_i, u_i )h
$

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



На главную   ::   Содержание