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

Страницы работы

12 страниц (Word-файл)

Содержание работы

Министерство образования Российской Федерации

Новосибирский Государственный Технический Университет

Кафедра Автоматизированных Систем Управления

РЕФЕРАТ

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

Группа:                  АСМ - 02

Студент:                Зайков А.В.                                                                                                                                    

Преподаватель:     к.т.н., доц. каф. АСУ,

Хоменко В.М.

Новосибирск

2002


СОДЕРЖАНИЕ

Введение.................................................................................................................................................................................. 3

Основные понятия......................................................................................................................................................... 4

Пример........................................................................................................................................................................................ 4

Матрица дохода. Горизонты планирования........................................................................................ 5

Пример........................................................................................................................................................................................ 6

Конечный и бесконечный горизонты планирования. Переоценка.............................. 6

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

Пример...................................................................................................................................................................................... 10

Заключение......................................................................................................................................................................... 11

Литература.......................................................................................................................................................................... 12


Введение

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

В марковских задачах принятия решений поощрения (доходы, потери) задаются при помощи  матрицы доходов, элементами которой являются доходы (положительные значения) или затраты (отрицательные значения), возникающие вследствие перехода системы из одного возможного состояния в другое. Матрицы переходных вероятностей и матрицы доходов зависят от стратегий, т.е. допустимых решений, которыми располагает лицо, принимающее решения (ЛПР). Основная цель — определение оптимальной стратегии (оптимального решения), максимизирующей ожидаемый доход за конечное или бесконечное число этапов марковского процесса изменения состояния изучаемой системы. Принцип оптимальности заключается в максимизации ожидаемого дохода за рассматриваемое (заданное) число этапов.


Основные понятия

Рассматривается система S, которая может иметь Sj состояний, j = 1,m, и в фиксированные моменты времени t1, t2 … случайным образом скачкообразно переходит в одно из этих состояний. Процесс изменения состояний системы предполагается марковским, т.е. вероятность перехода системы S в любое возможное состояние в момент ti, определяется только состоянием системы в момент ti-1. Моменты времени ti принято называть этапами или шагами марковского процесса.

Введем случайное событие sik, состоящее в том, что после i этапов система S находится в состоянии Sk, k = 1,m. При любом фиксированном i события sik, k = 1,m, образуют полную группу событий.

Вектор  является вектором вероятностей состояний системы S после i этапов при i = 1,N и вектором начальных вероятностей системы S при i = 0. В соответствии с исходными допущениями вероятность реализации случайного события sik при условии si-1j (т.е. система в i момент времени находится в состоянии Sk, при условии, что в предыдущий (i-1) момент времени система находилась в состоянии Sj) зависит от принятого после (i-1)-го этапа решения Xi-1l из множества G допустимых решений. Таким образом,

и матрица переходных вероятностей

 Mm(R)

При этом верны следующие утверждения:

·  сумма элементов любой строки матрицы переходных вероятностей равна единице (т.к. строка матрицы определяет вероятности перехода системы S из j-го состояния во все k-ые состояния, k = 1,m);

·  вектор состояний системы после i-го этапа равен:

, где p(i) — вектор вероятностей состояний системы после i этапов,

p(i-1) — вектор вероятностей состояний системы после (i-1) этапов.

Следовательно вектор p(i) в общем случае зависит от вектора начальных вероятностей состояний системы p(0) и вектора , который называют вектором решений (в этом легко убедиться, выразив p(i-1) через p(i-2) и т.д. и затем подставив вместо p(i-1)).

Пример

Похожие материалы

Информация о работе