Введение

Рассмотрим задачу об обслуживании машины. Машина может обслуживаться периодически, скажем, раз в час. В каждый момент существуют два состояния. Одно — рабочее (состояние 1), а другое — отказовое (состояние 2). Если машина отказывает, то она может быть восстановлена до состояния полной работоспособности. В любой период времени, когда машина работает, мы получаем доход 3 доллара за период. При этом вероятность остаться на следующем шаге в состоянии 1 равна 0,7, а вероятность перейти в состояние 2 равна 0,3. Если машина находится в отказовом состоянии, то ее можно отремонтировать двумя способами. Первый является ускоренным и требует затрат в 2 доллара (т. е. доход равен —2 долларам), при этом вероятность перехода в состояние 1 равна 0,6. Второй способ обычный, требует затрат в 1 доллар (т. е. доход равен — 1 доллару), и для него вероятность перехода в состояние 1 равна 0,4.

Рис. .1. Диаграммы переходов для задачи обслуживания машины. а) Ускоренный ремонт, б) Обычный ремонт.

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

Какую стратегию следует выбрать для максимизации суммарного среднего дохода при фиксированном начальном состоянии? Решение поставленного вопроса зависит от времени планирования.

Если оно конечно, то рассматриваемая задача (называемая задачей с конечным временем планирования) может быть непосредственно сведена к задаче динамического программирования (см. гл. 4), и оптимальная стратегия, являющаяся последовательностью решений, принимаемых в каждом состоянии, может быть найдена рекуррентным образом. Если же время планирования бесконечно, то нельзя применить ни метод динамического программирования, ни прямой перебор из-за бесконечного числа рассматриваемых стратегий. Более того, суммарный средний доход при этом не будет ограничен. Рассмотрим два подхода к решению задачи с бесконечным временем планирования. При одном из них вводится коэффициент переоценки. Задачи такого типа называются задачами с переоценкой. Если обозначить коэффициент переоценки, то единица дохода через время будет стоить всего единиц, и суммарный средний доход всегда конечен. Для задачи с переоценкой целевой функцией можно считать суммарный средний доход. В гл. 1 для решения таких задач предложены итерационный алгоритм и алгоритм линейного программирования. Кроме того, отмечена тесная взаимосвязь между указанными двумя подходами и приведены численные примеры. другом подходе рассматривается задача без переоценки. В этом случае, когда суммарный средний доход неограничен, целевой функцией можно считать средний доход за единицу времени в стационарном режиме.

Методы решения соответствующих задач приводятся в гл. 2, 3. Кроме того, в гл. 2 будет рассмотрен случай, когда суммарный средний доход в задаче без переоценки конечен.

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

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

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

Можно рассмотреть и другое обобщение — на случай дискретного времени и произвольных борелевских множеств состояний и решений. Такой процесс назовем обобщенным марковским процессом принятия решений. Для него будет изучаться только задача с переоценкой, для которой получены теоремы существования оптимальных планов (см. гл. 6).

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

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

После каждой главы приводятся комментарии и даются ссылки на литературу.