или вектор-строку, полученную в результате его транспонирования, перепишем соотношение (2.1-29) в виде

5 (X {П, Г) = 5 (X (/ + U), / + ДО =

= 5(х(0, 0 + т-f(x(0, u(0. t)Lt +

as(x(0.0 д^ + Оз(Д0. (2.1-30)

Подставим это выражение в правую часть формулы (2.1-26), подразумевая, что х(0 = х'(0. Так как выражения s\x{t), t) и dSdt не зависят от и (О, их можно вынести за знак минимума. Упростив полученное выражение и разделив обе части на Ы, придем к следующему соотношению:

-ъг-=т^ { Jt * (x° it), u it), t)+

+ /o(x(0, u(0, o)+-T (2.1-31)

в котором 04(ДО - остаточный член выше первого порядка малости от При Д^-0 в результате отбрасывания последнего члена в правой части получим уравнение Гамильтона - Якоби (называемое иногда уравнением Гамильтона - Якоби - Белл мана):

#Af(xO(0,u(0, 0 +

aS(x (0, t) - .у = mm dt ueu

+ /o(x (0, 11(0, о}- (2.1-32)

Это дифференциальное уравнение в частных производных является основным уравнением динамического программирования для непрерывных систем. Интересно отметить, что в результате минимизации правая часть соотношения (2.1-32) становится независимой от вектора u(t), в то время как само соотношение выполняется только для оптимального вектора u(t). Дифференциальное уравнение Гамильтона - Якоби часто используют в следующей форме:

dSixit). t) dSix4.t) j(o(,) о(,), +

-bfo(x (0, uO(0, О- (2.1-33)

Используя определение полной производной, это уравнение можно записать в виде

i 4-/о (X (0. (0. О = 0. (2.1-34)

Аналогично уравнение динамического программирования (2.1-32) иногда используют в форме соотношения

Kf- +/о (х- {i), u it), t)] = 0. (2.1-35)

min еиУ

Уравнение Гамильтона - Якоби как достаточное условие динамического программирования. Из доказательства, основанного на использовании функционального уравнения Беллмана, следует, что полученное в форме (2.1-32) или (2.1-35) уравнение Гамильтона - Якоби определяет необходимое условие оптимальности. Покажем теперь, что при определенных предположениях достаточное условие можно сформулировать аналогичным образом.

Пусть время Т свободно и конечное состояние х(Г) принадлежит некоторому множеству цели С. Для открытой области X пространства состояний определим функцию 5(х, t), удовлетворяющую следующим условиям:

1. Частная производная - непрерывная функция векторного аргумента х и времени t. Функция gradS=dS/dx является кусочно-непрерывной функцией векторного аргумента х и временя t. Для произвольного момента времени tTo, в котором одна из функций dS/dx или f{x, и, t) (или обе эти функции) претерпевает разрыв, выполняется следующее условие:

lim f=lim f. (2.1-36)

t-s.To+ ox tTo- ox

2. Для любого вектора x из открытой области X пространства состояний и произвольного момента времени i гамильтониан И = М(дЗ/дх, X, u, i) достигает абсолютного минимума при условии, что допустимое управление оптимально:

0 = M{dSldx, X, цо, t)<M(dS/dx, х, и, t). (2.1-37)

В этом случае говорят, что гамильтониан Н нормален по отношению к области X. Предполагается также, что вектор оптимального управления и (i) порождает единственную оптимальную траекторию x°(t).

3. На множестве цели С величина 5(х, )=0. Если условия 1, 2 и 3 выполняются, то

т

Six it), t) = min J /о(х(т), u(t), x)d. (2.1-38)

ueUi

Таким образом, в этом случае функция S(x, t) является минимумом по U результата интегрирования целевой функции /о(х, U, t) по переменной времени в промежутке от / до Т. Опти-

мальное управление uC переводит систему из начального состояния х(0) в конечное состояние x(t) С вдоль оптимальной траектории x°(t). Оказывается, что управление и^С^ в точности совпадает с решением функционального уравнения Гамильтона-Якоби.

Для доказательства этой теоремы запишем условия 1 и 2 в следующем виде:

/о(х, U, t) + (X, u, t) + >

>/o(x, uO, 0 + f (X, uO, i) + = 0.

(2.1-39)

Интегрируя правую часть этого неравенства вдоль оптимальной траектории x°(t), получим

/о(х ,иО)-Ь

Й5(х . х)

f(xO, цо, т) +

dS (х°, t)

dx = 0. (2.1-40)

Рассмотрим теперь интеграл

J(t) = J [/ (X. U, х) + Цх, U. х) +

dx. (2.1-41)

Докажем, что только и и х могуг минимизировать интеграл J(t) и что, как следует из выражения (2.1-40), абсолютный минимум этого интеграла равен нулю. Допустим, что это не так. Тогда найдутся управление u(t)u°(t) и траектория (t) фх(() такие, что при любом t интеграл J(t) будет равен нулю Отсюда получим, что для интеграла с переменным нижним пределом интегрирования рассматриваемое подынтегральное выражение тождественно равно нулю. Но из неравенства (2.1-39) следует, что подынтегральное выражение всегда положительно. Таким образом, не существует управления и траектории, отличных от и и х и удовлетворяющих заданным требованиям.

Пример. В примере, принадлежащем Розоноэру [20], метод динамического программирования применяется для системы дифференциальных уравнений

и целевой функции

Xi = UXi + х^ =/i, /о =/о(*ь Х2).

Основное уравнение динамического программирования запишется в виде

[ж+ + и' + /о(х„ X,)}.

Если предположить, что dSjdx2 > О, то можно найти управление и, при котором выражение в скобках достигает минимума. Из необходимого условия минимума

d du

dS . dS

найдем оптимальное управление

~ 2-1 dSldxo

Преобразовывая, получим нелинейное дифференциальное уравнение в частных производных

dt ~ dxi 4 sjdXi -гЛ

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

/ = ср (л:, (П 2 (Т)) + о (Xi (&), Х2 (&)) db

граничное условие записывается в виде S{Xi(T), Х2(Т)) = = (p(xi(T), Х2(Т)) и не зависит от и. Если система автономна и целевая функция не зависит явно от времени t, тогда и функция S не зависит от времени и dS/dt=0 (разд. 2.2). В этом случае, как правило, задача разрешима в дискретном виде, а решение дифференциального уравнения в частных производных находится с помощью рекуррентной формулы (2.1.-16). Иногда эту задачу удается решить, применяя аналитические методы разложения в ряд [20J.

2 2. СВЯЗЬ МЕТОДА ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ С ПРИНЦИПОМ ПОНТРЯГИНА

Принцип минимума Понтрягина можно вывести из дифференциального уравнения Беллмана [20]. Вместо переменной t будем рассматривать координату Хп+и заданную дифференциальным уравнением

=/ +1 = 1. (2.2-1)

и будем использовать обозначение dS/dx+y вместо dS/dt. Отметим, что для автономной системы вектор-функция f и целевая функция /о не зависят явно от времени t и / [ = 0, . +1 = 0. dS/dx +i = 0 и dS!dt = 0. Таким образом, в этом случае нет необходимости вводить новую переменную л: +1.

Введем еще одну координату Хо с помощью дифференциального уравнения

(2.2-2)

Если ср{х(Т), Т)=0, то задача минимизации функционала / вида (2.1-7) эквивалентна минимизации координаты Хо(Т). Введем векторы

~ т

X = [Xq, Xi, . . . , х^, An+il >

и

dS dS dS

(2.2-3) (2.2-4)

dx dXn+i .

= --4).

(2.2-5)

Используя обозначение

5 - S{xq, Xi, ... , л: , xi) - S(xi, x, ... , x, x i) + Xf,

(2.2-6)

перепишем равенство (2.2-5) в виде

dS dx

dS dS

dXo dxi

dx dx

n+lJ

(2.2-7)

(2.2-8)

Минимум положительной функции равен взятому с противоположным знаком максимуму совпадающей с ней по модулю отрицательной функции. Поэтому в результате несложных преобразований дифференциальное уравнение Гамильтона - Якоби можно записать в виде

О = min {pf} = - max

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

Введем теперь гамильтоновские функции состояния Hp и

.... НррЧ Hi, Нр = -Н^. (2.2-9)

В этом случае из равенства (2.2-8) получим, что О = min Н„ и О = max Н^.

(2.2-10)

Последние два уравнения идентичны соотношениям принципов минимума и 1иаксимума Понтрягина. Отсюда можно получить следующие выводы.

Во-первых, если оптимальный процесс существует, то для произвольного момента t оптимальное управление и (/) можно определить, решая задачу минимизации Hp или максимизируя Щ.

Отметим, что зависимость функций Hp и Н^от вектора управления и определяется зависимостью вектор-функции f от и. Так как компоненты векторов-функций р и ii являются частными производными известной по предположению функции Sjx(t), t), то для любой точки X можно найти гамильтонианы Н'р и Н' в функции векторного аргумента и (при этом частные производные следует определять вдоль оптимальной траектории) .

Во-вторых, минимум Hp и максимум Яф равны нулю в любой точке оптимальной траектории. Геометрически равенство (2.2-7) означает, что вектор 1р совпадает с градиентом

p = grad5= = - (2.2-11)

и как следствие хорошо известной теоремы получим отсюда ортогональность этого градиента к изоповерхностям S = const. Итак, в соответствии с принципом Понтрягина требуется выбрать вектор управления и таким образом, чтобы минимизировать проекцию вектора скорости

x = f (2.2-12)

на нормаль к изоповерхности S=const (или максимизировать эту проекцию на вектор отрицательной нормали), точнее обра тить эту проекцию в нуль. Следовательно, градиент функции S вдоль оптимального движения системы ортогонален в /г4-2-мерном пространстве состояний к вектору касательной x=f.

В-третьих, основное уравнение динамического программирования (2.1-32) можно представить в виде

+ Я = О, (2.2-13)

где

Яо=тшЯ =-тах ф, (2.2-14)

= * +/о Р * +/о - - т-/о) = - Я (2.2-15)

f, X, dS/dx, р, 15 -векторы размерности п (с нумерацией координат от 1 до п).

Основное и существенное преимущество принципа Понтрягина состоит в том, что при его применении не требуется решать сложного дифференциального уравнения динамического про-

граммирования, заданного в частных производных относительно функций S или S; при этом достаточно найти соответствующие оптимальной траектории решения р=- или р=-вспомогательной системы обыкновенных дифференциальных уравнений.

Пример. Рассмотрим неавтономную систему, для которой цель оптимизации состоит в получении наименьшего времени перехода. В рассматриваемом случае /о= 1 и dS/dt=0. Из соотношения (2.2-13) получим

uqU [ dx

или с учетом равенства (2.2-15)

= О, (2.2-16)

min N = 0, max = 0. (2.2-17)

Из соотношения (2.2-16) следует, что в п-мерном пространстве состояний вектор производной dS/dx не ортогонален к касательной x=f: вдоль оптимального движения системы скалярное произведение этих векторов равно -1. Для рассматриваемой задачи

т

S (х (t), t) = min J 1 rfx = 70 (2.2-18)

U£Ut

где P -минимальное время перехода. С возрастанием времени t величина 5 убывает. Уравнению S(xO(t), O = const удовлетворяют изоповерхности х=Т^ - 1 = const, которые окружают точку хСГ); вектор р направлен из области, а вектор if внутрь области, ограниченной изоповерхностью. В работе [21] эти изоповерхности названы поверхностью изохроны. Согласно принципу оптимальности динамического программирования, а также принципу Понтрягина, проекция вектора скорости х на р минимальна, а его проекция на вектор равна максимуму (рис. 2.5-1). Физически это очевидно. Любое движение по поверхности изохроны не дает вьпгрыша, так как из любой точки этой поверхности в конечное состояние х(Г) можно попасть за одно и то же время. Чем больше скорость движения, направленного по нормали к поверхности изохроны, тем скорее будет достигнута поверхность следующей изохроны, а следовательно, и конечная точка.

2..3. СВЯЗЬ МЕТОДА ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ С ВАРИАЦИОННЫМ ИСЧИСЛЕНИЕМ

Допустим, что целевая функция зависит также от вектора скорости. Запишем основное уравнение динамического програм-

мирования (2.1-32) в несколько менее общем виде:

dS (xV). t) dS (xV). t) o() /jx (), i (0, u (/)) = 0, (2.3-1)

где u() - вектор оптимального управления, a x () = /(xo(), (/), )-скорость изменения состояния под действием управления и'(/).

Допустим, что ограничения на вектор и отсутствуют, т. е. множество и совпадает со всем пространством размерности г. Необходимость в таком условии объясняется тем, что р вариационном исчислении на вектор управления не накладывается ограничений. Продифференцируем левую часть соотноиления (2.3-1) по вектору скорости х=х (/). Для простоты записи опустим обозначения независимых переменных. Первый член в соотношении (2.3-1) не зависит от х, в то время как второй член этого выражения можно записать в виде x (d5/6x). Отсюда и из равенства (дх/дх) =1 получим, что

-g+=0, k = (2.3-2)

В сокращенных обозначениях первоначальное уравнение (2.3-1) можно записать в следующем упрощенном виде:

:Х-ь/о = 0, х = х , х = х . (2.3-3)

ахТ

Запишем полную производную функции, стоящей в левой части равенства (2.3-2), по аргументу t

dtdx

+ x-b4f) = 0. (2.3-4)

дхдх [дх )

Частная производная по x для левой части равенства (2.3-3) имеет вид

dxdt йхбхТ дх

Сравнив два последние равенства, придем к уравнению Эйлера-Лагранжа в вариационном исчислении

---(j = 0, х = х , i-io. (2.3-6)

(Это соотношение получено в предположении непрерывности всех частных производных второго порядка.)

Допустим, что в конечный момент времени Т выполняется соотношение

(2.3-7)

Тогда с учетом равенства (2.3-2) получим из соотношения (2.3-3) следующее условие:

или

[i{T)-k(T)V

dfo дх

+ /о

= 0,

(2.3-8) (2.3-9)

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

(2.3-10)

в точке х=х'. Действительно, взяв частную производную выражения (2.3-10) по векторной переменной х и приравняв ее нулю, придем к условию (2.3-2). Дифференцируя вторично и принимая во внимание, что частные производные второго порядка от первого слагаемого в выражении (2.3-10) равны нулю, получим еще одно необходимое условие минимума для выражения (2.3-10), которое состоит в положительной определенности матрицы частных производных второго порядка

дЧо

(2.3-11)

от функции /о по переменной х. В одномерном случае будем иметь

>0. (2.3-12)

дх i=io

Неравенства (2.3-11) и (2.3-12) совпадают с условием Лежанд-ра в вариационном исчислении.

Во-вторых, если экстремум совпадает с абсолютным минимумом, то неравенство

/о(х, i, t) + ix >/о(х, хО, t) + -хо (2.3-13)

выполняется для любых

хфх^. (2.3-14)

Преобразуем соотношение (2.3-13) к виду

/о(х, X, t) -/о (х, х , i) + 1 [X - i ] > 0. (2.3-15)

Подставляя в это выражение условие экстремума (2.3-2), получим, что

/о(х, X, t) -/о(х, хО, i) -°(- f-) (к - хО) > 0. (2.3-16)

Последнее неравенство совпадает с условием Вейерштрасса из вариационного исчисления.

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

Sixit), t) = Si{xit)) + (T-t)So,

в котором 5о - постоянная величина. Следовательно, уравнения (2.3-2) и (2.3-3) не зависят от t:

°+/о-5о = 0.

Из последних двух уравнений получим дифференциальное уравнение для определения оптимальной траектории:

xO{t)= .

dfoldxo

С Другой стороны, уравнение Эйлера-Лаграннса в вариационном исчислении дает

дхо dt

,дхо )

Полная производная по времени от целевой функции fo=fo(x, О определяется равенством

/о /о , Ло I уО dt - dt дхо^

или

dfo dfo

dt dt