Презентация на тему "Q-схема моделирования (непрерывные марковские системы)"

Содержание

• 
  Слайд 1

  Q-схема моделирования (непрерывные марковские системы)

  Q – от англ. слова queue – «очередь». Основная теория для расчетов – непрерывные марковские процессы и теория массового обслуживания (ТМО) или система массового обслуживания (СМО) – это частный случай ТМО.

• 
  Слайд 2

  А.А. Марков (старший) – основоположник теории сетей Маркова

  А.А. Марков (1856 - 1922) Оставил труды в области Теории вероятностей и случайных процессов, математическом анализе и теории чисел. Не путать с А.А. Марковым младшим (сын), создателем алгорифмов Маркова.

• 
  Слайд 3
  

  Модель представляет собой граф, где узлы обозначают состояние моделируемого объекта, а дуги – интенсивность перехода из одного состояния в другое (сколько раз в единицу времени происходят переходы). Sk- состояние объекта моделирования ij- поток вероятностей переходи из i-го состояния в j-ое Непрерывный Марковский процесс

• 
  Слайд 4

  Основоположник теории потока однородных событий

  Александр Яковлевич Хи́нчин (1894—1959) профессор МГУ с 1927 года. Создатель теории потока однородных событий, Совместно с А.Н. Колмогоровым – создатель теории случайных процессов и теории массового обслуживания.

• 
  Слайд 5

  Поток событий

  Ключевое понятие Q-схемы моделирования – поток событий. Это – последовательность событий, происходящих одно за другим. Поток событий может быть: - Детерминированный (моменты времени появления событий определены заранее: либо происходят через равные промежутки времени, либо заданы определены законом ti=f(ti-1) ). - Cлучайный, когда появление событий случайно. t t0 t1 t2 t3 t4 t5 t6 t7

• 
  Слайд 6

  Случайный поток событий

  В отличие от случайной величины (из теории вероятностей, которая в результате испытания принимает только одно определенное значение и своего множества значений) случайный поток – это последовательность событий, возникающих в случайные моменты времени. Например, приход автобусов к остановке, поступление запросов на телефонную станцию, подход покупателя к кассе магазина, приход пакета информации к абоненты в компьютерной сети. Время между двумя событиями ( ) в случайном потоке задается с помощью функции распределения случайной величины. Такие потоки можно классифицировать по таким законам (равномерный, экспоненциальный, биномиальный, нормальный и т.д.). t t0 t1 t2 t3 t4 t5 t6 t7 

• 
  Слайд 7

  Свойства потока событий

  Интенсивность – среднее число событий, происходящих в единицу времени. Обычно обозначается как  или . Закон распределения интервалов между событиями (обычно задается с помощью непрерывной случайной величины). Существует или нет зависимость событий друг от друга (т.е. влияет ли последовательность предыдущих событий на появление текущего события). Однородность(стационарность) – неизменность параметров потока событий со временем. t t0 t1 t2 t3 t4 t5 t6 t7

• 
  Слайд 8

  Основные виды потоков событий

  Регулярный поток Равномерный Пуассоновский (экспоненциальный) Нормальный (Гаусса)

• 
  Слайд 9

  Регулярный поток

  Регулярный поток – когда события происходят через равный промежуток времени. Примеры – такты работы процессора, движение стрелки часов и т.д. Поток с ограниченным последействием (поток Пальма), т.е. поток, где время между событиями описывается случайной величиной. t t0 t1 t2 t3 t4 t5 t6 t7

• 
  Слайд 10

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

  M=(b-a)/2, D=(b-a)2/12 Где встречается в природе? Эксперименты, где точка ставится наудачу в определенном интервале; ошибка при округлении до ближайшего целого.

• 
  Слайд 11

  Нормальный закон распределения

  где  - среднеквадратическое отклонение с.в.; - математическое ожидание с.в.; x – время между двумя событиями. Где встречается в природе? погрешности измерений; отклонения геометрических размеров и положения элементов строительных конструкций при их изготовлении и монтаже; изменчивость физико-механических характеристик материалов и нагру­зок, действующих на строительные конструкции. M=, D=2

• 
  Слайд 12

  Пуассоновский (экспоненциальный) закон распределения

  В пуассоновском потоке интервал между событиями описывается с помощью экспоненциального вероятностного распределения. Пуассоновский поток, обладающий всеми тремя необходимыми свойствами: ординарность, отсутствие последействия, стационарность – называется простейшим (или стационарным пуассоновским) потоком. Где  - интенсивность потока, т.е. сколько в среднем событий происходит в единицу времени. Где встречается в природе? Поток событий, порождаемый множеством независимых источников.

• 
  Слайд 13

  Свойство Пуассоновского потока событий

  Сумма двух пуассоновских потоков интенсивностью 1 и 2 идентична пуассоновскому потоку с интенсивностью  = 1+ 2. Пуассоновский поток обладает свойствами отсутствия последействия и ординарности

• 
  Слайд 14

  Формула Пуассона

  Формула Пуассона показывает, вероятность того, что в единичный интервал времени в элементарном потоке событий попадет ровно m событий. m f(m) При =1   Где a = ;  - временной интервал; m – число событий в единицу времени;  - интенсивность потока событий;

• 
  Слайд 15

  Потоковые теоремы

  Центральная предельная теорема: Сумма n одинаково распределенных независимых случайных величин x со средним Мх и дисперсией Dx стремится к нормально распределенной величине с параметрами nМх и nDx при бесконечном увеличении n. Предельная теорема для суммарного потока: Достаточно больше число (более 5-7) независимых потоков событий, имеющих различное распределение, стремятся к экспоненциальному потоку с  равной сумме интенсивностей всех потоков (каждый поток оказывает примерно одинаковое влиянием на суммарный поток). Предельнаятеорема для разреженного потока Если любой поток разрежать произвольным образом, то при достаточно большом числе выброшенных точек поток будет стремиться к простейшему.

• 
  Слайд 16

  Поток Эрланга

  Просеянный экспоненциальный поток. Поток эрлангаk-го порядка, где k – число выброшенных событий. Поток эрланга 1-го порядка – экспоненциальный закон, 2-го порядка – удаляется каждое 2-е событие, 3-го порядка – удаляется два события, третье оставляется и т.д.

• 
  Слайд 17

  Эволюция нормированного потока Эрланга

  Если интенсивность простейшего потока , то при его просеивании и получении потока Эрланга k-го порядка, интенсивность потока будет /n. Нормированный поток Эрланга, когда при просеивании временную ось масштабируют, чтобы остался прежняя интенсивность потока . Когда порядок потока Эрланга kравняется 20-30, он приближается к нормальному распределению. Когда ранг k поток Эрланга вырождается в регулярный поток с временем между событиями равным 1/.

• 
  Слайд 18

  Генерация потока случайных событий

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

• 
  Слайд 19
  

  Генерация последовательности случайных чисел, согласно плотности вероятностей с.в.

  Как правило, в каждом языке программирования или среде моделирования существует генератор случайных чисел по равномерному распределению в интервале [0,1].Такую последовательность можно преобразовать в последовательность чисел с.в. любой функции плотности вероятностей с помощью метода обратной функции: f(x)=R -> x=f-1 (R), где R – последовательность равномерной с.в. из интервала [0,1] (базисное число), f-1– обратная функция; x – последовательность чисел с.в. заданного распределения.

• 
  Слайд 20

  Метод обратной функции

  Теорема. Если случайная величина  имеет плотность распределения вероятностей , то распределение случайной величины равномерно в интервале  [0,1], т. е. где Rav[0,1] – с.в. равномерной функции распределения

• 
  Слайд 21

  Получение последовательностей чисел для с.в. различных распределений

  Равномерное распределение на интервале [a,b]: Экспоненциальное распределение: Нормальное распределение:

• 
  Слайд 22

  Оценка статистических характеристик с.в.

  Оценка статистических характеристик – это определение закона распределения или других характеристик с.в., исходя из экспериментальных данных. Генеральная совокупность - совокупность всех мыслимых (возможных) результатов наблюдений над случайной величиной, которые в принципе могут быть проведены при данных условиях. Выборка — это конечный набор x1, x2, …, xN значений случайной величины, полученный в результате наблюдений. Число элементов N выборки называется ее объемом или размером. В выборке некоторые значения могут совпадать. Чем больше объем выборки, тем более точно можно установить статистическими методами закон распределения с.в.

• 
  Слайд 23
  

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

• 
  Слайд 24

  Элементарные статистические характеристики

  Математическое ожидание: Дисперсия: Дисперсия полученной величины

• 
  Слайд 25

  Диаграмма накопленных частот

  Вариационный ряд (или ряд распределения) z1, z2, …, zn получают из исходных данных путем расположения xm (m=1,2, …,n) в порядке возрастания от xmin до xmax так, чтобы xmin = z1 ≤ z2 ≤…≤ zn = xmax. Диаграмма накопленных частот Pn(x) является эмпирическим аналогом интегрального закона распределения (функции вероятности) P(x) и ее строят в соответствии с формулой: где n(x) - число элементов в выборке, для которых значение xj

• 
  Слайд 26

  Диаграмма накопленных частот (пример)

  Пусть имеется выборка объема 5: x1=5, x2=2, x3=4, x4=5, x5=7. Вариационный ряд для данной выборки будет таким: z1=2, z2=4, z3=5, z4=5, z5=7:

• 
  Слайд 27

  Гистограмма частот

  Гистограмма частот fn(x) является аналогом функции плотности распределения f(x). Алгоритм составления гистограммы: По оценочной формуле находим предварительное количество квантов (интервалов) К, на которое нужно разбить ось 0x: K = 1 + 3.2lg n, найденное значение K округляют до ближайшего целого числа. Определяем длину каждого кванта (интервала): Δx = (xmax - xmin)/K, которую для удобства можно округлить. Подсчитываем количество наблюдений nm, попавшее в каждый квант: nm равно числу членов вариационного ряда, для которых справедливо неравенство xm ≤ zl

• 
  Слайд 28

  Нахождение функции плотности вероятности

  Вариационный ряд (или ряд распределения) z1, z2, …, zn получают из исходных данных путем расположения xm (m=1,2, …,n) в порядке возрастания от xmin до xmax так, чтобы xmin = z1 ≤ z2 ≤…≤ zn = xmax. Диаграмма накопленных частот Pn(x) является эмпирическим аналогом интегрального закона интегрального закона распределения P(x) и ее строят в соответствии с формулой где n(x) - число элементов в выборке, для которых значение xj

• 
  Слайд 29
  
• 
  Слайд 30
  

  Для анализа с помощью Марковской сети поток событий должен обладать следующими свойствами:

  t t0 t1 t2 t3 t4 t5 t6 t7 Ординарность – в один момент не могут произойти сразу два события, т.е. p0(t,t+t) + p1(t,t+t) + p>1(t,t+t)=1.При t 0 p>1(t,t+t) 0. Отсутствие последействия – то, что текущее событие не зависит от предыдущих событий. Стационарность – то, что параметры потока не меняются с течением времени ((t)==Const). Всем вышеперечисленным требованиям удовлетворяет пуассоновский (или экспоненциальный) поток событий.

• 
  Слайд 31

  Литература

  1. Вентцель Е.С., Овчаров Л.А. Теория случайных процессов и ее инженерные приложения. — Учеб. пособие для втузов. — 2-е изд., стер. — М.: Высш. шк., 2000. — 383 с: 2. Клейнрок Л. Теория массового обслуживания. Пер. с англ. /Пер. И.И. Глушко; ред. В.И. Нейман. – М.: Машиностроение, 1979. – 432 с. 3/ Миллер Б. М., Панков А. Р. Теория случайных процеспроцессовв примерах и задачах. -М.: ФИЗМАТЛИТ, 2002. -320 с.