§ 13. Применение динамического программирования к дискретным системам

1. Рекуррентное соотношение Беллмана.

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

Системы, описываемые дифференциальными уравнениями, принято (в этом смысле) называть системами непрерывного действия.

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

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

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

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

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

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

где — координата системы, а — управляющая сила, которая должна удовлетворять ограничению

Начальное состояние системы задано

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

где Т — некоторая фиксированная величина. Будем считать, что

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

Так как

то исходное дифференциальное уравнение (1) можно заменить следующим приближенным соотношением:

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

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

Функционал (3) аппроксимируем интегральной суммой

Обозначая

придем в соответствии с (7), (2) и (8) к следующей задаче.

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

(13.11)

начальное состояние которой задано

(13.12)

найти управление и , удовлетворяющее ограничениям

(13.13)

и доставляющее минимум сумме

(13.14)

где N — некоторая фиксированная величина.

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

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

Поставленная выше задача, описываемая уравнениями (11) — (14), состоит в том, чтобы найти совокупность значений , которая минимизирует сумму (14) при условиях (11), (12), (13).

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

(13.15)

Так как согласно (11)

(13.16)

то выражение (15) принимает вид

(13.17)

Поскольку состояние предполагается известным, то выражение (17) зависит лишь от одной неизвестной величины , которая должна быть найдена с учетом ограничения (13) из условия минимизации величины Найденное оптимальное значение обозначим через . Получаемое при этом минимальное значение обозначим через

(13.18)

В (18) явно указано, что минимальное значение зависит от состояния системы .

В соответствии с (17) соотношение (18) можно переписать так:

(13.19)

Рассмотрим теперь интервал времени , состоящий из последнего и предпоследнего интервалов. Согласно (14) этому интервалу времени соответствует частичная сумма

или в соответствии с (15)

(13.21)

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

Найдем теперь величину , то есть минимум по и . Учтем при этом, что минимум по частичной суммы уже найден выше и этот минимум

представлен в виде функции от . Так как согласно (11)

(13.22)

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

(13.23)

Поскольку первое слагаемое в правой части (21) не зависит 1), то будем иметь

(13.24)

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

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

Обратимся теперь к интервалу времени , состоящему из трех последних интервалов. Этому интервалу времени согласно (14) соответствует частичная сумма

(13.25)

или согласно (20)

(13.26)

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

Найдем теперь величину то есть минимум по , и . Учтем при этом, что минимум по и частичной суммы уже найден выше (24) и этот минимум

представлен в виде функции от . Так как согласно (11) . Так как согласно (11) (13.27)

то имеет вид

(13.28)

Поскольку первое слагаемое в правой части (26) не зависит от и , то будем иметь

(13.29)

Выражение (29) приведено к такому виду, что минимизацию требуется выполнить лишь по одной переменной, а именно по . Найденное при этом значение будет искомым оптимальным значением, которое мы обозначим через .

Нетрудно теперь получить общую (рекуррентную) формулу, рассматривая интервал времени . Аналогично (24) и (29) будем иметь

Выражение (30) приведено к такому виду, что минимизацию требуется выполнить лишь по одной переменной, а именно по . Найденное при этом значение будет искомым оптимальным значением, которое мы обозначим через .

Таким образом, при помощи (19) и (30) будут найдены

(13.31)

В выражениях (31) явно указано, что найденные из рассмотрения частичных интервалов времени значения выражены в виде функций от состояния системы в начале частичного интервала.

Так как состояние задано, то значение определяется. Тогда согласно (11) найдется состояние и определится значение . После этого согласно (11) найдется состояние и определится значение и т. д.

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

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