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

Применение метода прямого перебора для анализа Марковской модели принятия решений при бесконечном количестве этапов.

При бесконечном количестве этапов мы предполагаем, что с течением времени система переходит в стационарный режим.

Для стационарного режима определены вероятности состояний при реализации U-й стратегии р_i(u).

При этом на основе матрицы решений D (Z) вычислены матрицы выигрышей для стационарных стратегий D (U). D (Z) >D (U).

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

— эта величина выигрыша при нахождении системы в i-том состоянии при реализации некой u-той стационарной стратегии.

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

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

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

Таким образом, для задачи полного перебора в исходные данные включены множеств общих стратегий z={1,2,…z…p} соответственно матрица переходных вероятностей R (z) и матрица стоимостей из состояния i в состояние j D (z).

Далее из общей стратегии справедливым условием, что z є Z.

Первый шаг алгоритма — в соответствии с общим числом стратегий p и общего числа состояний m формируется множество стационарных стратегий.

Делаем полный перебор всех ситуаций.

Второй шаг — для каждой из сформированных стационарных стратегий по матрицам конструируются матрицы принятых решений R (Z)>R (U), D (Z)>D (U). Очевидно, что количество переходов R (U) и количество выигрышей D (U)будет равно p^m.

Третий шаг — для каждой стационарной стратегии находится вектор стационарного распределения вероятностей (u)=[р₁(u), р₂(u)…р_i(u)…р_m(u)]. Для нахождения вектора (u) используется система линейных уравнений, представленная в матричной форме.

Решение системы линейных уравнений может быть выполнено либо методом подстановки, либо на основе приведения системы уравнений к канонической форме. Ах=В.

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

Где опять же н_i(u) — выигрыш за пребывание системы в i-м состоянии при реализации u-й стратегии.

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

Постановка задачи — рассматривается система, которая соответствует следующей базовой концептуальной модели.

Количество этапов N ограничено. Задано множество стратегий Z={1,2…z…p}, задана матрица вероятности переходов R (Z) и матрица выигрышей D (Z). Необходимо для каждого состояния на каждом из этапов найти оптимальные общие стратегии, которые обеспечивают максимальный локальный выигрыш.

Для решения этой задачи введем функцию f_n(i), которая означает оптимальный выигрыш для i-того состояния за n-1, n, n+1 этапы функционирования.

Для данной модели уравнение Беллмана представляется следующим образом.

н_i(z) — выигрыш от пребывания системы в i-м состоянии при реализации общей стратегии Z.

Этот выигрыш при реализации алгоритма обратной прогонки, если известно количество этапов и оно ограничено N, то для решения уравнения Беллмана целесообразно применить алгоритм обратной прогонки.

В этом случае решение производится начиная с последнего этапа принятия решений, то есть n=N и.

f_N(i)=max{н_i(z)}.

На следующем шаге рассматривается решение принятое на предпоследнем этапе, то есть n=N-1. В этом случае уравнение Беллмана.

Где н_i(z) — выигрыш от пребывания системы в i-м состоянии при реализации общей стратегии Z и в этом решении учитывается значение функции f_N(j), найденное в предыдущем решении. Функционал f_N-1(i) представляет собой локальный выигрыш, получаемый при функционировании системы за n-1 и n этапы. Аналогичные уравнения составляются для остальных шагов до первого шага включительно. После этого производится просмотр полученных таблиц в прямом порядке для нахождения безусловных оптимальных стратегий.