3.4. Алгоритм линейного программирования

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

Из соотношения (2.12) для любой получаем

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

Удобно расширить понятие решения и рассмотреть рандомизированные стратегии. Пусть означает

вероятность того, что в состоянии принимается решение Очевидно, что

Полагая

где

и используя равенство имеем

и

где — символ Кронекера. Из (1.3), (3.45) и (3.46) с очевидностью следует, что

Знак величины неизвестен, и ниже будет показано, что О для любого невозвратного состояния.

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

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

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

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

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

Лемма 3.6. Для любого и произвольного состояния из ограничения (3.55) принимают вид

Доказательство. Используя пункт леммы 2.3, просуммируем ограничения (3.55) по множеству

откуда следует (3.57).

Лемма 3.7. Для любого эргодического множества одно из ограничений (3.53), связанное с избыточно.

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

Леммы 3.6 и 3.7 дают необходимые ограничения для любого эргодического множества.

Лемма 3.8. Для любых ограничение (3.55) принимает вид

где

Доказательство. Из равенства получаем, что для любого Кроме того,

что соответствует (3.58). Далее, из соотношений

и (3.47) имеем

Так как у обращается в нуль для любого эргодического состояния у, то в силу (3.59) можно считать, что для любого Пусть двойственными

переменными будут векторы Тогда двойственная задача к (3.52) — (3.55) записывается в виде

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

где элементы векторов соответственно.

Двойственные переменные и являются единственным решением уравнений

где в силу (2.7) одно из значений в каждом эргодическом множестве полагается равным нулю. Тогда является одним из решений системы (3.65), и разность между решением (3.4) и есть вектор с равными друг другу компонентами.

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

или

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

Выбрать произвольное определить ограничения для каждого состояния в соответствии с классификацией состояний (используя леммы 3.6-3.8).

Найти допустимое базисное решение, которое соответствует стратегии и двойственным переменным (симплекс-множителям). Используя симплекс-множители, получить симплексный критерий.

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

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

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

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

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

Следующая теорема очевидна, если рассмотреть итерационный алгоритм нахождения стратегий.

Теорема 3.7. Оптимальная стратегия не зависит от начального распределения а.

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

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

Таблица 3.1 (см. скан) Данные для примера с несколькими классами

Проиллюстрируем алгоритм линейного программирования и итерационный алгоритм на примере, предложенном Ховардом [63]. Данные для задачи сведены в табл. 3.1. Пусть начальная стратегия, — соответствующая марковская матрица, — вектор доходов. Тогда

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

стратегий опущены.

Двойственные переменные

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

Тогда

Двойственные переменные

Используя симплексный критерий, находим, что оптимальная стратегия, поскольку

Ссылки и комментарии

Итерационный алгоритм нахождения стратегий для общего марковского процесса принятия решений (с несколькими эргодическими классами) впервые был предложен Ховардом [63]. Блекуэлл [14] рассмотрел эту задачу строго и указал на существование -оптимальных стратегий. В дальнейшем Вейнот [111] предложил алгоритм нахождения -оптимальных стратегий. Результаты, приведенные в разделах 3.2 и 3.3, получены Блекуэллом [14] и Вейнотом [111]. Формулировка в виде задачи линейного программирования для процесса с несколькими эргодическими классами дана Осаки и Майном [96]. Исследованию алгоритма линейного программирования для нахождения оптимальных стратегий в этом случае посвящена статья Питтеля [134].