Вероятностное динамическое программирование. Марковские процессы принятия решений

Лекция 12. Вероятностное динамическое программирование. Марковские процессы принятия решений 

    В задачах вероятностного динамического программирования (ВДП) состояния и значения выигрышей при переходах системы из одного состояния в другое являются случайными. Модели ВДП составляют основу теории марковских процессов принятия решений.

    Эволюция  многих экономических и технических систем описывается с помощью марковских случайных процессов.

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

    Средний ожидаемый доход за один переход из состояния равен

                      

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

    Определение оптимальной стратегии проведем на простом примере.

    Агропромышленная фирма производит и реализует некоторый продукт. Каждый год в начале сезона проводится химический анализ почвы и, в зависимости от его результатов, продуктивность поля на новый сезон оценивается как хорошая (1), удовлетворительная (2) или плохая (3).

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

    Пусть матрица переходов имеет вид: 
 

                  Состояние системы в следующем году

         

                      1       2         3    

Состояние системы в текущем году   

    Видно, что если состояние почвы в текущем году удовлетворительное (состояние 2), то в следующем году оно может остаться удовлетворительным с вероятностью 0,5 или стать плохим  (состояние 3) с той же вероятностью.

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

         1       2         3    

       

    С переходом из одного состояния в  другое связывается функция дохода, которая определяет прибыль или убыток за один год. Ее величина зависит от выбора решения (стратегии) (использовать удобрения или нет).

    Функции дохода (в тысячах денежных единиц) определяются матрицами и , соответствующими матрицам переходных вероятностей и :

                     1    2     3    

       

                1     2     3    

    

    Элементы  матрицы  учитывают затраты, связанные с применением удобрений. Например, если система находится в состоянии 1 и остается в этом состоянии и в следующем году, то доход  , если же удобрения не используются, то .

    В методе ВДП  рассматриваются задачи с конечным или бесконечным числом этапов.

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

    Модель  вероятностного динамического  программирования

      с конечным числом этапов 

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

    Пусть обозначает две возможные (альтернативные) стратегии поведения фирмы. Будем использовать матрицы переходных вероятностей и функций дохода   , заданные формулами (1)-(4).

    Задачу  ВДП можно сформулировать следующим образом. Пусть число состояний для каждого этапа (года) равно m (в нашей задаче m  =  3).

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

    Обратное рекуррентное соотношение, связывающее , имеет вид:

    

причем

              

Уравнение (5) учитывает то, что накапливающийся доход образуется в результате перехода из состояния на этапе n +1  с вероятностью .  Введя обозначение

                      

рекуррентное  уравнение ВДП можно записать в виде: 

В нашей задаче, например, в случае, когда удобрения не используются (k = 1), получим

       

    Таким образом, если состояние почвы в начале года оказывается хорошим, то при одном переходе ожидаемый годовой доход составляет 5,3, при удовлетворительном 3, и при плохом  - 1 (убыток).

    Рассмотрим задачу о стратегии агрофирмы с горизонтом планирования 3 года (N = 3) и матрицами (1)-(4).

    Полученные  рекуррентным способом значения параметров задачи сведены в таблицы, представленные ниже.

    Таблица 1. Выигрыш для каждого этапа

 

    Этап 3.

 

    Этап 2.

 

Этап 1.

 

    Оптимальное решение показывает, что в 1-й и 2-й годы агрофирма должна применять удобрения ( ) независимо от состояния почвы. На третий год следует применять удобрения только тогда, когда система находится в состояниях 2 или 3 (т.е. при удовлетворительном или плохом состояниях почвы). Суммарный ожидаемый доход за три года составит при хорошем состоянии системы в первый год, - при удовлетворительном состоянии системы в первый год и при плохом состоянии. 

      Рассмотрим  второй вариант ВДП – модель с бесконечным числом этапов. 

    Модель  вероятностного динамического  программирования

    с бесконечным числом этапов 

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

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

    Шаг 1. Вычисляется - ожидаемый доход, получаемый за один этап при стратегии s для заданного состояния . 

    Шаг 2. Вычисляются стационарные вероятности для матрицы переходных вероятностей , соответствующие стратегии s . Эти вероятности находятся из уравнений

                

где . 

    Шаг 3. Вычисляется ожидаемый доход за один шаг (этап) при выбранной стратегии s:

                        

    Шаг 4. Оптимальная стратегия определяется из условия 

                      

    Проиллюстрируем этот алгоритм на нашем примере в случае бесконечного горизонта планирования.

    В этой задаче имеется восемь стационарных стратегий