Управляемые цепи Маркова. Выбор стратегии

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

В рассмотренной ситуации имеет место управляемая цепь Мар­кова. Управление соответствует выбору стратегии.

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

Пусть в i-м состоянии имеется не одно, а множеств пере­ходных вероятностей . При имеем случай неуправляемой цепи Маркова. Если система находится в состоянии и принимается ре­шение то

- она получает доход ;

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

Таким образом, смысл -го решения в i-м состоянии заклю­чается в выборе одного набора переходных вероятностей из возможных. Предполагается, что доход ограничен при всех и .

Кроме того,

, при всех и .

Управляемой цепью Маркова называется конструкция, зада­ваемая параметрами , где К- решения, Р -вероятности переходов, r -доходы. Доход, полученный за несколько шагов, является случайной величиной, зависящей от начального состоя­ния и принимаемых в каждый момент времени решений.

Назовем решение, принимаемое в конкретный момент, частным управлением. Тогда управление есть последовательность решений в моменты n = 1, 2,... Качество управления можно оценить сред­ним суммарным доходом (при конечном времени) или среднем дохо­дом в единицу времени (при бесконечном времени).

Пусть (2)

Стратегией называется последовательность решений

где - вектор вида (2), i-я компонента которого, обозначаемая через , является решением, принимаемым в состоянии в момент п. Другими словами, задание стратегии означает пол­ное описание в каждый момент времени t =1, 2,..., п,... конкретных решений, которые должны были бы приниматься в i-м состоянии, если бы система находилась в нем в рассматриваемый момент.

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

Обозначим произвольную конечную часть стратегии через . Пусть зафиксированы произвольная стратегия некоторый момент времени п. Если в этот момент система находилась в состоянии , то в следующий (п+1)- й момент времени она будет находиться в состоянии с вероятностью , где . Тогда матрица переходных ве­роятностей в момент п имеет вид

Таким образом, при фиксированной стратегии получаем цепь Маркова с матрицами перехода

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

≥ при любых

называется оптимальной

Верны следующее утверждения:

Утверждение 1. Для бесконечного времени существует опти­мальная стационарная стратегия.

Утверждение 2. Для конечного времени существует оп­тимальная марковская стратегия.

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

Контрольные вопросы:

1. Сформулируйте теорему о предельных вероятностях.

2. В каких областях могут применяться цепи Маркова?

3. Приведите пример использования управляемых цепей Маркова.

Литература:

1. Высшая математика для экономистов: Учебник для вузов / Н.Ш. Кремер, Б.А. Путко, И.М. Тришин, М.Н.Фридман. Под ред. Н.Ш. Кремера. – М.: ЮНИТИ, 2005. – 471 с.

2. Общий курс высшей математики для экономистов: Учебник. / Под ред. В.И. Ермакова. –М.: ИНФРА-М, 2006. – 655 с.

3. Сборник задач по высшей математике для экономистов: Учебное пособие / Под ред.В.И. Ермакова. М.: ИНФРА-М, 2006. – 574 с.

4. Данко П.Е., Попов А.Г., Кожевникова Т.Я. Высшая математика в упражнениях и задачах. Ч. 1, 2. – М.: Оникс 21 век: Мир и образование, 2005. – 304 с. Ч. 1; – 416 с. Ч. 2.

5. Математика в экономике: Учебник: В 2-х ч. / А.С. Солодовников, В.А. Бабайцев, А.В. Браилов, И.Г. Шандара. – М.: Финансы и статистика, 2006.

6. Шипачев В.С. Высшая математика: Учебник для студ. вузов – М.: Высшая школа, 2007. – 479 с.