Интервал времени между двумя соседними событиями простейшего потока имеет распределение:
f 1 (x) = f(x) = (x³0),
где - интенсивность потока.
Используя метод имитации показательного (экспоненциального) распределения, получаем следующий способ моделирования пуассоновского потока:
t 0 =0; t j = t j -1 - (1/ ) lnu , (j=1,2,3,...).
Величина u - случайное число, получаемое от ДСЧ.
Равномерный поток
Для этого потока событий считается, что промежуток времени между последовательными событиями равномерно распределён на интервале , т.е.
f(x)=1/(b-a) , (a£x£b).
f 1 (x)=2(b-x)/(b-a) 2 ;
F 1 (x)=1-[(b-x) 2 /(b-a) 2 ] , (a£x£b)
Применяя для моделирования метод обратной функции, получим алгоритм вычисления первого момента времени
где u получают от ДСЧ.
Окончательно имеем следующий алгоритм моделирования равномерного потока:
1) момент времени t 1 наступления первого события вычисляется по формуле
2) для последующих моментов времени производимы вычисления по формуле
t j =t j -1 + a + (b-a)u;
Величина u вырабатывается ДСЧ.
Поток Эрланга порядка k
Потоком Эрланга k-го порядка называют поток событий, получающегося "прореживанием" простейшего потока, когда сохраняется каждая k-я точка (событие) в потоке, а все промежуточные выбрасываются.
Интервал времени между двумя соседними событиями в потоке Эрланга k-го порядка представляет собой сумму k независимых случайных величин Z 1 ,Z 2 ,...,Z k , имеющих показательное распределение с параметром λ:
Закон распределения случайной величины Z называется законом Эрланга k-го порядка и имеет плотность
, (x > 0).
Математическое ожидание и дисперсия случайной величины Z соответственно равны:
M[Z]=k/ ; D[Z]=k/ 2 .
На основе определения потока Эрланга получается простой способ моделирования: прореживается пуассоновский поток с интенсивностью = /k, т.е. в пуассоновском потоке допускаем моменты времени с номерами 1,2,...,k-1, а k-й момент оставляем, т.к. он принадлежит новому потоку и т.д. Таким образом, моменты времени потока Эрланга вычисляются по формулам:
где - интенсивность потока Эрланга k-го порядка, u j - случайные числа от ДСЧ.
3. ОБЪЕКТЫ И СРЕДСТВА ИССЛЕДОВАНИЯ
Объектами исследования в лабораторной работе являются потоки событий, образованные слиянием нескольких потоков с известными характеристиками.
В процессе имитации потоков событий используются различные методы сортировки.
Одним из простых методов сортировки является метод пузырька (BUBBLE) который позволяет массив A, содержащий N элементов, расположить, например, в возрастающем порядке. Соответствующий алгоритм приведен на рис.4.1. Однако. Более эффективным методом для данного типа задач будет метод вставки.
процедура BUBBLE(A, N);
Цикл I=1,N1;
Если A(K) £ A(J) то идти к 20;
Если (K³1), то идти к 10;
Рис.4.1. Подпрограмма сортировки методом пузырька
В лабораторной работе могут быть использованы и другие более эффективные методы сортировки (например, адресная сортировка и т.п.).
4. ПОДГОТОВКА К РАБОТЕ
4.1. Ознакомиться с основными типами потоков событий.
4.2. Ознакомиться с методами моделирования пуассоновского, равномерного потока событий и потока Эрланга порядка k.
4.3. Ознакомиться с методами сортировки массивов чисел.
5. ПРОГРАММА РАБОТЫ
В некоторую систему массового обслуживания по различным каналам поступают заявки, образующие поток событий заданного типа. На входе системы потоки сливаются в один. Составить алгоритм и программу имитации результирующего потока, указанного в варианте.
Первые 100 моментов времени поступления заявок в результирующем потоке вывести на печать. По первым 1000 заявкам рассчитать оценку средней интенсивности потока. Найденную оценку сравнить с теоретическим значением интенсивности потока.
5.1. Поток образован слиянием трёх пуассоновских потоков событий с интенсивностями 1 , 2 , 3 (1/с) (табл.5.1.).
Таблица 5.1.
| Вариант | ||||||
| 1 | 2,5 | 1,5 | ||||
| 2 | 0,5 | |||||
| 3 | 0,5 | 0,5 | 0,5 |
5.2. Поток образован слиянием двух равномерных потоков с параметрами a 1 , b 1 и a 2 , b 2 (с) (табл. 5.2.).
Таблица 5.2.
| Вариант | ||||||
| a 1 | 1,5 | |||||
| b 1 | 2,5 | 1,5 | ||||
| a 2 | 0,5 | |||||
| b 2 |
5.3. Поток образован слиянием пуассоновского потока с интенсивностью (1 /с) и равномерного потока с параметрами a и b (с) (табл.5 3.).
Таблица 5.3.
6. КОНТРОЛЬНЫЕ ВОПРОСЫ
6.1. Дать определение потока событий.
6.2. Как строится вероятностное описание потока событий.
6.3. В чём состоит способ моделирования стационарного потока с ограниченным последствием.
6.4. Охарактеризовать пуассоновский поток и способ его моделирования.
6.5. Охарактеризовать равномерный поток и способ его моделирования.
6.6. Дать характеристику потока Эрланга k-го порядка и метода его имитации.
6.7. Привести характеристики потока событий, исследованного в лабораторной работе.
Описывает количество наступивших случайных событий, происходящих с постоянной интенсивностью.
Вероятностные свойства потока Пуассона полностью характеризуются функцией Λ(А) , равной приращению в интервале А некоторой убывающей функции. Чаще всего поток Пуассона имеет мгновенное значение параметра λ(t) - функцию, в точках непрерывности которой вероятность события потока в интервале равна λ(t)dt . Если А - отрезок , то
Λ (A) = ∫ a b λ (t) d t {\displaystyle \Lambda (A)=\int \limits _{a}^{b}\lambda (t)\,dt}Поток Пуассона, для которого λ(t) равна постоянной λ , называется простейшим потоком с параметром λ .
Потоки Пуассона определяются для многомерного и вообще любого абстрактного пространства, в котором можно ввести меру Λ(А) . Стационарный поток Пуассона в многомерном пространстве характеризуется пространственной плотностью λ . При этом Λ(А) равна объему области А , умноженному на λ .
Классификация
Различают два вида процессов Пуассона: простой (или просто: процесс Пуассона) и сложный (обобщённый).
Простой процесс Пуассона
Пусть λ > 0 {\displaystyle \lambda >0} . Случайный процесс { X t } t ≥ 0 {\displaystyle \{X_{t}\}_{t\geq 0}} называется однородным Пуассоновским процессом с интенсивностью λ {\displaystyle \lambda } , если
Сложный (обобщённый) пуассоновский процесс
Обозначим через S k {\displaystyle S_{k}} сумму первых k элементов введённой последовательности.
Тогда определим сложный Пуассоновский процесс { Y t } {\displaystyle \{Y_{t}\}} как S N (t) {\displaystyle S_{N(t)}} .
Свойства
- Пуассоновский процесс принимает только неотрицательные целые значения, и более того
- Траектории процесса Пуассона - кусочно-постоянные, неубывающие функции со скачками равными единице почти наверное. Более точно
где o (h) {\displaystyle o(h)} обозначает «о малое» .
Критерий
Для того чтобы некоторый случайный процесс { X t } {\displaystyle \{X_{t}\}} с непрерывным временем был пуассоновским (простым, однородным) или тождественно нулевым достаточно выполнение следующих условий:
Информационные свойства
Зависит ли
T
{\displaystyle T}
от предыдущей части траектории?
P
({
T
>
t
+
s
∣
T
>
s
})
{\displaystyle \mathbb {P} (\{T>t+s\mid T>s\})}
- ?
Пусть u (t) = P (T > t) {\displaystyle u(t)=\mathbb {P} (T>t)} .
U
(t
∣
s)
=
P
(T
>
t
+
s
∩
T
>
s)
P
(T
>
s)
=
P
(T
>
t
+
s)
P
(T
>
s)
{\displaystyle u(t\mid s)={\frac {\mathbb {P} (T>t+s\cap T>s)}{\mathbb {P} (T>s)}}={\frac {\mathbb {P} (T>t+s)}{\mathbb {P} (T>s)}}}
u
(t
∣
s)
u
(s)
=
u
(t
+
s)
{\displaystyle u(t\mid s)u(s)=u(t+s)}
u
(t
∣
s)
=
s
(t)
⇔
u
(t)
=
e
−
α
t
{\displaystyle u(t\mid s)=s(t)\Leftrightarrow u(t)=e^{-\alpha t}}
.
Распределение длин промежутков времени между скачка́ми обладает свойством отсутствия памяти ⇔ оно показательно .
X
(b)
−
X
(a)
=
n
{\displaystyle X(b)-X(a)=n}
- число скачков на отрезке
[
a
,
b
]
{\displaystyle }
.
Условное распределение моментов скачков
τ
1
,
…
,
τ
n
∣
X
(b)
−
X
(a)
=
n
{\displaystyle \tau _{1},\dots ,\tau _{n}\mid X(b)-X(a)=n}
совпадает с распределением вариационного ряда, построенного по выборке длины
n
{\displaystyle n}
из
R
[
a
,
b
]
{\displaystyle R}
.
Плотность этого распределения f τ 1 , … , τ n (t) = n ! (b − a) n I (t j ∈ [ a , b ] ∀ j = 1 , n ¯) {\displaystyle f_{\tau _{1},\dots ,\tau _{n}}(t)={\frac {n!}{(b-a)^{n}}}\mathbb {I} (t_{j}\in \ \forall j={\overline {1,n}})}
ЦПТ
- Теорема.
P
(X
(t)
−
λ
t
λ
t
<
x)
⇉
x
λ
t
→
∞
Φ
(x)
∼
N
(0
,
1)
=
1
2
π
∫
−
∞
x
e
−
u
2
2
d
u
{\displaystyle \mathbb {P} {\biggl (}{\frac {X(t)-\lambda t}{\sqrt {\lambda t}}} Скорость сходимости: Поток Пуассона служит для моделирования различных реальных потоков: несчастных случаев, потока заряженных частиц из космоса, отказов оборудования и других. Так же возможно применение для анализа финансовых механизмов, таких как поток платежей и других реальных потоков. Для построения моделей различных систем обслуживания и анализа их пригодности. Использование потоков Пуассона значительно упрощает решение задач систем массового обслуживания , связанных с расчетом их эффективности. Но необоснованная замена реального потока потоком Пуассона там, где это недопустимо, приводит к грубым просчетам. Восстанавливаемые объекты после ремонта продолжают эксплуатироваться по прямому назначению. Надежность восстанавливаемых объектов принято оценивать по характеристикам потока отказов. В общем случае потоком
событий называется последовательность однородных событий, следующих одно за другим в случайные моменты времени. В теории надежности восстанавливаемых объектов в основном рассматриваются простейшие потоки событий, характеризующиеся ординарностью, стационарностью
и отсутствием последействия
(такие потоки событий чаще всего встречаются на практике). Поток событий называется ординарным,
если вероятность появления двух и более отказов в единичном интервале времени пренебрежимо мала по сравнению с вероятностью появления одного отказа. Таким образом, отказы в системе возникают по одному. Поток событий называется стационарным,
если вероятность попадания того или иного числа событий на интервал времени т зависит только от длины интервала и не зависит от того, где именно на оси расположен этот интервал. Стационарность потока событий означает, что плотность потока постоянна. Очевидно, что при наблюдении поток может иметь сгущения и разрежения. Однако для стационарного потока эти сгущения и разрежения не носят закономерного характера, а среднее число событий, попадающих на единичный интервал времени, остается постоянным для всего рассматриваемого периода. Отсутствие последействия
в простейшем потоке событий означает, что вероятность появления отказов в единичном интервале времени не зависит от возникновения отказов во всех предыдущих интервалах времени, т. е. отказы возникают независимо друг от друга. В электронно-вычислительных средствах поток отказов равен сумме потоков отказов отдельных устройств. Если каждый в отдельности поток оказывает на суммарный поток достаточно равномерное и небольшое влияние, то суммарный поток будет простейшим.
Пусть простейший поток отказов обладает следующими свойствами. 1. Время между отказами распределено по экспоненциальному закону с некоторым параметром А, (формулы (4.16)-(4.21)):
Следовательно, и Т 0 -
наработка до первого отказа распределена по экспоненциальному закону с тем же параметром X
(средняя наработка до первого отказа есть математическое ожидание Т
: 2. Пусть r(t) -
число отказов за время t
(r(t)
является случайной величиной). Вероятность того, что за время t
произойдет m
отказов при интенсивности отказов X,
определяется законом Пуассона (см. (4.22)): 3. Среднее число отказов за время t
равно: 4. Вероятность того, что за время t
не произойдет ни одного отказа, равна: P(t) = е
~ и. Описанный простейший поток событий также называют стационарным пуассоновским потоком.
Как уже было сказано выше, такой поток характерен для сложных высоконадежных объектов. Процесс функционирования восстанавливаемого объекта можно описать как последовательность чередующихся интервалов работоспособности и простоя, связанного с восстановлением. Предполагается, что отказ объекта немедленно фиксируется и с этого же момента начинается восстановительная процедура. Интервалы работоспособности (мы предполагаем 100%-ное восстановление объекта) являются независимыми и одинаково распределенными случайными величинами, при этом они не зависят от интервалов восстановления, которые также являются независимыми и одинаково распределенными случайными величинами (скорее всего, с другим распределением). Каждая из этих последовательностей интервалов формирует свой простейший поток событий. Напомним, что в случае восстанавливаемых объектов основной характеристикой является параметр потока отказов.
Эксплуатация таких объектов может быть описана следующим образом: в начальный момент времени объект начинает работу и работает до отказа, после отказа происходит восстановление и объект вновь работает до отказа и т. д. Параметр потока отказов определяется через ведущую функцию
Q(t)
данного потока, представляющую собой математическое ожидание числа отказов за время 1:
где r(t) -
число отказов за время t.
Параметр потока отказов со(0 характеризует среднее число отказов, ожидаемых в малом интервале времени, и определяется по формуле (2.9): Ведущая функция может быть выражена через параметр потока отказов: Для стационарных пуассоновских потоков,
как было сказано выше, интенсивность отказов - величина постоянная и равна X;
при этом она совпадает с параметром потока отказов. Действительно, по свойству 3 стационарного пуассоновского потока среднее число отказов за время г равно: Q.(t)
= M = Xt,
следовательно, Средняя наработка на отказ.
Как уже говорилось, этот показатель представляет собой отношение наработки к математическому ожиданию числа отказов в течение этой наработки. Поскольку при стационарном потоке отказов M}
sup
x
|
P
(X
(t)
−
λ
t
λ
t
<
x)
−
Φ
(x)
|
⩽
C
0
λ
t
{\displaystyle \sup \limits _{x}{\biggl |}\mathbb {P} {\biggl (}{\frac {X(t)-\lambda t}{\sqrt {\lambda t}}}
где
C
0
{\displaystyle C_{0}}
- константа Берри-Эссеена .Применение
При таких условиях интенсивность отказов X(t)
оказывается постоянной величиной:
