Суть динамического программирования. Предпосылки метода динамического программирования. Простой пример решения задач при помощи ДП
Для выбора оптимального решения при выполнении задач программирования иногда требуется перебирать большое количество комбинаций данных, что нагружает память персонального компьютера. К таким методам относится, например, метод программирования «разделяй и властвуй». В данном случае алгоритмом предусмотрено разделение задачи на отдельные мелкие подзадачи. Такой метод применяется только в тех случаях, когда мелкие подзадачи независимы между собой. Для того чтобы избежать выполнения лишней работы в том случае, если подзадачи взаимозависимы, используется метод динамического программирования, предложенный американцем Р.Беллманом в 50-х годах.
Суть метода
Динамическое программирование заключается в определении оптимального решения n-мерной задачи, разделяя ее n отдельных этапов. Каждый из них является подзадачей по отношению к одной переменной.
Основным преимуществом такого подхода можно считать то, что разработчики занимаются одномерными оптимизационными задачами подзадач вместо n-мерной задачи, а решение главной задачи собирается «снизу вверх».
Целесообразно применять динамическое программирование в тех случаях, когда подзадачи взаимосвязаны, т.е. имеют общие модули. Алгоритмом предусмотрено решение каждой из подзадач один раз, и сохранение ответов выполняется в специальной таблице. Это дает возможность не вычислять ответ заново при встрече с аналогичной подзадачей.
Задача динамического программирования оптимизации. Автором этого метода Р. Беллманом был сформулирован принцип оптимальности: каким бы ни являлось начальное состояние на каждом из шагов и решение, определенное на этом шаге, все следующие выбираются оптимальными по отношению к тому состоянию, которое принимает система в конце шага.
Метод усовершенствует выполнение задач, решаемых с помощью перебора вариантов или рекурсий.
Построение алгоритма задачи
Динамическое программирование предполагает построение такого алгоритма задач, при котором задача так разбивается на две или больше подзадач, чтобы ее решение складывалось из оптимального решения всех подзадач, входящих в нее. Далее возникает необходимость в написании рекуррентного соотношения и вычислении оптимального значения параметра для задачи в целом.
Иногда на 3-м шаге нужно дополнительно запоминать некоторую вспомогательную информацию о ходе выполнения каждой подзадачи. Это называется обратным ходом.
Применение метода
Динамическое программирование применяется при наличии двух характерных признаков:
- оптимальность для подзадач;
- наличие в задаче перекрывающихся подзадач.
Решая методом динамического программирования, сначала необходимо описать структуру решения. Задача обладает оптимальностью, если решение задачи складывается из оптимальных решений ее подзадач. В этом случае целесообразно использовать динамическое программирование.
Второе свойство задачи, существенное при данном методе, - небольшое число подзадач. Рекурсивное решение задачи использует одни и те же перекрывающиеся подзадачи, количество которых зависит от размера исходной информации. Ответ хранится в специальной таблице, программа экономит время, пользуясь этими данными.
Особенно эффективно применение динамического программирования тогда, когда по существу задачи нужно принимать решения поэтапно. Например, рассмотрим простой пример задачи замены и ремонта оборудования. Допустим, на литейной машине завода по изготовлению шин делают одновременно шины в двух разных формах. В том случае, если одна из форм выходит из строя, приходится машину разбирать. Понятно, что иногда выгоднее заменить и вторую форму для того, чтобы не разбирать машину на случай, если и эта форма окажется неработоспособной на следующем этапе. Тем более, бывает проще заменить обе работающие формы до того, как они начнут выходить из строя. Метод динамического программирования определяет наилучшую стратегию в вопросе о замене таких форм, учитывая все факторы: выгоду от продолжения эксплуатации форм, потери от простоя машины, стоимость забракованных шин и другое.
Динамическое программирование - тема, которой в рунете посвящено довольно мало статей, поэтому мы решили ею заняться. В этой статье будут разобраны классические задачи на последовательности, одномерную и двумерную динамику, будет дано обоснование решениям и описаны разные подходы к их реализации. Весь приведённый в статье код написан на Java.
О чём вообще речь? Что такое динамическое программирование?
Метод решения задачи путём её разбиения на несколько одинаковых подзадач, рекуррентно связанных между собой. Самым простым примером будут числа Фибоначчи - чтобы вычислить некоторое число в этой последовательности, нам нужно сперва вычислить третье число, сложив первые два, затем четвёртое таким же образом
на основе второго и третьего, и так далее (да, мы слышали про замкнутую формулу).
Хорошо, как это использовать?
Решение задачи динамическим программированием должно содержать следующее:
И что, мне для решения рекурсивный метод писать надо? Я слышал, они медленные.
Конечно, не надо, есть и другие подходы к реализации динамики. Разберём их на примере следующей задачи:
Вычислить n-й член последовательности, заданной формулами:
a 2n = a n + a n-1 ,
a 2n+1 = a n — a n-1 ,
a 0 = a 1 = 1.
Идея решения
Здесь нам даны и начальные состояния (a 0 = a 1 = 1), и зависимости. Единственная сложность, которая может возникнуть - понимание того, что 2n - условие чётности числа, а 2n+1 - нечётности. Иными словами, нам нужно проверять, чётно ли число, и считать его в зависимости от этого по разным формулам.
Рекурсивное решение
Очевидная реализация состоит в написании следующего метода:
Private static int f(int n){ if(n==0 || n==1) return 1; // Проверка на начальное значение if(n%2==0){ //Проверка на чётность return f(n/2)+f(n/2-1); // Вычисляем по формуле для чётных индексов, // ссылаясь на предыдущие значения }else{ return f((n-1)/2)-f((n-1)/2-1); // Вычисляем по формуле для нечётных //индексов, ссылаясь на предыдущие значения } }
И она отлично работает, но есть нюансы. Если мы захотим вычислить f(12) , то метод будет вычислять сумму f(6)+f(5) . В то же время, f(6)=f(3)+f(2) и f(5)=f(2)-f(1) , т.е. значение f(2) мы будем вычислять дважды. Спасение от этого есть - мемоизация (кеширование значений).
Рекурсивное решение с кэшированием значений
Идея мемоизации очень проста - единожды вычисляя значение, мы заносим его в какую-то структуру данных. Перед каждым вычислением мы проверяем, есть ли вычисляемое значение в этой структуре, и если есть, используем его. В качестве структуры данных можно использовать массив, заполненный флаговыми значениями. Если значение элемента по индексу N равно значению флага, значит, мы его ещё не вычисляли. Это создаёт определённые трудности, т.к. значение флага не должно принадлежать множеству значений функции, которое не всегда очевидно. Лично я предпочитаю использовать хэш-таблицу - все действия в ней выполняются за O(1) , что очень удобно. Однако, при большом количестве значений два числа могут иметь одинаковый хэш, что, естественно, порождает проблемы. В таком случае стоит использовать, например, красно-чёрное дерево .
Для уже написанной функции f(int) кэширование значений будет выглядеть следующим образом:
Private static HashMap
Не слишком сложно, согласитесь? Зато это избавляет от огромного числа операций. Платите вы за это лишним расходом памяти.
Последовательное вычисление
Теперь вернёмся к тому, с чего начали - рекурсия работает медленно. Не слишком медленно, чтобы это приносило действительные неприятности в настоящей жизни, но на соревнованиях по спортивному программированию каждая миллисекунда на счету.
Метод последовательного вычисления подходит, только если функция ссылается исключительно на элементы перед ней - это его основной, но не единственный минус. Наша задача этому условию удовлетворяет.
Суть метода в следующем: мы создаём массив на N элементов и последовательно заполняем его значениями. Вы, наверное, уже догадались, что таким образом мы можем вычислять в том числе те значения, которые для ответа не нужны. В значительной части задач на динамику этот факт можно опустить, так как для ответа часто бывают нужны как раз все значения. Например, при поиске наименьшего пути мы не можем не вычислять путь до какой-то точки, нам нужно пересмотреть все варианты. Но в нашей задаче нам нужно вычислять приблизительно log 2 (N) значений (на практике больше), для 922337203685477580-го элемента (MaxLong/10) нам потребуется 172 вычисления.
Private static int f(int n){
if(n<2) return 1; //Может, нам и вычислять ничего не нужно?
int fs = int[n]; //Создаём массив для значений
fs=fs=1; //Задаём начальные состояния
for(int i=2; i Ещё одним минусом такого подхода является сравнительно большой расход памяти. Сейчас нам предстоит, по сути, написать свою собственную рекурсию. Идея состоит в следующем - сначала мы проходим «вниз» от N до начальных состояний, запоминая аргументы, функцию от которых нам нужно будет вычислять. Затем возвращаемся «вверх», последовательно вычисляя значения от этих аргументов, в том порядке, который мы записали. Зависимости вычисляются следующим образом: LinkedList Полученный размер стека – то, сколько вычислений нам потребуется сделать. Именно так я получил упомянутое выше число 172. Теперь мы поочередно извлекаем индексы и вычисляем для них значения по формулам – гарантируется, что все необходимые значения уже будут вычислены. Хранить будем как раньше – в хэш-таблице. HashMap Все необходимые значения вычислены, осталось только написать Return values.get(n);
Конечно, такое решение гораздо более трудоёмкое, однако это того стоит. Для больше ясности разберём следующую задачу на одномерную динамику: На вершине лесенки, содержащей N ступенек, находится мячик, который начинает прыгать по ним вниз, к основанию. Мячик может прыгнуть на следующую ступеньку, на ступеньку через одну или через 2. (То есть, если мячик лежит на 8-ой ступеньке, то он может переместиться на 5-ую, 6-ую или 7-ую.) Определить число всевозможных «маршрутов» мячика с вершины на землю. На первую ступеньку можно попасть только одним образом - сделав прыжок с длиной равной единице. На вторую ступеньку можно попасть сделав прыжок длиной 2, или с первой ступеньки - всего 2 варианта. На третью ступеньку можно попасть сделав прыжок длиной три, с первой или со втрой ступенек. Т.е. всего 4 варианта (0->3; 0->1->3; 0->2->3; 0->1->2->3). Теперь рассмотрим четвёртую ступеньку. На неё можно попасть с первой ступеньки - по одному маршруту на каждый маршрут до неё, со второй или с третьей - аналогично. Иными словами, количество путей до 4-й ступеньки есть сумма маршрутов до 1-й, 2-й и 3-й ступенек. Математически выражаясь, F(N) = F(N-1)+F(N-2)+F(N-3) . Первые три ступеньки будем считать начальными состояниями. Здесь ничего хитрого нет. Исходя из того, что, по большому счёту, простое решение на массиве из N элементов очевидно, я продемонстрирую тут решение на массиве всего из трёх. Int vars = new int;
vars=1;vars=2;vars=4;
for(int i=3; i Так как каждое следующее значение зависит только от трёх предыдущих, ни одно значение под индексом меньше i-3 нам бы не пригодилось. В приведённом выше коде мы записываем новое значение на место самого старого, не нужного больше. Цикличность остатка от деления на 3 помогает нам избежать кучи условных операторов. Просто, компактно, элегантно. С двумерной динамикой не связано никаких особенностей, однако я, на всякий случай, рассмотрю здесь одну задачу и на неё. В прямоугольной таблице NxM в начале игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). Посчитайте, сколько есть способов у игрока попасть в правую нижнюю клетку. Логика решения полностью идентична таковой в задаче про мячик и лестницу - только теперь в клетку (x,y) можно попасть из клеток (x-1,y) или (x, y-1) . Итого F(x,y) = F(x-1, y)+F(x,y-1) . Дополнительно можно понять, что все клетки вида (1,y) и (x,1) имеют только один маршрут - по прямой вниз или по прямой вправо. Ради всего святого, не нужно делать двумерную динамику через рекурсию. Уже было упомянуто, что рекурсия менее выгодна, чем цикл по быстродействию, так двумерная рекурсия ещё и читается ужасно. Это только на таком простом примере она смотрится легко и безобидно. Private static int f(int i, int j) {
if(i==1 || j==1) return 1;
return f(i-1, j)+f(i, j-1);
}
В заключение приведу ряд типичных задач на одномерную и двумерную динамику, разборы прилагаются. При переработке радиоактивных материалов образуются отходы двух видов - особо опасные (тип A) и неопасные (тип B). Для их хранения используются одинаковые контейнеры. После помещения отходов в контейнеры последние укладываются вертикальной стопкой. Стопка считается взрывоопасной, если в ней подряд идет более одного контейнера типа A. Стопка считается безопасной, если она не является взрывоопасной. Для заданного количества контейнеров N определить количество возможных типов безопасных стопок. Ответом является (N+1)-е число Фибоначчи. Догадаться можно было, просто вычислив 2-3 первых значения. Строго доказать можно было, построив дерево возможных построений. Каждый основной элемент делится на два - основной (заканчивается на B) и побочный (заканчивается на A). Побочные элементы превращаются в основные за одну итерацию (к последовательности, заканчивающейся на A, можно дописать только B). Это характерно для чисел Фибоначчи. Например, так: //Ввод числа N с клавиатуры
N+=2;
BigInteger fib = new BigInteger;
fib=fib=BigInteger.ONE;
for(int i=2; i Мальчик подошел к платной лестнице. Чтобы наступить на любую ступеньку, нужно заплатить указанную на ней сумму. Мальчик умеет перешагивать на следующую ступеньку, либо перепрыгивать через ступеньку. Требуется узнать, какая наименьшая сумма понадобится мальчику, чтобы добраться до верхней ступеньки. Очевидно, что сумма, которую мальчик отдаст на N-ой ступеньке, есть сумма, которую он отдал до этого плюс стоимость самой ступеньки. «Сумма, которую он отдал до этого» зависит от того, с какой ступеньки мальчик шагает на N-ую - с (N-1)-й или с (N-2)-й. Выбирать нужно наименьшую. Например, так: Int Imax;
//*ввод с клавиатуры числа ступенек*
DP = new int;
for(int i=0; i Имеется калькулятор, который выполняет три операции: Определите, какое наименьшее число операций необходимо для того, чтобы получить из числа 1 заданное число N. Выведите это число, и, на следующей строке, набор исполненных операций вида «111231». Наивное решение состоит в том, чтобы делить число на 3, пока это возможно, иначе на 2, если это возможно, иначе вычитать единицу, и так до тех пор, пока оно не обратится в единицу. Это неверное решение, т.к. оно исключает, например, возможность убавить число на единицу, а затем разделить на три, из-за чего на больших числах (например, 32718) возникают ошибки. Правильное решение заключается в нахождении для каждого числа от 2 до N минимального количества действий на основе предыдущих элементов, иначе говоря: F(N) = min(F(N-1), F(N/2), F(N/3)) + 1 . Следует помнить, что все индексы должны быть целыми. Для воссоздания списка действий необходимо идти в обратном направлении и искать такой индекс i, что F(i)=F(N) , где N - номер рассматриваемого элемента. Если i=N-1 , записываем в начало строки 1, если i=N/2 - двойку, иначе - тройку. В каждой клетке прямоугольной таблицы N*M записано некоторое число. Изначально игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). При проходе через клетку с игрока берут столько килограммов еды, какое число записано в этой клетке (еду берут также за первую и последнюю клетки его пути). Требуется найти минимальный вес еды в килограммах, отдав которую игрок может попасть в правый нижний угол. 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.2. Основное
уравнение метода динамического
программирования Применим принцип
оптимальности к решению вариационной
задачи (4.1), (4.2). Для этого сначала
рассмотрим функционал
(4.3). Наименьшее значение его при связях
(4.1) обозначим: . (4.8) Если
. Оптимальное
управление
Интервал
. Согласно принципу
оптимальности последний участок также
является оптимальным: (4.9) Обозначим: , (4.10) где
. Хотя функция
. Учитывая, что ; , получим основное
уравнение метода динамического
программирования: (4.11) Это соотношение
состоит из двух утверждений: Если
(4.12) Здесь
изаменить согласно системе (4.1): .(4.13) Подставляя (4.13) в
(4.12) получим уравнение Р.Беллмана: . (4.14) Это уравнение в
частных производных относительно
. В случае бесконечного
интервала при
В том случае, когда
рассматривается функционал Больца (4.15) Уравнение (4.12)
сохраняет силу, функция v
в момент
. (4.16) 4.3. Две задачи
оптимального управления В теории оптимального
управления различают задачи двух типов:
программного управления и синтеза. В
первой задаче оптимальное управление
строится в виде функции временидля конкретных начальных и конечных
условий, если они заданы. Зависимость Во второй задаче
оптимальное управление
строится для каждого момента временикак функция вектора фазовых координатт.е. в виде . (4.17) Построение такой
зависимости является целью задачи
синтеза. Значение второй задачи в том,
что зависимость
Программное
управление и управление по обратной
связи осуществляются технически
по-разному. Первое может осуществляться
программным часовым механизмом, по
жесткому закону, как функция времени
.
Это управление никак не реагирует на
возможные отклонения состояний объекта
от идеального, желательного. Управление
по обратной связи осуществляется при
помощи регулятора, который по результатам
измерения реального состояния фазовых
координат вырабатывает сигнал, согласно
которому отклоняется управляющий орган. Обе задачи
взаимосвязаны. Решение одной можно
выразить через другое. Однако отметим,
что принцип максимума обычно приводит
к представлению управления в виде
программы, а метод динамического
программирования – в виде синтеза. Значительное
развитие получила задача синтеза
оптимального управления процессами,
описываемыми линейной системой
дифференциальных уравнений, при
минимизации интегральных квадратичных
функционалов. Она называется задачей
аналитического конструирования
оптимальных регуляторов (АКОР), или
задачей А.М.Летова. 4.4. Задача
аналитического конструирования
оптимальных регуляторов Предположим
уравнения возмущенного движения системы
имеют вид (4.18) Матрицы
Предполагается
также, что состояние системы (4.18) в каждый
момент времени
известно. В качестве критерия
оптимальности рассматривается
квадратичный функционал Больца где
Требуется найти
оптимальное (минимизирующее функционал
4.19) управление, являющееся функцией
текущего состояния
Для решения этой
задачи можно воспользоваться принципом
максимума, но наиболее короткий путь –
метод динамического программирования. В соответствии с
этим методом нужно найти функцию
. (4.20) В общем случае –
это сложная задача, однако для линейных
систем с квадратичным критерием
оптимальности функцию (4.21) где
. (4.22) Таким образом, для
линейных систем задача сводится к
отысканию функции
Минимизируя (4.23)
по
(4.24) Так как
Подставляя (4.24) в
(4.23), получим Квадратичная форма
(4.25) равна нулю при любых
(2.26) с граничным условием
(4.22). Интегрируя уравнение
(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) с матрицей
5. Оптимальное
управление стохастическими системами
в условиях неопределенности. 5.1. Характеристики
случайных сигналов В пособие в качестве
математических моделей возмущающих
воздействий и погрешностей измерений
используются стохастические (случайные)
процессы и последовательности. Случайный процесс
Через
Следует отметить,
что многие статистические характеристики
случайных процессов и последовательностей
совпадают. Как
известно, наиболее полной характеристикой
случайного
процесса является
- мерный закон распределения или
-мерная
плотность распределения Здесь символом
обозначается вероятность события,
заключенногов
скобках. Значение
может быть любым от I
до
Часто,
особенно в прикладных задачах, для
статистического описания
случайных процессов используют начальные
Математическое ожидание (среднее
значение) ; (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.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.45) где матрица
причем
Полученные
соотношения (5.45), (5.46) будут использованы
при статистическом анализе дискретных
систем. 5.3. Уравнения
моментов для линейных систем Сначала
рассмотрим непрерывные системы. Пусть
уравнения движения
имеют вид; . (5.47) Относительно
возмущающих воздействий
При
получении соотношений для математического
ожидания состояния системы
Учитывая
(5.28), получим: . (5.48) На
основании (5.47), (5.48) уравнение для
центрированной составляющей
. (5.49) Теперь
найдем уравнение для дисперсионной
матрицы
.
Дифференцируя по
матрицу
(5.50) Для
вычисления математического ожидания
. (5.51) Умножив выражение
(5.51) справа на
(5.52) С
учетом того, что , (5.53) уравнение
(5.50) примет вид; с начальным условием
Теперь
пусть поведение системы описывается
дискретным уравнением Будем полагать,
что начальное условие
и возмущающие воздействия
Осредняя
(5.55) и учитывая (5.37), получим: Уравнение
для центрированной составляющей
Используя
(5.57) и (5.37), найдем уравнение для
дисперсионной матрицы
(5.58) Определим
математическое ожидание
(5.59) Аналогично . Таким
образом, уравнение для определения
матрицы
5.4. Задача оптимальной
фильтрации и ее решение методом Калмана Как было показано
раньше, для оптимального управления по
принципу обратной связи необходимо
иметь полную информацию о состоянии
системы. Однако измерению доступны лишь
некоторые функции состояния или их
комбинации. Кроме того, наблюдаемый
сигнал содержит погрешности измерений.
В такой ситуации важной является задача
получения наилучшей оценки состояния
системы по результатам измерений –
задача оптимальной фильтрации. Предположим, что
динамический процесс описывается
совокупностью дифференциальных уравнений где
Пусть измерению
поддается
где
Относительно
свойств случайных процессов
Математически
задача оптимальной фильтрации ставится
как задача отыскания оценки
Калман предложил
искать уравнение фильтра в виде линейной
системы на вход которой подается
наблюдаемый сигнал
(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.71) Нетрудно
показать, что минимизация производной
критерия обеспечивает
минимум и для самого критерия Запишем
выражение
. (5.72) Подставив
в (5.72) выражение для
из (5.67) и соответствующее выражение для
,
получим: (5.73) Найдем
где
Используем свойство
дельта-функции: , если
имеетразрыв
в точке
Поскольку
. (5.74) Аналогично
можно найти
. (5.75) Подставив
полученные выражения для
Следующее
тождество легко проверить, раскрыв в
правой части скобки
и использовав симметрию матрицы
С
учетом тождества приведем уравнение
(5.76) к виду: В
правой части (5.78) от коэффициента
При
этом последний член в уравнении (5.78)
обращается в нуль и
уравнение приобретает вид с
начальным значением
Итак, можем записать
уравнение фильтра Уравнения
(5.79), (5.80), (5.81) представляют собой уравнения
фильтра Калмана-Бьюси. Система оценивания
(фильтр) схематически представлена на
рис. 16. Следует
отметить, что уравнение фильтра и его
параметры не зависят от
матрицы
Для
стационарной системы
при стационарном
возмущающем воздействии
и
стационарном шуме
измерителя
после окончания переходных процессов
матричный коэффициент усиления в фильтре
Калмана становится
постоянным
Запишем
уравнения стационарного фильтра Калмана
в следующем виде: ; (5.83) Один
из часто используемых способов решения
уравнения (5.84)
(обычно с помощью ЦВМ) заключается в
решении нестационарного уравнения
(5.80) с соответствующими постоянными
значениями коэффициентов,
из которых составлены матрицы А,
С, Q,
R,
и
произвольной неотрицательно
определенной матрицей начальных условий
для
в текущем времени до тех пор, пока
полученное решение не достигнет
постоянного установившегося
значения. Это окончательное значение
принимается за искомое
решение уравнения (5.84). Такой способ
решения удобен тем, что алгоритмы
решения дифференциальных уравнений,
как правило, эффективнее алгоритмов
решения нелинейных алгебраических
уравнений. Замечание 1. Важным свойством
полученной ошибки является то, что она
некоррелирована с ошибкой оценивания,
т.е. . Замечание 2. Пусть теперь
уравнение измерения имеет вид (5.62), а
погрешность измерения отсутствует. В
этом случае для получения оценки
которая может быть
представлена в виде (5.62) Замечание 3. Для управляемых
систем, описываемых совокупностью
уравнений Уравнение фильтра
может быть получено аналогично. В этом
случае уравнение фильтра будет иметь
вид где матрица
с начальным условием
Система
оценивания (фильтр) схематически
представлена на рис. 17. 5.5. Синтез
локально-оптимального управления
линейными стохастическими системами
при полной и точной информации. Пусть
управляемое движение в условиях
воздействия возмущений описывается
системой уравнений Случайный
процесс
. (5.88) Тогда
задача определения локально-оптимального
управления сводится к нахождению
В
качестве функционала, характеризующего
управляемое движение, возьмем
математическое ожидание локального
функционала
. Введем матрицу
корреляционных моментов . (5.89) Используя
(5.88), (5.89) функционал можно
(5.90) Таким
образом, значение критерия качества в
текущий момент времени определяется
матрицей корреляционных моментов. Найдем
уравнение для ее определения. Уравнение
управляемого процесса (5.87) с учетом
(5.88) можно представить в виде где матрица B
соответствии с (5.54) уравнение для матрицы
или,
с учетом (5.91), (5.92) Начальным
условием является, очевидно, Из
(5.92), (5.93) с учетом предположения о
симметричности матриц
, Таким
образом, задача определения оптимального
управления свелась к задаче определения
матрицы
Выпишем
составляющие
Обозначим
через
. где
Приращение
Тогда
из (5.94) следует, что В силу
произвольности
Найденное
значение
в силу
определенной положительности матрицы
Сравнивая
(5.88), (5.95) с (4.30), видим, что найденное
локально-оптимальное управление
полностью совпадает с локально-оптимальным
управлением для детерминированного
случая. Таким образом,
синтезированное локально-оптимальное
управление для детерминированной
системы при полной и точной информации
о ее состоянии оказывается
локально-оптимальным и для стохастической
системы, возбуждаемой случайным
возмущением типа белого шума Аналогичный
результат имеет место и при квадратичном
критерии качества (4.19). Это объясняется
тем, что при
5.6. Синтез
локально-оптимального управления
линейными стохастическими системами
(теорема разделения). Пусть управляемое
движение описывается уравнением (5.87),
а уравнение измерения – (5.62). Рассмотрим задачу
синтеза, оптимального по критерию При этом будем
отыскивать такое управление, значение
которого в момент времени
определяется значениями вектор-функции Обозначим через
Наряду с системой
(5.87) рассмотрим соответствующую ей
неуправляемую систему с уравнением
измерения Для вспомогательной
системы задача фильтрации решена и
оценка
(5.98) с начальным условием где матрица
Из уравнений (5.87)
и (5.97) следует, что , (5.99) где
Мы отыскиваем
управление, которое определяется в
момент времени
значениями вектор-функции (5.100) Из (5.99) и (5.100)
следует, что Найдем теперь
уравнение для определения
Учитывая (5.98),
найдем (5.101) Тогда уравнение
фильтра окончательно запишется в виде
(5.85) с начальным условием , (5.103) т.е. фильтр для
определения оценки состояния управления
системы есть динамическое звено, на
вход которого поступает измеряемый
сигнал и управление
Теорема разделения.
Локально-оптимальное управление системой
(5.87) по критерию (5.96) имеет вид: Здесь
Доказательство.
Рассмотрим функционал (5.96). Учитывая,
что оценки
, Так как на
Рассмотрим выражение Учитывая, что
,
нетрудно показать , что Таким образом, в
уравнении (5.102) выражение
В результате мы
пришли к задаче синтеза локально-оптимального
уравнения в системе (5.102), (5.103), возмущаемой
«белым шумом» при полном и точном
измерении ее состояния, решение которой
было дано в предыдущем разделе. Теорема
доказана. Можно показать, что теорема
разделения справедлива и при синтезе
оптимального управления по квадратичному
решению. Раздел Динамическое программирование представлен следующими калькуляторами:
В задачах динамического программирования экономический процесс зависит от времени (или от нескольких периодов времени), поэтому находится ряд оптимальных решений (последовательно для каждого этапа), обеспечивающих оптимальное развитие всего процесса в целом. Динамическое программирование представляет собой математический аппарат, позволяющий осуществлять оптимальное планирование управляемых процессов и процессов, зависящих от времени. Поэтапное проведение оптимизации называется многошаговым процессом принятия решения. Экономический процесс называется управляемым, если можно влиять на ход его развития. В основе метода динамического программирования (ДП) лежит принцип последовательной оптимизации: решение исходной задачи оптимизации большой размерности заменяется решением последовательности задач оптимизации малой размерности. Основным условием применимости метода ДП является возможность разбиения процесса принятия решений на ряд однотипных шагов или этапов, каждый из которых планируется отдельно, но с учетом результатов, полученных на других шагах. Например, деятельность отрасли промышленности в течение ряда хозяйственных лет или же последовательность тестов, применяемых при контроле аппаратуры, и т. д. Некоторые процессы (операции) расчленяются на шаги естественно, но существуют такие операции, которые приходится делить на этапы искусственно, например процесс наведения ракеты на цель.
Рассмотрим общее описание задачи динамического программирования
.
Сформулируем теперь задачу динамического программирования
: «Определить совокупность допустимых управлений (u
1 , …, u n
), переводящих систему из начального состояния ε 0 в конечное состояние ε n
и максимизирующих или минимизирующих показатель эффективности F
».
), выглядящим как набор перекрывающихся подзадач, сложность которых чуть меньше исходной. В этом случае время вычислений, по сравнению с «наивными» методами, можно значительно сократить. Ключевая идея в динамическом программировании достаточно проста. Как правило, чтобы решить поставленную задачу, требуется решить отдельные части задачи (подзадачи), после чего объединить решения подзадач в одно общее решение. Часто многие из этих подзадач одинаковы. Подход динамического программирования состоит в том, чтобы решить каждую подзадачу только один раз, сократив тем самым количество вычислений. Это особенно полезно в случаях, когда число повторяющихся подзадач экспоненциально велико. Метод динамического программирования сверху
- это простое запоминание результатов решения тех подзадач, которые могут повторно встретиться в дальнейшем. Динамическое программирование снизу
включает в себя переформулирование сложной задачи в виде рекурсивной последовательности более простых подзадач. Словосочетание «динамическое программирование» впервые было использовано в -х годах Р. Беллманом для описания процесса нахождения решения задачи, где ответ на одну задачу может быть получен только после решения задачи, «предшествующей» ей. В г. он уточнил это определение до современного. Первоначально эта область была основана, как системный анализ и инжиниринг, которая была признана IEEE . Вклад Беллмана в динамическое программирование был увековечен в названии уравнения Беллмана , центрального результата теории динамического программирования, который переформулирует оптимизационную задачу в рекурсивной форме. Слово «программирование» в словосочетании «динамическое программирование» в действительности к "традиционному" программированию (написанию кода) почти никакого отношения не имеет и имеет смысл как в словосочетании «математическое программирование », которое является синонимом слова «оптимизация». Поэтому слово «программа» в данном контексте скорее означает оптимальную последовательность действий для получения решения задачи. К примеру, определенное расписание событий на выставке иногда называют программой. Программа в данном случае понимается как допустимая последовательность событий. Нахождение кратчайшего пути в графе из одной вершины в другую, используя оптимальную подструктуру; прямая линия обозначает простое ребро; волнистая линия обозначает кратчайший путь между вершинами, которые она соединяет (промежуточные вершины пути не показаны); жирной линией обозначен итоговый кратчайший путь. Оптимальная подструктура
в динамическом программировании означает, что оптимальное решение подзадач меньшего размера может быть использовано для решения исходной задачи. К примеру, кратчайший путь в графе из одной вершины (обозначим s) в другую (обозначим t) может быть найден так: сначала считаем кратчайший путь из всех вершин, смежных с s, до t, а затем, учитывая веса ребер, которыми s соединена со смежными вершинами, выбираем лучший путь до t (через какую вершину лучше всего пойти). В общем случае мы можем решить задачу, в которой присутствует оптимальная подструктура, проделывая следующие три шага. Подзадачи решаются делением их на подзадачи ещё меньшего размера и т. д., пока не приходят к тривиальному случаю задачи, решаемой за константное время (ответ можно сказать сразу). К примеру, если нам нужно найти n!, то тривиальной задачей будет 1! = 1 (или 0! = 1). Перекрывающиеся подзадачи
в динамическом программировании означают подзадачи, которые используются для решения некоторого количества задач (не одной) большего размера (то есть мы несколько раз проделываем одно и то же). Ярким примером является вычисление последовательности Фибоначчи , и - даже в таком тривиальном случае вычисления всего двух чисел Фибоначчи мы уже посчитали дважды. Если продолжать дальше и посчитать , то посчитается ещё два раза, так как для вычисления будут нужны опять и . Получается следующее: простой рекурсивный подход будет расходовать время на вычисление решение для задач, которые он уже решал. Чтобы избежать такого хода событий мы будем сохранять решения подзадач, которые мы уже решали, и когда нам снова потребуется решение подзадачи, мы вместо того, чтобы вычислять его заново, просто достанем его из памяти. Этот подход называется кэширование . Можно проделывать и дальнейшие оптимизации - например, если мы точно уверены, что решение подзадачи нам больше не потребуется, можно выкинуть его из памяти, освободив её для других нужд, или если процессор простаивает и мы знаем, что решение некоторых, ещё не посчитанных подзадач, нам понадобится в дальнейшем, мы можем решить их заранее. Подводя итоги вышесказанного можно сказать, что динамическое программирование пользуется следующими свойствами задачи: Динамическое программирование обычно придерживается двух подходов к решению задач: Языки программирования могут запоминать результат вызова функции с определенным набором аргументов (мемоизация), чтобы ускорить «вычисление по имени». В некоторых языках такая возможность встроена (например, Scheme , Common Lisp , Perl), а в некоторых требует дополнительных расширений (C++). Известны сериальное динамическое программирование, включённое во все учебники по исследованию операций , и несериальное динамическое программирование (НСДП), которое в настоящее время слабо известно, хотя было открыто в 1960-х годах. Обычное динамическое программирование является частным случаем несериального динамического программирования, когда граф взаимосвязей переменных - просто путь. НСДП, являясь естественным и общим методом для учета структуры задачи оптимизации, рассматривает множество ограничений и/или целевую функцию как рекурсивно вычислимую функцию. Это позволяет находить решение поэтапно, на каждом из этапов используя информацию, полученную на предыдущих этапах, причём эффективность этого алгоритма прямо зависит от структуры графа взаимосвязей переменных. Если этот граф достаточно разрежен, то объём вычислений на каждом этапе может сохраняться в разумных пределах. Одним из основных свойств задач, решаемых с помощью динамического программирования, является аддитивность . Неаддитивные задачи решаются другими методами. Например, многие задачи по оптимизации инвестиций компании являются неаддитивными и решаются с помощью сравнения стоимости компании при проведении инвестиций и без них. Wikimedia Foundation
.
2010
.
динамическое программирование
- — [Е.С.Алексеев, А.А.Мячев. Англо русский толковый словарь по системотехнике ЭВМ. Москва 1993] динамическое программирование Раздел математического программирования, совокупность приемов, позволяющих находить оптимальные решения, основанные … Справочник технического переводчика
Динамическое программирование
- раздел математического программирования, совокупность приемов, позволяющих находить оптимальные решения, основанные на вычислении последствий каждого решения и выработке оптимальной стратегии для последующих решений.… … Экономико-математический словарь
Раздел математики, посвященный теории и методам решения многошаговых задач оптимального управления. В Д. п. для управляемых процессов среди всевозможных управлений ищется то, к рое доставляет экстремальное (наименьшее или наибольшее) значение… … Математическая энциклопедия
Раздел математики, посвящённый теории и методам решения многошаговых задач оптимального управления (См. Оптимальное управление). В Д. п. для управляемых процессов среди всех возможных управлений ищется то, которое доставляет… … Большая советская энциклопедия
динамическое программирование
- dinaminis programavimas statusas T sritis automatika atitikmenys: angl. dynamic programming vok. dynamische Programmierung, f rus. динамическое программирование, n pranc. programmation dynamique, f … Automatikos terminų žodynas
Раздел математич. программирования, изучающий многошаговые процессы поиска оптим. решения сложных задач. Применяется при составлении программ решения таких задач оптимизации, для к рых процесс поиска решения можно представить в виде нек рой… … Большой энциклопедический политехнический словарь
Создание стека индексов
Хорошо, математика - это красиво. А что с задачами, в которых не всё дано?
Идея решения
Реализация через рекурсию
private static int f(int n){
if(n==1) return 1;
if(n==2) return 2;
if(n==3) return 4;
return f(n-1)+f(n-2)+f(n-3);
}
Там вверху ещё было написано про какую-то двумерную динамику?..
Идея решения
Реализация через рекурсию
Реализация через массив значений
int dp = new int;
for(int i=0; iОтлично, я всё понял. На чём мне проверить свои навыки?
Взрывоопасность
Решение
Реализация
Подъём по лестнице
Решение
Реализация
Калькулятор
Решение
Реализация
int N;
//Ввод с клавиатуры
int a = new int;
a= 0;
{
int min;
for(int i=2; iСамый дешёвый путь
и минимизируется функционал
,
достигнутого к моменту временипри оптимизации процесса в интервале
.
и
отличаются интервалом и значениями.
Принцип оптимальности утверждает, что
оптимальные управления
и
в общей части интервала
совпадают, не зависимо от предыстории
процесса и вполне определяются состоянием
в момент
.
управления
и
не совпадают и
- управление, минимизирующее
(4.3).
- оптимальное управление, то
зависит от начального состояния
в момент
.
Следовательно,является функцией оти:
,
а от управленияи его вариаций функция
не зависит. Она вполне определяется
значениями
.
разделим на два интервала
и
и выражение (4.8) запишем в виде:
- приращение вектора фазовых координат
за время
.
Оно определяется согласно уравнениям
движения (4.1). Подставляя
из (4.10) в равенство (4.9), получим:
зависит только от фазовых координат и
времени, ее нельзя выносить за знак
.
Значение приращения
за время
зависит от управления в интервале
.
Но
не зависит от управления в интервале
и ее можно внести под знак
.
Введем
под знак минимума и разделим на
:
- управление, минимизирующее выражение
,
то основное уравнение метода динамического
программирования
зависит от управления по определению,
функция же
не зависит от него. Тем не менее,
производнаяот управления зависит. В этом можно
убедиться, если ее представить в виде
,
которое после подстановки
становится нелинейным. Согласно
определению(4.8) при
должно выполняться конечное условие
процесс должен быть асимптотически
устойчивым, т.е.
.
должна удовлетворять условию
рассматривается как программа.
дает уравнение обратной связи или
оптимального регулятора, замыкающего
систему. Она применяется при оптимальном
управлении переходным процессом.
,
размерности
и
,
соответственно, имеют в качестве своих
элементов известные функции
.
- симметричные неотрицательно определенные
матрицы,
- положительно определенная матрица;
*) - индекс транспонирования.
.
,
удовлетворяющего уравнению
можно искать в виде некоторой квадратичной
формы.
- есть некоторая, пока неизвестная,
квадратичная форма, удовлетворяющая в
силу (4.16) конечному условию
.
Дифференцируя (4.21) с учетом (4.18) получим
,
получим
,
то управление (4.24) действительно
доставляет минимум выражению
.
только в том случае, когда равна нулю
матрица, ее образующая. Таким образом,
получаем уравнение для определения
матрицы
,
а значит и параметры оптимального
управления (4.24). Нетрудно показать, что
матрица
- симметричная матрица. Для этого
достаточно транспонировать уравнение
(4.26). Тогда
.
(рассматривается установившийся режим).
Матрицатоже числовая и удовлетворяет
алгебраическому уравнению
.
В том случае, когда эту информацию
получить невозможно, для реализации
оптимального управления используются
оценки состояния, получаемые на основе
имеющейся неполной информации.
параметрически зависящий от времении определенный на множестве функций
и
.
,
минимизирующее
,
где- текущий момент времени. Такое управление
называется локально-оптимальным.
с необходимостью удовлетворяет условию
найдем локально-оптимальное управление
,
так как
,
а для реализации его необходима полная
информация о состоянии процесса
.
Задаваясь различными матрицами весовых
функций
,
можно обеспечить те или иные свойства
управляемого процесса, в частности
свойства устойчивости или асимптотической
устойчивости.
будет определена из условия
,
где-
некоторый фиксированный момент времени.
Потребуем также, чтобы в момент времениматричная функция
удовлетворяла конечному условию
,
определяемой из уравнения (4.33) с условием
(4.34) совпадает с управлением (4.24),
оптимальным по квадратичному критерию
(4.19) на интервале
.
- это такая функция, значение которой в
фиксированный момент
есть случайная величина, т.е. случайный
процесс можно рассматривать как случайную
величину, зависящую от параметра
.
В том случае, когда параметр
меняется дискретно, случайный процесс
называют случайной последовательностью.
будем обозначать реализацию случайного
процесса
.
.
Для произвольного
случайного процесса такую информацию
иметь невозможно. Однако существует
класс случайных процессов
(последовательностей), называемых
марковскими, для которых статистические
характеристики полностью
определяются двумерным законом
распределения или двумерной плотностью
распределения.
ицентральные
моменты
-гo
порядка. Здесь символом
обозначена операция осреднения
(математического ожидания). Наиболее
важную роль играют следующие моменты:
- центрированный случайный процесс с
нулевым
математическим ожиданием;
,
,
и
следует, что эти величины характеризуют
случайный процесс только в фиксированномсечении
.
Для характеристики связи двух различных
сечений случайного процесса используется
корреляционная
функция;
случайного
процесса не зависит
от времени, а корреляционная функция
является функцией одного
аргумента
,
то такой процесс называется стационарным
в широком смысле.
и
корреляционной функции
.
- плотностьраспределения
дисперсии (энергии) по частотам.
и корреляционная функция
связаны
прямым и обратным преобразованием
Фурье:
взаимно независимы
при любых значениях аргументов. Такой
процесс полностью характеризуется
одномерной функцией распределения.
Чисто случайный стационарный
процесс называют белым шумом, если
корреляционная функция
имеет вид
-
функции. Спектральная плотность такого
процесса постоянна по всем частотам.
Так как
,
то нетрудновидеть,
что дисперсия белого шума является
бесконечно большой. Такие процессы в
природе реально не существуют. Однако
реальный шум по его воздействию на
систему может быть заменен белым шумом.
Кроме того,
реальный случайный процесс можно
представить как выходной
сигнал некоторой системы (формирующего
фильтра), на вход которой
поступает белый шум. Поэтому задача
статистического анализа или синтеза
систем с реальными характеристиками
случайных воздействий
может быть сведена к задаче статистического
анализа или синтеза, когда входным
сигналом является белый шум. В настоящем
учебном
пособии, как правило, будут использоваться
модели белых шумов и
чисто случайных последовательностей.
является случайным процессом. Для
характеристики
векторного случайного процесса вводятся
следующие векторы
и матрицы:
:
:
означает транспонирование.
видно,
что на ее
диагонали расположены дисперсии
составляющих случайного процесса.
,
и
обладают следующими свойствами:
вводится
матрица спектральных плотностей как
преобразование Фурье ко вариационной
матрицы
,
т.е.
обладает следующим свойством:
,
управляющие воздействия
,
возмущающие
воздействия
в выход системы
в момент
.
-мерный
вектор состояния системы; через
-
-мерный
вектор управляющих воздействий; через
-
-мерный
вектор возмущений. Тогда уравнение
движения линейной
непрерывной динамической системы можно
записать в следующей
дифференциальной форме:
,
,
- матрицы размерностей
соответственно.
Элементами этих матриц являются
непрерывные функции.
Если матрицы
иявляются постоянными, то управляемаясистема
называется стационарной. Уравнения
(5.24) обычно называют уравнениями
состояния, так как они описывают изменение
переменных состояния системы
во времени.
-
-мерный
наблюдаемый сигнал;
-
матрица размерности
,характеризующая
способ измерения;
-
погрешность
измерения. Если
(
- единичная матрица) и
,
то говорят,
что измерение полное и точное.
,которая
удовлетворяет следующему матричному
уравнению:
,
третья составляющая характеризует
вынужденное движение, обусловленное
возмущениями
на интервале
.
и
являются
процессами типа белого шума. Матрицы
и
вектор
считаются известными. Предполагаются
известными в каждый
момент времени
и управляющие
воздействия.
- чисто
случайная последовательность.
-
дискретное время.
.
Уравнения движения имеют
вид:
состоит
из двух вектор-столбцов решений следующей
системы уравнений
имеет вид:
в виде
ряда:
.
постоянно
на шаге дискретности, получим следующую
эквивалентную дискретную
систему:
не только от
и
,
но оти всех предшествующих
.
Используя соотношения (5.33), для различныхможно записать:
определяется следующим образом:
при
.
и
начального
состояния
будем
предполагать, что они удовлетворяют
условиям (5.28).
осредним уравнение (5.47):
имеет вид:
и
учитывая, что матрицы
и
не случайные, получим:
используем
формулу Коши (5.27):
,
осредниви
учитывая (5.28),
получим:
.
удовлетворяют соотношениям (5.37). Найдем
уравнения для математического
ожидания и дисперсионной матрицы.
имеет
вид:
:
,
используясоотношение
(5.45) и свойства (5.37):
имеет
вид:
--мерный
вектор состояния,
--мерный
вектор возмущающих воздействий,
и
матрицы соответствующих размерностей.
-мерный
вектор некоторых комбинаций функций
состояния (5.25)
- погрешность измерения.
и начального состояния
будет предполагать, что они удовлетворяют
условиям (5.28), т.е. будет предполагать,
что это случайные процессы типа белого
шума, не коррелированные друг с другом
и начальным состоянием системы.
состояния системы (5.61)
на основе имеющейся информации
.
.
Тогда уравнения движения такой системы
можно описать совокупностью уравнений
и
подлежат определению, т.е. структура
фильтра задается, а параметры структуры
и начальное состояние определяются из
дополнительных условий.
,
то всегда будет ошибка оценки
и
можно использовать условие несмещенности
оценки
- симметричная положительно определенная
матрица.
примет вид:
для любого.
из
условия минимума критерия (5.65). Примем
для простоты выкладок, что
-
постоянная
единичная матрица, тогда
- корреляционная матрица ошибки оценивания
(матрица вторыхцентральных
моментов ошибок оценки компонент вектора
состояния
системы). Обозначим ее через
,
тогда
критерий оптимальности
есть сумма диагональных элементов этой
матрицы. В соответствие с условием
локальной оптимальности будем искать
оптимальное
значение матрицы
из
условия минимума производной
к
ритерия
по времени:
,
опуская для простоты время
:
,
для чего запишем уравнение Коши для
(5.67):
- весовая матричная функция. Тогда
.
:
и соответственно
транспонированные выражения для
в (5.73) получим:
:
будет
зависеть лишь последнее
слагаемое, причем оно представляет
собой положительно определенную
матрицу. Очевидно, что для минимизации
критерия (5.71) нужно выбрать
в
следующем виде:
.
,
однако
последняя должна быть положительно
определенной.
,
а уравнение Риккати (5.80) вырождается в
алгебраическое.При
этом процесс
и,
следовательно,
процесс
являются стационарными,
так что
.
необходимо воспользоваться производной
наблюдаемого сигнала
,
а корреляционная матрица
,
как и раньше, находится из матричного
уравнения
.
и
начальное состояние
будем
считать независимыми, обладающими
свойствами (5.28). Предполагается, что
состояние
в
любой момент времени
известно.
Будем искать управление
как
некоторую линейную функцию текущего
состояния
-матрицы
.
Оптимальную
матрицу
будем искать среди матриц, элементами
которых являются непрерывные функции
со значениями из открытой области.
(4.27)
преобразовать к виду
будет иметь вид
непосредственно следует, что матрица
является симметричной, т.е.
.
из условия минимума
(5.90). Для нахождения ее воспользуемся
условием (4.28). Дифференцируя (5.90) и
учитывая (5.92), получим
,
зависящие
от
:
искомую локально-оптимальную матрицу.
Введем в рассмотрение семейство матричных
функций сравнения
- произвольная
малая вариация матричной функции
из рассматриваемого класса.
,
вызванное вариацией матрицы
,
будет
иметь вид
и
предполагая, что матрица
не особая, из условия
получим уравнение для определения
оптимальной матрицы
действительно доставляет минимум
,
так как вторая вариация
.
Здесь.
поведение стохастической системы
зависит от возмущения
,
значение которого предсказать не
представляется возможным, и поэтому
управление целесообразно оставлять
таким же, как в детерминированном случае
при отсутствие этих возмущений.
на отрезке
.
оптимальную оценку состояния управляемой
системы, через
- ошибку оценивания.
удовлетворяет уравнению
определяется из уравнений (5.79), (5.80).
- фундаментальная матрица решений систем
(5.87).
на отрезке
.
Тогда для каждой реализации
процесса
управление
принимает конкретное значение, т.е.
управление является детерминированным
оператором от вектора наблюдений.
Поэтому
.
Для этого дифференцируя (5.100), получим
.
- заданные матрицы локального функционала,
а
- решение векторного уравнения (5.102) с
начальным условием (5.103).
и ошибка оценки
не коррелированны для всех,
функционал (5.96) можно представить в виде
не влияет ни
,
ни
,
то задача сводится к минимизациипри условиях (5.102), (5.103). При этом оценка
является полностью наблюдаемой.
можно рассматривать как эквивалентный
«белый шум» с корреляционной матрицей
.
Этот принцип гарантирует, что управление, выбранное на любом шаге, является не локально лучшим, а лучшим с точки зрения процесса в целом, так как это управление выбирается с учетом последствий на предстоящих шагах.
Пусть многошаговый процесс принятия решений разбивается на n
шагов. Обозначим через ε 0 – начальное состояние системы, через ε 1 , ε 2 , … ε n
– состояния системы после первого, второго, n
-го шага. В общем случае состояние
ε k
– вектор (ε k
1 , …, ε k s
).
Управлением
в многошаговом процессе называется совокупность решений (управляющих переменных) u k
= (u k
1 , ..., u k r
), принимаемых на каждом шаге k
и переводящих систему из состояния ε k
-1 = (ε k-
1 1 , …, ε k
-1 s
) в состояние ε k
= (ε k
1 , …, ε k s
).
В экономических процессах управление заключается в распределении и перераспределении средств на каждом этапе. Например, выпуск продукции любым предприятием – управляемый процесс, так как он определяется изменением состава оборудования, объемом поставок сырья, величиной финансирования и т. д. Совокупность решений, принимаемых в начале года, планируемого периода, по обеспечению предприятия сырьем, замене оборудования, размерам финансирования и т. д. является управлением. Казалось бы, для получения максимального объема выпускаемой продукции проще всего вложить максимально возможное количество средств и использовать на полную мощность оборудование. Но это привело бы к быстрому изнашиванию оборудования и, как следствие, к уменьшению выпуска продукции. Следовательно, выпуск продукции надо спланировать так, чтобы избежать нежелательных эффектов. Необходимо предусмотреть мероприятия, обеспечивающие пополнение оборудования по мере изнашивания, т. е. по периодам времени. Последнее хотя и приводит к уменьшению первоначального объема выпускаемой продукции, но обеспечивает в дальнейшем возможность расширения производства. Таким образом, экономический процесс выпуска продукции можно считать состоящим из нескольких этапов (шагов), на каждом из которых осуществляется влияние на его развитие.
Началом этапа (шага) управляемого процесса считается момент принятия решения (о величине капитальных вложений, о замене оборудования определенного вида и т. д.). Под этапом обычно понимают хозяйственный год.
Обычно на управление на каждом шаге u k
накладываются некоторые ограничения. Управления, удовлетворяющие этим ограничениям, называются допустимыми.
Предполагая, что показатель эффективности k
-го шага процесса зависит от начального состояния на этом шаге k
-1 и от управления на этом шаге u k
, получим целевую функцию всего многошагового процесса в виде:
.
Управление, при котором достигается максимум (минимум) функции F
называется оптимальным управлением
u
* = (u
1* ,…, u n
*).
Если переменные управления u k
принимают дискретные значения, то модель ДП называется дискретной
. Если переменные u k
изменяются непрерывно, то модель ДП называется непрерывной
.
В зависимости от числа параметров состояния s
и числа управляющих переменных r
различают одномерные
и многомерные
задачи ДП.
Число шагов в задаче может быть конечным
или бесконечным
.Прикладные задачи динамического программирования
История
Идея динамического программирования
Классические задачи динамического программирования
Литература
Ссылки
Смотреть что такое "Динамическое программирование" в других словарях: