Элементы динамического программирования оптимизация непрерывных систем

Оптимизация дискретных систем

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

(14.12)

Здесь — состояние системы на i-м шаге.

Тогда N-шаговому управлению можно поставить в соответствие траекторию движения системы

если задано — начальное состояние-системы.

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

Задача состоит в выборе-управления u, доставляю­щего экстремум выбранному критерию. Для простоты будем считать, что критерий аддитивен относи­тельно множества состояний, пробегаемых в процессе эволюции системы, т. е.

(14.13)

Введем функцию , равную численному значению критерия (14.13) при оптимальном k-шаговом управлении, начиная из состояния . Предположим, что система находится в некотором состоянии и над­лежит выбрать одношаговое управление таким обра­зом, чтобы максимизировать (14.13). Тогда

(14.14)

Пусть теперь система находится в состоянии и надлежит выбрать оптимальное двухшаговое управле­ние так, чтобы максимизировать (14.13). Тогда в соответствии с принципом оптимальности

Рассуждая аналогично, имеем

(14.15)

откуда, в частности,

(14.16)

Вычислительная процедура решения задачи теперь ясна. Отыскание оптимального управления начинаем с последнего шага. При этом для каждого из возмож­ных состояний системы , используя (14.14), необ­ходимо отыскать и запомнить оптимальное управление .Таким образом, будет известно оптимальное одношаговое управление для любого из возможных со­стояний системы. Теперь, используя (14.15) при k=2, для каждого из возможных состояний системы найдем оптимальное двухшаговое поведение . Обра­тим внимание на то, что при этом фактически прихо­дится решать одношаговую оптимизационную задачу отыскания , так как после отыскания с ис­пользованием соотношения (14.12) вычисляется состоя­ние , причем для каждого из оптимальное управ­ление уже было найдено ранее. Аналогично отыскивает­ся оптимальное поведение для k = 3, 4, ..., N-1. Поскольку начальное состояние системы фиксирова­но, при отыскании оптимального управления на первом шаге нет необходимости решать оптимизационную задачу для всех . Нужно сделать это только для исходного состояния .

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

Поясним вычислительную процедуру метода на сле­дующих примерах.