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

Пусть некоторая система в любой фиксированный момент t может находиться в одном из n состояний и перейти из этого состояния в любое другое. Пусть вероятность P_t(i,j) перехода в момент t из i-го состояния в j-е не зависит от предыстории системы. Такая система называется Марковской.

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

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

Мы будем рассматривать задачу с конечным плановым периодом.

Задача о садовнике.

Некто берет в аренду земельный участок на n лет и собирается использовать его для выращивания сельскохозяйственных культур. Состояние почвы может быть хорошим (Х), удовлетворительным (У) и плохим (П). Состояние почвы может меняться. Нужно принимать решения о внесении удобрений.

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

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

Аналогичными матрицами описывается состояние почвы и дохода при решении вносить удобрения:

Рассмотрим теперь общий подход к решению подобных задач.

Имеем систему с множеством состояний и множество управлений будем описывать их просто индексами . Рассматривается управление системой на шагах (шаги: ).

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

Нарисуем схему данной задачи:

Рассмотрим последний шаг. При переходе по дуге 4 выигрыш равен и зависит от управления. При переходе по дуге 5: , по дуге 6: . Располагая только информацией, что в начале – го шага мы находимся в – м состоянии, и мы знаем, с какой вероятностью можем попасть, в результате шага, в любое другое состояние, взвесим полученные возможные доходы от применяемого управления по вероятности:

эту величину и будем рассматривать в качестве дохода.

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

Решим задачу методом динамического программирования:

Обратная прогонка:

N-й шаг:

…………………………………………………………………………..

n-й шаг:

…………………………………………………………………………..

1-й шаг:

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

Возможности усложнения:

· ­ матрицы переходов состояний и доходов меняются в зависимости от шага: ;

· учитывается влияние инфляции: – коэффициент инфляции, – коэффициент дисконтирования, тогда: ;

· , при бесконечном плановом периоде нужно ориентироваться на средние доходы по каким-то интервалам.