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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


контрольная работа Марковские процессы. Основные понятия и задачи, решаемые с помощью Марковских процессов

Информация:

Тип работы: контрольная работа. Добавлен: 09.08.2012. Сдан: 2011. Страниц: 11. Уникальность по antiplagiat.ru: < 30%

Описание (план):


Марковские  процессы. Основные понятия и задачи, решаемые с помощью Марковских процессов
1. Основные понятия Марковских процессов 

     Марковские случайные процессы названы по имени выдающегося русского математика А.А. Маркова (1856-1922), впервые начавшего изучение вероятностной связи случайных величин и создавшего теорию, которую можно назвать “динамикой вероятностей”. В дальнейшем основы этой теории явились исходной базой общей теории случайных процессов, а также таких важных прикладных наук, как теория диффузионных процессов, теория надежности, теория массового обслуживания и т.д. В настоящее время теория Марковских процессов и ее приложения широко применяются в самых различных областях таких наук, как механика, физика, химия и др.
    Благодаря сравнительной простоте и наглядности математического аппарата, высокой достоверности и точности получаемых решений особое внимание Марковские процессы приобрели у специалистов, занимающихся исследованием операций и теорией принятия оптимальных решений.
     Несмотря на указанную выше простоту и наглядность, практическое применение теории Марковских цепей требует знания некоторых терминов и основных положений, на которых следует остановиться перед изложением примеров.
    Как указывалось, Марковские случайные процессы относятся к частным случаям случайных процессов (СП). В свою очередь, случайные процессы основаны на понятии случайной функции (СФ).
      Случайной функцией называется функция, значение которой при любом значении аргумента является случайной величиной (СВ). По- иному, СФ можно назвать функцию, которая при каждом испытании принимает какой-либо заранее неизвестный вид.
       Такими примерами СФ являются: колебания напряжения в электрической цепи, скорость движения автомобиля на участке дороги с ограничением скорости, шероховатость поверхности детали на определенном участке и т.д.
       Как правило, считают, что если аргументом СФ является время, то такой процесс называют случайным. Существует и другое, более близкое к теории принятия решений, определение случайных процессов. При этом под случайным процессом понимают процесс случайного изменения состояний какой-либо физической или технической системы по времени или какому-либо другому аргументу.
      Нетрудно заметить, что если обозначить состояние и изобразить зависимость , то такая зависимость и будет случайной функцией.
    Случайные процессы классифицируются по видам состояний и аргументу t. При этом случайные процессы могут быть с дискретными или непрерывными состояниями или временем.
      Кроме указанных выше примеров классификации случайных процессов существует еще одно важное свойство. Это свойство описывает вероятностную связь между состояниями случайных процессов. Так, например, если в случайном процессе вероятность перехода системы в каждое последующее состояние зависит только от предыдущего состояния, то такой процесс называется процессом без последействия.
      Отметим, во-первых, что случайный процесс с дискретными состояниями и временем называется случайной последовательностью.
        Если случайная последовательность обладает Марковским свойством, то она называется цепью Маркова.
      С другой стороны, если в случайном процессе состояния дискретны, время непрерывно и свойство последействия сохраняется, то такой случайный процесс называется Марковским процессом с непрерывным временем.
       Марковский случайный процесс называется однородным, если переходные вероятности остаются постоянными в ходе процесса.
     Цепь Маркова считается заданной, если заданы два условия.
1. Имеется  совокупность переходных вероятностей  в виде матрицы:
. (2)
2. Имеется  вектор начальных вероятностей
, ….. (3)
описывающий начальное состояние системы.
     Кроме матричной формы модель Марковской цепи может быть представлена в виде ориентированного взвешенного графа (рис. 1).

Рис. 1 Ориентированный взвешенный граф
        Множество состояний системы Марковской цепи, определенным образом классифицируется с учетом дальнейшего поведения системы.
1. Невозвратное множество (рис. 2).

Рис.2. Невозвратное множество
     В случае невозвратного множества возможны любые переходы внутри этого множества. Система может покинуть это множество, но не может вернуться в него.
2. Возвратное множество (рис. 3).

Рис. 3. Возвратное множество
     В этом случае также возможны любые переходы внутри множества. Система может войти в это множество, но не может покинуть его.
3. Эргодическое множество (рис. 4).

Рис. 4. Эргодическое множество
     В случае эргодического множества возможны любые переходы внутри множества, но исключены переходы из множества и в него.
4. Поглощающее множество (рис. 5)

Рис. 5. Поглощающее множество
     При попадании системы в это множество процесс заканчивается.
     В некоторых случаях, несмотря на случайность процесса, имеется возможность до определенной степени управлять законами распределения или параметрами переходных вероятностей. Такие Марковские цепи называются управляемыми. Очевидно, что с помощью управляемых цепей Маркова (УЦМ) особенно эффективным становится процесс принятия решений, о чем будет сказано впоследствии.
     Основным признаком дискретной Марковской цепи (ДМЦ) является детерминированность временных интервалов между отдельными шагами (этапами) процесса. Однако часто в реальных процессах это свойство не соблюдается и интервалы оказываются случайными с каким-либо законом распределения, хотя марковость процесса сохраняется. Такие случайные последовательности называются полумарковскими.
      Кроме того, с учетом наличия и отсутствия тех или иных, упомянутых выше, множеств состояний марковские цепи могут быть поглощающими, если имеется хотя бы одно поглощающее состояние, или эргодическими, если переходные вероятности образуют эргодическое множество. В свою очередь, эргодические цепи могут быть регулярными или циклическими. Циклические цепи отличаются от регулярных тем, что в процессе переходов через определенное количество шагов (циклов) происходит возврат в какое-либо состояние. Регулярные цепи этим свойством не обладают.

2. Марковский процесс с дискретным временем

     Итак, модель Марковского процесса представим в виде графа, в котором состояния (вершины) связаны между собой связями (переходами из i-го состояния в j-е состояние), см. рис. 1.
 
Рис. 2.1. Пример графа переходов
      Каждый переход характеризуется вероятностью перехода Pij. Вероятность Pij показывает, как часто после попадания в i-е состояние осуществляется затем переход в j-е состояние. Конечно, такие переходы происходят случайно, но если измерить частоту переходов за достаточно большое время, то окажется, что эта частота будет совпадать с заданной вероятностью перехода.
     Ясно, что у каждого состояния сумма вероятностей всех переходов (исходящих стрелок) из него в другие состояния должна быть всегда равна 1 (см. рис. 2.2.).
 
Рис. 2.2. Фрагмент графа переходов 
(переходы из i-го состояния являются 
полной группой случайных событий)
     Реализация Марковского процесса (процесс его моделирования) представляет собой вычисление последовательности (цепи) переходов из состояния в состояние (см. рис.2.3.). Цепь является случайной последовательностью и может иметь также и другие варианты реализации.
 
Рис. 2.3.. Пример марковской цепи, смоделированной 
по марковскому графу, изображенному на рис. 2.2.
 
        Математический аппарат дискретных Марковских цепей
      Основным математическим соотношением для ДМЦ является уравнение, с помощью которого определяется состояние системы на любом ее k-м шаге. Это уравнение имеет вид:
(4)

и называется уравнением Колмогорова-Чепмена.
       Уравнение Колмогорова-Чепмена относится к классу рекуррентных соотношений, позволяющих вычислить вероятность состояний Марковского случайного процесса на любом шаге (этапе) при наличии информации о предшествующих состояниях.
        Дальнейшие математические соотношения зависят от конкретного вида Марковской цепи. 

                                  3. Поглощающие Марковские цепи
            У поглощающих ДМЦ имеется множество, состоящее из одного или нескольких поглощающих состояний.
          Для примера рассмотрим переходную матрицу, описывающую переходы в системе, имеющей 4 возможных состояния, два из которых являются поглощающими. Матрица перехода такой цепи будет иметь вид:

Практически важным является вопрос о том, сколько  шагов сможет пройти система до остановки  процесса, то есть поглощения в том или ином состоянии. Для получения дальнейших соотношений путем переименования состояний матрицу переводят к блочной форме:
(6)


Такая форма позволяет представить матрицу в каноническом виде:

где - единичная матрица;
- нулевая матрица; 
- матрица, описывающая переходы  в системе из невозвратного  множества состояний в поглощающее  множество;
- матрица, описывающая внутренние  переходы в системе в невозвратном  множестве состояний.
       На основании канонической формы (6а) получена матрица, называемая фундаментальной:

       После соответствующих преобразований матрица примет вид:

       Каждый элемент матрицы соответствует среднему числу раз попадания системы в то или иное состояние до остановки процесса (поглощения).
4. Эргодические цепи
       Как указывалось выше под эргодической ДМЦ понимается цепь, не имеющая невозвратных состояний. Таким образом, в такой цепи возможны любые переходы между состояниями. Напомним, что эргодические цепи могут быть регулярными и циклическими.
      Поскольку согласно данному выше определению в эргодической ДМЦ на любом шаге должны быть возможными любые переходы, то очевидно при этом, что переходные вероятности не должны равняться нулю. Оказывается, из этого условия вытекают некоторые замечательные свойства регулярных ДМЦ:
    Степени при стремятся к стохастической матрице .
    Каждая строка матрицы представляет один и тот же вероятностный вектор все компоненты которого положительны.
    Вектор в теории ДМЦ занимает особое место из-за наличия многих приложений и называется вектором предельных или финальных вероятностей (иногда - стационарным вектором). Финальные вероятности определяют с помощью векторно-матричного уравнения

которое в развернутом виде будет выглядеть  так:

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

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

где
- фундаментальная матрица (15);
- диагональная матрица, образованная  из фундаментальной заменой всех  элементов, кроме диагональных, нулями;
D - диагональная  матрица с диагональными элементами, ;
Е - матрица, все элементы которой равны единице.
 

5. Управляемые Марковские цепи

 
      Как указывалось выше, под управляемыми Марковскими процессами понимают такие, у которых имеется возможность до определенной степени управлять значениями переходных вероятностей. В качестве примеров таких процессов можно привести любые торговые операции, у которых вероятность сбыта и получения эффекта может зависеть от рекламы, мероприятий по улучшению качества, выбора покупателя или рынка сбыта и т.д.
     Очевидно, что при создании математических моделей в данном случае должны фигурировать следующие компоненты:
    конечное множество решений (альтернатив) , где - номер состояния системы;
    матрицы переходов соответствующие тому или иному принятому k-му решению;
    матрицы доходов (расходов) , также отражающие эффективность данного решения.
       Управляемой цепью Маркова (УЦМ) называется случайный процесс, обладающий Марковским свойством и включающий в качестве элемента математической модели конструкцию (кортеж) . Решение, принимаемое в каждый конкретный момент (шаг процесса), назовем частным управлением.
     Таким образом, процесс функционирования системы, описываемой УЦМ, выглядит следующим образом:
        если система находится в состоянии и принимается решение , то она получает доход ;
        состояние системы в последующий момент времени (шаг) определяется вероятностью , то есть существует вероятность того, что система из состояния перейдет в состояние , если выбрано решение .
       Очевидно, общий доход за n шагов является случайной величиной, зависящей от начального состояния и качества принимаемых в течение хода процесса решений, причем это качество оценивается величиной среднего суммарного дохода (при конечном времени) или среднего дохода за единицу времени (при бесконечном времени).
       Стратегией p называется последовательность решений:

где
- вектор управления.
      Задание стратегии означает полное описание конкретных решений, принимаемых на всех шагах процесса в зависимости от состояния, в котором находится в этот момент процесс.
      Если в последовательности (векторе) p все одинаковы, то такая стратегия называется стационарной, т.е. не зависящей от номера шага. Стратегия называется Марковской, если решение , принимаемое в каждом конкретном состоянии, зависит только от момента времени n, но не зависит от предшествующих состояний.
        Оптимальной будет такая стратегия, которая максимизирует полный ожидаемый доход для всех i и n. В теории УМЦ разработаны два метода определения оптимальных стратегий: рекуррентный и итерационный.
       Первый, рекуррентный, метод применяется чаще всего при сравнительно небольшом числе шагов n. Его идея основана на применении принципа Беллмана и заключается в последовательной оптимизации дохода на каждом шаге с использованием рекуррентного уравнения следующего вида:

где
- полный ожидаемый доход;
шагов, если система находится в состоянии i;
- непосредственно ожидаемый доход,  т.е. доход на одном шаге, если  процесс начался с i-го состояния;
- величина полного ожидаемого  дохода за n прошедших шагов, если  процесс начинался с j-го состояния  (i? j).
       Таким образом, данный метод, по существу, аналогичен методу динамического программирования, отличием является лишь то, что на каждом шаге учитывается вероятность попадания системы в то или иное состояние. Поэтому этот метод называют стохастическим динамическим программированием.
       Второй - итерационный метод оптимизации применяется при неограниченном числе этапов (шагов) процесса. Этот метод использует свойство эргодичности Марковской цепи и заключается в последовательном уточнении решения путем повторных расчетов (итераций). При этих уточнениях находят решение, обеспечивающее в среднем минимум дохода при большом числе шагов. Оно уже не будет зависеть от того, на каком шаге производится оценка оптимальной стратегии, то есть является справедливым для всего процесса, независимо от номера шага. Важным достоинством метода является, кроме того, и то, что он дает возможность определить момент прекращения дальнейших уточнений.
      Главное отличие итерационного метода от рассмотренного ранее, рекуррентного, заключается в том, что в данном случае используется матрица предельных (финальных) вероятностей, где вследствие свойства эргодичности переходные вероятности постоянны на всех шагах процесса. Поскольку матрица доходов состоит также из постоянных, не зависимых от n величин, то можно предположить, что с ростом n общая величина доходов будет возрастать линейно.
 
 

6. Марковские случайные процессы с непрерывным временем

       Итак, снова модель Марковского процесса представим в виде графа, в котором состояния (вершины) связаны между собой связями (переходами из i-го состояния в j-е состояние), см. рис. 3.1..
 
Рис. 3.1. Пример графа Марковского 
процесса с непрерывным временем
          Теперь каждый переход характеризуется плотностью вероятности перехода ?ij. По определению:

       При этом плотность понимают как распределение вероятности во времени.
       Переход из i-го состояния в j-е происходит в случайные моменты времени, которые определяются интенсивностью перехода ?ij.
        К интенсивности переходов (здесь это понятие совпадает по смыслу с распределением плотности вероятности по времени t) переходят, когда процесс непрерывный, то есть, распределен во времени.
     Зная интенсивность ?ij появления событий, порождаемых потоком, можно сымитировать случайный интервал между двумя событиями в этом потоке.

где ?ij — интервал времени между нахождением системы в i-ом и j-ом состоянии.
       Далее, очевидно, система из любого i-го состояния может перейти в одно из нескольких состояний j, + 1, + 2, …, связанных с ним переходами ?ij, ?ij + 1, ?ij + 2, ….
       В j-е состояние она перейдет через ?ij; в (+ 1)-е состояние она перейдет через ?ij + 1; в (+ 2)-е состояние она перейдет через ?ij + 2 и т. д.
       Ясно, что система может перейти из i-го состояния только в одно из этих состояний, причем в то, переход в которое наступит раньше.
       Поэтому из последовательности времен: ?ij, ?ij + 1, ?ij + 2 и т. д. надо выбрать минимальное и определить индекс j, указывающий, в какое именно состояние произойдет переход.
       Рассмотрим пример. Моделирование работы станка. Промоделируем работу станка (см. рис. 3.2.), который может находиться в следующих состояниях: S0 — станок исправен, свободен (простой); S1 — станок исправен, занят (обработка); S2 — станок исправен, замена инструмента (переналадка) ?02 ?21; S3 — станок неисправен, идет ремонт ?13 ?30.
      Зададим значения параметров ?, используя экспериментальные данные, получаемые в производственных условиях: ?01 — поток на обработку (без переналадки); ?10 — поток обслуживания; ?13 — поток отказов оборудования; ?30 — поток восстановлений.
       Реализация будет иметь следующий вид (рис. 3.2.).
 
Рис. 3.2. Пример моделирования непрерывного 
марковского процесса с визуализацией на временной 
диаграмме (желтым цветом указаны запрещенные, 
синим — реализовавшиеся состояния)
       В частности, из рис. 3.2. видно, что реализовавшаяся цепь выглядит так: S0S1S0—… Переходы произошли в следующие моменты времени: T0T1T2T3—…, где T= 0, T= ?01, T= ?01 + ?10.
       Очень часто аппарат Марковских процессов используется при моделировании компьютерных игр. 
 
 
 
 
 
 
 
 
 
 
 
 
 

Практические  задания 

Задание 1
Три предприятия данного экономического района могут производить однородную продукцию в количествах, соответственно равных 180, 350, 20 единиц. Эта продукция должна быть поставлена пяти потребителям в количествах, соответственно равных 110, 90 120, 80, 150 единиц. Затраты, связанные с доставкой продукции задаются матрицей
       | 2 4 1 6 7|
С = | 3 3 5 4 2|
       | 8 9 6 3 4|.
    Составить такой план прикрепления  покупателей продукции ее поставщикам,  при котором общая стоимость  перевозок является минимальной.
Решение:
     Цель задачи состоит в минимизации  суммарной стоимости перевозок  сырья. Эта цель может быть  достигнута с помощью оптимальной  организации перевозок. Следовательно,  за неизвестные можно принять  количество сырья, перевозимого  от каждого поставщика каждому потребителю.
и т.д.................


Перейти к полному тексту работы


Скачать работу с онлайн повышением уникальности до 90% по antiplagiat.ru, etxt.ru или advego.ru


Смотреть полный текст работы бесплатно


Смотреть похожие работы


* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.