2.5. Марковские модели принятия решений.

Будем рассматривать задачу выбора не отдельного варианта, выбора управления: , где - множество управлений - отображение в пространство доходов; - бинарное отношение на множестве доходов.

Управление является оптимальным, если при всех

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

(2.35)

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

Одним из основных инструментов моделирования стохастических систем являются марковские цепи.

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

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

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

Пусть в -м состоянии имеется не одно, а множеств пере­ходных вероятностей

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

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

при (2.36)

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

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

Пусть

(2.37)

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

(2.38)

где - вектор вида 2.37.

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

Тогда матрица переходных вероятностей в момент п+1 имеет вид:

=

где решение, принимаемое в -м состоянии на шаге .

Пусть вектор доходов от принимаемых решений имеет вид:

(2.40)

где – доход в -м состоянии от принимаемого -го решения на шаге .

В общем же случае доходы могут быть заданы матрицей, если

они зависят не только от состояния, в котором находится система и от состояния, в которое она переходит.

Доход в момент времени n определяется вектором:

(2.4)

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

(2.42)

где – единичная матрица.

Стратегия , удовлетворяющая векторному неравенству

(2.43)

при всех называется оптимальной (для времени n). Пользуясь понятием отношения Парето, это неравенство можно записать в виде.

(2.44)