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

Размещено на http: //www. allbest. ru/

БЕЛОРУССКИЙ НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

МЕЖДУНАРОДНЫЙ ИНСТИТУТ ДИСТАНЦИОННОГО ОБРАЗОВАНИЯ

«Информационные системы и технологии»

Контрольная работа

По дисциплине «Методы принятия решения»

выполнил ст. гр. 41704212 Демьянова С.И.

проверила Боярышнова О.А

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

1.1 Концептуальная схема принятия решений в Марковской модели

Концептуальная схема принятия решений при использовании Марковской модели имеет следующие особенности:

· Во-первых, анализируемая система или анализируемый процесс характеризуется дискретным множеством состояний S1,S2, s, m.

· Функционирование системы представляет собой логическую последовательность этапов n-1, n, n+1… N этап. Где n малое - текущий номер этапа. Общее количество этапов N может быть фиксированным или равным бесконечности.

· В момент времени tn-1 система находится в одном из состояний S.

· Системному аналитику или управляющему алгоритму предоставлено право выбора одной из общих стратегий Z. И каждая из этих стратегий соответствует матрицам переходных вероятностей R_ij, где элементы матрицы задают вероятность перехода из состояния i, в котором находилась система в момент времени tn-1 в состояние j в следующий момент времени. Из состояния i можно перейти в нужное состояние

· Для каждой общей стратегии определена матрица выигрышей D. Элементы этой матрицы характеризуют локальные критерии оценки принятых решений. Элементы матрицы стоимостей d_ij фиксируют критерии эффективности, которые формируются при переходе системы из состояния i в состояние j. Необходимо для каждого из моментов принятия решений выбрать такую последовательность общих стратегий Z*, которая будет обеспечивать максимальный суммарный выигрыш от функционирования системы за N этапов. Каждое решение должно иметь свою стоимость.

Размещено на http: //www. allbest. ru/

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

Одна из модификаций Марковской модели предполагает, что количество этапов может быть бесконечным. Следовательно, при определенных ограничениях на матрицу R(Z) система переходит в установившийся режим.

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

Если число общей стратегии равно p, а число состояний m, то количество стационарных стратегий определяется как p^m .

Множество стационарных стратегий U=(1,2,…u,…p^m) формируется следующим образом:

1.Необходимо определить общую стратегию U1. Таким образом U=(1,1,1,1). То есть из m состояний стационарная стратегия U1 состоит в том, что система переводится в состояние 1.

2.В состоянии 2 если система находилась, можно применить общую стратегию U2, то есть переход во второе состояние.

3.Если система была в состоянии i, применяется общая стратегия Ui.

Анализ Марковской модели установившихся решений предполагает формирование для каждой стационарной стратегии матрицы переходных вероятностей R(U) и матрицы коэффициентов эффективности (выигрышей или доходов) D(U).

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

Первая строка матрицы переходов R[U=(u₁…u_i…u_m)]. Соответствует первой строке матрицы принятия решений R(z=u1). То есть матрица переходных вероятностей задает вероятности перехода из всех возможных состояний в момент времени tn-1 в первое состояние.

Матрица стоимостных показателей D[U=(u₁…u_i…u_m)] соответствует первой строке матрицы принятия решения D(z=u1), то есть матрица определяет все возможные критерии выигрышей при переходе системы из состояния iго в 1ое состояние.

Вторые строки матрицы переходов R[U=(u₁…u_i…u_m)] соответствуют вторым строкам матрицы принятия решений R(z=u2) и, соответственно, выигрыши D[U=(u₁…u_i…u_m)] - вторым строкам матрицей выигрышей D(z=u2).

Для i-й строки матрица переходов будет выглядеть как R(z=ui) и соответственно матрица стоимостей D(z=ui) для перехода из любого в любое состояние.

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

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

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

Для стационарного режима определены вероятности состояний при реализации 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, число стационарных стратегий существенно возрастает. Поэтому для задач большой размерности применяется метод динамического программирования для анализа Марковской модели.

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

Размещено на http: //www. allbest. ru/

Количество этапов 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 этапы. Аналогичные уравнения составляются для остальных шагов до первого шага включительно. После этого производится просмотр полученных таблиц в прямом порядке для нахождения безусловных оптимальных стратегий.

Размещено на Allbest.ru