Динамическое программирование

Динамическое  программирование

 

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

 

= + F(x₁, t₁), x' = f(x(t), u(t), t), 

x(t₀) = x₀, x(t₁) = x₁, {u(t)}ÎU.      (1)

 

Сущность подхода динамического  программирования состоит в следующем: данная конкретная задач управления "погружается" в более широкий  класс задач, которые характеризуются рядом параметров; затем с помощью центрального принципа – "принципа оптимальности" – определяется основное рекуррентное соотношение, связующее задачи из этого класса. Если выполнены некоторые дополнительные предположения относительно гладкости участвующих в рассмотрении функций, то из главного рекуррентного соотношения вытекает основное дифференциальное уравнение в частных производных – уравнение Беллмана, - решая которое можно найти решение вышеупомянутого широкого класса задач.

Вслед за этим, как частный случай, определяется и решение данной конкретной задачи.

 

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

Формулировка принципа оптимальности:

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

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

   x (фазовая координата)

x(t₁)        ^x*(t)

²

x(t)

   ¹

x(t₀)

    t₀        t        t₁  t (время)

 

На рисунке дана иллюстрация  принципа на примере задачи с одной фазовой координатой. Кривая x*(t) (t₀£t£t₁) – это фазовая траектория, соответствующая оптимальному управлению, начальное и конечное состояния – фиксированы. Вся траектория поделена на две части относительно момента времени t. Согласно принципу оптимальности, траектория 2, определенная при t£t£t₁, должна представлять собой оптимальную траекторию по отношению к начальному состоянию x(t). Следовательно, вторая часть оптимальной траектории сама по себе должна быть оптимальной траекторией, вне зависимости от того, что происходило с системой до того, как она пришла к состоянию, являющемуся начальным для второй части траектории.

Предположим, что общая  задача управления (1) имеет решение.

Максимальное значение целевого функционала задачи с начальным состоянием  x и начальным временем t

J*(x, t)

назовем функцией оптимального поведения.

Отметим, что в то время  как J представляет собой функционал, зависящий от {u(t)}, J* является функцией, зависящей от n+1 параметров x и t.

Таким образом, задача оказывается "погруженной" в более широкий класс задач, характеризуемых значениями n+1 начальных параметров. Оптимальной значение целевой функции исходной задачи (1) имеет, таким образом, вид

J* = J*(x₀, t₀).

Если J*(x, t) является функцией оптимального поведения для задачи с начальным состоянием x в момент t, то, согласно принципу оптимальности J*(x+Dx, t+Dt) является функцией оптимального поведения для второй части оптимальной траектории с начальным моментом времени t+Dt и начальным состоянием x+Dx. Поскольку прирост функции оптимального поведения на протяжении всего промежутка времени между t и t+Dt может происходить только за счет изменения подынтегральной функции, то он равен I(x,u,t)Dt. Значения функции оптимального поведения на всем интервале времени, начавшимся в момент t, представляют собой оптимальную сумму вкладов двух частей этого интервала времени. Таким образом, приходим к основному рекуррентному соотношению

 

J*(x, t) = {I(x, u, t)×Dt  + J*(x+Dx, t+Dt)} (2)

 

В динамическом программировании существенную роль играет предположение, что функция оптимального поведения J*(x, t) представляет собой однозначную и непрерывно дифференцируемую функцию от n+1 переменных. Иначе говоря, решения задач более широкого класса являются однозначными и непрерывными функциями относительно изменений начальных параметров. (Отметим, что во многих задачах эти предположения о гладкости не выполняются, кроме того, заранее вообще неизвестно, будут ли они выполнены в данной конкретной задаче).

Благодаря этому предположению  можно разложить J*(x+Dx, t+Dt) в точке (x, t) по формуле Тейлора:

 

J*(x+Dx, t+Dt) = J*(x, t) + Dx + Dt + …  (3)

 

где - это вектор-строка

= ( , , …, ).

 

Подставляя (3) в (2) и проводя  элементарные преобразования, получаем

0 =

{I(x, u, t) + + + … }.

Переходя к пределу  при Dt ® 0 с учетом того, что

= x' = f(x, u, t),

получаем 

 

- = {I(x, u, t) + f(x, u, t)}.  (4)

 

Уравнение (4) называется уравнением Беллмана и является основным дифференциальным уравнением в частных производных, используемых в динамическом программировании.

Так как второе слагаемое в (4) представляет собой скалярное произведение вектора-строки и вектора-столбца f(x, u, t), то уравнение Беллмана можно записать как

-

= {I(x, u, t) + f_j(x, u, t)}.

С уравнением Беллмана связано  в качестве граничного условия ограничение, налагаемое на конечное состояние:

J*(x(t₁), t₁) = F(x₁, t₁).

Это условие показывает, что значение функции оптимального поведения для задачи, начальным моментом и начальным состоянием которой являются соответственно конечный момент и конечное состояние, равно значению функции F, рассчитанному в данный момент времени при данном состоянии.

Если бы уравнение Беллмана было решено, то мы получили бы функцию оптимального поведения и, следовательно, оптимальное значение целевой функции для исходной задачи можно было бы определить как частное значение этой функции при указанных в формулировке задачи конкретных начальных условиях. Однако в общем случае это уравнение в частных производных первого порядка, как правило, нелинейное, не имеет аналитического решения. В принципе можно решать уравнения Беллмана, представленные в виде разностных схем, на ЭВМ с большим быстродействием. Однако даже современные ЭВМ, работающие с высокой скоростью счета, не обладают такой машинной памятью, которая позволяла бы найти достаточно хорошее приближение к решению даже при не очень больших размерностях. Беллман назвал это препятствие "проклятьем размерности" ("curse of dimensionality").

 

Решение многошаговых задач  оптимизации методом

динамического программирования

 

Во многих динамических задачах  время рассматривается не как непрерывная, а как дискретная величина. Задачи такого типа называются многошаговыми задачами оптимизации. Они могут решаться методом динамического программирования.

Рассмотрим некоторую динамическую систему S.

Пусть на k-м шаге (k = 1, 2, ..., n) состояние  системы определяется совокупностью  чисел (фазовыми координатами)  X =( ), которые получены в результате реализации управления U_k, обеспечивающего переход системы S из состояния X в состояние X . Будем полагать, что X зависит от X и U_k и не зависит от того, как система пришла в состояние X (свойство отсутствия последействия).

Пусть W_k(X , U_k) есть доход (выигрыш), полученный в результате реализации k-го шага. Тогда общий выигрыш полагаем равным

F = W_k(X , U_k)

(свойство аддитивности целевой функции).

Совокупность управлений U = ( , , ... , ), в результате реализации которых система S переходит за n шагов из начального состояния X⁰ в конечное X и при этом функция F принимает наибольшее значение, будем называть оптимальной стратегией управления.

Принцип оптимальности  Беллмана.

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

Оптимальную стратегию можно получить, если сначала найти оптимальную  стратегию управления на последнем n-м шаге, за тем на двух последних шагах и т.д. вплоть до первого шага.

Таким образом, решение задачи динамического  программирования целесообразно начинать с определения оптимального решения на последнем n-м шаге.

Для того, чтобы найти  это решение, нужно сделать всевозможные предположения о том, как мог закончиться предпоследний шаг и с учетом этого выбрать управление , обеспечивающее максимальное значение функции W_n(X , U_n). Такое управление , выбранное при определенных предположениях о том, как окончился предыдущий этап, называется условно оптимальным.

Принцип оптимальности  Беллмана требует находить на каждом шаге условно оптимальные управления для любого из возможных исходов предыдущего шага.

Обозначим через F_n(X⁰) максимальный доход, получаемый за n шагов при переходе системы S из начального состояния X⁰ в конечное состояние X , а через F_n-k (X ) - то же при переходе из X в X и оптимальном управлении на последних n-k шагах.

Тогда  

 

F_n(X⁰) =

[W₁(X⁰, U₁) + W₂(X¹, U₂) + ... + W_n(X , U_n)],

F_n-k(X⁰) = [W_k+1(X , U_k+1) + F_n-k-1(X )],

 

Последнее соотношение  называется основным функциональным уравнением Беллмана и представляет собой математическую формулировку принципа оптимальности.

Положим  k = n - 1. Тогда 

 

F₁(X ) = [W_n(X , U_n) + F₀(X )],   (*)

 

где F₀(X ) считаем известным.

Используя (*) и рассматривая всевозможные допустимые состояния X , X , ... , X , ... , системы на (n-1)-м шаге находим условно-оптимальные управления (X ), (X ), ... , (X ), ... , и соответствующие значения функции (*):

(X ), (X ),..., (X ), ... .

Таким образом, на n-м шаге находим условно-оптимальное управление при любом допустимом состоянии системы после (n-1)-го шага. Т.е., в каком бы состоянии система не оказалась после (n+1)-го шага, нам уже известно, какое следует принять решение на n-м шаге. Известно и соответствующее значение функции (*).

Переходим к рассмотрению функционального уравнения при k = n - 2.

 

F₂(X ) = [W_n-1(X , U_n-1) + F₁(X )],  (**)

 

Для того, чтобы найти  значение F₂ для всех допустимых значений X , очевидно, необходимо знать W_n-1(X , U_n-1) и F₁(X ). Но F₁(X ) мы уже определили на предыдущем шаге. Поэтому нужно произвести вычисления для W_n-1(X , U_n-1) при некотором наборе допустимых значений X и соответствующих управлений U_n-2. Эти вычисления позволят определить условно оптимальное управление U для каждого X . Каждое из таких управлений совместно с уже выбранным управлением на последнем шаге обеспечивает максимальное значение дохода на двух последних шагах.

Последовательно осуществляя  этот итерационный процесс, дойдем, наконец, до первого шага. На этом шаге нам известно, в каком состоянии может находиться система (в начальном). Поэтому уже не требуется делать предположения о допустимых состояниях системы, а остается лишь только выбрать управление, которое является наилучшим с учетом условно оптимальных управлений, уже принятых на всех последующих шагах.

Таким образом, в результате последовательного прохождения всех этапов от конца к началу определяем максимальное значение выигрыша за n шагов и для каждого из них находим условно оптимальное управление.

Чтобы найти оптимальную  стратегию управления, то есть определить искомое решение задачи, нужно  теперь пройти всю последовательность шагов, только на этот раз от начала к концу. А именно - на первом шаге в качестве оптимального управления возьмем найденное условно оптимальное управление U . На втором шаге найдем состояние X , в которое переводит систему управление . Это состояние определяет условно оптимальное управление U (X ), которое теперь будем считать оптимальным ( ). Зная , находим X = (X ), а значит - определяем = U (X ), и т.д. В результате этого находим решение задачи, то есть максимально возможный доход и оптимальную стратегию управления U^*, включающую оптимальные управления на отдельных шагах ( , , ... , ).

Таким образом, мы рассмотрели нахождение решения задачи динамического программирования в общем виде. Этот процесс является довольно громоздким, поэтому он используется обычно с применением ЭВМ. Отметим также, что изложена только идея, которая должна быть реализована в том или ином виде для каждого частного случая и далеко не всегда очевидно, как это сделать.

 

 

Задача о  минимизации расхода горючего самолетом

при наборе высоты и скорости

 

Пусть самолет, находящийся  на высоте Н₀ и имеющий скорость V₀ должен подняться на высоту Н_k н иметь скорость V_k. Известен расход горючего при подъеме самолета с любой высоты H₁ на любую высоту Н₂ > Н₁ при постоянной скорости, а также расход горючего при увеличении скорости от любого значения V₁ до любого значения V₂ > V₁ при неизменной высоте.