Материал: 6251
( )= c n .
Rn c n
Задача, рассмотренная в данном примере, очень простая и она могла быть решена обычными методами. Но этот пример имел целью показать, каким образом данная задача может быть сформулирована как многошаговый процесс оптимизации. Во многих более сложных задачах подобная формулировка часто является ключом к их решению при применении метода динамического программирования.
4 . 4 . 3 . Дискр етный вар иант м ето да динам ическо го про гр амм иро вания
Начать рассмотрение метода динамического программирования про-
ще с дискретного варианта процесса, подлежащего оптимизации. |
|
||
Пусть имеются дискретные возможные значения |
x X ={x1,x2 ,...,xl }. |
||
Время также течет дискретно, шагами t = kT . |
|
|
|
Ставится задача из начального состояния x(k0 ) |
перейти в заключи- |
||
тельное состояние x(k f ) с минимальным показателем качества |
|
||
R(x(k0 ),u(k),k0 )= T ∑k f |
r(x(k),u(k),k), |
(4.4.3) |
|
k=k0 |
|
|
|
то есть найти оптимальную траекторию, соединяющую точку x(k0 ) и точку x(k f ).
256
В критерии (4.4.3) r(x(k),u(k)) – потери от сделанного k-го шага. Например, это могут быть затраты энергии или штраф на k-м шаге.
Поскольку на каждом шаге (а таких шагов N = k f − k0 ) состояние объекта принимает только одно из l значений, то число возможных траекторий конечно и равно lN , и, в принципе, оптимальную траекторию можно было бы найти простым перебором. Однако в реальных случаях это потребовало бы непомерно большого объема вычислений. Метод динамического программирования позволяет резко сократить объем вычислительной работы.
Возьмём некоторую промежуточную точку k j . Показатель качества R
на интервале от k j до k f определяется состоянием объекта x(k j ) и управляющими воздействиями u(k) при k j ≤ k ≤ kf :
R(x(k j ),u(k),k j )= T ∑k f |
r(x(k),u(k),k). |
(4.4.4) |
k=k j |
|
|
Принцип оптимальности означает, что если выражение (4.4.3) минимально, то часть (4.4.4) также должна быть минимальной. Более того, оптимальная стратегия управления u (k) на интервале (kj ,kf ) является только функцией состояния x(k j ), то есть u (k)= gk (x(k j )). Поэтому оптимальное значение критерия (4.4.4) является лишь функцией состояния x(k j ) и самого k j :
R (x(k j ),k j |
)= min ∑k f |
Tr(x(k),u(k),k). |
(4.4.5) |
|
|
u(k) |
k=k j |
|
|
|
|
|
|
257 |
Очевидно, что при k j = k f R (x(k f ),k f )= 0 . Приняв это граничное
условие за исходное, можно воспользоваться уравнением (4.4.5) для вычисления u (k) при попятном движении от k = k f до k = k0 .
Действительно, на шаге k f −1 находим управление u (kf −1), соот-
ветствующее минимальному значению R, то есть, определяем и запоминаем R (x(k f −1),k f −1), которое будет являться функцией значения x в
начале последнего шага. Поиск минимума при этом ведётся только по одной переменной u(k f −1)
|
|
|
|
R (x(k |
f |
−1),k |
f |
−1)= minTr(x(k |
f |
−1),u(k |
f |
−1),k |
f |
−1). |
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
u(k ) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Важно отметить, что и u (k |
f |
−1), и значение R |
зависят от x(k |
f |
−1). |
|||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
Переходим |
|
к |
|
шагу |
|
k f |
|
− 2 . |
|
Оптимальной |
|
стратегией |
|
|
будет |
|||||||||||||||||
{u (k |
f |
|
− 2),u (k |
f |
−1)}, соответствующая |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
R (x(k |
|
−2),k |
|
−2)= minT{r(x(k |
|
−2),u(k |
|
−2),k |
|
−2)+r(x(k |
|
−1),u(k |
|
−1),k |
|
−1)}= |
||||||||||||||||
|
|
f |
|
f |
|
|
|
u(kf −1) |
|
|
f |
|
|
|
f |
|
|
|
f |
|
|
|
f |
|
|
|
f |
|
|
f |
|
|
minT{r(x(kf |
|
|
|
|
u(kf −2) |
|
|
|
|
|
|
|
−1),kf −1)}. |
|
|
|
|
|
|
|
|
|
|
|
||||||||
−2),u(kf |
−2),kf |
−2)+ R (x(kf |
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||
u(kf −2) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Минимизировать приходится всё выражение в фигурных скобках, по-
скольку само |
значение |
x(k f −1) |
зависит |
от u (k f − 2). Минимизация |
|||
опять |
осуществляется |
только |
по |
одной |
переменной, теперь уже по |
||
u (k |
f |
− 2). |
В результате |
получаем |
оптимальное управление |
||
|
|
|
|
|
|
|
|
258 |
|
|
|
|
|
|
|
{u (kf − 2),u (kf −1)}, значение x(k f −1) в конце предпоследнего шага и величину R (x(k f − 2),kf − 2) как функцию x(kf − 2). Заносим её в память
вместо R (x(k f −1),k f −1).
Далее процесс повторяется до тех пор, пока мы не придём в точку, соответствующую k = k0 . А значения x(k0 ) нам известно! Таким образом, определится стратегия оптимального управления
{u (k0 ),u (k0 +1),...,u (kf − 2),u (k f −1)}.
При |
получении |
|
оптимальной |
стратегии |
для |
|
|
вычисления |
||||||||||||||
R (x(k f |
− i),k f − i) |
для каждого узла в момент времени |
|
(kf |
− i)T необхо- |
|||||||||||||||||
димо хранить временно в памяти ЦВМ |
R (x(k |
f |
− i +1),k |
f |
− i +1) |
для мо- |
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
мента времени (kf |
− i +1)T . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
Поскольку R (x(k |
j |
),k |
j |
) не зависит от управления u, уравнение (4.4.5) |
||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
можно переписать в виде |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
k f |
|
|
|
|
|
|
|
|
|
|
),kj |
|
|
||
min Tr(x(kj |
),u(kj ),kj )+ ∑Tr(x(k),u(k),k)− R (x(kj |
) = 0 . |
||||||||||||||||||||
|
u(k) |
|
|
|
|
|
k=k j +1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Последнее уравнение эквивалентно условию |
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
R (x(k |
j |
+1),k |
j |
+1)− R (x(k |
j |
),k |
j |
) |
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
min r(x(kj |
),u(kj ),kj )+ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
= 0 |
. (4.4.6) |
||||
|
|
|
|
|
|
T |
|
|
|
|
|
|
|
|
||||||||
|
u(k) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
259 |