2. Теорема В. Г. Болтянского для задачи о быстродействии.

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

Лемма 1. Предположим, что на некотором открытом множестве D пространства X задана непрерывная и непрерывно дифференцируемая функция , удовлетворяющая для всех неравенству вида (8)

(15.13)

Тогда если — допустимое (то есть ) управление, переводящее изображающую точку из положения в положение , причем соответствующая траектория расположена целиком в множестве D, то время перехода из точки в точку оценивается неравенством

Доказательство. Пусть — точки, в которых управления терпят разрыв, причем

Обозначим еще

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

На каждом из интервалов функция непрерывна.

Согласно (8) и (1)

(15.15)

Внутри каждого из интервалов времени функция непрерывна и в соответствии с условием леммы имеет непрерывную производную по , удовлетворяющую неравенству (15)

Отсюда следует, что

Складывая левые и правые части этих соотношений, написанных для интервалов , получим

что совпадает с соотношением (14). Таким образом, лемма доказана.

Так как прибавление любой константы к функции не изменяет соотношения (8), то можно принять, что функция удовлетворяет условию

(15.16)

При этом неравенство (14) примет вид

(15.17)

Заметим теперь, что соотношение (7), представляющее собой уравнение Беллмана в задаче о быстродействии, было получено выше как необходимое условие оптимальности.

Здесь, при тех же предположениях о непрерывности и непрерывной дифференцируемости функции и условии , доказано, что если соотношение (8) имеет место, то управление, переводящее систему из точки в точку за время , является оптимальным.

Как следует из (17), быстрее осуществить этот переход невозможно. Следовательно, здесь показано, что соотношение (7) является достаточным условием оптимальности.

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

Рис. 15.1.

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

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

Можно показать (см. ниже стр. 285), что дуга АО (рис. 15.1) параболы и дуга OB параболы являются линиями переключения оптимального управления. В области над линией АОВ управление должно иметь вид и . Изображающая точка будет двигаться по дуге параболы . В точке встречи этой параболы с линией АО управление надо переключить и принять и . Дальнейшее движение будет происходить по линии до встречи с началом координат.

В области, расположенной ниже линии АОВ, надо принять и . Изображающая точка будет двигаться по дуге параболы .

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

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

Ниже (стр. 288) показано, что функция непрерывна во всей фазовой плоскости . Частные производные и существуют во всех точках фазовой плоскости , за исключением точек линии переключения АОВ. Ни в одной из точек линии переключения АО В частные производные и не существуют.

Предположим теперь в общем случае, что в множестве D, на котором задана функция , выделено некоторое множество М ("осободе множество" функции ) и что функция непрерывна на всем множестве D, а непрерывные частные производные имеет лишь в тех точках множества D, которые не принадлежат М.

Лемма 2. Пусть D — открытое множество фазового пространства X и М — некоторое множество, содержащееся в D. Предположим, что на множестве D задана непрерывная функция , которая в точках, не принадлежащих множеству М, имеет непрерывные частные производные и удовлетворяет неравенству (8)

Пусть, далее, — допустимое управление, переводящее изображающую точку из положения в положение причем соответствующая траектория расположена целиком в D и пересекается с множеством М лишь в конечное число моментов времени. Тогда оценка (14)

остается справедливой.

Доказательство . Заметим, что оценка (14) остается справедливой, если траектория пересекается с множеством М лишь в моменты времени или в один из этих моментов. Действительно, в этом случае полностью проходит доказательство леммы 1, поскольку функция по-прежнему непрерывна, а когда t заключено внутри интервалов (границы которых суть моменты времени, в которых управления терпят разрыв), точка лежит вне множества М и, следовательно, на этих интервалах производные существуют и непрерывны.

. Пусть теперь — все принадлежащие интервалу моменты встречи траектории с множеством причем . Обозначим еще

К каждому из отрезков применимо сделанное выше замечание, и потому

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

которое совпадает с требуемым в условии леммы неравенством (14). Таким образом, лемма доказана.

Отметим теперь, что ситуация, которая имеет место в задаче о быстродействии (см. пример на рис. 15.1), не охватывается условиями леммы 2.

Действительно, в этом примере (рис. 15.1, 15.2) не отдельные точки, а дуга оптимальной траектории расположена на линии переключения АОВ, то есть по терминологии леммы 2 целый участок оптимальной траектории расположен в множестве М. По условию леммы 2 допускается пересечение оптимальной траектории с множеством М лишь в конечное число моментов времени. Здесь же оптимальная траектория в течение некоторого промежутка времени находится в множестве М.

Выход из создавшейся трудности дается в приведенной ниже лемме 3.

Рис. 15.2.

Лемма 3. Сохраним предположения о функции , сделанные в лемме 2. Пусть — допустимое управление, переводящее изображающую точку из положения в положение , причем соответствующая траектория расположена целиком в D. Предположим еще, что как угодно близко к найдется такая точка , что траектория , исходящая из точки и соответствующая тому же управлению , пересекается с М лишь в конечное число моментов времени. Тогда оценка (14)

остается справедливой.

Доказательство. Выберем произвольное число , и пусть и (рис. 15.2) — такие окрестности точек и соответственно, что

Согласно теореме зависимости решений дифференциальных уравнений от начальных условий, существует такая окрестность точки , что всякое решение системы уравнений, аналогичной системе (1) (с тем же управлением )

(15.19)

для которого определено на всем отрезке и удовлетворяет соотношению .

По условию доказываемой леммы указанное решение системы (19) с начальными данными , пересекается с М лишь в конечном числе точек. Из этого вытекает в силу леммы 2, что имеет место неравенство

(15.20)

Далее, так как у то Следовательно, в соответствии с (18) имеем

(15.21)

Из соотношений (21) следует, что

(15.22)

Складывая левые и правые части неравенств (20) и (22), получим

(15.23)

Отсюда в виду произвольности вытекает неравенство (14).

Лемма 3 дает наиболее общие условия, при выполнении которых оценка (14) справедлива. Однако условия леммы 3 сформулированы отдельно для каждого управления . Остается еще показать справедливость этих условий для всевозможных управлений .

В. Г. Болтянским в цитированных выше работах показано, что при наложении некоторых условий на множество М сформулированные в лемме 3 условия выполняются для любых допустимых управлений .

В частности, это .имеет место, если М — кусочно-гладкое множество размерности .

Приведем определение кусочно-гладкого множества [15]. Пусть К — некоторый ограниченный -мерный выпуклый многогранник , расположенный в векторном пространстве переменных и рассматриваемый вместе с границей (то есть замкнутый). Предположим, что в некотором открытом множестве пространства , содержащем многогранник К, заданы непрерывно дифференцируемых функций

(15.24)

обладающих тем свойством, что функциональная матрица

имеет в каждой точке ранг s. Функции (24) осуществляют гладкое отображение многогранника К в пространстве X по формулам

(15.25)

Если это отображение взаимно однозначно (то есть различные точки многогранника К переводит в различные точки пространства X), то образ многогранника К называется криволинейным -мерным многогранником в пространстве X. Очевидно, что криволинейный многогранник является замкнутым и ограниченным множеством пространства .

Пусть теперь D — некоторое открытое множество фазового пространства X. Всякое множество Май, представляющееся в виде объединения конечного или бесконечного числа криволинейных многогранников, расположенных таким образом, что с каждым замкнутым ограниченным множеством, лежащим в D, пересекается лишь конечное число этих многогранников, называется кусочно-гладким множеством в D. (К границе множества D многогранники могут скапливаться.)

Если среди криволинейных многогранников, объединением которых является кусочно-гладкое множество М, имеется хотя бы один многогранник размерности k, а все остальные многогранники имеют размерность, меньшую или равную k, то кусочно-гладкое множество называется -мерным. В частности, всякая замкнутая в D гладкая поверхность размерности, меньшей чем , является кусочно-гладким множеством в D (ибо ее можно разбить на криволинейные многогранники). Из изложенного следует, что кусочно-гладкое в D множество размерности, меньшей чем , не содержит внутренних точек.

В качестве примера укажем, что при кусочно-гладкими множествами размерности <2 являются линии, состоящие из отдельных дифференцируемых кусков (например, линия АОВ на рис. 15.1).

Следующую лемму приведем без доказательства. Доказательство этой леммы требует привлечения ряда понятий теории гладких многообразий и дано в цитированных работах В. Г. Болтянского [15].

Лемма 4. Пусть М — кусочно-гладкое в D множество размерности . Пусть далее - допустимое управление, переводящее изображающую точку из положения в положение , причем соответствующая траектория расположена целиком в множестве D.

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

Из леммы 4 и леммы 3 вытекает непосредственно справедливость следующей основной леммы.

Основная лемма. Пусть М — кусочно-глад кое множество размерности расположенное в открытом множестве D фазового пространства X. Предположим, что на множестве D задана непрерывная функция , которая в точках, не принадлежащих множеству М, имеет непрерывные производные и удовлетворяет неравенству (8):

Тогда если - допустимое управление, переводящее изображающую точку из положения в положение , причем соответствующая траектория расположена целиком в множестве D, то для времени перехода справедлива оценка (14)

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

Теорема В. Г. Болтянского. Пусть М — кусочно-гладкое множество размерности , расположенное в фазовом пространстве X, и — непрерывная функция, заданная на X и имеющая в точках, не принадлежащих множеству М, непрерывные производные. Пусть, далее, для некоторой точки . Предположим, что для каждой отличной от точки существует допустимое управление , переводящее изображающую точку из положения в положение за время .

Для того чтобы все управления были оптимальными, необходимо и достаточно, чтобы во всех точках не принадлежащих множеству М, функция удовлетворяла уравнению Беллмана (7)

или, что то же самое, неравенству (8)

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

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

то есть быстрее чем за время осуществить этот перевод невозможно.

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