Способ вычисления матриц А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 ячеек.
Отсюда понятно, что вычислительная реализация метода динамического программирования сталкивается с большими трудностями. Эти трудности Р.Беллман назвал проклятием размерности. Для преодоления этих трудностей, приходится либо существенно пожертвовать точностью вычислений, либо отказаться от построения управления, оптимального в глобальном смысле, и ограничиться нахождением управлений и траекторий, оптимальном в глобальном смысле, то есть по отношению к малым (локальным) вариациям этих траекторий.
Вывод
Метод динамического программирования используется для исследования и решения задач оптимального управления процессами в условиях неопределенности. Если неопределенные факторы (внешние воздействия, возмущения, шумы) имеют случайную природу, то для описания процессов управления используется аппарат теории вероятности и случайных процессов. Если же неопределенные факторы связаны с активным противодействием противника или необходимо обеспечить гарантированный результат (застраховать от наихудших возможных реализаций неконтролируемых возмущений), то применяется аппарат теории игр. Метод динамического программирования используется также для построения оптимальных вычислительных алгоритмов поиска корней и экстремумов функций.
Задача оптимального управления с непрерывным временем, описываемым дифференциальными уравнениями. В этом случае метод динамического программирования приводит к нелинейному дифференциальному уравнению в частных произвольного первого порядка. Теория решений этого уравнения, иногда называемого уравнением Гамильтона-Якоби-Беллман-Айзекса, активно разрабатывается в последние годы.
Литература
1. Беллман Р. Динамическое программирование. .М.:Изд-во иностранная литература., 1960.
2. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования. M.: Наука, 1965.
3. Беллман Р., Калаба Р. Динамическое программирование и современная теория управления. М.: Наука, 1969.
4. Черноусько Ф.Л., Баничук Н.В. Вариационные задачи механики и управления: Численные методы. М.: Наука, 1973.
5. Элементы теории оптимальных систем. М.: Наука, 1975.
6. Черноусько Ф.Л., Меликян А.А. Игровые задачи управления поиском. М.: Наука, 1978.