Лекция 8. Динамическое программирование в задачах управления

Метод ДП - один из наиболее мощных и совершенных математических методов современной теории управления - был создан в конце 50-х гг американским математиком Ричардом Беллманом. Этот метод для вас не нов. В курсе Методы оптимизациии вы рассматривали его и знаете в чем он состоит. Его применение к многошаговому процессу управления, а также многочисленные приложения метода к разнообразным проблемам теории принятия решения, экономики и других предметных областей способствовали закреплению этого метода как одного из важнейших инструментов теории оптимальных управляемых процессов.

Сформулированный Р. Беллманом принцип оптимальности гласит:

Отрезок оптимального процесса от любой его точки до завершения сам является оптимальным с началом в этой точке.

Этот принцип легко доказывается от противного в предположении существования оптимальных процессов. На основании этого принципа выводится основное функциональное уравнение Беллмана или соответствующее реккурентное соотношение, если ОУ описывается моделью с дискретным временем.

Рассмотрим управляемую систему, состояние которой в каждый момент времени характеризуется n-мерным вектором х с компонентами х₁,..., х_n. Предполагаем, что время t изменяется дискретно и принимает целочисленные значения 0,1,... Так, для процессов в экономике дискретным значениям времени могут отвечать дни, декады, месяцы или годы, а для процессов в электронных устройствах интервалы между соседними дискретными моментами времени определяются тактовой частотой этих устройств. Предполагаем, что на каждом шаге на систему оказывается управляющее воздействие при помощи m-мерного вектора управления u с компонентами u,..., u_m. Таким образом, в каждый момент времени t состояние системы характеризуется вектором х(t), а управляющее воздействие - вектором u(t). На выбор управления обычно бывают наложены ограничения, которые в достаточно общей форме можно представить в виде

u(t) U, t=0,1,...(1)

Здесь U - заданное множество в n-мерном пространстве.

Под влиянием выбранного в момент t управления (принятого решения) система переходит в следующий момент времени в новое состояние. Этот переход можно описать соотношением

x(t+1)=f(x(t),u(t)), t=0,1,… (2)

Здесь f(х, и) - n -мерная функция от n -мерного вектора х и m -мерного вектора u, характеризующая динамику рассматриваемой системы. Эта функция предполагается известной (заданной) и отвечает принятой математической модели рассматриваемого управляемого процесса.

Зададим еще начальное состояние системы

х(0) = х°, (3)

где х⁰ - заданный n -мерный вектор. Таким образом, многошаговый процесс управления описывается соотношениями (1)-(3). Процедура расчета конкретного процесса сводится к следующему. Пусть в некоторый момент состояние системы х(t) известно. Тогда для определения состояния х(t+1) необходимо выполнить две операции:

1) выбрать допустимое управление u(t), удовлетворяющее условию (1);

2) определить состояние x(t+ 1) в следующий момент времени согласно (2).

Так как начальное состояние системы задано, то описанную процедуру можно последовательно выполнить для всех t = 0, 1,... Последовательность состояний х(0), х(1),...часто называется траекторией системы. Заметим, что выбор управления на каждом шаге содержит значительный произвол. Этот произвол исчезает, если задать цель управления в виде требования минимизации (или максимизации) некоторого критерия оптимальности. Таким образом мы, приходим к постановке задачи оптимального управления.

ЗАДАЧА ОПТИМАЛЬНОГО УПРАВЛЕНИЯ

Пусть задан некоторый критерий качества процесса-управления (критерий оптимальности) вида

J= + F(x(N)) (4)

Здесь R(х, и) и F(х) - заданные скалярные функции своих аргументов, N — момент окончания процесса, N > 0. При этом функция R может отражать расход средств или энергии управляемой системой на каждом шаге процесса, а функция F- характеризовать оценку конечного состояния системы или точность приведения в заданное состояние.

Задача оптимального управления формулируется как задача определения допустимых управлений u(0), u(1),..., и(N-1), удовлетворяющих ограничениям (1), и соответствующей траектории, то есть последовательности х(0), х(1),..., х(N), которые в совокупности доставляют минимальное значение критерию (4) для процесса (2), (3).

Минимизация критерия (4) обычно отвечает выбору управления, обеспечивающего наименьшие затраты средств, ресурсов, энергии, наименьшее отклонение от заданной цели или заданной траектории процесса. Наряду с этим часто ставится также задача о максимизации критерия вида (4), например о максимизации дохода или объема производства. Однако нетрудно видеть, что максимизация критерия J эквивалентна минимизации критерия (-J). Поэтому простая замена знака у функций R и F в (4) приводит задачу о максимизации критерия к задаче о его минимизации. Далее всюду для определенности рассматриваем задачу о минимизации критерия (4).

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

J=R(x0,u(0))+R(f(x0,u(0)),u(1))+ …=Ф(x0,u(0),u(1),…,u(N-1)).

Здесь Ф — некоторая громоздкая, но, вообще говоря, известная и вычисляемая функция своих аргументов. Таким образом поставленная задача оптимального управления свелась к задаче о минимизаций функции Ф от векторов u(0),u(1),u(t- 1), то есть от N переменных. При больших N (а обычно представляют интерес именно процессы с большими N), эта задача о минимизации функции большого числа переменных представляет трудности даже при использовании мощных компьютеров. Дополнительное осложнение вызвано тем, что переменные и(t) должны удовлетворять ограничениям (1).

Принципиально иной подход к поставленной проблеме дает метод динамического программирования.