ОиАС-5
.pdf1 Лекция 5
2.3. Метод динамического
программирования
2
В послевоенные годы наряду с задачами оптимального управления в технике возникли задачи об оптимальном управлении в экономике, управлении войсками и т. д. (задачи об управлении запасами, ресурсами, составление расписаний, организация тыла). Они не допускали эффективного численного решения на основе существующих методов. Это привлекло внимание математиков к этим задачам. При этом обнаружилось, что процесс решения многих из них может быть представлен как некоторый многоплановый процесс принятия решений. Эта концепция получила название метода динамического программирования, что означает принятие решений во времени.
Основу метода динамического программирования, разработанного американским математиком Р. Беллманом, составляет принцип оптимальности, используя который выводят функциональное уравнение метода. Решение этого уравнения приводит к синтезу оптимального управления.
Принцип оптимальности
3
Рассмотрим задачу об оптимальном стабилизирующем управлении. |
|
Пусть дан объект управления, описываемый уравнениями |
|
x = ϕ(x,u,t) |
(2.3.1) |
Требуется найти закон управления |
|
u = r(x, t), |
(2.3.2) |
чтобы на движениях системы (2.3.1), (2.3.2), возбужденных произвольными начальными отклонениями, минимизировался функционал
|
J = ∫t1 ϕ0 (x,u,t)dt |
(2.3.3) |
|
|
t0 |
|
|
При этом на управления (2.3.2) наложены ограничения u U. Для определенности |
|||
часто будем полагать, что |
|
|
|
–u |
* ≤ u (t) ≤ u *, |
(2.3.4) |
|
k |
k |
k |
|
где uk* (k=l, …, m) – заданные числа.
Отметим, что эта задача является вариационной задачей со свободным правым концом и фиксированным t1.
Для простоты изложения принципа оптимальности ограничимся частным случаем этой задачи, когда n=2, а m=1. В этом случае уравнения (2.3.1) и (2.3.2) примут вид:
x1 =ϕ1 (x1 , x2 ,u,t); |
(2.3.1') |
|
x2 =ϕ2 (x1 , x2 ,u,t); |
||
|
||
u = r(x1, x2, t) |
(2.3.2') |
|
а функционал (2.3.3) запишется, если опустить для простоты t в φ0, как |
|
|
J = ∫t1 ϕ0 (x1 , x2 ,u)dt |
(2.3.3') |
|
t0 |
|
4
Переходя к принципу оптимальности, допустим, что оптимальное управление (2.3.2) найдено. Этому управлению соответствует оптимальная траектория x1(t), x2(t), которую можно вычислить, подставляя в уравнения (2.3.1) функцию (2.3.2) и интегрируя (2.3.1) при некотором начальном условии x1(t0), x2(t0).
Отметим какую-либо точку х' на оптимальной траектории и назовем участок между точкой х(0)= {x1(t0), x2(t0)} и точкой х'= {x1(t'), x2(t')} первым (траектория 1), а участок между точками х'= {x1(t'), x2(t')} и х(1)= {x1(t1), x2(t1)} назовем вторым участком траектории (траектория 2).
5
Функциональное уравнение метода
динамического программирования
7
Несмотря на почти очевидный, эвристический характер принципа оптимальности, он имеет своим следствием далеко не очевидное функциональное уравнение. Переходя к его выводу, введем обозначения для значений функционала на оптимальных траекториях:
t
v[x1 (t0 ), x2 (t0 ),t0 ]= minu (t )<u* t∫1 ϕ0 (x1 (t), x2 (t),u(t))dt;
0
t1
v[x1 (t′), x2 (t′),t′]= minu (t )<u* ∫t′ ϕ0 (x1 (t), x2 (t),u(t))dt
Представим (полагая t' = t0 + τ; τ – достаточно малое число) функционал (2.3.3') в форме
t0∫+τϕ0 (x1 (t), x2 (t),u(t))dt + ∫t1 ϕ0 (x1 (t), x2 (t),u(t))dt
t0 |
t0 +τ |
Допустим, что оптимальное управление на втором участке известно. Значение, которое принимает функционал оптимизации при движении по этому участку, определяется выражением v[x1(t')x2(t')]. На основе принципа оптимальности можно записать функциональное уравнение
v[x1 (t0 ), x2 (t0 ),t0 |
]= |
|
|
min* |
t0∫+τϕ0 (x1 (t), x2 (t),u(t))dt +v[x1 (t0 |
+τ), x2 (t0 |
+τ),t0 |
+τ] |
||||||||||||||||||||||
|
||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
u (t0 )<u |
t0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
Учитывая малость τ, получим |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
v[x |
(t |
|
), x |
(t |
|
),t |
]= min |
{ϕ |
(x |
(t |
|
), x |
(t |
|
),u(t |
|
))τ +v[x |
(t |
|
+τ), x |
(t |
|
+τ),t |
|
+τ]} (2.3.5) |
|||||
1 |
|
0 |
2 |
|
0 |
0 |
|
|
|
u (t0 ) |
|
<u* |
0 |
1 |
|
0 |
2 |
|
0 |
|
0 |
1 |
|
0 |
2 |
|
0 |
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Минимизируя выражение в фигурных скобках по u(t0), получим оптимальное управление на первом участке. Однако в этом выражении функция v неизвестна. В связи с этим преобразуем (2.3.5).
8
Используя разложение в ряд Тейлора, получим
x |
(t |
|
|
|
+τ)= x |
(t |
)+ |
∂xi |
|
|
|
|
|
|
τ |
+o |
|
(τ) |
= x (t |
|
|
) |
+ϕ |
|
[x (t |
|
), x |
(t |
|
),u |
(t |
|
),t |
|
]τ +o |
(τ) (i |
||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
i |
|
0 |
|
|
|
|
|
|
|
|
|
|
i |
|
0 |
|
|
|
|
∂t |
|
t=t0 |
|
|
|
|
1i |
|
|
|
|
|
|
i |
0 |
|
|
|
|
|
i |
|
|
1 |
|
0 |
2 |
|
0 |
|
|
|
0 |
|
0 |
1i |
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
lim |
o1i (τ) |
→ 0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
τ→0 |
|
|
τ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
v[x (t +τ), x |
|
(t +τ),t +τ]= v |
x1 (t0 )+ϕ1 |
[x1 (t0 ), x2 (t0 ),u(t0 ),t0 ]τ +o11 (τ), |
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
1 |
|
0 |
|
|
|
|
|
|
2 |
|
|
0 |
|
|
|
|
|
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
x (t )+ϕ |
|
[x (t ), x (t ),u(t ),t |
|
]τ +o (τ),t +τ |
||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
0 |
|
|
|
|
2 |
|
|
|
1 |
0 |
|
|
2 |
|
|
0 |
|
|
0 |
0 |
|
|
|
|
12 |
0 |
|
|||
= v[x |
|
(t |
|
), x |
(t |
|
),t |
|
]+ |
|
∂v |
|
|
|
|
|
|
ϕ |
[x |
(t |
|
), x |
(t |
|
),u |
(t |
|
),t |
|
]τ + |
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
∂x1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||
|
|
|
1 |
|
|
0 |
|
|
2 |
|
|
|
0 |
|
|
0 |
|
|
|
|
|
tx==t0x (t |
) |
|
|
1 |
|
1 |
|
0 |
2 |
|
|
|
|
|
0 |
|
|
|
0 |
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x2 |
=x2 |
(t0 ) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
+ |
∂v |
|
|
|
|
|
|
ϕ |
2 |
[x |
(t |
0 |
), x |
|
(t |
0 |
),u(t |
0 |
),t |
0 |
]τ |
+ ∂v |
|
|
|
|
|
|
|
τ +o |
|
(τ) |
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||
|
∂x2 |
|
tx==t0x |
|
|
|
|
|
1 |
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
∂t |
|
|
tx=1=t0x1 (t0 ) |
|
|
|
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||
|
|
(t |
) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
1 |
|
1 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x2 =x2 (t0 ) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
x2 =x2 (t0 ) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
lim |
o3 (τ) |
→ 0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
τ→0 |
τ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
=1,2)
=
9
Подставляя эти выражения в (2.3.5), получим
|
|
|
|
|
|
|
|
|
|
|
|
ϕ |
[x (t |
|
), x |
(t |
|
),u(t |
|
)]τ +v[x |
(t |
|
), x |
(t |
|
),t |
]+ |
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
1 |
|
0 |
2 |
|
|
0 |
|
0 |
|
|
1 |
|
0 |
2 |
|
0 |
0 |
|
|
|
|
|
|
|||
v[x1 (t0 ), x2 (t0 ),t0 ]= umin(t0 )≤u* +∑ ∂v |
|
|
|
ϕi [x1 (t0 ), x2 (t0 ),u(t0 ),t0 ]τ + ∂v |
|
|
|
|
τ +o3 (τ) |
|||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
i=1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
∂t |
tx==t0x |
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
∂x |
|
t=t0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(t |
) |
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
i |
|
x =x (t ) |
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
0 |
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
i i |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x2 |
=x2 (t0 ) |
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
Сокращая v[x1(t0), x2(t0), t0] в обеих частях равенства и поделив результат на τ, |
||||||||||||||||||||||||||||||||||||||||
получим при τ → 0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
− ∂v |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
∂v |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
= |
|
min* ϕ0 |
[x1 |
(t0 ), x2 |
(t0 ),u(t0 )]+∑ |
|
|
ϕi |
[x1 (t0 ), x2 (t0 ),u(t0 ),t0 ] |
|||||||||||||||||||||||||||||
|
|
|
∂xi |
|
|
|||||||||||||||||||||||||||||||||||
|
|
|
|
|
||||||||||||||||||||||||||||||||||||
∂t |
|
tx=1=t0x1 (t0 ) |
|
|
u (t0 )≤u |
|
|
|
|
|
|
|
|
|
|
|
i=1 |
|
t=t0 |
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
|
|
x2 =x2 (t0 ) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
xi =xi (t0 ) |
|
|
|
|
|
|
|
|
|
|
|
||||
Учитывая, что полученный результат справедлив для любых x1(t0), x2(t0), t0, |
||||||||||||||||||||||||||||||||||||||||
опустим индекс «0» и запишем |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
− ∂v[x1 (t), x2 (t),t]= |
|
min* ϕ0 [x1 (t), x2 (t),u(t)]+∑2 ∂v[x1 (t), x2 (t),t]ϕi [x1 (t), x2 (t),u(t),t] |
||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||
|
|
∂t |
|
|
|
|
|
u (t |
)≤u |
|
|
|
|
|
|
|
|
|
|
|
|
|
i=1 |
|
|
∂xi |
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(2.3.6)
10