Приложение 3. Метод динамического программирования для дискретных систем. Численное решение функционального уравнения

Для удобства изложения существа метода ограничимся вначале частным случаем этой задачи, когда объект описывается уравнением первого порядка . Кроме того, заменим приближенно этот непрерывный объект дискретным. В связи с этим разобьем интервал на равных участков достаточно малой длины Т и будем рассматривать лишь дискретные значения в моменты времени соответственно (далее будем полагать ).

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

или

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

Начальные условия для этого разностного уравнения остаются прежними:

Для удобства изложения примем где - заданные функции. Заменим приближенно интеграл (2.3.3) суммой

Принимая во внимание, что и Т суть константы, запишем функционал качества в виде

Задача П.3.1. Определить функцию управления

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

Для определенности будем полагать, что эти ограничения на управления имеют вид

Сформулированная задача является, в сущности, задачей условного экстремума функции . Независимыми переменными являются числа .

Синтез на основе классических методов математического анализа. Используя связи , исключим из , тогда

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

К сожалению, подобные системы нелинейных уравнений трудно решить даже при сравнительно небольших .

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

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

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

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

Эти частные случаи будем называть -шаговыми процессами.

Обозначим значение функционала качества при -шаговом оптимальном процессе.

Пусть Для этого одношагового процесса уравнения и функционал имеют вид

Нетрудно видеть, что

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

Процедура 1. Положим , где есть некоторое фиксированное число. Тогда

Разобьем интервал допустимых изменений на i отрезков длиной и вычислим значение функции в точках разбиения. При некотором значении эта функция принимает наименьшее значение . Запомним .

Положим теперь . Тогда . При некотором эта функция принимает наименьшее значение.

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

задаваемой таблично.

Используя эту функцию, получим наименьшее значение функционала :

Рассмотрим теперь двухшаговый процесс . В этом случае

Представим где .

Значение зависит от выбора . При этом зависит от — от так как зависит от , которое в свою очередь определяется выбором .

Положим где — некоторое произвольное, но фиксированное число. Это управление отклоняет на величину .

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

Управление , доставляющее минимум , является управлением в одношаговом процессе (так как ) зафиксировано) и определяется формулой , т. е.

При этом

Значение функционала при определяется выражением

Минимизируя эту сумму по , получим

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

Таким образом, оптимальное управление в двухшаговом процессе имеет

При этом экстремальное значение функционала

Пусть . Для этого случая

Представим , где .

Пусть , где - произвольное, но фиксированное число.

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

На основе получим

Значение функционала при управлении определяется выражением

Минимизируя его по , получим

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

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

Повторяя эти рассуждения для , получим соотношение

которое является функциональным уравнением для дискретных систем.

Вывод этого уравнения опирался на принцип оптимальности, который можно переформулировать так:

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

Какие же трудности в решении задачи мы преодолели, используя подход, основанный на принципе оптимальности? Главной трудностью являлась минимизация функции переменных . Функциональное уравнение позволило свести задачу минимума функции N переменных к значительно более простой задаче минимизации функций одной переменной. Действительно, используя при , получим функции:

Отметим еще раз, что функции получены в результате минимизации функции одной переменной .

В задаче требуется найти управление вида

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

Таким образом, искомые функции управления

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

Учитывая, что , получим

Это выражение с точностью до обозначений совпадает с и поэтому, применяя процедуру 1, получаем оптимальное управление на последнем участке:

Минимальное значение определяется выражением

Рассмотрим интервал времени , состоящий из последнего и предпоследнего интервалов Этому интервалу соответствует частичная сумма

Состояние будем предполагать известным. Из принципа оптимальности следует, что лишь состояние и цель управления (минимизация ) определяют оптимальное управление на интервале .

Найдем минимум по . Учтем при этом

Первые два слагаемых в не зависят от и поэтому

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

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

Предполагая состояние известным, определим управления , минимизирующие сумму . В соответствии с принципом оптимальности, эти управления являются оптимальными для трех последних интервалов времени движения.

Учитывая, что первые два слагаемых в не зависят от , запишем

Применяя процедуру 1, получим оптимальное управление на интервале

Продолжая этот процесс, получим общую рекуррентную формулу

Используя процедуру 1, получаем оптимальное уравнение на интервале :

Это выражение совпадает с , а функциональное уравнение при совпадает с .