2.Общая постановка задачи динамического программирования. Принцип оптимальности Беллмана.

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

Положение , в которое может попасть процесс на k-ом шаге Тk - это одно из состояний Ski (i-номер состояния на данном шаге). Набор состояний  k = {Ski}, возможно , зависит от номера k шага Tk.

Из каждого или из некоторых положений Ski  k процесс может перейти под воздействием (управлением) в одно из состояний S(k+1)j набора  k+1 , состоящего из возможных состояний процесса на следующем, (k+1) - m шаге. В зависимости от выбора способа упраления uk на к-ом этапе , состояние S(k+1)j может оказаться различным. Набор возможных управлений на каждом этапе Tkь может зависеть и от того, в каком состоянии Ski находится процесс.

Таким образом, состояние S(k+1)j зависит от того,в каком состоянии Ski процесс находился на предыдущем этапе и какое управление мы применили к процессу на данном этапе:

S(k+1)j = Rk(Ski ; uk ),

где Rк - некоторая функция, зависящая от состояния и управления, примененного к этому состоянию.

Предположим, что величина f, характеризующая успешность завершенния процесса, равна сумме величин fk, зависящих от того, в каком состоянии Ski находился процесс на шаге Tk и какое было выбрано управление:

n-1

f(k) = fk (Ski ; uk); f =  fk (Ski ; uk)

k=0

Величину f =  fk (Ski ; uk) такого рода, каждое слагаемое fk зависит от состояния и управления на очередном этапе Так как называют аддитивным критерием процесса.

Целью исследования процесса является поиск такого набора управления u= (u0,u1, ... ,un-1), чтобы величина f приняла оптимальное (максимальное или минимальное ) значение при условии, что известно в каком состоянии S*0 находился процесс на начальном этапе Т0 и в какое состояние S*n он должен прийти на завершающем этапе. Эти состояния могут быть нежестко заданы, т.е. могут быть указаны подмножества, которым должны принадлежать состояния.

Замечание 1 Как в любых задачах математического программи-рования достаточно рассмотреть задачу минимизации аддитивного критерия f. Если исходная задача требует отыскания максимального значения f, то достаточно рассмотреть для тогоже процесса другой аддитивный критерий f = - f, который также является аддитивным.

n-1

f =  (- fk (Ski ; uk) )

k=0

При максимальном значении f = max критерия f значение f , очевидно, становится минимальным f min = min f для того же самого оптимального набора управлений.

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

f(u) min, uU, где U множество допустимых управлений u*=(u*0, u*1, ... , u*n-1), то есть таких наборов управлений, при которых процесс переходит из состояния S*0 на шаге T0 в состояние S*n на шаге Tn.

Набор управлений при котором функция принимает минимальное значение называется оптимальным управлением задачи.

Принцип оптимальности Беллмана

Основным принципом решения задач динамического програм-мирования служит принцип оптимальности Беллмана.

Рассмотрим задачу минимизации аддитивного критерия f. Общим принципом решения задач динамического программирования является рассмотрение и оптимизация процесса от конца ( этапа Тn-1 - последнего этапа, где выбирается управление) к началу (этапу Т0). Для каждого промежуточного состояния Ski этапа Так как отыщем такое управление u*k, для которого оказывается минимальной сумма.

n-1

f =  fj (Sij ; uj),

k=0

то есть сумма значений слагаемых аддитивного критерия f на последних этапах, начиная с к-го. Такое управление u*k называется условно оптимальным управлением, соответствующим состоянию Ski.

Пусть u*k - условно оптимальное управление, а f * (Ski)- cоответствующее ему минимальное значение функции f . Тогда для любого к=0,1, .... ,n-1

f * S(ki) = f k (Ski ; u*k)+ f * (Rk (Sik ; u*k))

= min [f k (Ski ; uk)* f ( Rk (Sik ; u*k) ) ]. (*)

Формула (*) называется принципом оптимальности Беллмана

Эта формула служит для отыскания на каждом этапе Tk для каждого состояния Ski значение функции f * S(ki), а также условно оптимального управления, если для следующего этапа значения для всех состояний уже известны. Управление u*k выбирают, отыскивая для всех возможных управлений uk значений суммы:

f k (Ski ; u*k)+ f * ();

и сравнивая их. Управление которое соответствует наименьшему значению суммы выбирается в качестве условно оптимального управления u*k Если минимальные значения получаются при нескольких различных управлениях, о все они условно оптимальны, т.е. uk не единственный.

Таким способом следует продвигаться от конечного этапа к начальному и когда достигается этап Т0 значения для всех состояний процесса на начальном этапе, в том числе и для начального S*0 . Значение даст минимально возможное значение аддитивного критерия f для всего процесса. Оптимальное управление u* получается, объединяя найденные условно оптимальные управления , соответствующие состояниям, в которые прцесс последовательно попадает, начиная с исходного состояния, если применять условно оптимальные управления на каждом шаге:

S*1=R0 (S*0, u*0), S*2=R1 (S*1, u*1), ... , S*3=R3 (S*3, u*3).

Таким образом задача динамического программирования является решенной.