При моделировании сетевых структур помимо задач, связанных с существованием потоков в транспортных, электрических, телефонных, компьютерных и прочих видах сетей, возникает целый класс задач, сводимых к задаче о кратчайшем пути. Например, задача о кратчайшем пути всякий раз решается программой - маршрутизатором при нахождении сайта по его имени в сети Интернет.
Задача о кратчайшем пути в ориентированной сети является типичной задачей динамического программирования, поэтому, хотя динамическое программирование, также как и сетевое планирование, связано с развитием процессов во времени, моделирование которых более детально рассмотрено в следующем разделе, рассмотрим уже в этом параграфе метод динамического программирования на примере поиска кратчайшего пути.
Понятие динамического программирования тесно связано с многошаговыми процессами принятия решений. Многошаговый процесс принятия решений можно определить, как процесс принятия последовательных решений, направленных на достижение заданной цели. Многошаговые процессы принятия решений постоянно встречаются в самых различных ситуациях, от ремонта автомобиля в автосервисе до управления космическим аппаратом.
Динамическое программирование можно приблизительно определить, как набор математических процедур, используемых при анализе многошаговых процессов принятия решений. Каждый многошаговый процесс принятия решений представляет собой развитие следующей задачи: найти кратчайший путь в направленной, ациклической сети.
Динамическое программирование можно рассматривать как единую теорию благодаря единому набору идей и приемов, которые используются при математическом анализе различных задач. Эти идеи и приемы и составляют сущность динамического программирования. Беллман одним из первых понял суть принципа оптимальности и стал применять его ко многим оптимизационным задачам, возникающих в математике, технике, исследовании операций и в других областях.
Таким образом, понятие динамического программирования связано с многошаговым процессом принятия решений для достижения определенной цели. Например, перевод летательного аппарата с одной орбиты на другую представляет собой типичную задачу динамического программирования, при условии, если коррекция орбиты осуществляется приложением импульса в дискретные моменты времени, а целью является экономия топлива.
Характеризуя динамическое программирование, как набор математических процедур для оптимального управления дискретной системой, в общем виде задачу оптимального управления можно сформулировать следующим образом. В дискретные моменты времени t = 1, 2,..., N система находится в одном из множеств s i состояний, характеризуемых вектором состояния x (t) . Переход между последовательными состояниями осуществляется с помощью вектора управления u (t) по закону:
x ( t ) = g ( t ) (x ( t ) , u ( t )) ; t = 1, 2,..., N
Управления u (t) выбираются из множества допустимых управлений и образуют последовательность допустимых управлений u (0) ,u (1) ,…,u (N) . Последовательность допустимых управлений при заданном начальном состоянии х (0) определяет траекторию системы х (0) ,х (1) ,х (2) ,…,х (N) .
Всякой траектории соответствует свое значение критерия оптимальности F , или целевой функции управления, слагающегося из отдельных вкладов на каждом этапе управления:
Задачa оптимального управления заключается в нахождении среди множества последовательностей управления такой, которая достигает минимального значения F. Такая последовательность называется оптимальной последовательностью управлений и определяет оптимальную траекторию.
В основе динамического программирования лежит принцип оптимальности Беллмана, который можно сформулировать так. Оптимальная стратегия обладает таким свойством, что каково бы ни было начальное состояние и решение в начальный момент, последующие решения должны формулировать оптимальную стратегию относительно состояния, возникающего после начального решения.
Смысл принципа оптимальности становится ясней, если учесть, что для оптимальной траектории каждый ее участок между конечной точкой и любой промежуточной также является оптимальной траекторией. Принцип оптимальности, или иначе метод динамического программирования, позволяет отыскать оптимальную многошаговую стратегию путем решения совокупности более простых одношаговых оптимизационных задач.
Метод динамического программирования хорошо иллюстрируется на примере поиска кратчайшего пути между крайними узлами ориентированной сети. Рассмотрим некоторую ориентированную сеть, насчитывающую 12 узлов, которую нужно пройти от начального узла (1) до конечного узла (12) за четыре шага, передвигаясь с каждым шагом от узла к узлу.
Рис. 6.4.1. Прохождение ориентированной сети по кратчайшему пути.
Числа, указанные при дугах (i,j ) равны длинам дуг l ij между узлами i и j (в условных единицах). Возможные состояния системы s i в данном случае связаны с нахождением в i -м узле, управление u (t) связано с выбором направления пути на каждом шаге управления. Четыре шага управления u (1) ,...,u (4) последовательно переводят систему из начального состояния s 1 в конечное состояние s 12 и, таким образом, образуют некоторую траекторию, которую необходимо отыскать. В роли критериея оптимальности F в данном случае выступает длина траектории L , слагающаяся из длин отдельных дуг:
Если поиски кратчайшего пути, т. е. оптимальной траектории, начинать не с начала, а сконца сети и двигаться в обратном направлении к началу, то в этом случае мы имеем алгоритм «обратной прогонки». В данном случае при реализации алгоритма обратной прогонки движение осуществляется от конечного состояния s 12 к начальному состоянию s 1 .
Вначале поиска кратчайшего пути составляется таблица переходов. Число строк таблицы равно числу шагов управления, число столбцов равно числу состояний минус один. В этой таблице будут храниться шаги управления и соответствующие им значения критерия оптимальности L t для всех возможных состояний системы после каждого шага.
Таблица 6.4.1
| i t | s 1 | s 2 | s 3 | s 4 | s 5 | S 6 | s 7 | s 8 | s 9 | s 10 | s 11 |
| 12 | 12 6 | ||||||||||
| 10 | 11 10 | ||||||||||
| 5 | |||||||||||
| 1 |
Заполненные клетки таблицы разбиты пополам. В верхнюю часть заполненной клетки заносится управление u (t) , т. е. в данном случае номер узла, в который осуществляется переход. В нижнюю часть заполненной клетки заносится то значение вклада L t в общее значение критерия оптимальности L , которое было получено при переходеиз соответствующего этой клетке узла в конечный узел.
Заполнение таблицы начинается с первой строки, где хранится информация о последнем шаге пути. Последний, в данном случае четвертый шаг пути определен однозначно при переходе из любого предпоследнего состояния, которым может быть любое из трех возможных: s 9 , s 10 , s 11 . Поэтому оптимальное управление на последнем шаге очевидно. В зависимости от предпоследнего состояния вклад в критерий оптимальности L 4 (9) = 12, L 4 (10) = 6, либо L 4 (11) = 7. Эти значения вклада в L записываются в нижней части клеток первой строки табл. 6.4.1.
Перед предпоследним – в данном случае третьим - шагом множество возможных состояний системы есть {s 5 , s 6 , s 7 , s 8 }. Применим теперь принцип Беллмана для определения траектории на третьем и четвертом шаге. Он заключается в том, что независимо от первых двух шагов управления отрезок траектории на последних двух шагах сам по себе является оптимальной траекторией, т.е. дает минимум вклада L 3 в критерий оптимальности.
Если состояние системы перед предпоследним шагом есть состояние s 8 , то на последних шагах вклад в L определяется соотношением
L 3 (s 5)=min{ 
}.
Поскольку из s 5 возможны переходы в s 9 и s 11 .т.е.:
g(s 5 ,9) = s 9 ; ; L 4 (s 9) = 12,
g(s 5 ,11) = s 11 ; ; L 4 (s 11) = 7,
L 3 (s 5) = min{6+12, 4+7} = 11 и u (3) = 11.
Это означает, что если система находится в состоянии s 5 , то оптимальное управление заключается сначала в переходе в состояние s 11 , затем в состояние s 12 . Длина дуги из s 5 в s 12 при этом оказывается равна 11 единиц.
Рассчитывая вклад в L аналогично для переходов из состояний s 6 , s 7 , s 8 , получим следующие вклады:
L 3 (s 6)=min{7+12, 6+6)=12 , u (3) =10;
L 3 (s 7)=min{5+6, 3+7)=10, u (3) =11;
L 3 (s 8)=min{10+6, 12+7)=16, u (3) =10;
Полученные четыре пары чисел записываются во вторую строку Табл. 6.4.1.
На втором шаге управления вклад в критерий оптимальности в зависимости от исходного состояния есть
L 2 (s 2) = min{ } = min{11+11, 14+10} = 22, u (2) = 5;
L 2 (s 3) = min{ } = min{7+11, 9+12} = 18, u (2) = 5;
L 2 (s 4) = min{ } = min{2+16, 3+12, 6+10} = 15, u (2) = 6;
Полученные три пары чисел записываются в третью строку Табл.6.4.1.
Начальное состояние s 1 определено однозначно, поэтому в последней строке таблицы заполняется единственная клетка, куда носятся значения 3 и 24 поскольку:
L 1 (s 1) = min{ 
} = min{5+22, 6+18, 11+15} = 24, u (1) = 3.
Теперь можно окончательно определить последовательность оптимального многошагового управления. На первом шаге u (1) = 3, т.е. из узла 1 переходим в узел 3, на втором шаге u (2) = 5, т.е. переходим в узел 5, далее после управления u (3) = 11 - в узел 11 и, наконец, в узел 12. Окончательно получаем, что кратчайший путь по сети, изображенной на Рис. 6.4.1, проходит по последовательности состояний s 1 →s 2 →s 5 →s 11 →s 12 , а его протяженность составляет 24 условных единиц.
Поиск кратчайшего пути можно также осуществлять из начала сети, реализуя при этом алгоритм прямой прогонки, который выполняет в сущности те же операции сложения и сравнения, но в несколько иной последовательности.
В алгоритмах прямой и обратной прогонки, хотя и отличных по существу, предусматривается одно сложение и одно сравнение на каждую дугу. Следовательно, оба алгоритма обладают одинаковым быстродействием. Тем не менее, существует важное различие. В алгоритме прямой прогонки рассматриваются дуги, исходящие из тех узлов, кратчайшие пути l i до которых уже известны.
В алгоритме обратной прогонки рассматриваются дуги, входящие в те узлы, кратчайшие пути l j до которых ещё неизвестны. В силу последнего обстоятельства предпочтение чаще отдаётся алгоритму прямой прогонки. Этот алгоритм можно применять при любой структуре множества кратчайших путей.
Решение простой задачи о кратчайшем пути иллюстрирует ряд следующих характерных особенностей, которые присущи значительно более сложным многошаговым процессам принятия решений:
1. Исходная задача погружается во множество оптимизационных задач; при этом для каждого узла решается своя задача.
2. Множество решений оптимизационных задач описывается функциональным уравнением, представляющим собой систему уравнений, которые связывают несколько оптимизационных задач. В такой системе каждое уравнение соответствует одному узлу и содержит обычно операторы типа min, mах или minimax справа от знака равенства, а переменные типа g i , и g j - по обе стороны от него.
3. Решение множества оптимизационных задач можно найти с помощью алгоритма обратной прогонки, который равнозначен упорядоченной процедуре решения последовательности функциональных уравнений.
Динамическое программирование хорошо подходит для решения проблем, связанных с моделированием сетевых систем, не обладающих специальной структурой. Так, алгоритмы прямой и обратной прогонки пригодны для проведения вычислений в ациклических сетях. Алгоритм обратной прогонки можно обобщить и использовать для решения задач, в которых есть элемент случайности. Для алгоритма прямой прогонки это нельзя сделать.
Понятие «состояние» играет центральную роль в динамическом программировании, при этом под состояниями понимается следующее. Переход осуществляется из состояния в состояние, заключающее в себе всю предысторию процесса, т. е. состояние описано с той степенью подробности, которая позволяет провести вычисление (оценку) текущих альтернативных решении.
Для сетевой модели состояниями являются узлы, а дуги, выходящие из некоторого узла, отображают различные решения, которые можно принимать в данном узле (состоянии). При таком толковании можно говорить, что переход происходит из состояния в состояние, а состояния представляют собой точки, в которых принимаются решения. Приведенное утверждение означает, что дуги, выходящие из узла, не имеют никакого отношения к тому, каким путём был достигнут тот или иной узел, т. е. не зависят от входящих дуг.
Элементы состояния часто называют переменными состояния. В моделях динамического программирования состояния иногда группируются в стадии, и переход осуществляется от одной стадии к другой. Например, в задаче о кратчайшем пути имеются состояния, но нет стадий, так как нельзя сгруппировать состояния в множества таким образом, чтобы происходил переход от одного множества к другому.
Погружение во множество оптимизационных задач равносильно введению понятия пространство состояний, которое представляет собой множество состояний. В функциональном уравнении оптимальный отклик рассматривается как функция стартового состояния, а принцип оптимальности устанавливает взаимосвязь между оптимальными откликами для различных стартовых состояний.
Множество S возможных (или наблюдаемых) состояний называется пространством состояний, а элемент s из S определяет конкретное состояние. С каждым состоянием s связано множество D (s ) . Элемент d из множества D (s ) называется решением. Правило, согласно которому определяется допустимое решение для каждого состояния, называется стратегией d.
Фактически стратегия d ставит в соответствие каждому состоянию s некоторый элемент d(s ) из множества D (s ). Набор всех таких d образует пространство стратегий D. Последнее означает, что выбор решения в некотором состоянии не ограничивает выбор во всех других состояниях. По существу, D представляет собой декартово произведение множеств D (s ) по s .
Одна из идей динамического программирования состоит в том, каждой стратегии d должна соответствовать так называемая функция прибыли V d (s ), которую можно получить, исходя из состояния s и используя стратегию d. Понятие функции прибыли (или дохода) обобщает понятие вклада L t в общее значение критерия оптимальности L, рассматриваемое при решении задачи о кратчайшем пути.
Выражение «используя стратегию d» означает, что в состоянии s выбирается решение d(s ); затем предполагается, что процесс перешел в состояние s " , т. е. реализуется состояние s ", в котором выбирается решение d(s "), и т. д. Функция прибыли имеет довольно сложную структуру, поскольку она зависит от последовательности состояний и решений, от вознаграждений, которые связаны с этими состояниями и решениями, а также от способа агрегирования вознаграждений.
Состояние представляет собой описание предыстории процесса со степенью подробности, позволяющей провести оценку текущих альтернативных решений. Основным свойством состояний является то, что состояние является краткой записью предыстории процесса, причем степень детализации позволяет определить локальную функцию дохода.Иными словами, локальная функция дохода может зависеть лишь от s , d и v.
В следующей главе будут более подробно рассмотрены цепи Маркова, имеющие большое значение для моделирования временной эволюции производственных и технических систем. Существуют также Марковские модели принятия решений, в которых состояние s
определяется некоторой парой чисел (n,i
) , решением является зависящая от них функция k
, а локальная функция дохода определяется выражением типа h
[(n
, I
) , k, v
] = R k i
(n
) + å j P k ij
(n
)v
(n+
1,j
) (n
Марковские модели принятия решений обобщаются в разных направлениях, в частности, на случай Марковских задач о восстановлении . Наиболее полезное обобщение получается, когда рассматриваются неравные или переменные времена переходов. В простых моделях предполагается, что переход из состояния в состояние и наблюдение состояния осуществляются мгновенно, а отрезок времени между переходами из состояния в состояние может иметь переменную или случайную длину.
Всякий раз, когда наблюдается некоторое состояние, выбирается решение, которое уже нельзя изменять до тех пор, пока процесс не перейдет в новое состояние, где выбирается новое решение, и т. д. Данная модель представляет собой комбинацию теории цепей Маркова и теории восстановления; обычно ее называют Марковской задачей о восстановлении.
Контрольные вопросы к главе 6.
1. Из каких компонентов состоит ориентированная сеть?
1. Как строится матрица пропускных способностей сети?
1. Как образуется матрица потока в сети?
1. Для чего вычитаются матрицы пропускных способностей и потоков?
1. Что такое и для чего служит сетевой график?
1. Как определяются времена раннего начала и раннего окончания работ?
1. Что представляет собой общий резерв времени для некоторого события на сетевом графике?
1. Как определяется критический путь?
1. Что называется вектором состояния некоторой системы?
1. Что представляет собой траектория системы в пространстве состояний?
1. В чем заключается задача оптимального управления?
1. Как формулируется критерий оптимальности?
1. Что представляет собой динамическое программирование?
1. Сформулируйте принцип оптимальности Беллмана.
1. В чем сущность алгоритмов прямой и обратной прогонки при поиске кратчайшего пути?
Варианты заданий к главе 6.
Для сетей в каждом из вариантов:
1) Найти максимальный поток из источника (1) в конечный узел сети – сток, полагая, что одно из чисел в скобках у каждой дуги (i, j) определяет пропускную способность дуги;
1) Полагая, что дуги (1)®(2), (1)®(3) и т. д. определяют некоторые работы, минимальная и максимальная продолжительность которых заданы числами, указанными при соответствующих дугах, найти критический путь от начального события (1) до конечного;
1) Произвести поиск кратчайшего пути от начального узла до конечного узла сети. Считать расстояния между узлами i, j заданными одним из чисел в скобках.
X
4
Динамическое программирование (иначе «динамическое планирование») есть особый метод оптимизации решений, специально приспособленный к так называемым «многошаговым» (или «многоэтапным») операциям.
Представим себе некоторую операцию О, распадающуюся на ряд последовательных «шагов» или «этапов», - например, деятельность отрасли промышленности в течение ряда хозяйственных лет; или же преодоление группой самолетов нескольких полос противовоздушной обороны; или последовательность тестов, применяемых при контроле аппаратуры. Некоторые операции (подобно вышеприведенным) расчленяются на шаги естественно; в некоторых членение приходится вводить искусственно - скажем, процесс наведения ракеты на цель можно условно разбить на этапы, каждый из которых занимает какое-то время
Итак, рассмотрим операцию О, состоящую из шагов (этапов). Пусть эффективность операции характеризуется каким-то показателем W, который мы для краткости будем в этой главе называть «выигрышем». Предположим, что выигрыш W за всю операцию складывается из выигрышей на отдельных шагах:
где - выигрыш на i-м шаге.
Если W обладает таким свойством, то его называют аддитивным критерием .
Операция О, о которой идет речь, представляет собой управляемый процесс, т. е. мы можем выбирать какие-то параметры, влияющие на его ход и исход, причем на каждом шаге выбирается какое-то решение, от которого зависит выигрыш на данном шаге и выигрыш за операцию в целом. Будем называть это решение «шаговым управлением». Совокупность всех шаговых управлений представляет собой управление операцией в целом. Обозначим его буквой , а шаговые управления - буквами :
Следует иметь в виду, что в общем случае - не числа, а, может быть, векторы, функции и т. д.
Требуется найти такое управление при котором выигрыш W обращается в максимум:
То управление при котором этот максимум достигается, будем называть оптимальным управлением. Оно состоит из совокупности оптимальных шаговых управлений:
Тот максимальный выигрыш, который достигается при этом управлении, мы будем обозначать :
Формула (12.5) читается так: величина W есть максимум из всех при разных управлениях (максимум берется по всем управлениям возможным в данных условиях). Иногда это последнее оговаривается в формуле и пишут:
Рассмотрим несколько примеров многошаговых операций и для каждого из них поясним, что понимается под «управлением» и каков «выигрыш» (показатель эффективности)
1. Планируется деятельность группы промышленных предприятий на период хозяйственных лет (-летку). В начале периода на развитие группы выделены какие-то средства которые должны быть как-то распределены между предприятиями. В процессе работы предприятия вложенные в него средства частично расходуются (амортизируются), а частично сохраняются и снова могут быть перераспределены. Каждое предприятие за год приносит доход, зависящий от того, сколько средств в него вложено. В начале каждого хозяйственного года имеющиеся в наличии средства перераспределяются между предприятиями. Ставится вопрос: какое количество средств в начале каждого года нужно выделять каждому предприятию, чтобы суммарный доход за лет был максимальным?
Выигрыш W (суммарный доход) представляет собой сумму доходов на отдельных шагах (годах):
значит, обладает свойством аддитивности.
Управление на шаге состоит в том, что в начале года предприятиям выделяются какие-то средства (первый индекс - номер шага, второй - номер предприятия). Таким образом, шаговое управление есть вектор с к составляющими:
Разумеется, величины в формуле (12.6) зависят от количества вложенных в предприятия средств.
Управление всей операцией состоит из совокупности всех шаговых управлений:
Требуется найти такое распределение средств по предприятиям и по годам (оптимальное управление при котором величина W обращается в максимум.
В этом примере шаговые управления были векторами; в последующих примерах они будут проще и выражаться просто числами.
2. Космическая ракета состоит из ступеней, а процесс ее вывода на орбиту - из этапов, в конце каждого из которых очередная ступень сбрасывается. На все ступени (без учета «полезного» веса кабины) выделен какой-то общий вес:
где - вес ступени.
В результате этапа (сгорания и сбрасывания ступени) ракета получает приращение скорости А, зависящее от веса данной ступени и суммарного веса всех оставшихся плюс вес кабины. Спрашивается, как нужно распределить вес G между ступенями, чтобы, скорость ракеты V при ее выводе на орбиту была максимальна?
В данном случае показатель эффективности (выигрыш) будет
где А - выигрыш (приращение скорости) на шаге.
Управление представляет собой совокупность весов всех ступеней
Оптимальным управлением будет то распределение весов по ступеням, при котором скорость V максимальна. В этом примере шаговое управление - одно число, а именно, вес данной ступени.
3. Владелец автомашины эксплуатирует ее в течение лет. В начале каждого года он может принять одно из трех решений:
1) продать машину и заменить ее новой;
2) ремонтировать ее и продолжать эксплуатацию;
3). продолжать эксплуатацию без ремонта.
Шаговое управление - выбор одного из этих трех решений. Непосредственно числами они не выражаются, но можно приписать первому численное значение 1, второму 2, третьему 3. Какие нужно принять решения по годам (т. е. как чередовать управления 1, 2,3), чтобы суммарные расходы на эксплуатацию, ремонт и приобретение новых машин были минимальны?
Показатель эффективности (в данном случае это не «выигрыш», а «проигрыш», но это неважно) равен
(12.10)
где - расходы в i-м году. Величину W требуется обратить в минимум.
что означает: первые два года эксплуатировать машину без ремонта, последующие три года ее ремонтировать, в начале шестого года продать, купить новую, затем снова эксплуатировать без ремонта и т. д. Любое управление представляет собой вектор (совокупность чисел):
где каждое из чисел имеет одно из трех значений: 1, 2 или 3. Нужно выбрать совокупность чисел (12.11), при которой величина (12.10) минимальна.
4. Прокладывается участок железнодорожного пути между пунктами А и В (рис. 12.1).
Местность пересеченная, включает лесистые зоны, холмы, болота, реку, через которую надо строить мост. Требуется так провести дорогу из в В, чтобы суммарные затраты на сооружение участка были минимальны.
В этой задаче, в отличие от трех предыдущих, нет естественного членения на шаги: его приходится вводить искусственно, для чего, например, можно отрезок АВ разделить на частей, провести через точки деления прямые, перпендикулярные АВ, и считать за «шаг» переход с одной такой прямой на другую. Если провести их достаточно близко друг от друга, то можно считать на каждом шаге участок пути прямолинейным. Шаговое управление на i-м шаге представляет собой угол , который составляет участок пути с прямой АВ. Управление всей операцией состоит из совокупности шаговых управлений:
Требуется выбрать такое (оптимальное) управление при котором суммарные затраты на сооружение всех участков минимальны:
(12.12)
Итак, мы рассмотрели несколько примеров многошаговых задач исследования операций. А теперь поговорим о том, как можно решать подобного рода задачи?
Любую многошаговую задачу можно решать по-разному: либо искать сразу все элементы решения на всех шагах, либо же строить оптимальное управление шаг за шагом, на каждом этапе расчета оптимизируя только один шаг. Обычно второй способ оптимизации оказывается проще, чем первый, особенно при большом числе шагов.
Такая идея постепенной, пошаговой оптимизации и лежит в основе метода динамического программирования. Оптимизация одного шага, как правило, проще оптимизации всего процесса: лучше, оказывается, много раз решить сравнительно простую задачу, чем один раз - сложную.
С первого взгляда идея может показаться довольно тривиальной.
В самом деле, чего казалось бы, проще: если трудно оптимизировать операцию в целом, разбить ее на ряд шагов. Каждый такой шаг будет отдельной, маленькой операцией, оптимизировать которую уже нетрудно. Надо выбрать на этом шаге такое управление, чтобы эффективность этого шага была максимальна. Не так ли?
Нет, вовсе не так! Принцип динамического программирования отнюдь не предполагает, что каждый шаг оптимизируется отдельно, независимо от других. Напротив, шаговое управление должно выбираться дальновидно, с учетом всех его последствий в будущем. Что толку, если мы выберем на данном шаге управление, при котором эффективность этого шага максимальна, если этот шаг лишит нас возможности хорошо выиграть на последующих шагах?
Пусть, например, планируется работа группы промышленных предприятий, из которых часть занята выпуском предметов потребления, а остальные производят для них машины. Задача операции - получить за лет максимальный объем выпуска предметов потребления. Допустим, планируются капиталовложения на первый год. Исходя из узких интересов этого шага (года), мы должны были бы все наличные средства вложить в производство предметов потребления. Но правильно ли будет такое решение с точки зрения эффективности операции в целом? Очевидно, нет. Это решение - расточительное, недальновидное. Имея в виду будущее, надо выделить какую-то долю средств и на производство машин. От этого объем продукции за первый год, конечно, снизится, зато будут созданы условия для его увеличения в последующие годы.
Еще пример. Допустим, что в задаче 4 (прокладка железнодорожного пути из А в В) мы прельстимся идеей сразу же устремиться по самому легкому (дешевому) направлению. Что толку от экономии на первом шаге, если в дальнейшем он заведет нас (буквально или фигурально) в «болото»?
Значит, планируя многошаговую операцию, надо выбирать управление на каждом шаге с учетом всех его будущих последствий на еще предстоящих шагах. Управление на шаге выбирается не так, чтобы выигрыш именно на данном шаге был максимален, а так, чтобы была максимальна сумма выигрышей на всех оставшихся до конца шагах плюс данный.
Однако из этого правила есть исключение. Среди всех шагов есть один, который может планироваться попросту, без оглядки на будущее. Какой это шаг? Очевидно, последний! Этот шаг, единственный из всех, можно планировать так, чтобы он сам, как таковой принес наибольшую выгоду.
Поэтому процесс динамического программирования обычно разворачивается от конца к началу: прежде всего планируется последний, шаг. А как его спланировать, если мы не знаем, чем кончился предпоследний? Т. е. не знаем условий, в которых мы приступаем к последнему шагу?
Вот тут-то и начинается самое главное. Планируя последний шаг, нужно сделать разные предположения о том, чем кончился предпоследний, шаг, и для каждого из этих предположений найти условное оптимальное управление на шаге («условное» потому, что оно выбирается исходя из условия, что предпоследний шаг кончился так-то, и так-то).
Предположим, что мы это сделали, и для каждого из возможных исходов предпоследнего шага знаем, условное оптимальное управление и соответствующий ему условный оптимальный выигрыш на шаге. Отлично! Теперь мы можем оптимизировать управление на предпоследнем, шаге. Снова сделаем все возможные предположения о том, чем кончился предыдущий, и найти не условно оптимальный, а просто оптимальный выигрыш .
В самом деле, пусть мы знаем, в каком состоянии была управляемая система (объект управления S) в начале первого шага. Тогда мы можем выбрать оптимальное управление на первом шаге. Применив его, мы изменим состояние системы на некоторое новое S и в этом состоянии мы подошли ко второму шагу. Тогда нам тоже известно условное оптимальное управление которое к концу второго шага переводит систему в состояние и т. д. Что касается оптимального выигрыша W за всю операцию, то он нам уже известен: ведь именно на основе его максимальности мы выбирали управление на первом шаге.
Таким образом, в процессе оптимизации управления методом динамического программирования многошаговый процесс «проходится» дважды: первый раз - от конца к началу, в результате чего находятся условные оптимальные управления и условные оптимальные выигрыши за оставшийся «хвост» процесса; второй раз - от начала к концу, когда нам остается только «прочитать» уже готовые рекомендации и найти безусловное оптимальное управление состоящее из оптимальных шаговых управлений
Первый этап - условной оптимизации - несравненно сложнее и длительнее второго. Второй этап почти не требует дополнительных вычислений.
Автор не льстит себя надеждой, что из такого описания метода динамического программирования читатель, не встречавшийся с ним до сих пор, поймет по-настоящему его идею. Истинное понимание возникает при рассмотрении конкретных примеров, к которым мы и перейдем.
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), возмущаемой «белым шумом» при полном и точном измерении ее состояния, решение которой было дано в предыдущем разделе. Теорема доказана. Можно показать, что теорема разделения справедлива и при синтезе оптимального управления по квадратичному решению.
В рассмотренных выше моделях управленческих задач не учитывался время. Это так называемые одноэтапные модели, которые позволяют анализировать статические, не зависящие от времени процессы, допустим, когда изменениями исследуемого процесса во времени можно пренебречь. Управленческое решение по такого моделирования имеет смысл или в условиях стабильности системы, или на короткий промежуток в будущем.
В реальности все экономические процессы и явления функционируют и развиваются во времени, то есть по своей природе динамичны. Это требует от менеджеров решения практических задач, в которых необходимо учитывать возможные изменения экономических процессов во времени при условии, что процессом можно управлять, то есть влиять на ход его развития.
Динамическое программирование - это математический аппарат, с помощью которого решаются многошаговые задачи оптимального управления. В таком программировании для управления процессом среди множества всех допустимых решений ищут оптимальное в смысле определенного критерия, то есть такое решение, которое дает экстремальное (больше или меньше) значения целевой функции - некоторой числовой характеристики процесса. Во многостепенность понимают или многоступенчатую структуру процесса, или распределение управления на ряд последовательных этапов, соответствующих, как правило, различным моментам времени. Таким образом, слово "программирование" означает принятие управленческих решений, а слово "динамическое" указывает на существенное значение времени и порядка выполнения операций в процессах и методах, которые рассматриваются.
В задачи динамического программирования относятся задачи календарного планирования, распределения инвестиций, управление запасами, текущего и капитального ремонта, выбора методов проведения рекламы и тому подобное.
В одних задачах динамического программирования управленческий процесс распадается на этапы естественным путем, например месяц, квартал, год. В других ситуациях разделение на этапы может иметь условный характер. Особенность всех задач динамического программирования заключается в том, что на каждом этапе можно учитывать предыдущие изменения, управлять ходом событий, оценивая при этом качество такого управления. Итак, динамическое программирование позволяет принять ряд управленческих решений, обеспечивает оптимальность развития системы в целом.
Рассмотрим общую постановку задачи этого программирования. Пусть исследуется некоторый экономический процесс, имеющий п последовательных этапов. На каждом 7-м этапе процесс может быть в разных состояниях бы, каждый из которых характеризуется конечным множеством параметров. С каждым этапом задачи связано принятие определенного управленческого решения хи, которое переводит систему из одного состояния в другое. Предполагается, что состояние si системы в конце 7-го этапа определяется только предыдущим состоянием si_1 и управлением хи на 7-м этапе и не зависит от предыдущих состояний и управлений. Тогда состояние si системы записывается в виде зависимости
Si = ф (в, _!, Хи), i = 1, П.
Эффективность всего процесса управления может быть представлена как сумма эффективностей управленческих решений отдельных этапов, то есть
При названных условиях задача динамического программирования формулируется так: определить такую допустимую последовательность управленческих решений X = {x1, x2, хп}, которая переводит систему из начального состояния 50 в завершающий состояние sn и при которой достигается максимальная эффективность управления.
Планируя многоэтапный процесс управления, в задачах динамического программирования необходимо на каждом этапе выбирать управленческое решение с учетом его последствий на тех этапах, которые еще впереди. Только на последнем этапе можно принять управленческое решение, которое даст максимальный эффект, поскольку следующий шаг для него не существует. Поэтому задачи динамического программирования решаются с конца.
Максимум целевой функции на заключительном п-м этапе равна
^ п-О = шах / п ^ п-и хп).
Соответственно, на (п - 1) -етапи имеем
г * п-1 (5п-2) = ШaХ ((fn-1 (sn-2, хп-1) + г * п ^ п-1)).
Учитывая эту закономерность, для произвольного k-этапа можем записать рекуррентную зависимость
г * (пятый-1) = Шахи (Л (ик-1, хк) + г * + 1)).
Такая рекуррентная зависимость представляет собой математическую запись принципа оптимальности Беллмана.
Определив по рекуррентными зависимостями условно-оптимальный эффект на начальном этапе, проводят безусловную оптимизацию управления в "обратном" направлении, в результате чего находят последовательность управленческих решений, обеспечивает максимальную эффективность системы в целом.
Основные особенности метода динамического программирования
1. Идея и метод динамического программирования больше приспособлены к дискретных задач, которыми в большинстве являются задачи управления.
2. Метод динамического программирования можно применять при любом способа задания целевой функции и с любой допустимой множеством состояний и управлений. Этого преимущества лишены классические методы оптимизации и другие вычислительные методы математического программирования.
3. Вычислительные схемы метода динамического программирования в дискретном случае связанные с переборкой оптимальных значений показателя эффективности и управления на к-м шаге для всех возможных значений переменной состояния, но объем расчетов при этом значительно меньше, чем при прямом переборки вариантов. Это связано с тем, что на этапе условной оптимизации неудачные варианты сразу отбрасываются, а сохраняются лишь условно оптимальные на данном этапе.
4. Метод динамического программирования дает возможность анализа чувствительности к изменению исходных данных состояний sk и их количества п. Фактически здесь на каждом шагу решается не одна задача, а множество однотипных задач для различных состояний sk и различных к (1 <к <п) . Поэтому с изменением исходных данных нельзя не решать задачу заново, а сделать только несложные добавление к уже выполненных расчетов, то есть продолжить уже решенную задачу за счет увеличения количества шагов п или количества значений sk.
1. Появление нелинейных моделей связана с необходимостью учитывать и проявлять нелинейные закономерности, которые влияют на принятие оптимального решения. Такие закономерности включаются в ограничения задачи и целевую функцию.
2. По характеру функций и ограничений, которыми описываются задачи нелинейного программирования, их можно классифицировать следующим образом: классические задачи оптимизации; задачи с нелинейной целевой функцией и линейными ограничениями; задачи выпуклого, квадратичного, сепарабельного программирования.
3. В отличие от задач линейного программирования, для решения нелинейных задач не существует универсального метода. В каждом конкретном случае необходимо выбирать лучший метод.
4. Динамическое программирование - это математический аппарат, с помощью которого решаются многошаговые задачи оптимального управления. Во многостепенность понимают или многоступенчатую структуру процесса, или распределения управления на ряд последовательных этапов, соответствующих, как правило, различным моментам времени.
5. В задачи динамического программирования относятся задачи календарного планирования, распределения инвестиций, управление запасами, текущего и капитального ремонта, выбора методов проведения рекламы и тому подобное. Особенность всех задач динамического программирования заключается в том, что на каждом этапе можно учитывать предыдущие изменения и управлять ходом событий, оценивая при этом качество такого управления.
6. Решение задач динамического программирования базируется на принципе оптимальности Беллмана. В процессе оптимизации управления методом динамического программирования многошаговый процесс выполняется дважды. Первый раз - от конца к началу, в результате чего находят условно оптимальные управления. Второй - от начала до конца, в результате чего находят оптимальное управление процессом в целом.
ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ, раздел оптимального управления, посвящённый теории и методам решения многошаговых задач. В задачах оптимального управления среди возможных управлений ищется то, при котором достигается экстремальное (наименьшее или наибольшее) значение так называемой целевой функции - некоторой числовой характеристики процесса. В динамическом программировании под многошаговостью понимают либо многоступенчатую структуру процесса, либо то, что управление разбивается на ряд последовательных этапов (шагов), соответствующих, как правило, различным моментам времени. Иногда многошаговость проистекает из существа процесса, но она может вводиться и искусственно для того, чтобы обеспечить возможность применения методов динамического программирования. Под программированием в динамическом программировании понимают принятие решений (планирование), а слово «динамическое» указывает на существенную роль времени и порядка выполнения операций. Методы динамического программирования являются составной частью методов, используемых в исследовании операций, и применяются в задачах оптимального планирования (например, в задачах об оптимальном распределении ресурсов, в теории управления запасами, в задачах замены оборудования) и при решении многих технических проблем (например, в задачах управления последовательными химическими процессами, в задачах оптимальной прокладки дорог).
Пусть процесс управления некоторой системой Х состоит из m шагов (этапов); на i-м шаге управление y i переводит систему из состояния x i-1 , в котором она находилась после (i - 1)-го шага, в новое состояние x i . При этом задана функция f i (х, у), и новое состояние определяется по этой функции значениями x i-1 , y i так, что x i = f i (x i-1 , y i), i = 1, 2,..., m. Таким образом, управления у 1 , у 2 , ..., у m переводят систему из начального состояния х 0 ∈ Х 0 в конечное состояние х m ∈ Х m , где Х 0 и Х m - совокупности допустимых начальных и конечных состояний системы Х.
Одна из возможных постановок задач динамического программирования состоит в следующем. При заданном начальном состоянии х 0 требуется выбрать управления у 1 , у 2 , ..., у m таким образом, чтобы система Х перешла в допустимое конечное состояние и при этом заданная целевая функция F(х 0 , у 1 , х 1 ,..., у m , х m) достигла максимального значения F*, т. е.
где максимум берётся по всем управлениям у 1 , ..., у m , для которых х m ∈ Х m .
В динамическом программировании обычно предполагается, что целевая функция является аддитивной. В рассмотренном примере это означает, что
Кроме того, в динамическом программировании предполагается, что в задаче отсутствует последействие: решения (управления), принимаемые на шаге i, оказывают влияние только на состояние x i системы в момент i. Оба упомянутых ограничительных условия можно ослабить, но только за счёт существенного усложнения метода.
В основе динамического программирования лежит принцип оптимальности, сформулированный Р. Беллманом. Пусть выбраны некоторые управления у 1 , у 2 , ..., y k и тем самым траектория х 0 , х 1 , ...,x k состояний и требуется завершить процесс, т. е. выбрать у k+1 , ..., у m (а значит, и x k+1 , ..., х m).
Если завершающая часть процесса не будет оптимальной в смысле достижения максимума функции
то и весь процесс не будет оптимальным. Пользуясь принципом оптимальности Беллмана, можно получить основное функциональное соотношение динамического программирования, которое состоит в следующем. Пусть ω m (х) = 0,
k = 1, 2, ..., m, где максимум берётся по всем управлениям у, допустимым на шаге k. Соотношение, определяющее зависимость ω k-1 от ω k , называется уравнением Беллмана. Смысл этих функций достаточно ясен: если система на шаге k-1 оказалась в состоянии х, то ω k-1 (х) есть максимально возможное значение функции F k . Одновременно с построением функций ω k-1 (х) находятся условные оптимальные управления y k (х) на каждом шаге, т. е. значения оптимального управления при всевозможных предположениях о состоянии х системы на шаге k-1. Окончательно оптимальные управления находятся последовательным вычислением величин ω 0 (х 0) = F*, у 1 , х 1 , у 2 , ..., у m , x m .
С помощью динамического программирования решается не одна конкретная задача при определённом х 0 , а сразу все подобные однотипные задачи при любом начальном состоянии. Численная реализация динамического программирования довольно сложна, так как требует запоминания большого количества информации, поэтому динамическое программирование целесообразно применять в тех случаях, когда необходимо многократно решать типовые задачи (например, определение оптимального режима полёта самолёта при меняющихся погодных условиях). Обычно задача динамического программирования формулируется для дискретных процессов, но в ряде случаев динамическое программирование применяется и для решения динамических задач с непрерывными параметрами.
Динамическое программирование дало новый подход ко многим задачам вариационного исчисления. Важный раздел динамического программирования составляют стохастические задачи динамического программирования, т. е. задачи, в которых на состояние системы и на целевую функцию влияют случайные факторы.
Строгое обоснование динамического программирования следует из результатов Л. С. Понтрягина и его учеников по математической теории управляемых процессов.
Лит.: Беллман Р. Динамическое программирование. М., 1960; Математическая теория оптимальных процессов. М., 1961; Ховард Р. А. Динамическое программирование и марковские процессы. М., 1964; Хедли Дж. Нелинейное и динамическое программирование. М., 1967; Хедли Дж., Уайтин Т. Анализ систем управления запасами. М., 1969.
