и в общем виде

ft] Ы = min [L К Ио) + ftjx {g {хо, Uo))], (15.7)

где fu {Xq) для каждого Л/ соответствует оптимальному значению функцио- . нала / для Л/-шаговой задачи оптимизации, когда в качестве исходного состояния выбирается координата Хо-

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

(лго) = min [L [хо, и) М]; (15.8а)

min [Ь [хо, и) Мfti [g {хо, и))]; N = , . . .. (15.86)

е{ 8}

Уравнения (15.8) позволяют найти оптимальную последовательность управлений для произвольного целого числа N. При этом выполним следующие действия:

1) в момент времени дг1 каждое возможное значение состояния х/ 1 рассматриваем как начальное состояние, а задачу оптимизации как одно-шаговую при переходе из состояния х 1 в лгдг. Из уравнения (15.8а) определим u)v-i = {N-i) и /I {xn-i); введем обе эти величины в память машины для каждого значения Xtj i,

2) в момент времени дг 2 используем уравнение (15.86) для вычисления /2 {xn-2) и и (л:лг 2); введем их в память машины для каждого возможного значения Хдг 2. При осуществлении этого процесса необходимо использовать хранящиеся в памяти значения /ь Здесь задача оптимизации рассматривается как двухшаговая задача для начального состояния Xfj 2;

3) в момент времени t g используем уравнение (15.86) для вычисления /з(ллг-з) и и (ллг-з); введем их в память машины для каждого возможного значения Xtj g. При осуществлении этого процесса используем хранящиеся в памяти значения fl,

4) продолжаем выполнение описанного выше процесса до момента времени to;

5) для нахождения оптимальной последовательности при движении из произвольной начальной точки Хо берем из памяти хранящееся там значение . * (-о) - первое значение в оптимальной последовательности щ. Зная его, с помощью выражения (15.2) находим х;

6) берем из памяти и* (х) второе значение в оптимальной последовательности ui. Зная его, с помощью выражения (15.2) находим Х2,

7) продолжаем этот процесс для получения всей оптимальной последовательности управлений {щ, Ui, . . ., а также последовательности, характеризующей оптимальную траекторию {xl, xl, . . ., х]]],

8) критерий качества для данной задачи равен /дг, и он хранится в памяти машины.

Заметим, что в данном параграфе рассматривались динамические системы, динамика которых описывается уравнением (15.2). Таким образом, учет динамики несущественно усложняет решение задач методом динамического программирования. На основе метода динамического программи-

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

15.2. ПРИНЦИП ОПТИМАЛЬНОСТИ

Сделаем ряд замечаний относительно метода, изложенного & предьщу-щем параграфе.

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

1) каково значение гипотезы, введенной для отыскания оптимальной последовательности управлений;

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

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

Итак, в основе метода лежит указанная гипотеза, которую Р. Беллман называет принципом оптимальности. Приведем его формулировку. Оптимальная последовательность управлений для -шагового процесса [щ,. и], . . ., ul/ i] такова, что независимо от значения управления щ и, следовательно, от значения xi выбор остальных N - 1 значений в последовательности {ui, . . ., Um-i} должен обеспечить оптимальную последовательность управлений относительно состояния xl, которое рассматривается теперь как начальное состояние. Этот принцип можно легко доказать от обратного.

Предположим, что [щ, ul, . . ., Ылг-i} представляет собой оптимальную последовательность управлений, причем управление uo переводит систему из состояния Хо в х1. Допустим, что принцип оптимальности не выполняется, тогда для начального состояния xi существует последовательность {Mi, ыГ, Um-i], которая дает меньшее значение функционала f, чем последовательность {-Ml, ul, . . ., Ылг-i)- Это означает, что последовательность {uq, Ul, . . ., Un-i] приведет в результате к меньшему значению функционала чем оптимальная последовательность [ul, ul, . . ., Ылг-i). что невозможно.

Рассмотрим вновь функциональные уравнения. (15.8а и б), которые для ясности изложения выпишем еще раз:

/; [хо] = min [L (хо, и) М];

fN{xo)= mm [L (хо, и) М ff,i (g (хо, и))].

Заметим прежде всего, что функциональные уравнения позволяют выполнять действия последовательно, начиная с N = I. Иначе говоря, задача сведена к -шаговой, причем на каждом шаге выбирается единственное зна-

) Рекомендуем читателю самостоятельно решить задачи 15.1-15.3, используя предлагаемый подход. - .

чение и таким образом, чтобы минимизировать величину [L (лго. и) At + + {g{xo, и)). Это имеет существенное преимущество перед методами, в соответствии с которыми требуется проверять все возможные пути, ведущие к цели.

Однако этому не следует придавать чрезмерно большого значения, так как последнее просто указывает на разницу между слепым и вдумчивым подходами. Если требуется повысить эффективность вычислительной процедуры, то можно воспользоваться более рациональным методом, чем изложенный в § 15.1

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

Так, например, уравнения (15.8) определяют критерий качества /* как функцию начальной точки х. Это значит, что с каждой начальной точкой л: о автоматически связан некоторый критерий оптимальности Таким образом, можно представить себе гиперповерхность определенную

в пространстве переменных рассматриваемой задачи. Стремление обеспечить минимум показателя качества на каждом шаге заставляет выбирать такое управление и*, которое определяет движение в направлении максимального уменьшения f*. Нетрудно убедиться в том, что сказанное выше в точности соответствует смыслу уравнений (15.8).

Заметим, что динамическое программирование, по-видимому, позволяет решать более широкий круг задач, чем рассматриваемые в настоящее время. Вместо того, чтобы получать какую-либо конкретную последовательность управлений {ы*} и конкрегный функционал /*, мы можем с помощью уравнений (15.8) вычислить эти величины для всех возможных начальных точек. Этот прием назьшается погружением задачи и связан с ее обобщением. Он весьма характерен для метода динамического программирования. Путем погружения первоначальной задачи с заданной начальной точкой в более .общий класс задач с произвольными начальными условиями можно определить общую картину изменения функционала /* и, следовательно, сделать -ВЫВОДЫ относительно того, какой должна бьггь оптимальная последовательность \и*\.

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

Заметим, что описанный в предыдущем параграфе метод обратного динамического программирования не является единственным способом использования принципа оптимальности. Можно применять также и прямой метод. В случае прямого динамического программирования принцип оптимальности формулируется следующим образом. Оптимальная последовательность управления [щ щ, . . ., для Л/-шагового процесса должна быть такой, чтобы независимо от значения иы-х и, следовательно, состояния первые N значений в последовательности [щ . лг-il составляли оптимальную последовательность управлений относительно состояния % ь рассматриваемого как конечное состояние.

) Действительно, при использовании динамического программирования в том виде, как это сделано в § 15.1, задача 6 может оказаться неразрешимой. При решении любой нетриваль-лой задачи может нехватить памяти даже самой крупной современной вычислительной машины. Поэтому разрабатываются более совершенные вычислительные методы, связанные с динамическим программированием (см. например, работы [114] и [115]).