Часть 4. Марковская задача принятия решений

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

1. Сформулировать задачу принятия решения в условиях риска с тремя альтернативами.

2. На основе данных задачи выбрать оптимальную альтернативу.

Описание алгоритма решения задачи

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

Рассмотрим матрицу переходных вероятностей:

		Состояние системы на следующем этапе
	Текущее состояние системы		x	y	z
Р¹=	x	0, 3	0, 6	0, 1
	y	0, 1	0, 5	0, 4
	z		0, 6	0, 4

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

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

		Состояние системы на следующем этапе
	Текущее состояние системы		x	y	z
Р²=	x	0, 1	0, 6	0, 3
	y	0, 05	0, 2	0, 75
	z	0, 1	0, 2	0, 7

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

В настоящем случае матрицы R¹ и R², соответствуют матрицам переходных вероятностей P¹ и P².

R¹=		x	y	z
x
y
z	-2	-1

R²=		x	y	z
x
y	-1
z	-2	-1

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

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

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

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

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

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

где для всех j.

k – альтернативы.

- вероятности перехода системы из i в j при альтернативе k.

- элемент матрицы доходов R при переходе системы из i в j при альтернативе k.

- доход, который был получен на этапе n+1, когда система была в состоянии j.

Приведенное уравнение основано на том, что накапливающийся доход получается в результате перехода из состояния i на этапе n в состояние j этапе n+1 с вероятностью . Введя обозначение

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

Для промежуточных значений функция состояния:

1 2 3 456