Файл: Сирл, С. Матричная алгебра в экономике.pdf

4. М А Р К О В С К И Е Ц ЕП И С В О З Н А Г Р А Ж Д Е Н И Е М

До сих пор мы рассматривали лишь вероятность пребывания в раз­ личных состояниях в различные периоды времени. Теперь добавим информацию, касающуюся вознаграждения, или выплаты, которые могут быть получены при переходах. Пусть ri} — вознаграждение, соответствующее переходу из состояния i в состояние /'; его можно интерпретировать как вознаграждение непосредственно за переход, либо как вознаграждение за пребывание в состоянии i (либо в состоя­ нии /) в течение одного периода времени. Первая интерпретация соот­ ветствует, например, такому случаю, когда состояниями являются места города, а переходами — перевозки пассажиров такси; Гц будет тогда прибылью, входящей в плату за проезд из места i в место /. Вторая интерпретация соответствует, например, случаю, когда состоя­ ниями являются альтернативные состояния некоторой машины; r i} может быть, например, прибылью, полученной при пребывании в состоянии i за период времени, предшествовавший переходу.

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

Предположим, что система начинает функционировать с состояния i\ пусть Vi (я) — суммарное ожидаемое вознаграждение после я пере­

мы. Теперь предположим, что за первый переход система переходит в состояние /. Вознаграждение за этот переход равно гц. Кроме того, когда система достигла состояния /, ожидаемое вознаграждение после всех п переходов можно выразить как гц + Vj (п — 1), где слагаемое

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

213

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

где q' — [q1q2 ... q^-]. Из уравнения (9) видно, что qt является i-м диа­ гональным элементом матрицы PR' и, следовательно, q' есть векторстрока, состоящая из диагональных элементов матрицы P R '.

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

8 = i

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

где вектор х — Тлу n2...njV] представляет собой вектор стационарных вероятностей.

Пример. Предположим, что R есть матрица вознаграждений (в дол­ ларах) для примера с машиной, приведенного в начале главы:

лировки после перехода (либо наоборот), прибыль равна 1 доллару; наконец, если машина не отрегулирована ни до, ни после перехода, то

2 1 4

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

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

Стационарное ожидаемое вознаграждение g вычисляется из урав­

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

5.ОПТИМАЛЬНЫЕ СТРАТЕГИИ В МАРКОВСКИХ ЦЕПЯХ

Впредыдущем параграфе матрицу вознаграждений R мы брали

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

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

215

0,90 доллара, то важно ответить на такой вопрос: этому ли правилу

Общий подход к решению этой проблемы состоит в рассмотрении

Заметим, что верхний индекс (£) в данном случае указывает, что выбрано £-е решение; он не означает возведения в степень. Теперь под vt (я) мы будем подразумевать максимальное ожидаемое вознагражде­ ние за п переходов при условии, что система находится в настоящее время в состоянии i и в каждом из последующих периодов принимаются оптимальные решения. Теперь щ (п) можно записать в следующем виде:

Решение проблемы выбора решений происходит следующим обра­ зом. Вначале решают все уравнения (13) при я = 1, находя для каждого начального состояния i оптимальное решение, т. е. то значе­ ние £, которое максимизирует правую часть соответствующего из урав­ нений (13)1. Пусть вектор оптимальных решений для случая, когда должны пройти я периодов, обозначается

d (я) = Ыг (я) d2(n) ... dN (я)]'.

Тогда dt (я) есть оптимальное решение для случая, когда система на­ ходится в состоянии г и должно пройти я периодов. Решение уравне­ ний (13) получается непосредственно, поскольку v (0) = 0, и уравне­ ния преобразуются к виду:

Максимизирующее значение k может быть найдено полным перебором.

2 1 6

Как только уравнения (13) решены для каждого элемента v (1), оп­ тимальные решения записываются в виде вектораd(\), где i-й элемент di (1) есть целое число в диапазоне от 1 до К, которое максимизирует ожидаемое вознаграждение за один переход при условии, что система

мое число периодов. Затем рассматривают множество векторов опти­ мальных решений {d (n), d (п —■1), ..., d (1)}, задающее оптимальную стратегию. Оптимальная стратегия используется следующим обра­ зом: если должно пройти п периодов и система находится в состоянии г, то применяют решение k = di (/г). Затем после перехода система по­ падает в некоторое новое состояние (назовем его /'). Теперь остался (п — 1) период, и оптимальное решение есть k = dj (п — 1). Подоб­ ным образом векторы оптимальных решений позволяют нам принимать оптимальные решения безотносительно к тому, в какие состояния пе­ реходит система; как уже упоминалось, для случая, когда система, начинает с состояния i, максимальное ожидаемое вознаграждение за п периодов задается величиной vt (п).

Пример. В нашем примере с машиной положим в качестве решаю­ щего правила для k — 1 правило «не делать ничего», а для k = 2 — правило «всегда ремонтировать машину, если она этого требует». Пусть стоимость ремонта равна 0,90 доллара. При действии по пра­

При действии по правилу 2 (всегда ремонтировать машину, если она этого требует) матрицы Р и R будут такими:

Мы видим, что в этих матрицах зафиксированы безусловный пе­ реход из состояния 2 в состояние 1 и стоимость ремонта (0,90 долла­ ра), связанного с этим переходом.

Зная Р(к) и R W , мы можем получить q(k\ воспользовавшись урав­ нениями (9):

2 1 7