26497

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

Реферат

Менеджмент, консалтинг и предпринимательство

Системному аналитику или управляющему алгоритму предоставлено право выбора одной из общих стратегий Z. И каждая из этих стратегий соответствует матрицам переходных вероятностей Rij где элементы матрицы задают вероятность перехода из состояния i в котором находилась система в момент времени tn1 в состояние j в следующий момент времени. Необходимо для каждого из моментов принятия решений выбрать такую последовательность общих стратегий Z которая будет обеспечивать максимальный суммарный выигрыш от функционирования системы за N этапов. Если...

Русский

2013-08-18

2.13 MB

95 чел.

3

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

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

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

  1.  Во-первых, анализируемая система или анализируемый процесс характеризуется дискретным множеством состояний S1,S2, s, m.
  2.   Функционирование системы представляет собой логическую последовательность этапов n-1, n, n+1… N  этап. Где n малое – текущий номер этапа. Общее количество этапов N может быть фиксированным или равным бесконечности.
  3.  В момент времени tn-1 система находится в одном из состояний S.
  4.  Системному аналитику или управляющему алгоритму предоставлено право выбора одной из общих стратегий Z. И каждая из этих стратегий соответствует матрицам переходных вероятностей Rij, где элементы матрицы задают вероятность перехода из состояния i, в котором находилась система в момент времени tn-1 в состояние j в следующий момент времени. Из состояния i можно перейти в нужное состояние
  5.  Для каждой общей стратегии определена матрица выигрышей D. Элементы этой матрицы характеризуют локальные критерии оценки принятых решений. Элементы матрицы стоимостей dij фиксируют критерии эффективности, которые формируются при переходе системы из состояния i в состояние j. Необходимо для каждого из моментов принятия решений выбрать такую последовательность общих стратегий Z*, которая будет обеспечивать максимальный суммарный выигрыш от функционирования системы за этапов. Каждое решение должно иметь свою стоимость.

1

2

s

i

m

1

2

s

j

m

Состояния

rij(z)

dij(z)

(n-1)

этап

n

этап

(n+1)

этап

tn-1

tn

S={1,2…S…i…m}

z={1,2…z…p}

R=|| rij(z)||

D=|| dij(z)||

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Третий шаг – для каждой стационарной стратегии находится вектор стационарного распределения вероятностей (u)=[π1(u),π2(u)…πi(u)…πm(u)]. Для нахождения вектора(u) используется система линейных уравнений, представленная в матричной форме

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

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

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

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

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

1

2

s

i

m

1

2

s

j

m

rij(z)

dij(z)

(n-1)

период

n

период

(n+1)

период

tn-1

tn

fn(1)

fn(2)

fn(S)

fn(i)

fn(m)

fn+1(1)

fn+1(2)

fn+1(S)

fn+1(j)

fn+1(m)

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

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

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

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

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

В этом случае решение производится начиная с последнего этапа принятия решений, то есть n=N и fN(i)=max{νi(z)}

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

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


 

А также другие работы, которые могут Вас заинтересовать

75906. Диссидентское движение в СССР: основные направления, лидеры и результаты деятельности 19.6 KB
  Диссиденты (лат. dissidents - несогласный) - термин, который с середины 70-х годов применялся к лицам, открыто спорившим с официальными доктринами в тех или иных областях общественной жизни СССР и пришедшим к явному столкновению с аппаратом власти. Первые годы брежневского правления
75907. Сравнительный анализ политических программ двух-трех современных российских политических партий (целевая аудитория (электорат) партии, образ желаемого будущего России (политическая, социально-экономическая модели, место России в международных процессах) 16.93 KB
  Все три партии видят будущее России поразному. Окончательное формирование социалистических общественных отношений В качестве альтернативы этим шагам предусмотрена программаминимум которая предполагает национализацию природных богатств России установление власти трудящихся и т. В программе ЕР нет ясного положения относительно будущего России какой она должна быть отсутствует там и идеология партии.
75908. Аграрная политика в дореволюционной России и в СССР: крепостное право и коллективизация без выдачи паспортов, община и колхоз 16.6 KB
  Крепостное право и кресьянская община. В России крестьянская община зародилась вместе с Древнерусским государством и видоизменяясь просуществовала вплоть до конца 1920х. В период Киевской Руси крестьянская община стала основной производящей единицей.
75909. В чем причины кризиса советской экономики в 1980-е гг.? Системный кризис, падение цен на нефть, нерентабельность производства, экстенсивный характер развития? Причины субъективные и объективные 15.55 KB
  Системный кризис падение цен на нефть нерентабельность производства экстенсивный характер развития Причины субъективные и объективные. Проблемы экономического развития были вызваны рядом причин: Системный кризис. В условиях догоняющего развития без демократических свобод при отсутствии гражданского общества в СССР произошла подмена цели средствами главной жертвой которой стала свобода как необходимое хотя и не единственное условие развития человека его инициативы и предприимчивости. Советская модель хозяйствования лишенная...
75910. Как характеризуют существовавшие в конце 80-х - начале 90-х программы реформ Г.Явлинский и А.Чубайс? Каковы отличия в подходах и восприятии 18.19 KB
  Российская приватизация по масштабам и объему стоящих перед ней задач принципиально отличалась от приватизации осуществленной в 1980е годы в странах Запада.Чубайс прохладно относился к приватизации однако понимал важность ее осущетсвления в рамках проведения рыночных реформ. списка литры: мы вели очень жесткую теоретическую дискуссию с Виталием Найшулем как автором концепции ваучерной приватизации приводили ему длинный список катастрофических тяжелейших последствий которые она неизбежно повлечет за собой. мне лично тема приватизации...
75911. Особенности шоковой терапии и приватизации в России 18.04 KB
  Особенности процесса приватизации происходившего в России: массовый характер приватизации вызванный высокой долей государственной собственности в стране а также стремлением ускорить процесс преобразования экономической структуры общества; значительный удельный вес неэквивалентных форм безвозмездная передача оплата не в полной мере и др. вызванный отсутствием денежных средств в частных руках; проведение особого ваучерного этапа приватизации. Целью приватизации провозглашалось создание эффективного собственника однако бесплатная...
75912. Российские экономические реформы 1990-х гг. в оценках западных исследователей: направления критики 19.84 KB
  В оценках западных исследователей: направления критики Негативная оценка результатов российских реформ общее в выступлениях экономистов Оправдывать или объяснять логику развития событий в России становится неприличным и социально опасным Российские реформы далеки от того чтобы считать их феноменально успешными Главные аргументы критиков Игнорирование китайского опыта...
75913. Понятие «модернизация». Что подразумевают под «европейской модернизацией» России? Какие исторические формы этот процесс приобретал? Можно ли считать сталинскую индустриализацию модернизацией 16.6 KB
  Что подразумевают под европейской модернизацией России Какие исторические формы этот процесс приобретал Можно ли считать сталинскую индустриализацию модернизацией Модернизация современный термин используемый для характеристики давно уже идущего в мире процесса процесса социальных изменений посредством которых менее развитые общества приобретают характеристики отличающие большинство развитых обществ. Несмотря на то что исторически многие страны в своем развитии шли бок о бок термин модернизация долгое время не использовался....
75914. Помешало ли строительство империи в России (XVIII-XIX вв.) созданию российской (русской) нации? Точки зрения Хоскинга и Миллера. Понятие нации и русского национализма в России до 1917 года 20 KB
  Усилия уходившие на сбор налогов и создание армии для нужд империи требовали подчинения практически всего населения особенно русских интересам государства и таким образом затрудняли создание общественных ассоциаций представляющих основу для национального самосознания в гражданском смысле. В России условия для национального самосознания были созданы в XVI веке изобретением традиции это дало толчок и послужило оправданием первых шагов по строительству империи но в середине XVII века само имперское государство внезапно отказалось от...