Министерство образования и науки РФ
ГОУ ВПО «УГТУ-УПИ»
Курсовая работа
По дисциплине: теория информационных процессов и систем
На тему: комбинированные задачи использование динамического программирования для их решения.
Примеры решения задач предполагающих необходимость выбора оптимального варианта из очень большого количества возможных вариантов.
Семестр № 7.
Преподаватель:Александров О.Е.
Студентка гр.ДО 43010 да
г. Алапаевск
Запольских Алевтина Евгеньевна
Екатеринбург 2006
Динамическое программирование
Введение
Метод динамического программирования – широко известный и мощный математический метод теории управления, был предложен в конце 50-х годов американским математиком Р.Беллманом и быстро получил широкое распространение, чему способствовали ярко и доходчиво написанные книги самого Беллмана, которые были быстро переведены на русский язык и изданы у нас в стране . Вскоре стало ясно, что метод динамического программирования тесно связан с классическим методом Гамильтона-Якоби в аналитической механике (для систем с непрерывным временем) и с последовательным анализом Вальда ( для систем с дискретным временем). Однако весьма общая и отчетливая формулировка метода динамического программирования, дана Беллманом, а также многочисленные приложения метода к разнообразным проблемам теории принятия решения, экономики, экологии и других областей знания способствовали закреплению этого метода как одного из важнейших инструментов теории управляемых процессов.
Задача оптимального управления.
Пусть задан некоторый критерий качества процесса управления ( критерий оптимальности) вида
Здесь R (x,u) и F(x) – заданные скалярные функции своих аргументов, N – момент окончания процесса, N>0.При этом функция R может отражать расход средств или энергии на каждом шаге процесса, а функция F – характеризовать оценку конечного состояния системы или точность приведения в заданное состояние.
Задача оптимального управления формулируется как задача определения допустимых управлений u(0), u(1),-,u(N-1), удовлетворяющих ограничениям, и соответствующей траектории, то есть последовательности x(0),x(1),-,x(N), которые в совокупности доставляют минимальное значение.
Минимизация обычно отвечают выбору управления, обеспечивающего наименьшие затраты средств, ресурсов, энергии, наименьшее отклонение от заданной цели или заданной траектории процесса. Наряду с этим часто ставится также задача о максимизации критерия , например о максимизации дохода или объема производства. Однако нетрудно видеть, что максимизация критерия J эквивалентна минимизации критерия (-J). Поэтому простая замена знака у функции R и F приводит задачу о максимизации критерия к задаче о его максимизации.
Элементарный подход.
Элементарный подход к поставленной задаче оптимального управления, состояние системы в каждый последующий момент времени выражается через ее состояние и управления в предыдущий момент времени. Применяя это соотношение многократно, можно выразить состояние системы во все моменты времени только через начальное состояние x0 и управления в предшествующие моменты. В результате получаем:
J=R(x0,u(0))+R(f(x0,u(0)),u(1))+_=F(x0,u(0),u(1),_,u(N-1)).
Здесь F – некоторая громоздкая, но, вообще говоря , известная функция своих аргументов. Таким образом, поставленная задача оптимального управления свелась к задаче о минимизации функции F от векторов u(0),u(1),_,u(N-1), то есть от Nm переменных. При больших N (а обычно представляет интерес именно процессы с большими N) это задача о минимизации функции большого числа переменных .
Принцип оптимальности.
Сформулированный Р.Беллманом принцип оптимальности гласит: отрезок оптимального процесса от любой его точки до конца процесса сам является оптимальным процессом с началом в данной точке.
Принцип оптимальности легко доказывается от противного. Пусть x(t)=x* - некоторая точка оптимальной траектории, то есть состояние системы вдоль оптимального процесса в момент t, 0<t<<N. Рассуждая от противного, предположим, что отрезок этого процесса от момента времени t до момента N не является оптимальным процессом в смысле критерия качества при начальном условии x(t)=x*. Значит, существует допустимое управление и соответствующая ему траектория, для которых критерий Jt принимает наименьшее значение, чем на исходном оптимальном процессе. На ряду с исходным оптимальным процессом x(k), k=0,1,_,N, процесс состоящий из двух участков: исходного процесса x(k) при k= = 0,1,_,t и «улучшенного» процесса при k= =t+1, _,N. Для этого составного процесса критерий J будет иметь меньшее значение, чем для исходного процесса, так как сумма первых t слагаемых для составного процесса остается той же, что и для исходного процесса, а сумма остальных слагаемых, равна Jt , уменьшится по сравнению с исходным процессом. Данное утверждение означает, что исходный процесс не является оптимальным, а это противоречит сделанному предложению.
Таким образом, принцип оптимальности доказан. Столь простое доказательство наводит на мысль о тривиальности этого принципа. Однако это не так: принцип оптимальности является следствием аддитивности и не имеет места с случае неаддитивного критерия.
Метод динамического программирования.
В типичном случае динамическое программирование применяется к задачам оптимизации, которые не решаются простым перебором ( из-за временных ограничений или слишком большого объема необходимой памяти) жадными алгоритмами ( из-за того, что они не делают оптимального результата), а более простой путь решения если и существует, то его нахождение неочевидно. У таких задач может быть много быть много решений и в общем случае это определяет некий показатель ( назовем его качеством решения), и требуется выбрать оптимальное, при котором данный показатель становится либо минимумом либо максимумом ( или еще чем-то:) – в зависимости от условия задачи).
По своему принципу динамическое программирование напоминает метод разделяй и властвуй задача делится на подзадачи, которые либо являются очевидными, либо сводятся к своим подзадачам и т.д. Но есть и некоторые отличия например, таких подзадач относительно немного, что позволяет решит каждую только один раз.
Небольшое количество подзадач, многие из которых приходится решать много раз называется перекрытием подзадач и является характерным признаком динамического программирования.
Вторым характерным признаком излагаемого метода является оптимальность для подзадач. Задача обладает таким свойством, если оптимальное решение задачи содержит оптимальные решения ее подзадач.
Общий рецепт построения алгоритмов по принципу динамического программирования следующий:
Хорошо понять условие.
Найти такое разбиение задачи на две или более подзадач, чтобы оптимальное решение задачи содержало оптимальное решение всех подзадач, которые в нее входят.
Написать рекуррентное соотношение ( если мы разбиваем задачу на подзадачи, значит, можем выразить качество решения задачи либо через ее подзадачи, либо элементарным образом).
Вычислить оптимальное решение значение параметра для задачи. Тут возможно два варианта если задачу решаем рекурсивно, значит процедура делит заданную ей задачу на подзадачи ( предварительно выяснив, не является ли задача тривиальной и проверив, не решалась ли она ранее тогда нужно лишь взять уже готовое решение из соответствующего массива) и получив решение ставив флаг, что эта подзадача уже решена. Такое решение называется сверху вниз т.е. берем глобальную задачу, потом решаем только необходимые для нее подзадачи. Если же рекурсия невозможна по техническим или еще какам-нить причинам , то применяется такой подход: решаются сначала элементарные подзадачи, потом только те, которые требуют результатов уже решенных подзадач и т.д. , пока не будет решена общая задача. Такой метод называется решением снизу вверх в большинстве случаев он оказывается быстрее, но менее понятным и простым, хотя есть и исключения.
Если необходимо получить не только значения качества оптимального решения, но и найти само решение, то на шаге 3 нужно также запомнить некоторую дополнительную информацию о ходе решения решение каждой подзадачи. Этот шаг иногда еще называют обратным ходом.
Пример1.Перемножение матриц.
Задача о перемножении матриц формулируется следующим образом: дана последовательность из n матриц (А1,А2,Аn) заданных размеров (матрица I имеет размеры pi-1 x pi); требуется найти такую полную расстановку скобок в произведении А1А2А3Аn, чтобы количество умножений было минимально возможным (далее кол-во умножений еще называется стоимостью т.е. это именно тот параметр, который в данной задаче необходимо минимизировать).
Произведение матриц ассоциативно [A(BC)=(AB)C], то расстановка скобок не повлияет на результат, но может существенно повлиять на кол-во умножений. Для начала нужно убедиться в том, что полный перебор всех возможных вариантов не даст эффективного алгоритма: действительно, в каждой тройке матриц можно расставить скобки двумя вариантами, а значит в 3n матриц можно расставить скобки не мене, чем 2n вариантами, т.е. кол-во вариантов (а следовательно и время работы программы, перебирающей все варианты) экспоненциально зависят от n.
Шаг1. найти разбиение задачи на подзадачи.
Обозначим через Ai..j матрицу, являющуюся произведением матриц AiAi+1Aj. Последнее произведение матриц при оптимальной расстановке скобок в произведении А1А2Аn производится между матрицами А1..k и Ak+1…n. Иными словами ,при перемножении, диктуемом такой расстановкой скобок мы сначала вычисляем произведение А1..k, потом Ak+1…n и наконец, вычисляем их произведение. Значит стоимость этой оптимальной расстановки равна стоимости вычисления каждой из этих двух матриц плюс стоимость их перемножения.
Способ вычисления матриц А1..k и Ak+1…n не влияет на резуль
Шаг2. Написать рекуррентное соотношение.
Обозначим через m[i, j] минимальную стоимость вычисления матриц Ai..j. Тогда будет i=j, т.е...j=Ai и умножения вообще не нужны, следовательно стоимость равна 0.
Случай: i<k<j
Тогда: m[i, j]-m[i, j]+m[k+1,j]+p1-ip+pj
В этом равенстве подразумевается, что лучшее значение k нам известно. В действительности его еще нужно найти. Тут единственным вариантом является перебор всех значений k в промежутке от i до j-1. Т.е окончательно получаем:
0,если=j
M[i,j]= min (m[I,j]+m[k+1,j]+p1-p2+pj),если <j
Шаг3.Вычислить оптимального значение для всей задачи.
Пользуясь соотношением, полученным на шаге 2, легко написать рекурсивный алгоритм, вычисляющий оптимальное решение для всей задачи. Когда промежуточные значения m[i, j] вычислять лишь по одному разу и заносить в массив.
Рекурсивный алгоритм:
Код:
Function GetM(i, j: integer):longint;
Var k: integer
Res: longint;
begin
if m [i,j]-1 then {«-1»-ми изначально должен быть заполнен весь массив m, кроме главной диагонали, где 0, т.к. m[i, j]=0}
begin
GetM:=m[Ii,j];
Exit;
End;
Res: GetM(i+1,j);{для нахождения минимума изначально инициализируем первым возможным значением k=I [GetM(i,i)=0}
S[i,j]:=i;
For k:=i+1 to j-1 do
If res> GetM(i,k)= GetM(k+1,j)+ p[i-1]*p[k]*p[j] then
begin
res:= GetM(i,k)+ GetM(k+1,j)+ p[i-1]*p[k]*p[j];
s[I,j]:=k;
end;
GetM:=res;
m[Ii,j]:=res;
end;
Интеративный алгоритм:
Код:
…..
For i:=1 to n do m[i, j]=0; { тут можно и «0» - ми сразу заполнять, чтобы не трудиться проверять еще, главная это диагональ или нет}
For i:=2 to n do {кол-во сомножителей, которое расчитываем}
For i:=1 to n-1+1 do begin
J:=i+1-1;
m[i, j]=m[i+1,j]+ p[i-1]*p[i]*p[j];
S[i,j]:=i;
For k:=i+1 to j-1 do
If m[I,j] m[I,k] + m[k+1,j]+ p[i-1]*p[k]*p[j] then
begin
m [I,j] m[I,k] + m[k+1,j]+ p[i-1]*p[k]*p[j];
S[i,j]:=i;
end;
end;
…..
Шаг4.Построение оптимального решения.
Код:
Procedure PrintSolution(i,j:integer);
begin
if i=j tnen
write(A,i)
eise
begin
write(();
PrintSolution(s[i,j]+1,j);
write(();
end;
end;
Попятная процедура.
При вычислении минимума функции по некоторому аргументу обычно определяются две величины: значение минимума и значение аргумента, при котором минимум достигается. Это значение, которое может быть неединственным, обозначим словом arg min.
Положим t=N-1
Вычисляя этот минимум, найдем функцию S(x,N-1) и значение u, доставляющее данный минимум:
Запись uN-1(x) означает, что значение и зависит от х как от параметра. Определив S(x,N-1) и полагая t=N-2, найдем функцию S(x,N-2) и соответствующее значение аргумента u=uN-2(x). Продолжая этот процесс в сторону уменьшения t, получим последовательно функцию S(x,t) и при t=N-1,N-2,_,1,0. Отметим, что функция ut(x) определяет оптимальное управление в момент t при условии, что система находится в состоянии х. Эта форма задания управления называется управлением по обратной связи.
Прямая процедура.
Нужно воспользоваться результатами попятной процедуры для решения исходной задачи, то есть, для построения оптимального управления и оптимальной траектории.
Полагая t=0и x=x0, найдем управление в начальный момент: u(0)=u0(x0). Далее определим состояние x(1)=f(x0,u(0)).Продолжая этот процесс, найдем u(1)=u1(x(1)),x(2) . Вообще имеем
U(t)= ut(x(t)),X(t+1)=f(x(t),u(t)),
X(0)=x0,t=0,1,__,N-1.
Минимальное значение критерия оптимальности, отвечающей этой траектории, J=S(x0,0).
Пример.
Задача об оптимальном функционировании фермы по разведению скота и птиц. Пусть х - число животных( или птиц) на ферме в начале некоторого интервала времени. Из этого числа их животных отправляется на продажу, а остальные животные приносят приплод, так что их число возрастает в q раз за рассматриваемый интервал.
x(t+1)=q[1-u(t)x(t),t=0,1,_
Здесь q>1 – постоянный коэффициент,u – управляющее воздействие(доля животных, отправляемых на продажу). Ограничение в данном случае имеет вид 0 # u # 1.
Расходы на содержание животных прием пропорциональными их оставшемуся числу и равными a[1-u(t)x(t), где a>0 – постоянная .Выручку от продажи считаем равной cu(t)x(t), где с – цена одного животного на рынке. Поставим задачу максимизация дохода фермы за N шагов по времени. Эта задача эквивалентна минимизации убытка ( то есть дохода со знаком минус).
Критерий оптимальности: R(x,u)=a(1-u)x-cux, F(x)=-cx.
Последнее равенство определяет (со знаком минус) стоимость животных на ферме в конце процесса.
S(x,N)=-cx
Не сложный результат позволяет реализовать попятную процедуру и построить функции S(x,t) и соответствующие им управления ut.
Окончательные результаты:
S(x,t)=a(qN-1-1)(q-1)-1x-cqN-1x,
ut(x)=0 или a<c(q-1);
S(x,t)=-cx,ut(x)=1 при a>c(q-1)
Если a<c(q-1), то есть расходы на содержание животных сравнительно невелики, то имеет смысл не направлять животных на продажу ( ut(x)=0) и получить наибольший доход, сравнив все поголовье к концу процесса. Если же a>c(q-1), то есть расходы на содержание велики, то целесообразно отправить на продажу сразу всех животных. В случае a=c(q-1) оптимальное уравнение неединственно: в этом случае любое уравнение приводит к одному и тому же результату.
Более сложные и более содержательные результаты получим, если учтем запись рыночной цены с от числа продаваемых животных х ( цена убывает с ростом х), а также зависимость расходов на содержание одного животного а от числа животных на ферме.
Обсуждение.
Попятная и прямая процедура метода динамического программирования в совокупности дают способ решения поставленной задачи оптимального управления. Однако при реализации этого метода мы получилось более общий и универсальный результат. В попятной процедуры построено оптимальное управление по обратной связи, то есть управление как функция текущего состояния системы ut(x). Теперь нетрудно дать решение задачи оптимального управления при любом начальном условии вида x(t)=x*: для этого нужно просто реализовать прямую процедуру для этого начального условия. Реализация прямой процедуры не представляет серьезных трудностей и сводится, к вычислению известных функций при конкретных значениях аргументов.
Наибольшую сложность представляет попятная процедура, включающая минимизацию функций по m – мерному векторному аргументу u. Здесь нужно выполнить N процедуру минимизации функций от m переменных. Это, вообще говоря, значительно более простая задача, чем минимизация одной функции по Nm переменным, что требуется при элементарном подходе.
Однако есть серьезное осложнение. Дело в том, что попятная процедура предусматривает построение функций S(x,t) и ut(x), зависящих от n – мерного вектора x. По этому вектору x не нужно выполнять операции минимизации, но даже простое табулирование и хранение функций n переменных представляют большие трудности. Если, к примеру, составлять таблицы, придавая каждой переменной 100 значений, то для хранения таблицы одной функции n переменных понадобится 100n ячеек памяти. Всего же попятная процедура, в которой участвуют функции S(x,t) и ut(x), потребует (m+1)Ni i100n ячеек.
Отсюда понятно, что вычислительная реализация метода динамического программирования сталкивается с большими трудностями. Эти трудности Р.Беллман назвал проклятием размерности. Для преодоления этих трудностей, приходится либо существенно пожертвовать точностью вычислений, либо отказаться от построения управления, оптимального в глобальном смысле, и ограничиться нахождением управлений и траекторий, оптимальном в глобальном смысле, то есть по отношению к малым (локальным) вариациям этих траекторий.
Вывод
Метод динамического программирования используется для исследования и решения задач оптимального управления процессами в условиях неопределенности. Если неопределенные факторы (внешние воздействия, возмущения, шумы) имеют случайную природу, то для описания процессов управления используется аппарат теории вероятности и случайных процессов. Если же неопределенные факторы связаны с активным противодействием противника или необходимо обеспечить гарантированный результат (застраховать от наихудших возможных реализаций неконтролируемых возмущений), то применяется аппарат теории игр. Метод динамического программирования используется также для построения оптимальных вычислительных алгоритмов поиска корней и экстремумов функций.
Задача оптимального управления с непрерывным временем, описываемым дифференциальными уравнениями. В этом случае метод динамического программирования приводит к нелинейному дифференциальному уравнению в частных произвольного первого порядка. Теория решений этого уравнения, иногда называемого уравнением Гамильтона-Якоби-Беллман-Айзекса, активно разрабатывается в последние годы.
Литература
Беллман Р. Динамическое программирование. .М.:Изд-во иностранная литература., 1960.
Беллман Р., Дрейфус С. Прикладные задачи динамического программирования. M.: Наука, 1965.
Беллман Р., Калаба Р. Динамическое программирование и современная теория управления. М.: Наука, 1969.
Черноусько Ф.Л., Баничук Н.В. Вариационные задачи механики и управления: Численные методы. М.: Наука, 1973.
Элементы теории оптимальных систем. М.: Наука, 1975.
Черноусько Ф.Л., Меликян А.А. Игровые задачи управления поиском. М.: Наука, 1978.