Метод динамического программирования в управлении. Метод динамического программирования
Для выбора оптимального решения при выполнении задач программирования иногда требуется перебирать большое количество комбинаций данных, что нагружает память персонального компьютера. К таким методам относится, например, метод программирования «разделяй и властвуй». В данном случае алгоритмом предусмотрено разделение задачи на отдельные мелкие подзадачи. Такой метод применяется только в тех случаях, когда мелкие подзадачи независимы между собой. Для того чтобы избежать выполнения лишней работы в том случае, если подзадачи взаимозависимы, используется метод динамического программирования, предложенный американцем Р.Беллманом в 50-х годах.
Суть метода
Динамическое программирование заключается в определении оптимального решения n-мерной задачи, разделяя ее n отдельных этапов. Каждый из них является подзадачей по отношению к одной переменной.
Основным преимуществом такого подхода можно считать то, что разработчики занимаются одномерными оптимизационными задачами подзадач вместо n-мерной задачи, а решение главной задачи собирается «снизу вверх».
Целесообразно применять динамическое программирование в тех случаях, когда подзадачи взаимосвязаны, т.е. имеют общие модули. Алгоритмом предусмотрено решение каждой из подзадач один раз, и сохранение ответов выполняется в специальной таблице. Это дает возможность не вычислять ответ заново при встрече с аналогичной подзадачей.
Задача динамического программирования оптимизации. Автором этого метода Р. Беллманом был сформулирован принцип оптимальности: каким бы ни являлось начальное состояние на каждом из шагов и решение, определенное на этом шаге, все следующие выбираются оптимальными по отношению к тому состоянию, которое принимает система в конце шага.
Метод усовершенствует выполнение задач, решаемых с помощью перебора вариантов или рекурсий.
Построение алгоритма задачи
Динамическое программирование предполагает построение такого алгоритма задач, при котором задача так разбивается на две или больше подзадач, чтобы ее решение складывалось из оптимального решения всех подзадач, входящих в нее. Далее возникает необходимость в написании рекуррентного соотношения и вычислении оптимального значения параметра для задачи в целом.
Иногда на 3-м шаге нужно дополнительно запоминать некоторую вспомогательную информацию о ходе выполнения каждой подзадачи. Это называется обратным ходом.
Применение метода
Динамическое программирование применяется при наличии двух характерных признаков:
- оптимальность для подзадач;
- наличие в задаче перекрывающихся подзадач.
Решая методом динамического программирования, сначала необходимо описать структуру решения. Задача обладает оптимальностью, если решение задачи складывается из оптимальных решений ее подзадач. В этом случае целесообразно использовать динамическое программирование.
Второе свойство задачи, существенное при данном методе, - небольшое число подзадач. Рекурсивное решение задачи использует одни и те же перекрывающиеся подзадачи, количество которых зависит от размера исходной информации. Ответ хранится в специальной таблице, программа экономит время, пользуясь этими данными.
Особенно эффективно применение динамического программирования тогда, когда по существу задачи нужно принимать решения поэтапно. Например, рассмотрим простой пример задачи замены и ремонта оборудования. Допустим, на литейной машине завода по изготовлению шин делают одновременно шины в двух разных формах. В том случае, если одна из форм выходит из строя, приходится машину разбирать. Понятно, что иногда выгоднее заменить и вторую форму для того, чтобы не разбирать машину на случай, если и эта форма окажется неработоспособной на следующем этапе. Тем более, бывает проще заменить обе работающие формы до того, как они начнут выходить из строя. Метод динамического программирования определяет наилучшую стратегию в вопросе о замене таких форм, учитывая все факторы: выгоду от продолжения эксплуатации форм, потери от простоя машины, стоимость забракованных шин и другое.
Динамическим программированием называется метод оптимизации, в котором процесс принятия решения может быть разбит на шаги . Каждый шаг переводит объект управления из состояния в состояние посредством управления . Если общее количество шагов равно , то можно говорить о последовательности состояний системы, которую она принимает в результате воздействия различных управлений Целевая функция системы зависит от начального состояния и управления
Предполагается, что состояние системы в конце -того шага зависит только от предшествующего состояния и управления на -том шаге . Тогда уравнение состояния системы имеет вид
Если считать целевую функцию аддитивной от показателя эффективности каждого шага, то на шаге 
и целевая функция имеет вид
Решением задачи динамического программирования является определение такого управления 
, которое переводит систему из состояния в состояние при наибольшем (наименьшем) значении .
Для решения задачи динамического программирования был сформулирован так называемый принцип оптимальности. Его смысл которого сводится к следующему: каково бы ни было состояние системы в результате выполнения какого-либо числа шагов, управление на ближайшем шаге нужно выбирать так, чтобы оно в совокупности с оптимальным управлением на всех последующих шагах приводило к максимальному выигрышу на всех оставшихся шагах включая данный.
Рассмотрим последний шаг . Состояние системы к началу шага , управление, а - целевая функция. Согласно принципу оптимальности управление нужно выбирать так, чтобы для любого состояния получался условный максимум целевой функции
Решение , при котором достигается называется условным оптимальным управлением на шаге . Условный максимум целевой функции отыскивается для всех возможных состояний системы на последнем шаге. Далее рассматривается совместно последний и предпоследний шаг. Целевая функция в этом случае имеет вид
Отыскивается условное оптимальное управление на двух последних шагах для всех возможных состояний системы на предпоследнем шаге
Состояние системы при известном управлении определяется как 
, в связи с чем целевая функция зависит только от состояния на предыдущем шаге и текущего управления. Далее рассматривается три, четыре и т.д. последних шага. В общем случае для шага получается уравнение Белмана, впервые разработавшего метод динамического программирования.
В результате условной оптимизации могут быть получены последовательности значений критериальной функции и условных управлений
Решение задачи динамического программирования получается в результате подстановки конкретного значения в выражение для решения на первом шаге и . Далее определяется состояние первого шага
и так далее для всех шагов. Оптимальное решение задачи получается при последовательном расчете оптимальных решений и и новых состояний 
.
При практической реализации метода динамического программирования на ЭВМ возникает ряд трудностей, связанных, в частности, со способами описания состояния объекта управления. Как правило, рассматривается конечное число состояний объекта управления на каждом шаге. Тем не менее, наибольший интерес представляет случай отыскания оптимального состояния объекта из бесконечного числа возможных состояний, например, методом математического программирования. В доступной литературе такие материалы отсутствуют, кроме того, не имеется сведений о программной реализации метода динамического программирования, хотя потребность в решении таких задач в достаточно велика. Из сказанного следует, что доведение методов динамического программирования до практического использования представляет собой актуальную и важную задачу исследования.
Среди задач, решаемых с помощью математического программирования, можно выделить отдельный класс задач, требующих оптимизации многошаговых (многоэтапных) процессов. Такие задачи отличаются возможностью разбиения решения на несколько взаимосвязанных этапов. Для решения подобных задач используется динамическое программирование или, как его еще называют, многоэтапное программирование. Его методы оптимизированы для поиска оптимального решения многошаговых задач, которые можно разделить на несколько этапов, шагов и т. д.
Происхождение термина
Использование в названии слова «динамический» первоначально предполагало, что разделение на подзадачи будет происходить в основном во времени. При использовании динамических методов для решения производственных, хозяйственных и иных задач, в которых фигурирует временной фактор, разбивание на отдельные этапы не составляет труда. Но использовать технику динамического программирования возможно и в задачах, где отдельные этапы не связаны по времени. Всегда в многошаговой задаче можно выделить параметр или свойство, по которому можно произвести разделение на отдельные шаги.
Алгоритм (метод) решения многоэтапных задач
Алгоритм илиметод динамического программирования основан на использовании принципа последовательного оптимизирования задачи, когда решение общей задачи разбивается на ряд решений отдельных подзадач с последующим объединением в единое решение. Очень часто отдельные подзадачи оказываются одинаковыми, и одно общее решение значительно сокращает время расчета.
Особенностью метода является автономность решения задачи на каждом отдельном этапе, т. е. независимо от того, как оптимизировался и решался процесс на предыдущем этапе, в текущем расчете используются только параметры процесса, характеризующие его в данный момент. Например, водитель, двигающийся по дороге, принимает решение о текущем повороте независимо от того, как и сколько он ехал до этого.
Метод сверху и метод снизу
Несмотря то что при расчете на отдельном этапе решения задачи используются параметры процесса на текущий момент, результат оптимизации на предыдущем этапе влияет на расчеты последующих этапов для достижения наилучшего результата в целом. Динамическое программирование называет такой принцип решения методом оптимальности, который определяет, что оптимальная стратегия решения задачи вне зависимости от начальных решений и условий должна последующими решениями на всех этапах составить оптимальную стратегию относительно первоначального состояния. Как видим, процесс решения задачи представляет собой непрерывную оптимизацию результата на каждом отдельном этапе от первого до последнего. Такой метод называется методом программирования сверху. На рисунке схематически показан алгоритм решения сверху вниз. Но существует класс многошаговых задач, в которых максимальный эффект на последнем этапе уже известен, например, мы уже приехали из пункта А в пункт Б и теперь хотим узнать, правильно мы ехали на каждом предыдущем этапе или можно было что-то сделать более оптимально. Возникает рекурсивная последовательность этапов, т. е. мы идем как бы «от обратного». Этот метод решения получил название "метод программирования снизу".
Практическое применение
Динамическое программирование может использоваться в любой сфере деятельности, где присутствуют процессы, которые можно по какому-либо параметру (время, сумма, температура и т. д.) разделить на ряд одинаковых небольших этапов. Наибольшее применение динамические способы решения получили в теории управления и при разработке вычислительных систем.
Поиск оптимального пути
С помощью динамической оптимизации возможно решение широкого класса задач по нахождению или оптимизации кратчайшего пути и других задач, в которых «классический» метод перебора возможных вариантов решения приводит к увеличению времени расчета, а иногда вообще неприемлем. Классическая задача динамического программирования - это задача о рюкзаке: дано некоторое количество предметов с определенной массой и стоимостью, и необходимо выбрать набор предметов с максимальной стоимостью и массой, не превосходящий объем рюкзака. Классический перебор всех вариантов в поисках оптимального решения займет значительное время, а с помощью динамических методов задача решается в приемлемые сроки. Задачи поиска кратчайшего пути для транспортной логистики являются основными, и динамические методы решения оптимально подходят для их решения. Наиболее простым примером такой задачи является построение кратчайшего маршрута автомобильным GPS-навигатором.
Производство
Динамическое программирование широко используется при решении разнообразных производственных задач, таких как управление складскими запасами для поддержания нужного количества комплектующих в любой момент времени, календарное планирование производственного процесса, текущий и капитальный ремонт оборудования, равномерная загрузка персонала, максимально эффективное распределение инвестиционных средств и т. д. Для решения производственных задач методами динамического программирования разработаны специальные программные пакеты, интегрированные в популярные системы управления предприятиями, такие как SAP.
Научная сфера
Методы динамического программирования широко применяются в различных научных исследованиях. Например, они успешно используются в алгоритмах распознавания речи и образов, при обработке больших массивов данных в социологии и
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), возмущаемой «белым шумом» при полном и точном измерении ее состояния, решение которой было дано в предыдущем разделе. Теорема доказана. Можно показать, что теорема разделения справедлива и при синтезе оптимального управления по квадратичному решению.
Для развития трех торговых предприятий выделено 4 млн. руб. Известна эффективность капитальных вложений в каждое предприятие, заданное значением нелинейной функции? k (x k). Требуется составить оптимальный план распределения капитальных вложений между предприятиями. Предполагается, что распределение денежных средств проводится в целых числах x k , x k = 0, 1, 2, 3, 4.
Исходные данные.
Используя метод динамического программирования, решаем задачу с помощью сервиса распределение денежных средств .
I этап. Условная оптимизация.
1-ый шаг. k = 3.
2-ый шаг. k = 2.
3-ый шаг. k = 1.
Поясним построение таблиц и последовательность проведения расчетов.
Столбцы 1, 2 и 3 для всех трех таблиц одинаковы, поэтому их можно было бы сделать общими. Столбец 4 заполняется на основе исходных данных о функциях дохода, значения в столбце 5 берутся из столбца 7 предыдущей таблицы, столбец 6 заполняется суммой значений столбцов 4 и 5 (в таблице 3-го шага столбцы 5 и 6 отсутствуют).
В столбце 7 записывается максимальное значение предыдущего столбца для фиксированного начального состояния, и в 8 столбце записывается управление из 2 столбца, на котором достигается максимум в 7.
Этап II. Безусловная оптимизация.
Из таблицы 3-го шага имеем F* 3 (e 0 = 4) = 7.6. То есть максимальный доход всей системы при количестве средств e 0 = 4 равен 7.6 млн. руб.
Из этой же таблицы получаем, что первому торговому предприятию следует выделить u* 1 (e 0 = 4) = 1
Из таблицы 2-го шага имеем F* 2 (e 1 = 3) = 4.5. То есть максимальный доход всей системы при количестве средств e 1 = 3 равен 4.5 млн. руб.
Из этой же таблицы получаем, что второму торговому предприятию следует выделить u* 2 (e 1 = 3) = 2
При этом остаток средств составит:
Последнему торговому предприятию достается 1 млн. руб..
Таким образом, применив метод динамического программирования, мы нашли, что капитальные вложения в размере 4 млн. руб. необходимо распределить следующим образом:
1-му торговому предприятию выделить 1;
2-му торговому предприятию выделить 2;
3-му торговому предприятию выделить 1;
Что обеспечит максимальный доход, равный 7.6 млн. руб.