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

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

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

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

Пример .

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

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

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

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

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

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

Причем -вектор координат состояния

- вектор управления

Пусть и требуется минимизировать интеграл

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

Пусть начальное условие заданы, значение , вообще говоря, не известно.

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

Второму участку соответствует часть интеграла (1), равная

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

Это означает, что в том случае, когда начальное состояние системы есть , а начальный момент времени , то не зависимо от того, каким образом пришла система к этому состоянию. Ее оптимальным последующим движением будет траектория 2. Действительно допустим противное – тогда критерий (1), рассматриваемый для интервала времени от до , будет наименьшим не для траектории 2, а для какой-либо иной траектории , исходящей из точки и показанной пунктиром на рис.2. Но в этом случае можно было бы построить «лучшую» траекторию, чем траектория 1-2, и для первоначальной задачи, нужно лишь выбрать управление таким, чтобы описываемая траектория 1, а затем . Между тем мы исходим из того, что траектория 1-2 оптимальна. Противоречие доказывает невозможность существования траектории , обеспечивающее меньшее значение, чем траектория 2. И так траектория 2 оптимальна.

Сформулированный выше принцип оптимальности является весьма общим необходимым условием оптимального процесса, справедливым как для непрерывных, так и для дискретных систем.

Принцип оптимальности выглядит почти тривиальным и, на первый взгляд бедным по содержанию утверждением. Однако из него можно, как показывал Беллман, методически рассуждая вывести необходимое условие для оптимальной траектории, имеющее отнюдь не тривиальный характер. В сущности, принцип оптимальности не так уж тривиален, как может в начале показаться. Это видно хотя бы из того, что утверждение, кажущееся его обобщением: «Любой участок оптимальной траектории является оптимальной траекторией» - вообще говоря, не справедливо. Так, например, первый участок траектории на рис.2 может сам по себе не быть оптимальной траекторией, т.е. не давать минимум интегралу , если заданы только лишь начальные условия .

Поясним это утверждение элементарной иллюстрацией. Как распределяет свой силы хороший бегун при беге на длинную дистанцию? Действует ли он по принципу: Беги на каждом отрезке на столько быстро, на сколько сможешь? Конечно нет, ведь, бегун может «выдохнуться» за долго до подхода к цели. Разумно распределяя свои ресурсы в соответствии с конечной целью, бегун в начале экономит свои силы, чтобы не «выдохнуться» в конце дистанции. Аналогичным образом любое управлением не должно быть «близоруким», не должно руководствоваться лишь достижением наилучшего моментального, локального эффекта. Оно должно быть «дальновидным», оно должно быть подчинено конечной цели, т.е. минимизации функционала (1) на всем интервале от до . Только в том случае, когда задана конечная точка первого участка при , первый участок также сам по себе является оптимальной траекторией.

Можно дать и другую формулировку принципа оптимальности:

Эквивалентность этой и предыдущей формулировок очевидно, если понимать под «предысторией» системы ту траекторию 1, по которой изображающая точка пришла в положение (рис.2). Под состоянием системы в рассматриваемый момент времени понимается в данном случае именно то состояние, соответствующее точке при .

Поясним метод рассуждения Беллмана на простом принципе управляемого объекта с управлением

.

Где – единственная координата системы:

Единственное управляемое воздействие, ограниченное некоторой областью .

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

где для удобства за примем время равное нулю, т.е. ; значение будем для простоты считать фиксированным.

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

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

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

Начальное условие остается прежним

Интервал (28) приближенно заменяется суммой

Задача теперь состоит в определении последовательности дискретных значений управляющего воздействия , т.е. величины , минимизирующих сумму (32) при условиях (4), (30) и (31), наложенных на систему таким образом, требуется найти минимум сложной функции многих переменных. Однако МДП дает возможность свести эту операцию к последовательности минимизаций значительно более простых функций одного переменного.

Для решения задачи применяется прием, заключающийся в «понятном» движении о конца процесса, т.е. от момента , к его началу. Допустим сначала, что рассматривается момент . Все значения , кроме последнего , уже каким то образом были осуществлены, причем получено некоторое значение , соответствующие моменту . Согласно принципу оптимальности воздействие не зависит от «предыстории» системы и определяется лишь состоянием и целью управления.

Рассмотрим последний участок траектории от до . Величина влияет лишь на те члены суммы (32), которые относятся к этому участку.

Обозначим сумму этих членов через .

из (30) получаем

Следовательно, так же зависит от . Найдем допустимое значение , удовлетворяющее (4) и минимизирующее величину . Обозначим найденное минимальное значение через . Эта величина очевидно зависит от состояния системы при т.е. от значения , входящее в (33) и (34). И так

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

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

1.2 Метод динамического программирования и его основные этапы

В основе метода динамического программирования лежит принцип оптимальности, впервые сформулированный в 1953 г. американским математиком Р. Э. Беллманом: каково бы ни было состояние системы (S) в результате какого-либо числа шагов, на ближайшем шаге нужно выбирать управление так, чтобы оно в совокупности с оптимальным управлением на всех последующих шагах приводило к оптимальному выигрышу на всех оставшихся шагах, включая выигрыш на данном шаге. При решении задачи на каждом шаге выбирается управление, которое должно привести к оптимальному выигрышу. Если считать все шаги независимыми, тогда оптимальным управлением будет то управление, которое обеспечит максимальный выигрыш именно на данном шаге.

Метод динамического программирования включает три основных этапа:

Предварительный этап.

Этап условной оптимизации.

Этап безусловной оптимизации.

Предварительный этап проводится с целью уменьшения вычислительной работы на последующем этапе решения и, по существу, заключается в нахождении всех допустимых значение управлений и фазовых переменных. Иными словами, на данном этапе отбрасываются все заведомо неподходящие, нереализуемые значения фазовых и управляющих переменных. Проводится предварительный этап в естественном порядке от первого шага к последнему: i = 1, 2, … , N, а опираются соответствующие расчеты на уровне процесса

Этап условной оптимизации. На данном этапе решения задачи, называемом условной оптимизацией, определяются функция Беллмана и оптимальные управления для всех возможных состояний на каждом шаге, начиная с последнего в соответствии с алгоритмом обратной прогонки. На последнем, n-м шаге, оптимальное управление - определяется функцией Беллмана (1.1):

Этот максимум (или минимум) определяется по всем возможным для k и S значениям переменной управления X.

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

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

Таблица 1.1

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

Виды математических моделей, используемых в экономике

Общая задача оптимизации, чтобы ее можно было описать моделью ДП должна удовлетворять следующим условиям: 1. Задача может интерпретироваться как n-шаговый процесс управления...

Динамическое программирование

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

Использование метода динамического программирования для решения экономических задач

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

Классификация математических моделей, используемых в экономике и менеджменте

Общая задача оптимизации, чтобы ее можно было описать моделью ДП должна удовлетворять следующим условиям: Задача может интерпретироваться как n-шаговый процесс управления...

Классификация экономико-математических методов и моделей

Рассматривается управляемая система, которая под влиянием управления переходит из начального состояния в конечное состояние. Предположим, что процесс управления системой можно разбить на n шагов. Пусть - состояния системы после 1-го, 2-го, …...

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

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

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

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

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

Распределение инвестиций между предприятиями: "Малышок", "Ронда", "Товиус", "Сластёна", "Читек"

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

Распределение средств между предприятиями: ОАО "Весёлый молочник", ОАО "Нижнекамская пищевая компания", ООО "Сэлдом", ООО "СтойКом", ОАО "Счастье"

Динамическое программирование (ДП) - метод оптимизации, приспособленный к операциям, в которых процесс принятия решения может быть разбит на этапы (шаги). Такие операции называются многошаговыми. Начало развития ДП относится к 50-м годам XX в...

Трендовые и корреляционные модели

Делим динамический ряд 1 на количество частей, равное количеству неизвестных коэффициентов выравнивающей функции...

Экономические модели зависимости величины активов, подверженных кредитному риску, от пассивов, прибыли (убытков), ВВП

На первом этапе необходимо построить уравнение парной линейной регрессии. Эмпирическое уравнение парной линейной регрессии имеет следующий вид: (1) где Y - объясняемая переменная, X - объясняющая переменная, е - случайная величина (ошибка)...

4.1. Принцип оптимальности

Рассмотрим систему

и функционал

(4.2)

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

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

. (4.3)

Пусть сначала найден минимум (4.2) и соответствующее ему оптимальное управление (рис. 14а):

а потом – минимум (4.3) и оптимальное управление (рис. 14б):

В последнем случае предполагается, что в момент процесс начинается с состояния
, достигнутого к моменту временипри оптимизации процесса в интервале
.

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

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

(4.6)

Рис. 14а Рис.14б

Тогда для первой задачи введем управление

(4.7)

и вычислим функционал

При управлении (4.7) функционал (4.2) принимает меньшее значение, чем при (4.4). Но управлениеявляется оптимальным. Поэтому допущение (4.6) неверно.

A предположение

противоречит тому, что
- управление, минимизирующее
(4.3).

Таким образом, остается, что

,

и если оптимальное управление единственное, то

Кратко принцип оптимальности можно сформулировать так: последний участок оптимальной траектории является оптимальным независимо от предыстории процесса.

4.2. Основное уравнение метода динамического программирования

Применим принцип оптимальности к решению вариационной задачи (4.1), (4.2). Для этого сначала рассмотрим функционал (4.3). Наименьшее значение его при связях (4.1) обозначим:

. (4.8)

Если
- оптимальное управление, то

.

Оптимальное управление
зависит от начального состояния
в момент
. Следовательно,является функцией оти:
, а от управленияи его вариаций функция
не зависит. Она вполне определяется значениями
.

Интервал
разделим на два интервала
и
и выражение (4.8) запишем в виде:

.

Согласно принципу оптимальности последний участок также является оптимальным:

(4.9)

Обозначим:

, (4.10)

где
- приращение вектора фазовых координат за время
. Оно определяется согласно уравнениям движения (4.1). Подставляя
из (4.10) в равенство (4.9), получим:

.

Хотя функция
зависит только от фазовых координат и времени, ее нельзя выносить за знак
. Значение приращения
за время
зависит от управления в интервале
. Но
не зависит от управления в интервале
и ее можно внести под знак
. Введем
под знак минимума и разделим на
:

.

Учитывая, что

;

,

получим основное уравнение метода динамического программирования:

(4.11)

Это соотношение состоит из двух утверждений:

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

(4.12)

Здесь
зависит от управления по определению, функция же
не зависит от него. Тем не менее, производнаяот управления зависит. В этом можно убедиться, если ее представить в виде

изаменить согласно системе (4.1):

.(4.13)

Подставляя (4.13) в (4.12) получим уравнение Р.Беллмана:

. (4.14)

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

.

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

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

(4.15)

Уравнение (4.12) сохраняет силу, функция v в момент
должна удовлетворять условию

. (4.16)

4.3. Две задачи оптимального управления

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

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

. (4.17)

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

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

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

Значительное развитие получила задача синтеза оптимального управления процессами, описываемыми линейной системой дифференциальных уравнений, при минимизации интегральных квадратичных функционалов. Она называется задачей аналитического конструирования оптимальных регуляторов (АКОР), или задачей А.М.Летова.

4.4. Задача аналитического конструирования оптимальных регуляторов

Предположим уравнения возмущенного движения системы имеют вид

(4.18)

Матрицы
, размерности
и
, соответственно, имеют в качестве своих элементов известные функции
.

Предполагается также, что состояние системы (4.18) в каждый момент времени известно.

В качестве критерия оптимальности рассматривается квадратичный функционал Больца

где
- симметричные неотрицательно определенные матрицы,
- положительно определенная матрица; *) - индекс транспонирования.

Требуется найти оптимальное (минимизирующее функционал 4.19) управление, являющееся функцией текущего состояния
.

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

В соответствии с этим методом нужно найти функцию
, удовлетворяющего уравнению

. (4.20)

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

(4.21)

где
- есть некоторая, пока неизвестная, квадратичная форма, удовлетворяющая в силу (4.16) конечному условию

. (4.22)

Таким образом, для линейных систем задача сводится к отысканию функции
. Дифференцируя (4.21) с учетом (4.18) получим

Минимизируя (4.23) по
, получим

(4.24)

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

Подставляя (4.24) в (4.23), получим

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

(2.26)

с граничным условием (4.22).

Интегрируя уравнение (4.26) в обратном направлении, получим
, а значит и параметры оптимального управления (4.24). Нетрудно показать, что матрица
- симметричная матрица. Для этого достаточно транспонировать уравнение (4.26). Тогда

откуда с учетом симметричности матриц следует, что
.

Замечание 1 . В том случае, когда система (4.18) стационарна (матрицы A и B – числовые матрицы), матрицы - числовые матрицы,
(рассматривается установившийся режим). Матрицатоже числовая и удовлетворяет алгебраическому уравнению

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

4.5. Синтез локально-оптимального управления

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

Рассмотрим непрерывный управляемый процесс, описываемый системой дифференциальных уравнений (4.18).

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

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

В качестве критерия оптимальности рассмотрим функционал

матрица удовлетворяют тем же требованиям, что и в параграфе 4.4.

Нетрудно показать , что локально-оптимальное уравнение
с необходимостью удовлетворяет условию

. (4.28)

Воспользуемся этим условием.

Тогда, дифференцируя (4.27) в силу (4.18), найдем выражение для определения производной

из условия
найдем локально-оптимальное управление

Найденное управление действительно доставляет производной
, так как

.

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

Потребуем, например, чтобы на локально-оптимальном управлении выполнялось условие

. (4.31)

Тогда, подставляя (4.30) в (4.29), из (4.31) найдем

(4.32)

Из условия (4.32) следует, что оно будет выполнено, если матрица
будет определена из условия

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

(4.34)

Тогда из сравнения формул (4.24), (4.26), (4.22) и (4.30), (4.33), (4.34) следует, что локально-оптимальное управление(4.30) по критерию (4.27) с матрицей
, определяемой из уравнения (4.33) с условием (4.34) совпадает с управлением (4.24), оптимальным по квадратичному критерию (4.19) на интервале
.

5. Оптимальное управление стохастическими системами в условиях неопределенности.

5.1. Характеристики случайных сигналов

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

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

Через
будем обозначать реализацию случайного процесса
.

Следует отметить, что многие статистические характеристики случайных процессов и последовательностей совпадают.

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

или -мерная плотность распределения

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

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

Математическое ожидание (среднее значение)

; (5.3)

Дисперсия случайного процесса

Второй начальный момент

где
- центрированный случайный процесс с нулевым математическим ожиданием;

Среднеквадратичное отклонение

. (5.6)

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

. (5.7)

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

Если плотность распределения имеетгауссовский характер, то такой процесс называют гауссовским

.

Гауссовский процесс полностью определяется заданием математического ожидания
и корреляционной функции
.

Важной характеристикой стационарного случайного процесса в широком смысле является спектральная плотность
- плотностьраспределения дисперсии (энергии) по частотам.

Спектральная плотность
и корреляционная функция
связаны прямым и обратным преобразованием Фурье:

; (5.8)

. (5.9)

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

Наряду со скалярными случайными процессами можно рассматривать и векторные случайные процессы:

где каждая компонента
является случайным процессом. Для характеристики векторного случайного процесса вводятся следующие векторы и матрицы:

Математическое ожидание :

; (5.11)

Дисперсионная матрица
:

(5.12)

с элементами

; (5.13)

Ковариационная матрица
:

(5.14)

с элементами

; (5.15)

Матрица

с элементами

. (5.17)

Здесь
означает транспонирование.

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

Матрицы
,
и
обладают следующими свойствами:

; (5.18)

для всех и (5.I9)

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

. (5.21)

Матрица
обладает следующим свойством:

(5.22)

5.2. Математическое описание линейных систем при случайных возмущениях.

В общем виде уравнение управляемой динамической системы может быть записано в виде:

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

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

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

В данном учебном пособии будут рассматриваться только линейные системы.

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

Обозначим через

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

Здесь
,
,
- матрицы размерностей соответственно. Элементами этих матриц являются непрерывные функции. Если матрицы
иявляются постоянными, то управляемаясистема называется стационарной. Уравнения (5.24) обычно называют уравнениями состояния, так как они описывают изменение переменных состояния системы во времени.

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

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

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

(5.26)

В интегральной форме решение системы (5.24), в соответствии с формулой Коши, можно представить в следующем виде:

(5.27)

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

Относительно системы (5.24), (5.25) сделаем следующие предположения:

(5.28)

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

Одним из видов динамических систем являются дискретные системы, которые можно разделить на два типа:

а) собственно дискретные системы, такие как ЦВМ, автоматы различных типов и т.д.;

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

Рассмотрим поведение непрерывной системы с дискретным управлением, которое можно представить в виде кусочно-постоянной вектор-функции (рис. 15), т.е. управляющие воздействия можно записать в следующем виде:

для (5.29)

где - последовательность моментов времени, не обязательно равноотстоящих друг от друга.

Если нас интересует состояние системы только в дискретные моменты времени , то непрерывную систему (5.24) в эти моменты, используя соотношение (5.27), можно записать в следующем виде:

(5.30)

Учитывая (5.29), соотношение (5.30) перепишем в виде:

(5.31)

Третье слагаемое в соотношении (5.3I) можно рассматривать как некоторую случайную последовательность. В том случае, когда случайный процесс типа белого шума, то справедливо следующее соотношение:

,

где
- чисто случайная последовательность.

Вводя обозначения

(5.32)

систему уравнений (5.31) запишем в виде:

Матрицы называются переходными матрицами по состоянию, управлению и возмущению соответственно;
- дискретное время.

Уравнение измерений, соответственно, можно записать в виде:

Иногда систему (5.33) - (5.34) записывают в следующем виде:

Относительно систем (5.33), (5,34) будем предполагать, что:

(5.37)

Пример. Рассмотрим вращательное движение тела вокруг одной из осей под действием возмущающего момента
. Уравнения движения имеют вид:

, (5.38)

где - момент инерция тела;- угол поворота тела в некоторойинерциальной системе координат. Вводя новые переменные

(5.39)

получим уравнения движения объекта в нормальной форме:

(5.40)

Для этой системы уравнений фундаментальная матрица
состоит из двух вектор-столбцов решений следующей системы уравнений

с начальными условиями

Отсюда следует, что матрица
имеет вид:

(5.41)

Этот же результат получается, если искать матрицу
в виде ряда:

Рассмотрим поведение системы (5.40) через равные промежутки времени в моменты , т.е.
.

На основании соотношений (5.3I) - (5.33), полагая, что
постоянно на шаге дискретности, получим следующую эквивалентную дискретную систему:

(5.43)

(5.44)

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

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

, (5.45)

где матрица
определяется следующим образом:

причем
при
.

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

5.3. Уравнения моментов для линейных систем

Сначала рассмотрим непрерывные системы. Пусть уравнения движения имеют вид;

. (5.47)

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

При получении соотношений для математического ожидания состояния системы
осредним уравнение (5.47):

Учитывая (5.28), получим:

. (5.48)

На основании (5.47), (5.48) уравнение для центрированной составляющей
имеет вид:

. (5.49)

Теперь найдем уравнение для дисперсионной матрицы . Дифференцируя по матрицу
и учитывая, что матрицы
и
не случайные, получим:

(5.50)

Для вычисления математического ожидания
используем формулу Коши (5.27):

. (5.51)

Умножив выражение (5.51) справа на
, осредниви учитывая (5.28), получим:

(5.52)

С учетом того, что

, (5.53)

уравнение (5.50) примет вид;

с начальным условием
.

Теперь пусть поведение системы описывается дискретным уравнением

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

Осредняя (5.55) и учитывая (5.37), получим:

Уравнение для центрированной составляющей
имеет вид:

Используя (5.57) и (5.37), найдем уравнение для дисперсионной матрицы
:

(5.58)

Определим математическое ожидание
, используясоотношение (5.45) и свойства (5.37):

(5.59)

Аналогично

.

Таким образом, уравнение для определения матрицы
имеет вид:

5.4. Задача оптимальной фильтрации и ее решение методом Калмана

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

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

где
--мерный вектор состояния,
--мерный вектор возмущающих воздействий,
и
матрицы соответствующих размерностей.

Пусть измерению поддается
-мерный вектор некоторых комбинаций функций состояния (5.25)

где
- погрешность измерения.

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

Математически задача оптимальной фильтрации ставится как задача отыскания оценки
состояния системы (5.61)
на основе имеющейся информации
.

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

(5.63)

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

Так как
, то всегда будет ошибка оценки

.

Тогда для определения искомых матриц
и
можно использовать условие несмещенности оценки

(5.64)

и условие ее оптимальности

где
- симметричная положительно определенная матрица.

Для того, чтобы использовать условия (5.64) и (5.65) найдем уравнение для ошибки оценивания. Вычитая (5.63) из (5.61) с учетом (5.62), получим

Если теперь положить, что

то уравнение для ошибки оценки
примет вид:

с начальным условием

. (5.68)

Из (5.67), (5.68) следует, что условие несмещенности оценки (5.64) будет выполнено, если положить

. (5.69)

Чтобы убедиться в этом, достаточно взять математическое ожидание от выражений (5.67), (5.68)

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

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

Здесь
- корреляционная матрица ошибки оценивания (матрица вторыхцентральных моментов ошибок оценки компонент вектора состояния системы). Обозначим ее через
, тогда критерий оптимальности есть сумма диагональных элементов этой матрицы. В соответствие с условием локальной оптимальности будем искать оптимальное значение матрицы
из условия минимума производной к ритерия по времени:

. (5.71)

Нетрудно показать, что минимизация производной критерия обеспечивает минимум и для самого критерия

Запишем выражение
, опуская для простоты время :

. (5.72)

Подставив в (5.72) выражение для из (5.67) и соответствующее выражение для , получим:

(5.73)

Найдем
, для чего запишем уравнение Коши для (5.67):

где
- весовая матричная функция. Тогда

Используем свойство дельта-функции:

,

если имеетразрыв в точке
.

Поскольку

. (5.74)

Аналогично можно найти
:

. (5.75)

Подставив полученные выражения для
и соответственно транспонированные выражения для
в (5.73) получим:

Следующее тождество легко проверить, раскрыв в правой части скобки и использовав симметрию матрицы
:

С учетом тождества приведем уравнение (5.76) к виду:

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

При этом последний член в уравнении (5.78) обращается в нуль и уравнение приобретает вид

с начальным значением
.

Итак, можем записать уравнение фильтра

Уравнения (5.79), (5.80), (5.81) представляют собой уравнения фильтра Калмана-Бьюси.

Система оценивания (фильтр) схематически представлена на рис. 16.

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

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

Запишем уравнения стационарного фильтра Калмана в следующем виде:

; (5.83)

Один из часто используемых способов решения уравнения (5.84) (обычно с помощью ЦВМ) заключается в решении нестационарного уравнения (5.80) с соответствующими постоянными значениями коэффициентов, из которых составлены матрицы А, С, Q, R, и произвольной неотрицательно определенной матрицей начальных условий для в текущем времени до тех пор, пока полученное решение не достигнет постоянного установившегося значения. Это окончательное значение принимается за искомое решение уравнения (5.84). Такой способ решения удобен тем, что алгоритмы решения дифференциальных уравнений, как правило, эффективнее алгоритмов решения нелинейных алгебраических уравнений.

Замечание 1.

Важным свойством полученной ошибки является то, что она некоррелирована с ошибкой оценивания, т.е.

.

Замечание 2.

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

которая может быть представлена в виде (5.62)

Замечание 3.

Для управляемых систем, описываемых совокупностью уравнений

Уравнение фильтра может быть получено аналогично. В этом случае уравнение фильтра будет иметь вид

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

с начальным условием
.

Система оценивания (фильтр) схематически представлена на рис. 17.

5.5. Синтез локально-оптимального управления линейными стохастическими системами при полной и точной информации.

Пусть управляемое движение в условиях воздействия возмущений описывается системой уравнений

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

. (5.88)

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

В качестве функционала, характеризующего управляемое движение, возьмем математическое ожидание локального функционала
(4.27)

.

Введем матрицу корреляционных моментов

. (5.89)

Используя (5.88), (5.89) функционал можно
преобразовать к виду

(5.90)

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

Найдем уравнение для ее определения. Уравнение управляемого процесса (5.87) с учетом (5.88) можно представить в виде

где матрица

B соответствии с (5.54) уравнение для матрицы
будет иметь вид

или, с учетом (5.91),

(5.92)

Начальным условием является, очевидно,

Из (5.92), (5.93) с учетом предположения о симметричности матриц ,
непосредственно следует, что матрица
является симметричной, т.е.
.

Таким образом, задача определения оптимального управления свелась к задаче определения матрицы
из условия минимума
(5.90). Для нахождения ее воспользуемся условием (4.28). Дифференцируя (5.90) и учитывая (5.92), получим

Выпишем составляющие
, зависящие от
:

Обозначим через
искомую локально-оптимальную матрицу. Введем в рассмотрение семейство матричных функций сравнения

.

где
- произвольная малая вариация матричной функции
из рассматриваемого класса.

Приращение
, вызванное вариацией матрицы
, будет иметь вид

Тогда из (5.94) следует, что

В силу произвольности
и предполагая, что матрица
не особая, из условия
получим уравнение для определения оптимальной матрицы

Найденное значение
действительно доставляет минимум
, так как вторая вариация

в силу определенной положительности матрицы
. Здесь.

Сравнивая (5.88), (5.95) с (4.30), видим, что найденное локально-оптимальное управление полностью совпадает с локально-оптимальным управлением для детерминированного случая.

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

Аналогичный результат имеет место и при квадратичном критерии качества (4.19).

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

5.6. Синтез локально-оптимального управления линейными стохастическими системами (теорема разделения).

Пусть управляемое движение описывается уравнением (5.87), а уравнение измерения – (5.62).

Рассмотрим задачу синтеза, оптимального по критерию

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

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

Наряду с системой (5.87) рассмотрим соответствующую ей неуправляемую систему

с уравнением измерения

Для вспомогательной системы задача фильтрации решена и оценка
удовлетворяет уравнению

(5.98)

с начальным условием

где матрица
определяется из уравнений (5.79), (5.80).

Из уравнений (5.87) и (5.97) следует, что

, (5.99)

где
- фундаментальная матрица решений систем (5.87).

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

(5.100)

Из (5.99) и (5.100) следует, что

Найдем теперь уравнение для определения
. Для этого дифференцируя (5.100), получим

Учитывая (5.98), найдем

(5.101)

Тогда уравнение фильтра окончательно запишется в виде (5.85)

с начальным условием

, (5.103)

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

Теорема разделения. Локально-оптимальное управление системой (5.87) по критерию (5.96) имеет вид:

Здесь
- заданные матрицы локального функционала, а
- решение векторного уравнения (5.102) с начальным условием (5.103).

Доказательство. Рассмотрим функционал (5.96). Учитывая, что оценки
и ошибка оценки
не коррелированны для всех, функционал (5.96) можно представить в виде

,

Так как на
не влияет ни
, ни
, то задача сводится к минимизациипри условиях (5.102), (5.103). При этом оценка является полностью наблюдаемой.

Рассмотрим выражение

Учитывая, что , нетрудно показать , что

Таким образом, в уравнении (5.102) выражение
можно рассматривать как эквивалентный «белый шум» с корреляционной матрицей
.

В результате мы пришли к задаче синтеза локально-оптимального уравнения в системе (5.102), (5.103), возмущаемой «белым шумом» при полном и точном измерении ее состояния, решение которой было дано в предыдущем разделе. Теорема доказана. Можно показать, что теорема разделения справедлива и при синтезе оптимального управления по квадратичному решению.

Метод динамического программирования, как алгоритмическое выражение достаточно общей теории управления

В изложении существа метода динамического программирования мы опираемся на книгу “Курс теории автоматического управления” (Палю де Ла Барьер: французское издание 1966 г., русское издание - “Машиностроение”, 1973 г.), хотя и не повторяем его изложения. Отдельные положения взяты из упоминавшегося ранее курса “Исследование операций” Ю.П.Зайченко.

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

1. Рассматриваемая задача может быть представлена как N ‑шаговый процесс, описываемый соотношением:

X n + 1 = f(X n , U n , n) , где n - номер одного из множества возможных состояний системы, в которое она переходит по завершенииn -ного шага;X n - вектор состояния системы, принадлежащий упомянутому n -ному множеству; U n - управление, выработанное на шаге n (шаговое управление), переводящее систему из возможного её состояния вn -ном множестве в одно из состояний (n + 1 )‑го множества. Чтобы это представить наглядно, следует обратиться к рис. 8‑1, о котором речь пойдет далее.

2. Структура задачи не должна изменяться при изменении расчетного количества шагов N.

3. Размерность пространства параметров, которыми описывается состояние системы, не должна изменяться в зависимости от количества шагов N.

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

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

5. Критерий оптимального выбора последовательности шаговых управлений U n и соответствующей траектории в пространстве формальных параметров имеет вид:

V = V 0 (X 0 , U 0) + V 1 (X 1 , U 1) + ...+ V N - 1 (X N- 1 , U N - 1) + V N (X N) .

Критерий V принято называть полным выигрышем, а входящие в него слагаемые - шаговыми выигрышами . В задаче требуется найти последовательность шаговых управлений U n и траекторию, которым соответствует максимальный из возможных полных выигрышей . По своему существу полный “выигрыш” V - мера качества управления процессом в целом . Шаговые выигрыши, хотя и входят в меру качества управления процессом в целом, но в общем случае не являются мерами качества управления на соответствующих им шагах, поскольку метод предназначен для оптимизации управления процессом в целом, а эффектные шаговые управления с большим шаговым выигрышем, но лежащее внеоптимальной траектории интереса не представляют. Структура метода не запрещает при необходимости на каждом шаге употреблять критерий определения шагового выигрыша V n , отличный от критериев, принятых на других шагах.

С индексом n - указателем-определителем множеств возможных векторов состояния - в реальных задачах может быть связан некий изменяющийся параметр, например: время, пройденный путь, уровень мощности, мера расходования некоего ресурса и т.п. То есть метод применим не только для оптимизации управления процессами, длящимися во времени, но и к задачам оптимизации многовариантного одномоментного или нечувствительного ко времени решения, если такого рода “безвременные”, “непроцессные” задачи допускают их многошаговую интерпретацию.

Теперь обратимся к рис. 8‑1 - рис. 8‑3, повторяющие взаимно связанные рис. 40, 41, 42 из курса теории автоматического управления П. де Ла Барьера.

На рис. 8‑1 показаны начальное состояние системы «0» и множества её возможных последующих состояний «1», «2», «3», а также возможные переходы из каждого возможного состояния в другие возможные состояния. И всё это вместе похоже на карту настольной детской игры, по которой перемещаются фишки: каждому переходу-шагу соответствует свой шаговый выигрыш, а в завершающем процесс третьем множестве - каждому из состояний системы придана его оценка, помещенная в прямоугольнике. Принципиальное отличие от игры в том, что гадание о выборе пути, употребляемое в детской игре, на основе бросания костей или вращения волчка и т.п., в реальном управлении недопустимо, поскольку это - передача целесообразного управления тем силам, которые способны управлять выпадением костей, вращением волчка и т.п.

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

Рис. 8-1. К существу метода динамического программирования

В соответствии с этим на рис. 8‑2 анализируются возможные переходы в завершающее множество состояний «3» из каждого возможного состояния в ему предшествующем множестве состояний «2», будто бы весь предшествующий путь уже пройден и осталось последним выбором оптимального шагового управления завершить весь процесс. При этом для каждого из состояний в множестве «2» определяются все полные выигрыши как сумма = «оценка перехода» + «оценка завершающего состояния». Во множестве «2» из полученных для каждого из состояний, в нём возможных полных выигрышей, определяется и запоминается максимальный полный выигрыш и соответствующий ему переход (фрагмент траектории). Максимальный полный выигрыш для каждого из состояний во множестве «2» взят в прямоугольную рамку, а соответствующий ему переход отмечен стрелкой. Таких оптимальных переходов из одного состояния в другие, которым соответствует одно и то же значение полного выигрыша, в принципе может оказаться и несколько. В этом случае все они в ме­тоде неразличимы и эквивалентны один другому в смысле по­­строенного критерия оптимально­сти выбора траектории в пространстве параметров, которы­ми описывается система.

Рис. 8-2. К существу метода динамического программирования

После этого мно­жество «2», пред­шествовавшее завер­шающему процесс множеству «3», мож­но рассматривать в качестве завершаю­щего, поскольку из­вестны оценки каждого из его возможных состояний (мак­симальные полные выигрыши) и дальнейшая оптимизация последовательности шаговых управлений и выбор оптимальной траектории могут быть проведены только на ещё не рассмотренных множествах, предшествующих множеству «2» в оптимизируемом процессе (т.е. на множествах «0» и «1»).

Таким образом, процедура, иллюстрируемая рис. 8‑2, работоспособна на каждом алгоритмическом шаге метода при переходах из n -го в (n - 1) -е множество, начиная с завершающего N ‑ного множества до начального состояния системы.

В результате последовательного попарного перебора множеств, при прохождении всего их набора, определяется оптимальная последовательность преемственных шаговых управлений, максимально возможный полный выигрыш и соответствующая им траектория. На рис. 8‑3 утолщённой линией показана оптимальная траектория для рассматривавшегося примера.

В рассмотренном примере критерий оптимальности - сумма шаговых выигрышей. Но критерий оптимальности может быть построен и как произведение обязательно неотрицательных сомножителей.

Рис. 8-3. К существу метода динамического программирования

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

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

1). Метод динамического программирования формально нечувствителен к характеру причинно-следственных обусловленностей (в частности, он не различает причин и следствий). По этой причине каждая конкретная интерпретация метода в прикладных задачах должна строиться с неформальным учетом реальных причинно следственных обусловленностей;

2). Если прогностика в согласии с иерархически высшим объемлющим управлением, а частное вложенное в объемлющее управление осуществляется квалифицировано, в силу чего процесс частного управления протекает в ладу с иерархически высшим объемлющим управлением, то НЕ СУЩЕСТВУЕТ УПРАВЛЕНЧЕСКИ ЗНАЧИМОЙ РАЗНИЦЫ МЕЖДУ РЕАЛЬНЫМ НАСТОЯЩИМ И ИЗБРАННЫМ БУДУЩИМ. Процесс целостен, по какой причине еще не свершившееся, но уже нравственно избранное и объективно не запрещенное Свыше будущее, в свершившемся настоящем защищает тех, кто его творит на всех уровнях: начиная от защиты психики от наваждений до защиты от целенаправленной “физической” агрессии. То есть, если матрица возможных состояний (она же матрица возможных переходов) избрана в ладу с иерархически высшим объемлющим управлением, то она сама - защита и оружие, средство управления, на которое замкнуты все шесть приоритетов средств обобщенного оружия и управления.

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

Но для пользования методом динамического программирования и сопутствующими его освоению неформализованными в алгоритме жизненными проявлениями матриц перехода , необходимо СОБЛЮДЕНИЕ ГЛАВНОГО из условий:

В задачах оптимизации процессов управления метод динамического программирования <реального будущего: - по умолчанию> работоспособен только, если определён вектор целей управления, т.е. должно быть избрано завершающее процесс конкретное состояние.

В реальности это завершающее конкретное состояние должно быть заведомо устойчивым и приемлемым процессом, объемлющим и несущим оптимизируемый методом частный процесс. Но выбор и определение конкретных характеристик процесса, в который должна войти управляемая система по завершении алгоритма метода - лежит вне его самого в области “мистики” или в области методов, развитых в нематематических по своему существу науках.

«Каково бы ни было состояние системы перед очередным шагом, надо выбирать управление на этом шаге так, чтобы выигрыш на данном шаге плюс оптимальный выигрыш на всех последующих шагах был максимальным.» - Е.С.Вентцель, “Исследование операций. Задачи, принципы, методология.”, М., “Наука”, 1988 г., с. 109.

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

Это тем более справедливо для последовательных многовариантных шаговых переходов, если матрица возможных состояний вписывается в пословицу «Все дороги ведут в “Рим”», а которые не ведут в “Рим”, - ведут в небытие . Для такого рода процессов, если избрана устойчивая во времени цель и к ней ведут множество траекторий, то при устойчивом пошаговом управлении “расстояние” между оптимальными траекториями, идущими к одной и той же цели из различных исходных состояний, от шага к шагу сокращается, вплоть до полного совпадения оптимальных траекторий, начиная с некоторого шага. Это утверждение тем более справедливо, чем более определённо положение завершающего процесс вектора целей в пространстве параметров. По аналогии с математикой это можно назвать асимптотическим множеством траекторий: асимптотичность множества траекторий выражается в том, что «все дороги ведут в “Рим”...»

И в более общем случае, рекомендации Нового Завета и Корана утверждают возможность обретения благодати, милости Вседержителя вне зависимости от начального состояния (греховности человека) в тот момент, когда он очнулся и увидел свои дела такими, каковы они есть.

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

То есть методдинамического программирования, необходимостью как определенности в выборе конечного состояния-процесса, так и выявления истинного начального состояния, сам собой защищен от применения его для наукообразной имитации оптимизации управления при отсутствии такового. Это отличает метод динамического программирования, в частности от аппарата линейного программирования, в который можно сгрузить экспромтные оценки “экспертами” весовых коэффициентов в критериях оптимизации Min (Z) либоMax (Z) .

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

Примерами тому “Математическая экономика на персональном компьютере” под ред. М.Кубонива, в которой глава об управлении в экономике содержит исключительно макроэкономические интерпретации аппарата линейного программирования (прямо так и названа “Управление в экономике. Линейное программирование и его применение”), но ничего не говорит о векторе целей управления и средствах управления; в ранее цитированном учебнике Ю.П.Зай­че­н­ко описание метода динамического программирования, так же построено на задачах иного характера.

Однако при мотивации отказа от макроэкономических интерпретаций метода динамического программирования авторы обычно ссылаются на так называемое в вычислительной математике «про­кля­тие размерности», которое выражается в том, что рост размерности пространства параметров задачи N вызывает рост объема вычислений, пропорциональный N k , где показатель степени k > 1 . Такой нелинейный сверхпропорциональный рост объема вычислений действительно делает многие вычислительные работоспособные процедуры никчемными в решении практических задач как из-за больших затрат машинного времени компьютеров, так и из-за накопления ошибок в приближенных вычислениях. Но это «проклятие размерности» относится не только к методу динамического программирования, но и к другим методам, которые, однако, встречаются и в их макроэкономических интерпретациях.

ВАЖНО ОБРАТИТЬ ВНИМАНИЕ И ПОНЯТЬ: Если в математике видеть науку об объективной общевселенской мере (через “ять”), а в её понятийном, терминологическом аппарате и символике видеть одно из предоставленных людям средств описания объективных частных процессов, выделяемых ими из некоторых объемлющих процессов, то всякое описание метода динамического программирования есть краткое изложение всей ранее изложенной достаточно общей теории управления, включая и её мистико-религи­оз­ные аспекты; но - на языке математики.

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

На нём показаны два объекта управления «А» и «Б» в начальном состоянии; три объективно возможных завершающих состояния (множество «5»); множества («1» - «4») промежуточных возможных состояний; и пути объективно возможных переходов из каждого состояния в иные.

Рис. 9 можно уподобить некоторому фрагменту общевселенской меры развития (многовариантного предопределения) - одной из составляющих в триединстве «материя-информация-мера».

Если принять такое уподобление рис. 9, то объективно возможен переход из любого начального состояния «0:1» или «0:2» в любое из завершающих состояний «5:1», «5:2», «5:3». Но эта объективная возможность может быть ограничена субъективными качествами управленцев, намеревающихся перевести объекты «А» и «Б» из начального состояния в одно из завершающих состояний.

Если дано свыше Различение, то управленец «А» (или «Б») снимет с объективной меры “кальку”, на которой будет виден хотя бы один из множества возможных путей перевода объекта из начального состояния во множество завершающих. Если Различение не дано, утрачено или отвергнуто в погоне за вожделениями, или бездумной верой в какую-либо традицию, но не Богу по совести, то на “кальке” будут отсутствовать какие-то пути и состояния, но могут “появиться” объективно невозможные пути и состояния, объективно не существующие в истинной Богом данной мере. Кроме того по субъективному произволу управленца выбирается и желанное определенное завершающее состояние из их множества. Соответственно следование отсебятине или ошибка в выборе предпочтительного завершающего состояния может завершиться катастрофой с необратимыми последствиями.

Рис. 9. Динамическое программирование, Различение и достаточно общая теория управления

Но матрица возможных состояний, показанная на рис. 9, вероятностно предопределяет только частный процесс в некой взаимной вложенности процессов.

По этой причине каждое из начальных состояний «0:1», «0:2» может принадлежать либо одному и тому же, либо различным объемлющим процессам, в управленческом смысле иерархически высшим по отношению к рассматриваемому; то же касается и каждого из завершающих состояний «5:1», «5:2», «5:3» в паре «исходное - завершающее» состояния. Каждый из объемлющих процессов обладает их собственными характеристиками и направленностью течения событий в нём.

Может оказаться, что цель «5:1» очень привлекательна, если смотреть на неё из множества начальных неудовлетворительных состояний. Но не исключено, что объемлющий процесс, к которому завершающее состояние «5:1» принадлежит, как промежуточное состояние, в силу взаимной вложенности процессов, на одном из последующих шагов завершается полной и необратимой катастрофой. Например, цель «5:1» - не опоздать на “Титаник”, выходящий в свой первый рейс, ... ставший трагическим и последним. Чтобы не выбирать такую цель из множества объективно возможных, необходимо быть в ладу с иерархически наивысшим объемлющим управлением, которое удержит частное ладное с ним управление от выбора такой цели, принадлежащей к обреченному на исчезновение процессу.

Но если рис. 9 - “калька” с объективной меры, то может статься, что какое-то завершающее состояние, являющееся вектором целей - отсебятина, выражающая желание “сесть на два поезда сразу”. Иными словами разные компоненты вектора целей принадлежат к двум или более взаимно исключающим друг друга иерархически высшим объемлющим процессам протекающим одновременно.

Это один из случаев неопределенности и дефективности вектора целей, делающий метод динамического программирования неработоспособным, а реальный процесс “управления” неустойчивым, поскольку одна и та же “лодка” не может пристать и к правому, и к левому берегу одновременно, даже если привлекательные красоты на обоих берегах реки, при взгляде издали из-за поворота реки совмещаются, создавая видимость подходящего для пикника весьма уютного места. Чтобы не выбрать такого вектора целей, также необходимо, чтобы Свыше было дано Различение правого и левого “бере­гов” потока бытия.

То есть алгоритму динамического программирования, даже если его можно запустить, сопутствует еще одно внешнее обстоятельство, которое тоже очевидно, “само собой” разумеется, но в большинстве случаев игнорируется: завершающее частный оптимизируемый процесс состояние должно принадлежать объемлющему процессу, обладающему заведомо приемлемыми собственными характеристиками течения событий в нём.

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

Концепция управления в объективной мере, обладает собственными характеристиками, которые совместно с субъективными характеристиками субъекта-управленца, порождают вероятностную предопределенность осуществления им концепции управления. Значение вероятностной предопределенности успешного завершения процесса - объективная иерархически высшая мера, оценка замкнутой системы «объект + управленец + концепция», в отличие от вероятности - объективной меры системы «объект + объективно существующая концепция управления».

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

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

Вследствие нетождественности вероятности и вероятностной предопределенности очень хорошая концепция может быть загублена плохими исполнителями её: на двухколесном велосипеде ездить лучше, чем на трехколёсном, но не все умеют; но некоторые ещё будут доказывать, что на двухколесном и ездить нельзя, поскольку он падает и сам по себе, а не то что с сидящим на нём человеком, тем более на ходу, - если они ранее не видели, как ездят на двухколесном; а третьи, не умея и не желая учиться ездить самим, из ревности не отдадут велосипед тем, кто умеет.

Поэтому после принятия концепции к исполнению необходимо придерживаться концептуальной дисциплины и взращивать концептуальную дисциплину. То есть необходимо поддерживать достаточно высокое качество управления на каждом шаге всеми средствами, чтобы не оказаться к началу следующего шага в положении, из которого в соответствии с избранной концепцией управления перевод объекта в избранное завершающее состояние невозможен. Этот случай - уклонение с избранного пути «2:2» -> «3:3» показан: дуга «2:2» -> «3:1» - необратимый срыв управления, после которого невозможен переход в состояние «5:3»; дуга «2:2» -> «3:2» - обратимый срыв управления, в том смысле что требуется корректирование концепции, исходя из состояния «3:2», рассматриваемого в качестве начального.

Если на рис. 9 объективной иерархически высшей мере качества состояний, в которых могут находиться объекты субъектов-управленцев «А» и «Б», соответствует шкала качества возможных состояний «I », то для их блага целесообразен переход из множества состояний «0» в состояние «5:3». Но выбор ими направленности шкалы оценки качества состояний нравственно обусловлен и субъективен: либо как показано на рис. 9 «I », либо в противоположном «I » направлении.

Если на рис. 9 возможные состояния сгруппированы во множества «1», «2», «3», «4», «5» по признаку синхронности, то в координатных осях 0ty , при шкале качества состояний «I » расстояние от оси 0t до любой из траекторий - текущая ошибка управления при движении по этой траектории. Площадь между осью 0t и траекторией - интеграл по времени от текущей ошибки. Он может быть использован как критерий-минимум оптимальности процесса управления в целом, т.е. в качестве полного выигрыша, являющегося в методе динамического программирования мерой качества, но не возможных состояний, не шагов-переходов из одного состояния в другое, а всей траектории перехода. Но в общем случае метода шаговые выигрыши могут быть построены и иначе.

Если принят критерий оптимальности типа минимум

R УПР m =< R - (ФУР m - R С)

ΣR i =< k x ЭП, i = 1, ... , n

R УПР m => R min (ЛП-4),

Найти Max(Y), Y = F K T P Б

X KБ (E - A T) P Б - (ФУР m - R С) = R УПР l =< R - (ФУР m - R С)

R УПР m => R min (ЛП-РВ).

Найти Max(Y), Y = F K T P Б

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

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

Если считать целевую функцию аддитивной от показателя эффективности каждого шага, то на шаге и целевая функция имеет вид

Решением задачи динамического программирования является определение такого управления , которое переводит систему из состояния в состояние при наибольшем (наименьшем) значении .

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

Рассмотрим последний шаг . Состояние системы к началу шага , управление, а - целевая функция. Согласно принципу оптимальности управление нужно выбирать так, чтобы для любого состояния получался условный максимум целевой функции

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

Отыскивается условное оптимальное управление на двух последних шагах для всех возможных состояний системы на предпоследнем шаге

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

В результате условной оптимизации могут быть получены последовательности значений критериальной функции и условных управлений

Решение задачи динамического программирования получается в результате подстановки конкретного значения в выражение для решения на первом шаге и . Далее определяется состояние первого шага

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

При практической реализации метода динамического программирования на ЭВМ возникает ряд трудностей, связанных, в частности, со способами описания состояния объекта управления. Как правило, рассматривается конечное число состояний объекта управления на каждом шаге. Тем не менее, наибольший интерес представляет случай отыскания оптимального состояния объекта из бесконечного числа возможных состояний, например, методом математического программирования. В доступной литературе такие материалы отсутствуют, кроме того, не имеется сведений о программной реализации метода динамического программирования, хотя потребность в решении таких задач в достаточно велика. Из сказанного следует, что доведение методов динамического программирования до практического использования представляет собой актуальную и важную задачу исследования.