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

Uj=1 – используем рекламу, =0 – нет.

F*j(xi) – полный ожидаемый максимальный результат за период j, j+1….n, если к началу j-ого этапа система находилась в состоянии xi.

F^*_j(x_i)=max_u=1,0

V_i^u-ожидаемый одношаговый результат, если система находится в состоянии x_i.

F^*_j(x_i)=max_u=1,0

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

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

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

3.Записанное рекуррентное уравнение можно использовать и для оценки произвольной стационарной оценки с номером q.

 

20.Марковские процессы принятия решений с бесконечным числом этапов: специфика постановки задачи. Отыскание оптимальных стратегий на бесконечном временном горизонте методом полного перебора.

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

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

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

Метод полного перебора

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

Q – стац стратегии

P^q,R^q – матрицы переходных вероятностей и результатов.

Действие алгоритма сводится к 4 шагам:

1) По заданным матрицам Pq и Rq находят средний ожидаемый доход за один этап для каждого i-ого состояния системы.

V_i^q=

2) По данной матрице находим финальные состояния системы из матричного уравнения системы P^{q q}= ^q, ^q=( ^q_{1, 2}^q….)

3) находят ожидаемый выигрыш за i – этап: E^q. После выполнения этого алгоритма для всех стационарных стратегий получают набор Е¹, Е², …, Е^q ожидаемых результатов, из которых и выбирается оптимум.

4) Сопоставляем оценки, выбираем