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

18.05.2019

Допустим, есть задача, которую мы уже решили динамическим программированием, например, извечные числа Фибоначчи.
Давайте немного переформулируем её. Пусть у нас есть вектор , из которого мы хотим получить вектор . Чуть-чуть раскроем формулы: . Можно заметить, что из вектора можно получить вектор путем умножения на какую-то матрицу, ведь в итоговом векторе фигурируют только сложенные переменные из первого вектора. Эту матрицу легко вывести, вот она: . Назовём её матрицей перехода.

Это значит, что если взять вектор и умножить его на матрицу перехода n - 1 раз, то получим вектор , в котором лежит fib[n] - ответ на задачу.

А теперь, зачем всё это надо. Умножение матриц обладает свойством ассоциативности, то есть (но при этом не обладает коммутативностью, что по-моему удивительно). Это свойство даёт нам право сделать так: .

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

А теперь пример посерьёзнее:

Пример №3: Пилообразная последовательность

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

Решение

Для начала решение без матрицы перехода:

1) Состояние динамики: dp[n] - количество пилообразных последовательностей длины n , заканчивающихся на цифру last . Причём если less == 0 , то последняя цифра меньше предпоследней, а если less == 1 , значит больше.
2) Начальные значения:
for last in range(10): dp = 9 - last dp = last 3) Пересчёт динамики:
for prev in range(10): if prev > last: dp[n] += dp if prev < last: dp[n] += dp 4) Порядок пересчёта: мы всегда обращаемся к предыдущей длине, так что просто пара вложенных for "ов.
5) Ответ - это сумма dp[N] .

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

Вектор и матрица перехода

Динамика по подотрезкам

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

Пример №4: Запаковка строки

Вот Развернутое условие . Я вкратце его перескажу:

Определим сжатую строку:
1) Строка состоящая только из букв - это сжатая строка. Разжимается она в саму себя.
2) Строка, являющаяся конкатенацией двух сжатых строк A и B . Разжимается она в конкатенацию разжатых строк A и B .
3) Строка D(X) , где D - целое число, большее 1 , а X - сжатая строка. Разжимается она в конкатенацию D строк, разжатых из X .
Пример: “3(2(A)2(B))C” разжимается в “AABBAABBAABBC” .

Необходимо по строке s узнать длину самой короткой сжатой строки, разжимающийся в неё.

Решение

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

1) Состояние динамики: d[l][r] - сжатая строка минимальной длины, разжимающаяся в строку s
2) Начальные состояния: все подстроки длины один можно сжать только в них самих.
3) Пересчёт динамики:
У лучшего ответа есть какая-то последняя операция сжатия: либо это просто строка из заглавных букв, или это конкатенация двух строк, или само сжатие. Так давайте переберём все варианты и выберем лучший.

Dp_len = r - l dp[l][r] = dp_len # Первый вариант сжатия - просто строка. for i in range(l + 1, r): dp[l][r] = min(dp[l][r], dp[l][i] + dp[i][r]) # Попробовать разделить на две сжатые подстроки for cnt in range(2, dp_len): if (dp_len % cnt == 0): # Если не делится, то нет смысла пытаться разделить good = True for j in range(1, (dp_len / cnt) + 1): # Проверка на то, что все cnt подстрок одинаковы good &= s == s if good: # Попробовать разделить на cnt одинаковых подстрок и сжать dp[l][r] = min(dp[l][r], len(str(cnt)) + 1 + dp[l] + 1) 4) Порядок пересчёта: прямой по возрастанию длины подстроки или ленивая динамика.
5) Ответ лежит в d .

Пример №5:

Динамика по поддеревьям

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

Пример №6: Логическое дерево

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

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

Решение

1) Состояние динамики: d[v][x] - количество операций, требуемых для получения значения x в вершине v . Если это невозможно, то значение состояния - +inf .
2) Начальные значения: для листьев, очевидно, что своё значение можно получить за ноль изменений, изменить же значение невозможно, то есть возможно, но только за +inf операций.
3) Формула пересчёта:
Если в этой вершине уже значение x , то ноль. Если нет, то есть два варианта: изменить в текущей вершине операцию или нет. Для обоих нужно найти оптимальный вариант и выбрать наилучший.

Если операция «И» и нужно получить «0», то ответ это минимум из значений d[i] , где i - сын v .
Если операция «И» и нужно получить «1», то ответ это сумма всех значений d[i] , где i - сын v .
Если операция «ИЛИ» и нужно получить «0», то ответ это сумма всех значений d[i] , где i - сын v .
Если операция «ИЛИ» и нужно получить «1», то ответ это минимум из значений d[i] , где i - сын v .

4) Порядок пересчёта: легче всего реализуется лениво - в виде поиска в глубину из корня.
5) Ответ - d xor 1] .

Динамика по подмножествам

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

Пример №7: Гамильтонов цикл минимального веса, или задача коммивояжера

Задан взвешенный (веса рёбер неотрицательны) граф G размера N . Найти гамильтонов цикл (цикл, проходящий по всем вершинам без самопересечений) минимального веса.

Решение

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

1) Состояние динамики: dp[v] - путь минимального веса из вершины 0 в вершину v , проходящий по всем вершинам, лежащим в mask и только по ним.
2) Начальные значения: dp = 0 , все остальные состояния изначально - +inf .
3) Формула пересчёта: Если i -й бит в mask равен 1 и есть ребро из i в v , то:
dp[v] = min(dp[v], dp[i] + w[i][v]) Где w[i][v] - вес ребра из i в v .
4) Порядок пересчёта: самый простой и удобный способ - это написать ленивую динамику, но можно поизвращаться и написать перебор масок в порядке увеличения количества единичных битов в ней.
5) Ответ лежит в d[(1 << N) - 1] .

Динамика по профилю

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

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

Профиль - это k (зачастую один) столбцов, являющиеся границей между уже замощённой частью и ещё не замощённой. Эта граница заполнена только частично. Очень часто является частью состояния динамики.

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

Пример №8: Замощение доминошками

Найти количество способов замостить таблицу N x M с помощью доминошек размерами 1 x 2 и 2 x 1 .

Решение

Здесь профиль - это один столбец. Хранить его удобно в виде двоичной маски: 0 - не замощенная клетка столбца, 1 - замощенная. То есть всего профилей .

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

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

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

Примеры переходов (из верхнего профиля можно перейти в нижние и только в них):

После этого сохранить всё в массив can - 1 , если можно перейти, 0 - если нельзя.
1) Состояние динамики: dp - количество полных замощений первых pos - 1 столбцов с профилем mask .
2) Начальное состояние: dp = 1 - левая граница поля - прямая стенка.
3) Формула пересчёта:
dp += dp * can
4) Порядок обхода - в порядке увеличения pos .
5) Ответ лежит в dp.

Полученная асимптотика - .

Динамика по изломанному профилю

Это очень сильная оптимизация динамики по профилю. Здесь профиль - это не только маска, но ещё и место излома. Выглядит это так:

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

Переходы в динамике по изломанному профилю на примере задачи про замощение доминошками (пример №8):

Восстановление ответа

Иногда бывает, что просто знать какую-то характеристику лучшего ответа недостаточно. Например, в задаче «Запаковка строки» (пример №4) мы в итоге получаем только длину самой короткой сжатой строки, но, скорее всего, нам нужна не её длина, а сама строка. В таком случае надо восстановить ответ.

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

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

Небольшие оптимизации

Память

Зачастую в динамике можно встретить задачу, в которой состояние требует быть посчитанными не очень большое количество других состояний. Например, при подсчёте чисел Фибоначчи мы используем только два последних, а к предыдущим уже никогда не обратимся. Значит, можно про них забыть, то есть не хранить в памяти. Иногда это улучшает асимптотическую оценку по памяти. Этим приёмом можно воспользоваться в примерах №1, №2, №3 (в решении без матрицы перехода), №7 и №8. Правда, этим никак не получится воспользоваться, если порядок обхода - ленивая динамика.

Время

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

Замена состояния

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

Пример №9: Разложение числа

Требуется найти количество разложений числа N на различные слагаемые. Например, если N = 7 , то таких разложений 5:

3 + 4
2 + 5
1 + 7
1 + 2 + 4

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

1. Динамическое программирование. Основные понятия…………………2

2. Суть метода динамического программирования………………………..4

3. Пример решения задачи методом динамического программирования………………………………………………………...7

Список используемых источников……………………………………...11

1. Динамическое программирование. Основные понятия.

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

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

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

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

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

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

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

Для процессов с непрерывным временем динамическое программирование рассматривается как предельный вариант дискретной схемы решения. Получаемые при этом результаты практически совпадают с теми, которые получаются методами максимума Л. С. Понтрягина или Гамильтона-Якоби-Беллмана.

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

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

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

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

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

где w i - выигрыш на i -м шаге. Если W обладает таким свойством, то его называют аддитивным критерием .

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

Шаговые управления в общем случае не числа, а, как правило, векторы, функции и т.п.

В модели динамического программирования процесс на каждом шаге находится в одном из состояний s множества состояний S . Считается, что всякому состоянию сопоставлены некоторые шаговые управления. Эти управления таковы, что управление, выбранное в данном состоянии при любой предыстории процесса, определяет полностью следующее состояние процесса. Обычно выделены два особых состояния: s 0 - начальное и s w - конечное.

Итак, пусть каждому состоянию поставлено множество допустимых шаговых управлений , и каждому шаговому управлению , соответствует - состояние, в которое процесс попадает из s i в результате использования шагового управления u . Пусть процесс находится в начальном состоянии s 0 . Выбор переводит процесс в состояние s 1 = σ(s 0 ,u 1), выбор - в состояние s 2 = σ(s 1 ,u 2) и т.д. В результате получается траектория процесса, которая состоит из последовательности пар

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

конечны и U s для различных s не пересекаются.

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

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

Тот максимальный выигрыш, который достигается при этом управлении обозначим W max :

W max = max U {W (u )}. (2.5)

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

Загрузку рюкзака можно представить себе как процесс, состоящий из n шагов. На каждом шаге требуется ответить на вопрос: взять данный предмет в рюкзак, или нет? Таким образом, шаг процесса - присваивание переменной x i значения 1 или 0.

Теперь определим состояния. Очевидно, что текущее состояние процесса характеризует остаточная грузоподъёмность рюкзака - вес, который остался в нашем распоряжении до конца (до полной укладки рюкзака). Следовательно, под состоянием перед i -м шагом понимается величина

(2.6)

при этом s 0 является начальным состоянием, которому соответствует величина b - исходная грузоподъемность рюкзака.

Управление на i -м шаге означает присваивание двоичной переменной x i значения 0 или 1. Значит, на каждом шаге имеем всего два управления. Причем допустимость управления u i , устанавливающего x i = 1, определяется условием

(2.8)

Шаговый выигрыш можно определить как . Поэтому

(2.10)

Требуется найти оптимальное управление , при котором величина выигрыша (2.10) обращается в максимум.

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

Задание . Инвестор выделяет средства в размере 5 тыс. ден. ед., которые должны быть распределены между тремя предприятиями.

Требуется, используя принцип оптимальности Беллмана, построить план распределения инвестиций между предприятиями, обеспечивающий наибольшую общую прибыль, если каждое предприятие при инвестировании в него средств x тыс. ден. ед. приносит прибыль p;(x) тыс. ден. ед. (i=1, 2 и 3) по следующим данным:

Решение . Составим математическую модель задачи.

1.Число шагов равно 3.

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

3. Управление на i-ом шаге (i=1,2,3) выберем x i - количество средств, инвестируемых в i- ое предприятие.

4. Выигрыш p i (x i) на i-ом шаге - это прибыль, которую приносит i-ое предприятие при инвестировании в него средств xi. Если через выигрыш в целом обозначить общую прибыль W, то W=p 1 (x 1)+ p 2 (x 2)+ p 3 (x 3).

5. Если в наличии имеются средства в количестве s тыс. ден. ед. и в i-ое предприятие инвестируется x тыс. ден. ед, то для дальнейшего инвестирования остается (s-x) тыс. ден. ед. Таким образом, если на i-ом шаге система находилась в состоянии s и выбрано управление x, то на (i+1)-ом шаге система будет находится в состоянии (s-x), и, следовательно, функция перехода в новое состояние имеет вид: f i (s, x) = s-x.

6.На последнем (i=3) шаге оптимальное управление соответствует количеству средств, имеющихся в наличии, а выигрыш равен доходу, приносимым последним предприятием: x 3 (s)=s, W 3 (s)=p 3 (s).

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

W 2 (s) = max{p 2 (x) + W 3 (s - x)}

Проведем пошаговую оптимизацию, по результатам которой заполним таблицу.

s	i=3	i=2	i=1
	x 3 (s)	W 3 (s)	x 2 (s)	W 2 (s)	x i (s)	W i (s)
		4,27		4,27
		7,64		7,64
		10,25		10,97
		15,93		15,93
		16,12		19,26		19,26

В первой колонке таблицы записываются возможные состояния системы, в верхней строке - номера шагов с оптимальным управлением и выигрышем на каждом шаге, начиная с последнего. Так как для последнего шага i=3 функциональное уравнение имеет вид x 3 (s)=s, W3(s)=p3(s), то две колонки таблицы, соответствующие i=3, заполняются автоматически по таблице исходных данных.

На шаге i=2 основное функциональное уравнение имеет вид

W 2 (s) = max{p 2 (x) + W 3 (s - x)}

Поэтому для проведения оптимизации на этом шаге заполним таблицу для различных состояний s при шаге i=3.

s	x	s-x	p 2 (x)	W 3 (s-x)	p 2 (x)+W 3 (s-x)	W 2 (s)
				4,27	4,27	4,27
		3,33		3,33
				7,64	7,64	7,64
		3,33	4,27	7,6
		4,87		4,87
				10,25	10,25	10,97
		3,33	7,64	10,97
		4,87	4,27	9,14
		5,26		5,26
				15,93	15,93	15,93
		3,33	10,25	13,58
		4,87	7,64	12,51
		5,26	4,27	9,53
		7,34		7,34
				16,12	16,12	19,26
		3,33	15,93	19,26
		4,87	10,25	15,12
		5,26	7,64	12,9
		7,34	4,27	11,61
		9,49		9,49

На шаге i=1 основное функциональное уравнение имеет вид

W x (s) = max{ p x (x) + W 2 (s - x)}

а состояние системы перед первым шагом s=5, поэтому для проведения оптимизации на этом шаге заполним таблицу.

s	x	s-x	p i (x)	W 2 (s-x)	p i (x)+W 2 (s-x)	Wi(s)
				19,26	19,26	19,26
		3,22	15,93	19,15
		3,57	10,97	14,54
		4,12	7,64	11,76
			4,27	8,27
		4,85		4,85

Видно, что наибольшее значение выигрыша составляет 19,26. При этом оптимальное управление на первом шаге составляет x 1 (s 1)=0 (s 1 =5), на втором шаге x 2 (s 2) =1 (s 2 =s 1 -x 1 =5) и на третьем шаге x 3 (s 3) =4 (s 3 =s 2 -x 2 =4).

Это означает, что (0, 1, 4) - оптимальный план распределения инвестиций между предприятиями.

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

Список используемых источников

1. Беллман Р., Динамическое программирование, пер. с англ., М., 1960

2. Болтянский В. Г.,Математические методы оптимального управления, М., 1966

А теперь пример посерьёзнее:

Пример №3: Пилообразная последовательность

Решение

Для начала решение без матрицы перехода:

Вектор и матрица перехода

Динамика по подотрезкам

Пример №4: Запаковка строки

Вот Развернутое условие . Я вкратце его перескажу:

Необходимо по строке s узнать длину самой короткой сжатой строки, разжимающийся в неё.

Решение

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

Пример №5: Дубы

Динамика по поддеревьям

Пример №6: Логическое дерево

Решение

4) Порядок пересчёта: легче всего реализуется лениво - в виде поиска в глубину из корня.
5) Ответ - d xor 1] .

Динамика по подмножествам

Пример №7: Гамильтонов цикл минимального веса, или задача коммивояжера

Решение

Динамика по профилю

Пример №8: Замощение доминошками

Найти количество способов замостить таблицу N x M с помощью доминошек размерами 1 x 2 и 2 x 1 .

Решение

Примеры переходов (из верхнего профиля можно перейти в нижние и только в них):

Полученная асимптотика - .

Динамика по изломанному профилю

Переходы в динамике по изломанному профилю на примере задачи про замощение доминошками (пример №8):

Восстановление ответа

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

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

Небольшие оптимизации

Память

Время

Замена состояния

Пример №9: Разложение числа

3 + 4
2 + 5
1 + 7
1 + 2 + 4

ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ, раздел оптимального управления, посвящённый теории и методам решения многошаговых задач. В задачах оптимального управления среди возможных управлений ищется то, при котором достигается экстремальное (наименьшее или наибольшее) значение так называемой целевой функции - некоторой числовой характеристики процесса. В динамическом программировании под многошаговостью понимают либо многоступенчатую структуру процесса, либо то, что управление разбивается на ряд последовательных этапов (шагов), соответствующих, как правило, различным моментам времени. Иногда многошаговость проистекает из существа процесса, но она может вводиться и искусственно для того, чтобы обеспечить возможность применения методов динамического программирования. Под программированием в динамическом программировании понимают принятие решений (планирование), а слово «динамическое» указывает на существенную роль времени и порядка выполнения операций. Методы динамического программирования являются составной частью методов, используемых в исследовании операций, и применяются в задачах оптимального планирования (например, в задачах об оптимальном распределении ресурсов, в теории управления запасами, в задачах замены оборудования) и при решении многих технических проблем (например, в задачах управления последовательными химическими процессами, в задачах оптимальной прокладки дорог).

Пусть процесс управления некоторой системой Х состоит из 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.

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), возмущаемой «белым шумом» при полном и точном измерении ее состояния, решение которой было дано в предыдущем разделе. Теорема доказана. Можно показать, что теорема разделения справедлива и при синтезе оптимального управления по квадратичному решению.