5.4. Полумарковские процессы принятия решений с переоценкой

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

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

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

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

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

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

Пусть -мерный вектор суммарных средних доходов с учетом переоценки при произвольной стратегии и норме переоценки а

Определение 5.1. Стратегия называется -оптимальной если для любой стратегии .

Теорема 5.1. Существует стационарная -опти-мальная стратегия.

Доказательство этой теоремы, основанное на принципе сжатых отображений, принадлежит Денардо [31] и будет приведено в примере 4 раздела 7.5.

В силу теоремы 5.1 можно искать -оптимальные стратегии в классе стационарных стратегий, число которых конечно, и воспользоваться полученной ранее формулой (6.41).

Сформулируем теперь задачу линейного программирования применительно к полумарковским процессам принятия решений с переоценкой. Из (5.41) для любой стационарной стратегии имеем

Суммарный средний доход с учетом переоценки при начальном распределении а имеет вид

где

или

Для дальнейшего удобно расширить понятие решений и рассмотреть рандомизированные (или смешанные) стратегии.

Пусть вероятность того, что в состоянии принимается решение Эта вероятность не зависит от времени поскольку рассматриваются лишь стационарные стратегии. Ясно, что

Используя распределение получаем для произвольной стационарной стратегии следующее равенство:

где

Отметим, что величины зависят от так как элементы матрицы выражаются через Определим новые переменные

Используя перепишем (5.69) в виде

Выполняя несложные преобразования, получаем

Последнее равенство справедливо в силу (5.67). Следовательно,

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

при ограничениях

Эта задача аналогична рассмотренной в разделе 1.3.

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

Доказательство этой теоремы в точности совпадает с доказательством следствия теоремы 1.6.

Теорема 5.2 играет важную роль в обосновании итерационного алгоритма нахождения стратегий.

Рассмотрим теперь двойственную по отношению к (5.76) — (5.78) задачу. Она имеет смысл, поскольку ранг матрицы системы ограничений (5.77) равен (см. раздел 1.3). Эту задачу можно записать в виде

при ограничениях

свободны от ограничений, (5.81)

где двойственная переменная является координатой вектора доходов -оптимальная стратегия.

Табл. 5.1 изображает диаграмму Таккера для прямой и двойственной задач. Используя результаты раздела 1.4 и теорему 5.2, немедленно получаем итерационный алгоритм нахождения стратегий для полумарковского процесса с переоценкой. Заметим, что двойственные переменные (5.81) являются одновременно симплекс-множителями для прямой задачи.

Итерационный алгоритм нахождения стратегий состоит из двух последовательно выполняемых процедур.

Таблица 5.1 (см. скан) Диаграмма Танкера для полумарковского процесса принятия решений с переоценкой

Процедура определения весов. Выбирая произвольную стационарную стратегию решим уравнения

где индекс соответствует выбранной стратегии

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

Если пусто при всех 5, то стратегия оптимальна является вектором суммарных средних доходов с учетом переоценки.

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

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

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

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

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

Доказательство. Для двух стратегий имеем

Вычитая (5.82) из (5.83), получаем

Определим -мерный вектор у следующим образом:

В силу условия теоремы если непусто, и если пусто. Используя (5.85) и обозначая преобразуем выражение (5.84) к виду

Решая уравнение (5.85) относительно находим

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

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

то все они -оптимальны.