Прикладная математика
1 1 1 1 1 1 1 1 1 1 Рейтинг 0.00 (0 Голоса)

Марковские цепи с вознаграждением

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

Например:

1. Состояниями являются места города, а переходами – перевозки пассажиров такси; прибыль, входящая в плату за проезд из места в место .

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

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

.

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

(8)

Теперь запишем

, (9)

так что представляет ожидаемое вознаграждение за следующий переход при условии, что текущее состояние. Тогда

. (10)

В силу того, что уравнения (9) и (10) справедливы для , уравнение (10) может быть записано в векторной форме:

, (11)

где . Из уравнения (9) видно, что является м диагональным элементом матрицы и, следовательно, есть вектор-строка, состоящая из диагональных элементов матрицы .

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

или в векторной форме

, (12)

где вектор представляет собой вектор стационарных вероятностей.

ПРИМЕР: Предположим, что есть матрица вознаграждений (в денежных единицах) с компьютером:

.

Это означает, что в случаях, когда компьютер нормально работает до и после перехода, прибыль равна 2 ден. ед.; в тех случаях, когда он начинает работу в нормальном состоянии, но затем требует регулировки после перехода (либо наоборот), прибыль равна 1 ден. ед.; наконец, если компьютер неотрегулирован ни до, ни после перехода, то потери равны 1 ден. ед. Пусть, как это было задано ранее,

и

.

Тогда из (9) имеем

.

Следовательно, в уравнении (11)

,

где мы полагаем . Тогда

,

то есть если компьютер начинает с рабочего состояния, ожидаемая прибыль за один период времени равна 1,70 ден. ед.; если он начинает с состояния, требующего ремонта, ожидаемая прибыль равна 0,2 ден. ед.

Ожидаемая прибыль за два периода может быть вычислена подобным же образом с помощью формулы (11) при :

.

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

Стационарное ожидаемое вознаграждение вычисляется из уравнения (12):

.

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

Добавить комментарий


Защитный код
Обновить

Google