Контрольні запитання

1. Яка модель реалізації алгоритму вибрана для визначення часу обслуговування заявки у відповідній моделі СМО.

2. Як знайти ймовірність перебування випадкового процесу у групі станів.

3. Яким чином можна побудувати модель програми у вигляді марківського ланцюга та обчислити час її виконання.

Рекомендована література

1. М.Зелковиц, А.Шоу, Дж.Геннон. Принципы разработки программного обеспечения.-М. «Мир».1982, 368с.

2. Е.С.Вентцель. Исследование операций. - М. «Советское радио», 1972, 552с.

3. И.В.Романовский. Дискретный анализ: Учебное пособие для студентов,3-е изд, -СПб:«Невский диалект»; БХВ Петербург, 2003.

4. Е.В.Бережная. Математические методы моделирования экономических систем. -М. «Финансы и статистика», 2001.

5. Тьюарсон. Разреженные матрицы. – М. «Мир», 1977, 192с.

4.Лекція 4 Потоки подій

План лекції

1. Потік подій. Найпростіший потік та його властивості.

2. Пуасонівські потоки подій і безперервні харківські ланцюги.

3. Граничні ймовірності станів.

1. Потік подій. Найпростіший потік і його властивості.

При розгляді систем з дискретними станами й безперервним часом часто доводиться мати справу з так званими потоками подій.

Потоком подійназивається послідовність однорідних подій, що випливають одна за одною у якісь випадкові моменти часу.

Наприклад: потік відмов обчислювальної системи, потік звертань до ЗП й т.д.

У загальному випадку переходи системи зі стану в стан відбуваються через послідовність подій, тобто потоку подій. Тому має сенс розглянути також потоки й з'ясувати їхні властивості.

Зобразимо потік подій як послідовність точок на осі часу

Положення кожної точки на осі є випадковим.

Потік подій називається регулярним, якщо події випливають одна за одною через строго визначенні проміжки часу.

Такий потік досить рідко зустрічається на практиці, що й побачимо надалі, та становить інтерес як деякий граничний випадок.

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

1. Потік подій називають стаціонарним, якщо ймовірність влучення того або іншого типу подій на ділянку часу довжиною τ залежить тільки від довжини ділянки й не залежить від того, де саме на осі t розташована ця ділянка.

2. Потік подій називають потоком без післядії, якщо для будь-яких непересічних ділянок часу число подій, що попадають на один з них, не залежить від того, скільки подій потрапило не на іншій.

3. Потік подій називається ординарним, якщо ймовірність влучення на елементарну ділянку двох або більше подій неважливо мала в порівнянні з імовірністю влучення однієї події.

Розглянемо більш докладно ці властивості:

Стаціонарністьозначає однорідність за часом. Імовірнісні характеристики такого потоку не повинні змынюватися залежно від часу. Інтенсивність (або щільність) потоку подій (середнє число подій в одиницю часу) для стаціонарного потоку повинна залишатися постійною для всього розглянутого періоду. Наприклад, потік викликів на телеграфній станції між 12 і 13 годинами.

Відсутність післядіїозначає, що події, що утворять потік, з'являються в послідовні моменти часу незалежно одна від одної . Наприклад, потік автомобілів на бензозаправку.

Ординарність – означає, що події відбуваються поодинці, а не парами, трійками й т.д.

Якщо в неординарному потоці події відбуваються лише парами або трійками. Це можна розглянути як ординарний потік пар, трійок і т.п. Справа буде складнішою якщо число подій, що утворять такий «пакет» - випадково. Тоді доводиться розглядати не тільки потік пакетів, але й випадкову величину числа подій у пакеті.

Із усього різноманіття потоків виділимо потік, що називається простішим. Такий потік має всі три зазначені властивості одночасно.

Наприклад, доведено, що при суперпозиції досить великої кількості потоків, що володіють післядією (аби тільки вони були стаціонарними і ординарними), утвориться сумарний потік, який можна розглядати як найпростіший.

Якщо потік подій не має післядії, ординарний, але не є стаціонарним він називається нестаціонарним пуассоновским потоком.

У такому потоці інтенсивність залежить від часу, тобто

λ=λ(t)

Для найпростішого потоку

λ =const

Пуассоновский потік подій (як стаціонарний, так і нестаціонарний) тісно пов'язані з відомим розподілом Пуассона.

Відповідно до цього розподілу ймовірність влучення дорівнює m подій за інтервал часу тривалістю τ дорівнює

де

α=λτ, тобто не залежить від того, де на осі t обрана ця ділянка. Для нестаціонарного пуассоновского потоку

а значить залежить від того, у якій точці t₀ починається ділянка τ.

Запишемо наступні важливі співвідношення для найпростішого потоку:

Нас цікавить інтервал часу T між сусідніми подіями в такому потоці. Очевидно T - випадкова величина.

Функція розподілу величини T буде

F(t)= 1-e^-λt,

а щільність розподілу f(t) випадкової величини T буде дорівнювати:

f(t)=λe^-λt

Такий закон розподілу називається показовим або експонентним, а величина λ – називається параметром послідовного закону. Характеристики випадкової величини T – математичне очікування m_t і дисперсія D_t має вигляд:

m_{t =} 1/λ

D_{t =} 1/λ^2.

Середньоквадратичне відхилення:

σ_t = √D_t =1/λ

Для показового закону розподілу математичне очікування й середньоквадратичне відхилення рівні один одному й зворотні параметру λ.

Графік закону розподілу має вигляд:

Інакше кажучи, проміжок часу T між сусідніми подіями в найпростішому потоці розподілений за показовим законом, його середнє значення й середньоквадратичне відхилення дорівнює 1/λ, де λ - інтенсивність потоку.

Існує ще одне цікаве співвідношення.

Імовірність того, що на ділянці тривалістю ∆t з'явиться якась одна подія потоку дорівнює

P₁(∆t)= 1-e^-λ∆t, розкладаючи в ряд e-e^-λ∆t

і зневажаючи величинами більш високого порядку одержимо:

P₁(∆t)≈λ∆t