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

Министерство образования Саратовской области

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

Работа

Ученицы 11 «Б» класса

МОУ «Лицея № 15»

Шаймановой Юлии

Научный руководитель:

Копова Ольга Васильевна

Саратов  2012

Содержание.

Введение…………………………………………………………………………..3

1. Общая постановка задачи динамического программирования…………….4
2. Общая формульная запись решения задачи оптимального управления      методом динамического программирования………………………………..8
3. Стохастические задачи динамического программирования………………14
4. Задача инвестирования………………………………………………..……..18

Заключение……………………………………………………….………………20

Список литературы……………………………….……………………………...21

Введение.

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

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

Общеизвестно пристальное внимание, уделяемое современной наукой вопросам планирования во всех областях человеческой деятельности.

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

Для проведения этой работы был изучен следующий теоретический материал:

1. Вентцель Е.С. Элементы динамического программирования; изд-во Наука, 1964г., 176с
2. Таха Х. Введение в исследование операций; 7 изд., пер. с англ., М.: Издат. дом «Вильямс», 2005г., 912с.
3. Беллман Р. Динамическое программирование. М.: Изд-во иностр. лит., 1960г, 400 с.
4. Хедли Дж. Нелинейное и динамическое программирование, пер. с англ., М., 1967г.

В этой литературе рассматривается метод динамического программирования.

В 1 главе сформулирована общая постановка задачи динамического программирования и этой задаче дана геометрическая интерпретация, поставив ее как задачу управления движением точки в фазовом пространстве.

Во 2 главе рассмотрена запись в общем виде не только постановки, но и решения задачи динамического программирования.

В 3 главе рассмотрена запись постановки и решения стохастической задачи динамического программирования в общем виде.

В 4 главе рассмотрена и решена с помощью методов динамического программирования задача инвестирования.

1. Общая постановка задачи динамического программирования.

Интерпретация управления в фазовом пространстве

Самая общая задача оптимального (наилучшего) планирования ставится следующим образом.

Пусть предполагается к осуществлению некоторое мероприятие или серия мероприятий (короче, «операция»), преследующая определенную цель. Спрашивается: как нужно организовать (спланировать) операцию для того, чтобы она была наиболее эффективной, т. е. наилучшим образом удовлетворяла поставленным перед ней требованиям?

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

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

Вообще критерий эффективности в каждом конкретном случае выбирается исходя из целевой направленности операции и задачи исследования (какой элемент управления оптимизируется и для чего).

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

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

Рассмотрим следующую общую задачу.

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

С процессом изменения состояния системы S связана какая-то наша заинтересованность, выражающаяся численно с помощью критерия W, и нужно организовать процесс так, чтобы этот критерий обратился в максимум (минимум).

Обозначим наше управление (т. е. всю систему мероприятий, с помощью которой мы влияем на состояние системы S) одной буквой U. Критерий W зависит от этого управления; эту зависимость мы запишем в виде формулы:

W=W(U)                                                               (1.1)

Требуется найти такое управление U («оптимальное управление»), при котором критерий W достигает максимума:

W*=max{W(U)}                                                     (1.2)

                                                U

Запись max читается: «максимум по U», а формула (1.2) означает:

есть максимальное из значений, которые принимает критерий W при всех возможных управлениях U.

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

С учетом начальных и конечных условий задача оптимального управления формулируется следующим образом: из множества возможных управлений U найти такое управление U*, которое переводит физическую систему S из начального состояния S0 в конечное Sкон так, чтобы некоторый критерий W(U) обращался в максимум.

Дадим процессу управления геометрическую интерпретацию. Для этого нам придется несколько расширить наши привычные геометрические представления и ввести понятие о так называемом «фазовом пространстве».

Состояние физической системы S, которой мы управляем, всегда можно описать с помощью того или другого количества численных параметров. Такими параметрами могут быть, например, координаты физического тела и его скорость; количество средств, вложенных в группу предприятий; численность группировки войск и т.д., Эти параметры мы будем называть фазовыми координатами системы, а состояние системы изображать в виде точки S’ с этими координатами в некотором условном фазовом пространстве. Изменение состояния системы S в процессе управления будет изображаться, как перемещение точки S в фазовом пространстве. Выбор управления U означает выбор определенной траектории точки S в фазовом пространстве, определенного закона движения,

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

Пусть, например, состояние системы S характеризуется только одним параметром — координатой x. Тогда изменение этой координаты будет изображаться перемещением точки S по оси Ох (или по определенному ее участку, если на координату x наложены какие-то ограничения). В данном случае фазовое пространство будет одномерным и представляет собой ось абсцисс Ох или ее участок, а управление интерпретируется законом движения точки S из исходного состояния S0 в конечное Sкон. (рис. 1.1).

 Рис. 1.1

Если состояние системы S характеризуется двумя параметрами x1 и x2 (например, абсцисса материальной точки и ее скорость), то фазовым пространством будет плоскость x1Ox2 или какая-то ее часть (если параметры x1 и x2 наложены ограничения), а управляемый процесс будет изображаться перемещением точки S из S0 в Sкон по определенной траектории на плоскости x1Ox2 (рис. 1.2).

Если состояние системы характеризуется тремя параметрами x1, x2, x3  (например, две координаты и скорость), то фазовым пространством будет обыкновенное трехмерное пространство или его часть, а управляемый процесс изобразится перемещением точки S по пространственной кривой (рис. 1.3)

                    Рис. 1.2                                       Рис. 1.3

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

x1, x2, …, xn

мы будем изображать его как точку S в n-мерном фазовом пространстве, а управление интерпретировать, как перемещение точки S из какой-то начальной области S0 в конечную Sкон по некоторой «траектории», по определенному закону.

Итак, сформулируем общую задачу оптимального управления в терминах фазового пространства:

Найти такое управление U* (оптимальное управление), под влиянием которого точка S фазового пространства переместится из начальной области S0 в конечную область Sкон так, что при этом критерий W обратится в максимум.

Поставленную общую задачу можно решать различными способами — далеко не только методом динамического программирования. Характерным для динамического программирования является определенный методический прием, а именно: процесс перемещения точки S из S0 в Sкон разделяется на ряд последовательных этапов (шагов) (рис. 3.4), и производится последовательная оптимизация каждого из них, начиная с последнего. На каждом этапе расчета     ищется     сначала условное оптимальное управление (при всевозможных предположениях о результатах предыдущего шага), а затем, после того как процесс оптимизации доведен до исходного состояния S0, снова проходится вся последовательность шагов, но уже с начала до конца, и на каждом шаге из множества условных оптимальных управлений выбирается одно.

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

В этом — все существо метода динамического программирования и все оправдание его применения на практике. Если такого упрощения процедуры оптимизации от разделения процесса на этапы не происходит, применение метода динамического программирования теряет свой смысл.

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

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

Если  критерий W обладает таким  свойством:

                                                             (2.1)

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

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

Дадим постановку и общую схему решения задач динамического программирования с аддитивным критерием.

Пусть имеется процесс управления физической системой S, расчлененный на m шагов (этапов). В нашем распоряжении на каждом (i-м) шаге имеется управление Ui посредством которого мы переводим систему из состояния Si-1, достигнутого в результате (i-1)-го шага, в новое состояние Si, которое зависит от Si-1, и выбранного нами управления Ui. Эту зависимость мы запишем так:

Si=Si(Si-1, Ui)                                                                     (2.2)

рассматривая  Si как функцию двух аргументов Si-1 и Ui.

Заметим, что для применения метода динамического программирования существенно, чтобы новое состояние Si зависело только от состояния Si-1 и управления на i-м шаге Ui и не зависело от того, каким образом система пришла в состояние Si-1. Если это оказывается не так, то следует «обогатить» понятие «состояния системы», введя в него те параметры из прошлого, от которых зависит будущее, т.е. увеличить число измерений фазового пространства.

Под влиянием управлений U1, U2, …, Um система переходит из начального состояния S0 в конечное Sкон. В результате всего процесса за m шагов получается «доход» или «выигрыш»

                                                           (2.3)

где wi(Si-1,Ui)– выигрыш на i-м шаге, зависящий, естественно, от предыдущего состояния системы Si-1 и выбранного управления Ui.

Задана область начальных состояний S0 и конечных состояний Sкон. Требуется выбрать начальное состояние S*0 и управления U*1, U*2, …, U*m на каждом шаге так, чтобы после m шагов система перешла в область Sкон и при этом выигрыш W обратился в максимум.

Опишем в общем виде процедуру применения метода динамического программирования к решению этой задачи.

Для этого нам понадобится ввести некоторые новые обозначения. Мы уже обозначили W – выигрыш за все время процесса; wi – выигрыш за i-й шаг. Поскольку процесс динамического программирования разворачивается с конца, нам придется внести специальное обозначение для выигрыша, приобретаемого за несколько последних шагов процесса.

Обозначим:

Wm – выигрыш за последний шаг,

Wm-1,m – выигрыш за два последних шага,

…

Wi,i+1, …, m – выигрыш за последние (m–i+1) шага, начиная с i-го и кончая m-м.

Очевидно,

Wm=wm,

Wm-1,m=wm-1+wm,

 …                                                                          (2.4)

Wi,i+1, …, m=wi+wi+1+…+wm

Как мы уже знаем, процесс оптимизации управления методом динамического программирования начинается с последнего (m-го) шага. Пусть после (m-1)-го шага система находится в состоянии Sm-1. Так как последний (m-й) шаг должен перевести систему в состояние Sm=Sкон, то в качестве Sm-1 можно брать не все в принципе возможные состояния системы, а только те, из которых за один шаг можно перейти в область Sкон.

Предположим, что состояние Sm-1 нам известно, и найдем при этом условии условное оптимальное управление на m-м шаге; обозначим его U*m(Sm-1). Это – то управление, которое, будучи примененным на m-м шаге, переводит систему в конечное состояние Sm, причем выигрыш на этом последнем шаге Wm достигает своего максимального значения:

W*m(Sm-1)={Wm(Sm-1, Um)}                                         (2.5)

Напомним смысл символической формулы Wm(Sm-1, Um) означает выигрыш вообще (не оптимальный) на последнем шаге; он зависит как от результата предыдущего шага Sm-1, так и от примененного на данном шаге управления Um. Из всех выигрышей Wm(Sm-1, Um) при разных управлениях Um выбирается тот выигрыш W*(Sm-1), который имеет максимальное значение; это и означает запись max. Заметим, что в качестве управлений Um мы должны брать только те, которые переводят систему из заданного состояния Sm-1 в состояние Sm, принадлежащее области Sкон.

Находя условное максимальное значение выигрыша W*m(Sm-1), мы тем самым находим и условное оптимальное управление U*m(Sm-1). Тот факт, что условный максимальный выигрыш W*m(Sm-1) достигается при условном оптимальном управлении U*m(Sm-1), мы запишем символически в виде

W*m(Sm-1)U*m(Sm-1)

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

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

Перейдем к оптимизации предпоследнего ((m-1)-го) шага. Сделаем снова предположение, что в результате (m-2)-го шага система пришла в состояние Sm-2. Пусть на (m-1)-м шаге мы применили управление Um-1. В результате этого управления мы на (m-1)-м шаге получим выигрыш, зависящий как от состояния системы, так и от примененного управления:

wm-1=wm-1(Sm-2; Um-1)                                                          (2.6)

а система перейдет в новое состояние Sm-1, тоже зависящее от предыдущего состояния и от управления:

Sm-1=Sm-1(Sm-2; Um-1)                                                           (2.7)

Но для любого результата (m-1)-го шага следующий, m-й шаг уже оптимизирован, и максимальный выигрыш на нем равен

W*m(Sm-1)=W*m(Sm-1(Sm-2, Um-1))                                          (2.8)

Введем в рассмотрение полный выигрыш на двух последних шагах при любом управлении на (m-1)-м шаге и оптимальном управлении на m-м шаге. Обозначим его W+m-1,m; знак «+» будет нам напоминать, что это выигрыш при неполностью оптимизированном управлении, в отличие от знака «*», которым мы обозначили выигрыш при полностью оптимизированном управлении. Выигрыш W+m-1,m, очевидно, зависит от предыдущего состояния системы Sm-2 и примененного на (m-1)-м шаге управления Um-1. Учитывая формулы (2.6) и (2.8), получим следующее выражение для W+m-1,m:

W+m-1,m (Sm-2, Um-1)=wm-1(Sm-2, Um-1)+ W*m(Sm-1(Sm-2, Um-1))              (2.9)

Нам нужно выбрать такое оптимальное условное управление на (m-1)-м шаге U*m-1(Sm-2), при котором величина (2.9) достигла бы максимума:

W*m-1,m (Sm-2)=max{ W+m-1,m(Sm-2, Um-1)}                                (2.10)

Так же, как и на предыдущем этапе оптимизации, в качестве состояний Sm-2 после (m-2) шагов нужно брать не все возможные состояния системы, а только те, из которых можно перейти в Sкон за два шага.

Таким образом, найден максимальный условный выигрыш на двух последних шагах и соответствующее ему оптимальное управление на (m-1)-м шаге:

W*m-1,m(Sm-2)U*m-1(Sm-2)

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

W*m-2,m-1,m(Sm-3)U*m-2(Sm-3)

W*m-3,m-2,m-1,m(Sm-4)U*m-3(Sm-4)

и т.д.

Если мы уже оптимизировали (i+1)-й шаг для любого исхода i-го, т.е. нашли

W*i+1, …, m(Si)U*i+1(Si),

то условная оптимизация i-го шага производится согласно общей формуле

W*i,i+1, …, m(Si-1)=max{W+ i,i+1, …, m(Si-1, Ui)}                                   (2.11)

где

W+i, i+1, …, m(Si-1, Ui)=wi(Si-1, Ui)+ W*i+1, …, m(Si(Si-1, Ui))       (2.12)

– выигрыш, достигаемый на последних шагах, начиная с i-го, при любом управлении на i-м шаге и оптимальном управлении на всех последующих; Si(Si-1, Ui) – то состояние, в которое переходит система из Si-1 под влиянием управления Ui.

Таким образом, определяется условный максимальный выигрыш на последних шагах, начиная с i-го, и соответствующее оптимальное условное управление на i-м шаге:

W*i, i+1, …, m(Si-1) U*i(Si-1)                                                  (2.13)

Применяя последовательно, шаг за шагом, описанную процедуру, мы дойдем, наконец, до первого шага:

W*1, …, m(S0) U*1(S0),                                                       (2.14)

где S0 – какое-то начальное состояние системы, принадлежащее к области S0 возможных начальных состояний.

Остается выбрать оптимальным образом начальное состояние системы S*0. Если начальное состояние S0 в точности задано (т.е. вся область S0 сводится к одной точке S0), то выбора нет. Если же точка S0 может свободно выбираться в пределах области S0, то нужно оптимизировать выбор начального состояния, т.е. найти абсолютный (уже не условный) максимальный выигрыш за все шаги:

W*1, …, m=max{W*1, …, m(S0)},                                               (2.15)

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

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

W*=W*1,2, …, m S*0                                                           (2.16)

Но построено ли уже оптимальное управление? Нет еще: ведь мы нашли на каждом шаге только условное оптимальное управление.

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

В качестве начального состояния системы берется S*0 (или просто S0, если начальное состояние жестко фиксировано). На первом шаге применяется оптимальное управление U*1

U*1=U*1(S*0)                                                                     (2.17)

После чего система переходит в новое состояние

S*1=S1(S*0, U*1)                                                                   (2.18)

Теперь нужно выбрать оптимальное управление на втором шаге. Мы уже оптимизировали его для любого результата первого шага, т.е. знаем U*2(S1); подставляя в него S*1, получим

U*2=U*2(S*1)                                                                   (2.19)

И так далее, пока не дойдем до оптимального управления на последнем шаге

U*m=U*m(S*m-1)                                                                (2.20)

и конечного состояния системы

S*m=S*кон=S*m(S*m-1, U*m)                                                  (2.21)

В результате всей этой процедуры находится, наконец, решение задачи: максимально возможный выигрыш W* и оптимальное управление U*, состоящее из оптимальных управлений на отдельных шагах (вектор оптимального управления)

U*=(U*1, U*2, …, U*m)                                                        (2.22)

Таким образом, в процессе динамического программирования последовательность этапов проходится дважды: первый раз — от конца к началу, в результате чего находится максимальное значение выигрыша W*, оптимальное начальное состояние процесса S*0 и условное оптимальное управление на каждом шаге; второй раз — от начала и концу, в результате чего находится оптимальное управление U*i на каждом шаге и конечное состояние системы при оптимальном управлении S*кон.

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

Эти трудности связаны, во-первых, с выбором группы параметров x1,x2,…, xn, характеризующих состояние физической системы S. Как уже было сказано, эти параметры нужно выбирать так, чтобы при заданном состоянии S(x1,x2, …, xn) системы S в любой момент ее следующее состояние S’(x1’,x2’, …, xn’), в которое она переходит под влиянием управления U, зависело только от прежнего состояния S и управления и не зависело от «предыстории» процесса, т. е. от того, когда, как и в результате каких управлений система пришла в состояние S. Если это оказывается не так, приходится те элементы прошлого, от которых зависит будущее, включать в совокупность параметров x1,x2, …, xn, характеризующих состояние системы в данный момент. А это приводит к увеличению числа измерений фазового пространства и, значит, к усложнению задачи.

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

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

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

На практике нередко встречаются такие задачи планирования, в которых заметную роль играют случайные факторы, влияющие как на состояние системы S, так и на выигрыш W. В таких задачах управляемый процесс не полностью определяется начальным состоянием So и выбранным управлением U, а в какой-то мере зависит от случая. Условимся такие задачи планирования называть «стохастическими» (вероятностными).

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

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

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

                                                               (3.1)

Где wi  – «выигрыш», приобретаемый на i–м этапе процесса.

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

Нам хотелось бы выбрать такое управление U, при котором выигрыш W обращался бы в максимум. Но очевидно, что сделать это мы не можем: при любом нашем управлении выигрыш W останется случайным. Однако мы можем выбрать такое управление, при котором среднее значение  случайного выигрыша W будет максимальным. Обозначим среднее значение (математическое ожидание) величины W буквой :

                                                     (3.2)

Учитывая формулу (15.1) и пользуясь свойством математического ожидания (математическое ожидание суммы случайных величин равно сумме их математических ожиданий), запишем в виде

                                                             (3.3)

где  – средний выигрыш на i-м этапе.

Таким образом, в стохастических задачах вместо самого критерия W, который случаен, рассматривается его среднее значение ; этот критерий тоже аддитивен.

Задача динамического        программирования сводится к следующему: выбрать такое оптимальное управление U*, состоящее из оптимальных управлений , , … на отдельных этапах, чтобы аддитивный критерий обратился в максимум.

Состояние системы Si после i-го шага не полностью определяется состоянием Si-1  и управлением Ui, а зависит еще и от случая. Состояние Si при заданных Si-1 и Ui является случайным, а от заданных Si-1 и Ui зависит только распределение вероятностей для разных вариантов состояния Si.

Выигрыш wi на i-м шаге тоже не полностью определяется предыдущим состоянием системы Si-1 и примененным управлением Ui, а представляет собой случайную величину. И от Si-1 и Ui зависит только распределение вероятностей между его возможными значениями. Но так как нас интересует не сам случайный выигрыш wi, а только его среднее значение на каждом шаге, эту случайную величину можно осреднить с учетом распределения вероятностей и ввести в рассмотрение условный средний выигрыш на i-м шаге при заданном состоянии Si-1 после (i – l)-го шага и определенном управлении на i-м шаге Ui:

                                                           (3.4)

Мы будем предполагать, что как распределение вероятностей для случайного состояния Si, так и условный средний выигрыш (3.4) зависят только от Si-1 и Ui и не зависят от «предыстории» процесса, т. е. от того, каким образом, когда и в результате какого управления система пришла в состояние Si-1.

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

В этом – коренная разница между детерминированной и стохастической задачами динамического программирования. В детерминированной задаче оптимальное управление является единственным и указывается заранее как жесткая программа действий. В стохастической задаче оптимальное управление является случайным и выбирается в ходе самого процесса в зависимости от случайно сложившейся ситуации. Это – управление с «обратной связью» от фактического состояния системы к управлению.

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

Условное оптимальное управление  на i-м шаге стохастического процесса – это такое управление, которое, будучи применено на i-м шаге, обращает в максимум условный средний выигрыш на всех последующих шагах: от i-го до m-го включительно. Этот максимум мы можем найти аналогично тому, как мы делали в детерминированной схеме, с той разницей, что вместо самого выигрыша, который случаен, рассматривается его среднее значение.

Процесс планирования, как всегда, разворачивается, начиная с последнего (m-го) шага. Фиксируется состояние системы Sm-1 после (m – l)-го шага, и при этом условии ищется то управление  которое обращает в максимум средний условный выигрыш на m-м шаге:

                                     (3.5)

Когда найдена зависимость  и  от Sm-1 оптимизация последнего шага закончена. В какое бы состояние Sm-1 случайно ни пришла система после m – 1 шагов, мы уже знаем, что нам делать дальше и какой максимальный средний выигрыш мы получим на последнем шаге.

Затем оптимизируется (m – 1)-й шаг. Здесь дело обстоит не так просто. Сначала зафиксируем состояние Sm-2 после m-2 шагов и найдем средний выигрыш на двух последних шагах при любом управлении Um-1 на (m – 1)-м шаге и при оптимальном управлении на последнем, которое нам уже известно. Чтобы найти этот средний выигрыш будем рассуждать следующим образом. При заданном Sm-1 и любом управлении Um-1 состояние Sm-1 будет случайным, но мы знаем для него распределение вероятностей, зависящее от Sm-2 и Um-1. Случайное состояние Sm-1 определяет собой максимальный средний условный выигрыш на m-м шаге ; осредним эту величину с учетом распределения вероятностей состояния Sm-1. Получим «дважды осредненный» максимальный условный выигрыш на m-м шаге, зависящий уже не от Sm-1 (по нему произведено второе осреднение), а от Sm-2 и Um-1. Обозначим этот выигрыш

                                             (3.6)

к нему нужно прибавить средний условный выигрыш на (m- 1)-м шаге при управлении и Um-1 на этом шаге:

получим

               (3.7)

Найдем то управление на (m – 1)-м шаге, при котором величина (15.10) обращается в макимум:

(3.8)

Обозначим это условное оптимальное управление . Taким образом, в результате оптимизации (m – 1)-го шага найдены условное оптимальное управление  и соответствующий ему максимальный средний условный выигрыш на двух последних шагах .

Аналогичным образом оптимизируется любой i-й шаг. Для каждого исхода i-го шага Si уже известен условный максимальный средний выигрыш на последующих шагах:

                                                                (3.9)

Так как состояние Si случайно и его распределение зависит от Si-1 и Ui, то можно случайный выигрыш (3.9) осреднить с учетом распределения вероятностей Si и получить «дважды осредненный» выигрыш

Сложив его со средним выигрышем на i-м шаге при любом управлении Ui, получим

                    (3.10)

Условное оптимальное управление на i-м шаге  найдется как то управление, при котором величина (3.11) достигает максимума:

(3.11)

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

                                                     (3.12)

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

                             (3.13)                  

все элементы которого, кроме первого, являются случайными и зависят от состояния системы. Соответствующий этому управлению максимальный средний выигрыш равен (3.12).

4. Задача инвестирования

Постановка задачи:

Некто планирует инвестировать C тыс. долл. через фондовую биржу в течение последующих n лет. Инвестиционный план состоит в покупке акций в начале года и продаже их в конце этого же года. Накопленные деньги затем могут быть снова инвестированы (все или часть) в начале следующего года. Степень риска инвестиции представлена тем, что прибыль имеет вероятностный характер. Изучение рынка свидетельствует о том, что прибыль от инвестиции зависит от m условий рынка (благоприятных или неблагоприятных). При этом условие i приводит к прибыли wi с вероятностью pi, i= 1,2,… m. Как следует инвестировать С тыс.долл. для наибольшего накопления к концу n лет?

Решение:

Обозначим

Si – сумма денежных средств, доступных для инвестирования в начале

        i-го года (S1=C)

Ui – сумма реальной инвестиции в начале i-го года (UiSi)

Пусть Wi – максимальная ожидаемая сумма поступления денежных средств за годы от i до n при условии, что в начале i-го года имеется сумма Si. Для k-го условия рынка имеем следующее:

Si=(Si–1–Ui–1)+(1+wk)Ui–1=Si–1+wkUi–1                                  (4.1)

Поскольку вероятность для k-го условия рынка равна pk, рекуррентное уравнение динамического программирования имеет следующий вид:

                         (4.2)

Где Wn+1(Sn+1)=Sn+1, так как после n-го года инвестиции нет. Отсюда следует, что

     (4.3)

Введя обозначение

                                                                     (4.4)

получаем

                 если                                      (4.5)

                                                                если                                                         

                                                                                   если

                                    если                   (4.6)

Теперь решим конкретную задачу.

Постановка задачи:

Пусть в предыдущей модели инвестирования объем инвестиции составляет C=10 000 долл. на 4-летний период. Существует 40% вероятность того, что вы удвоите деньги, 20% – останетесь при своих деньгах и 40% – потеряете весь объем инвестиции. Необходимо разработать оптимальную стратегию инвестирования.

Решение:

Используя принятые в модели обозначения, получаем следующее:

C=10000, n=4,m=3,

p1=0,4; p2=0,2; p3=0,4;

w1=2, w2=0,w3=–1

Этап 4:

Найдем среднюю прибыль (4.4):

                  =0,4*2+0,2*0+0,4*(–1)=0,4

Тогда W4(S4) равно (4.6):

                  W4(S4)=(1+0,4)S4 =1,4 S4

Этап 3:

Так как , то U3=S3:

Этап 2:

Так как , то U2=S2:

Этап 1:

Так как , то U1=S1:

Вывод:

Оптимальную инвестиционную политику можно сформулировать следующим образом. Так как , а следовательно Ui=Si для i=1, 2, 3, 4, то оптимальным решением является инвестирование всех наличных денежных средств в начале каждого года. Накопленные денежные средства к концу четырех лет составят 3,8416S1 =3,8416*10000=38416 долл.

Заключение

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

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

Список литературы.

1. Вентцель Е.С. Элементы динамического программирования; изд-во Наука, 1964, 176с
2. Таха Х. Введение в исследование операций; 7 изд., пер. с англ., М.: Издат. дом «Вильямс», 2005г., 912с.
3. Беллман Р. Динамическое программирование. М.: Изд-во иностр. лит., 1960. 400 с.
4. Хедли Дж. Нелинейное и динамическое программирование, пер. с англ., М., 1967.