Вероятностное динамическое программирование и марковские процессы принятия решений
В задачах вероятностного динамического программирования (ВДП) состояния и значения выигрышей при переходах системы из одного состояния в другое являются случайными. Модели ВДП составляют основу теории марковских процессов принятия решений.
Эволюция многих экономических и технических систем описывается с помощью марковских случайных процессов.
При анализе т.н. марковских процессов с доходами учитывается множество стратегий, которым соответствуют некоторые вероятности переходов 
и значения доходов за один переход (этап) 
.
Средний ожидаемый доход за один переход из состояния 
равен
Целью использования ВДП является нахождение оптимальной стратегии, максимизирующей ожидаемый доход от всего процесса.
Определение оптимальной стратегии проведем на простом примере.
Агропромышленная фирма производит и реализует некоторый продукт. Каждый год в начале сезона проводится химический анализ почвы и, в зависимости от его результатов, продуктивность поля на новый сезон оценивается как хорошая (1), удовлетворительная (2) или плохая (3).
Будем считать, что продуктивность в текущем году зависит только от состояния почвы в предыдущем году. В этом случае переходы системы из одного состояния в другое можно представить как Марковский процесс.
Пусть матрица переходов имеет вид:
Состояние системы в следующем году
1 2 3
Состояние системы в текущем году 
Видно, что если состояние почвы в текущем году удовлетворительное (состояние 2), то в следующем году оно может остаться удовлетворительным с вероятностью 0,5 или стать плохим (состояние 3) с той же вероятностью.
В результате агротехнических мероприятий (например, удобрения почвы) можно изменить переходные вероятности. Пусть это приведет к новой матрице переходных вероятностей 
:
1 2 3
С переходом из одного состояния в другое связывается функция дохода, которая определяет прибыль или убыток за один год. Ее величина зависит от выбора решения (стратегии) (использовать удобрения или нет).
Функции дохода (в тысячах денежных единиц) определяются матрицами 
и 
, соответствующими матрицам переходных вероятностей 
и :
1 2 3
1 2 3
Элементы матрицы 
учитывают затраты, связанные с применением удобрений. Например, если система находится в состоянии 1 и остается в этом состоянии и в следующем году, то доход 
, если же удобрения не используются, то 
.
В методе ВДП рассматриваются задачи с конечным или бесконечным числом этапов.
Может ставиться также задача оценки ожидаемого дохода при заранее определенной стратегии поведения в случае того или иного состояния системы. В нашем случае ЛПР может принять решение всегда применять удобрения, если состояние почвы плохое. В таком случае говорят, что процесс принятия решений описывается стационарной стратегией.
Рассмотрим сначала алгоритм решения задачи выбора оптимального управления для случая конечного числа этапов.