Найпростіші потоки марківські процеси та ланцюги рішення. Поняття про марківські випадкові процеси. Основні поняття Марківських процесів

30.05.2020 Онлайн сервіси

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

Але часто ще важливо знати, коликонкретно настане те чи інше подія у часі.

Коли подій багато і вони йдуть один за одним, то вони утворюють потік. Зауважимо, що події при цьому повинні бути однорідними, тобто чимось схожими одна на одну. Наприклад, поява водіїв на АЗС, які бажають заправити свій автомобіль. Тобто однорідні події утворюють певний ряд. У цьому вважається, що статистична характеристика цього явища (інтенсивність потоку подій) задана. Інтенсивність потоку подій вказує, скільки в середньомувідбувається таких подій за одиницю часу. Але коли саме станеться кожна конкретна подія, треба визначити методами моделювання. Важливо, що коли ми згенеруємо, наприклад, за 200 годин 1000 подій, їх кількість дорівнює приблизно величині середньої інтенсивності появи подій 1000/200 = 5 подій на годину, що є статистичною величиною, що характеризує цей потік в цілому.

Інтенсивність потоку у певному сенсі є математичним очікуванням кількості подій за одиницю часу. Але реально може виявитися, що в одну годину з'явиться 4 події, в іншій — 6, хоча в середньому виходить 5 подій на годину, тому однієї величини для характеристики потоку недостатньо. Другою величиною, що характеризує наскільки великий розкид подій щодо математичного очікування, є, як і раніше, дисперсія. Власне, саме ця величина визначає випадковість появи події, слабку передбачуваність моменту її появи. Про цю величину ми розповімо у наступній лекції.

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

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

Інтенсивність потоку λ - Це середня кількість подій в одиницю часу. Інтенсивність потоку можна розрахувати експериментально за такою формулою: λ = N/Tн, де N- Число подій, що відбулися за час спостереження Tн.

Якщо інтервал між подіями τ jдорівнює константі або визначений будь-якою формулою у вигляді: t j = f(t j- 1), то потік називається детермінованим. Інакше потік називається випадковим.

Випадкові потоки бувають:

ординарні: ймовірність одночасної появи двох і більше подій дорівнює нулю;
стаціонарні: частота появи подій λ (t) = const( t) ;
без післядії: ймовірність появи випадкової події залежить від моменту здійснення попередніх подій.

Пуасонівський потік

За стандарт потоку в моделюванні прийнято купувати пуасонівський потік.

Пуасонівський потік- Це простий потік без післядії.

Як раніше було зазначено, ймовірність того, що за інтервал часу (t 0 , t 0 + τ ) станеться mподій, визначається із закону Пуассона:

де a- Пуассон.

Якщо λ (t) = const( t) , то це стаціонарний потік Пуассона(Найпростіший). В цьому випадку a = λ · t . Якщо λ = var ( t) , то це нестаціонарний потік Пуассона.

Для найпростішого потоку ймовірність появи mподій за час τ дорівнює:

Ймовірність непояви (тобто жодного, m= 0 ) події за час τ дорівнює:

Рис. 28.2 ілюструє залежність P 0 від часу. Очевидно, що чим більше час спостереження, тим ймовірність не появи жодної події менше. Крім того, чим більше значення λ , Тим крутіше йде графік, тобто швидше зменшується ймовірність. Це відповідає тому, що й інтенсивність появи подій велика, то ймовірність непояви події швидко зменшується з часом спостереження.

Імовірність появи хоча б однієї події ( PХБ1С) обчислюється так:

так як PХБ1С+ P 0 = 1 (або з'явиться хоча б одна подія, або не з'явиться жодного, іншого не дано).

З графіка на рис. 28.3 видно, що ймовірність появи хоча б однієї події прагне згодом до одиниці, тобто за відповідного тривалого спостереження події така обов'язково рано чи пізно відбудеться. Чим довше ми спостерігаємо за подією (чим більше t), тим більша ймовірність того, що подія відбудеться - графік функції монотонно зростає.

Чим більша інтенсивність появи події (чим більше λ ), тим швидше настає ця подія, і тим швидше функція прагне одиниці. На графіку параметр λ представлений крутістю лінії (нахил дотичної).

Якщо збільшувати λ , то при спостереженні за подією протягом одного й того ж часу τ , Імовірність настання події зростає (див. рис. 28.4). Очевидно, що графік виходить із 0, оскільки якщо час спостереження нескінченно мало, то ймовірність того, що подія відбудеться за цей час, мізерна. І навпаки, якщо час спостереження нескінченно велике, то подія обов'язково відбудеться хоча б один раз, отже графік прагне до значення ймовірності рівної 1.

Вивчаючи закон, можна визначити, що: m x = 1/λ , σ = 1/λ , тобто для найпростішого потоку m x = σ . Рівність математичного очікування середньоквадратичного відхилення означає, що цей потік - потік без післядії. Дисперсія (точніше середньоквадратичне відхилення) такого потоку велика. Фізично це означає, що час появи події (відстань між подіями) погано передбачувано випадково перебуває в інтервалі m x σ < τ j < m x + σ . Хоча ясно, що в середньому воно приблизно дорівнює: τ j = m x = Tн/ N . Подія може з'явитись у будь-який момент часу, але в межах розкиду цього моменту τ jщодо m xна [– σ ; +σ ] (величину післядії). На рис. 28.5 показані можливі положення події 2 щодо осі часу при заданому σ . У даному випадкукажуть, що перша подія не впливає на другу, другу на третю тощо, тобто післядія відсутня.

За змістом Pодно r(див. лекцію 23. Моделювання випадкової події. Моделювання повної групи несумісних подій), тому, висловлюючи τ із формули (*) , остаточно визначення інтервалів між двома випадковими подіями маємо:

τ = -1/ λ · Ln ( r) ,

де r— рівномірно розподілене від 0 до 1 випадкове число, яке беруть із ГСЧ, τ - інтервал між випадковими подіями (випадкова величина τ j ).

приклад 1 . Розглянемо потік виробів, які приходять технологічну операцію. Вироби приходять випадковим чином – у середньому вісім штук за добу (інтенсивність потоку λ = 8/24 [од/год]). Необхідно промоделювати цей процес протягом Tн = 100 годин. m = 1/λ = 24/8 = 3 тобто в середньому одна деталь за три години. Зауважимо, що σ = 3. На рис. 28.6 представлений алгоритм, що генерує потік випадкових подій.

На рис. 28.7 показано результат роботи алгоритму - моменти часу, коли деталі приходили на операцію. Як видно, всього за період Tн = 100 виробничий вузол обробив N= 33 вироби. Якщо запустити алгоритм знову, то Nможе бути рівним, наприклад, 34, 35 або 32. Але в середньому, за Kпрогонів алгоритму Nбуде рівно 33.33… Якщо порахувати відстань між подіями tз iі моментами часу, що визначаються як 3 · i, то в середньому величина дорівнюватиме σ = 3 .

Моделювання неординарних потоків подій

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

Припустимо, що M k = 10 , σ = 4 (тобто, у середньому у 68 випадках зі 100 приходить від 6 до 14 вагонів у складі поїзда) та їх число розподілено за нормальним законом. У місце, зазначене (*) у попередньому алгоритмі (див. рис. 28.6), потрібно вставити фрагмент, показаний на рис. 28.8.

Приклад 2 . Дуже корисним у виробництві є вирішення наступного завдання. Який середній час добового простою обладнання технологічного вузла, якщо вузол обробляє кожен виріб випадковий час, заданий інтенсивністю потоку випадкових подій λ 2? При цьому експериментально встановлено, що привозять вироби на обробку також у випадкові моменти часу, задані потоком λ 1 партіями по 8 штук, причому розмір партії коливається випадково за нормальним законом m = 8 , σ = 2 (див. лекцію 25). До початку моделювання T= 0 складі виробів був. Необхідно промоделювати цей процес протягом Tн = 100 годин.

На рис. 28.9 представлений алгоритм, що генерує випадковим чином потік приходу партій виробів на обробку та потік випадкових подій - виходу партій виробів з обробки.

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

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

Tпр. пор. = 24 · ( t 1 ін. t 2 ін. t 3 ін. t 4 пр. + … + t Nін)/ Tн.

Завдання 1 . Змінюючи величину σ , встановіть залежність Tпр. пор. ( σ ) . Задаючи вартість за простий вузл 100 євро/год, встановіть річні втрати підприємства від нерегулярності в роботі постачальників. Запропонуйте формулювання пункту договору підприємства з постачальниками «Величина штрафу за затримку постачання виробів».

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

Моделювання нестаціонарних потоків подій

У ряді випадків інтенсивність потоку може змінюватися з часом λ (t). Такий потік називається нестаціонарним. Наприклад, середня кількість за годину машин швидкої допомоги, що залишають станцію за викликами населення великого містапротягом доби може бути різним. Відомо, наприклад, що найбільша кількість викликів падає на інтервали з 23 до 01 години ночі та з 05 до 07 ранку, тоді як в інші години воно вдвічі менше (див. рис. 28.11).

У цьому випадку розподіл λ (t) може бути задано або графіком, або формулою, або таблицею. На алгоритмі, показаному на рис. 28.6 в місце, позначене (**), потрібно буде вставити фрагмент, показаний на рис. 28.12.

4. Моделювання за схемою марківських випадкових процесів

Для обчислення числових параметрів, що характеризують стохастичні об'єкти, потрібно побудувати деяку ймовірну модель явища, що враховує випадкові фактори, що його супроводжують. Для математичного опису багатьох явищ, що розвиваються у формі випадкового процесу, може бути успішно застосований математичний апарат, розроблений в теорії ймовірностей для так званих марківських випадкових процесів. Пояснимо це поняття. Нехай є певна фізична система S, стан якої змінюється з часом (під системою Sможе розумітися будь-що: технічний пристрій, ремонтна майстерня, обчислювальна машина і т. д.). Якщо стан Sзмінюється за часом випадковим чином, кажуть, що в системі Sпротікає випадковий процес. Приклади: процес функціонування ЕОМ (надходження замовлень на ЕОМ, вид цих замовлень, випадкові виходи з ладу), процес наведення на мету керованої ракети (випадкові обурення (перешкоди) у системі управління ракетою), процес обслуговування клієнтів у перукарні або ремонтній майстерні (випадковий характер) потоку заявок (вимог), що надійшли з боку клієнтів).

Випадковий процес називається марківським процесом (або «процесом без наслідку»), якщо для кожного моменту часу t0 ймовірність будь-якого стану системи в майбутньому (при t> t0 ) залежить тільки від її стану в теперішньому (при t= t0 ) і залежить від цього, як і як система прийшла у цей стан (т. е. як розвивався процес у минулому). Нехай Sтехнічний пристрій, який характеризується деяким ступенем зношеності S. Нас цікавить, як воно працюватиме далі. У першому наближенні характеристики роботи системи в майбутньому (частота відмов, потреба в ремонті) залежать від стану пристрою теперішній моменті не залежать від того, коли і як пристрій досяг свого реального стану.

Теорія марківських випадкових процесів – великий розділ теорії ймовірності з широким спектром додатків (фізичні явища типу дифузії або перемішування шихта під час плавлення доменної печі, процеси утворення черг).

4.1. Класифікація марківських процесів

Марківські випадкові процеси поділяються на класи. Перша класифікаційна ознака – характер спектра станів. Випадковий процес (СП) називається процесом з дискретними станами, якщо можливі стани системи S1,S2,S3…можна перерахувати, а сам процес полягає в тому, що іноді система S стрибком (миттєво) перескакує з одного стану в інший.

приклад. Технічний пристрійскладається з двох вузлів I та II, кожен з яких може вийти з ладу. Стану: S1– обидва вузли працюють; S2– перший вузол відмовив, другий робітник; S 3 – другий вузол відмовив, перший робітник; S4– обидва вузли відмовили.

Існують процеси з безперервними станами (плавний перехід зі стану до стану), наприклад, зміна напруги в освітлювальній мережі. Розглянемо лише СП з дискретними станами. І тут зручно користуватися графом станів, у якому можливі стану системи позначаються вузлами, а можливі переходи - дугами.

Друга класифікаційна ознака – характер функціонування в часі. СП називається процесом з дискретним часом, якщо переходи системи зі стану в стан можливі тільки в певні, заздалегідь фіксовані моменти часу: t1,t2…. Якщо перехід системи зі стану на стан можливий у будь-який наперед невідомий випадковий момент, то говорять про СП з безперервним часом.

4.2. Розрахунок марківського ланцюга з дискретним часом

Sз дискретними станами S1,S2, …Snта дискретним часом t1,t2, … ,tk, …(Кроки, етапи процесу, СП можна розглядати як функцію аргументу (номери кроку)). У випадку СП полягає у тому, що відбуваються переходи S1® S1® S2® S3® S4® S1® … у моменти t1,t2,t3 ….

Будемо позначати подію, яка полягає в тому, що після k– кроків система перебуває в стані Si. За будь-якого kподії https://pandia.ru/text/78/060/images/image004_39.gif "width="159".

Така випадкова послідовність подій називається марківським ланцюгом. Описуватимемо марківський ланцюг (МЦ) за допомогою ймовірностей станів. Нехай – ймовірність того, що після k- кроків система перебуває в стані Si. Легко бачити, що " k DIV_ADBLOCK389">

Користуюся введеними вище подіями. Сума членів у кожному рядку матриці повинна дорівнювати 1. Замість матриці перехідних ймовірностей часто використовують розмічений граф станів (позначають на дугах ненульові ймовірності переходів, ймовірності затримки не потрібні, оскільки вони легко обчислюються, наприклад P11=1-(P12+P13)). Маючи у розпорядженні розмічений граф станів (або матрицю перехідних ймовірностей) та знаючи початковий стан системи, можна знайти ймовірності станів p1(k),p2(k),…pn(k)" k.

Нехай початковий стан системи Smтоді

p1(0)=0 p2(0)=0…pm(0)=1…pn(0)=0.

Перший крок:

p1(1)=Pm1, p2(1)=Pm2,…pm(1)=Pmm,… ,pn(1)=Pmn.

Після другого кроку за формулою повної ймовірності отримаємо:

p1(2)=p1(1)P11+p2(1)P21+…pn(1)Pn1,

pi(2)=p1(1)P1i+p2(1)P2i+…pn(1)Pni абоhttps://pandia.ru/text/78/060/images/image010_33.gif" width="149" height="47"> (i=1,2,..n).

Для неоднорідний МЦ Перехідні можливості залежать від номера кроку. Позначимо перехідні можливості для кроку k через .

Тоді формула для розрахунку ймовірностей станів набуває вигляду:

4.3. Марківські ланцюги з безперервним часом

4.3.1. Рівняння Колмогорова

Насправді значно частіше трапляються ситуації, коли переходи системи зі стану на стан відбувається у випадкові моменти часу, які заздалегідь вказати неможливо: наприклад, вихід з ладу будь-якого елемента апаратури, закінчення ремонту (відновлення) цього елемента. Для опису таких процесів у ряді випадків може бути з успіхом застосована схема марковського випадкового процесу з дискретними станами та безперервним часом – безперервний ланцюг Маркова. Покажемо, як виражаються ймовірності станів такого процесу. Нехай S=(S1,S2,…Sn).Позначимо через pi(t)- Імовірність того, що в момент tсистема Sперебуватиме у стані ). Очевидно. Поставимо завдання – визначити для будь-кого tpi(t). Замість перехідних ймовірностей Pijвведемо на розгляд щільності ймовірностей переходу

Якщо не залежить від t, говорять про однорідний ланцюг, інакше - про неоднорідний. Нехай нам відомі всім пар станів (заданий розмічений граф станів). Виявляється, знаючи розмічений граф станів, можна визначити p1(t),p2(t).pn(t)як функції часу. Ці ймовірності задовольняють певного виду диференціальних рівнянь (рівняння Колмогорова).

Інтегрування цих рівнянь при відомому початковому стані системи дасть ймовірності станів як функції часу. Зауважимо, що p1+p2+p3+p4=1і можна обійтися трьома рівняннями.

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

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

При розгляді процесів, що протікають у системі з дискретними станами та безперервним часом, часто буває зручно уявити собі процес так, ніби переходи системи зі стану в стан відбуваються під дією якихось потоків подій. Потоком подій називається послідовність однорідних подій, що йдуть одна одною в якісь, взагалі кажучи, випадкові моменти часу. (Потік викликів на телефонній станції; потік несправностей (збоїв) ЕОМ; потік вантажних складів, що надходять на станцію; потік відвідувачів; потік пострілів, спрямованих на мету). Зображатимемо потік подій послідовністю точок на осі часу ot. Положення кожної точки на осі є випадковим. Потік подій називається регулярним , якщо події слідують одна одною через суворо певні проміжки часу (рідко зустрічається практично). Розглянемо спеціального типу потоки, при цьому введемо ряд визначень. 1. Потік подій називається стаціонарним Якщо ймовірність попадання того чи іншого числа подій на ділянку часу довжиною залежить тільки від довжини ділянки і не залежить від того, де саме на осі ot розташована ця ділянка (однорідність за часом) - ймовірнісні характеристики такого потоку не повинні змінюватися від часу. Зокрема так звана інтенсивність (або щільність) потоку подій (середня кількість подій в одиницю часу) постійна.

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

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

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

Розглянемо осі оtде спостерігається потік подій, деяка ділянка довжини t, що починається в момент t0 і що закінчується в момент t0 + t. Неважко довести (доказ дається у всіх курсах теорії ймовірності), що ймовірність попадання на цю ділянку рівно m подій виражається формулою:

(m=0,1…),

де а- Середня кількість подій, що припадає на ділянку t.

Для стаціонарного (найпростішого) пуасонівського потоку а=lt, тобто не залежить від того, де на осі otвзято ділянку t. Для нестаціонарного пуассонівського потоку величина авиражається формулою

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

Розглянемо осі otнайпростіший потік подій із постійною інтенсивністю l. Нас цікавитиме інтервал часу T між подіями у цьому потоці. Нехай l – інтенсивність (середнє число подій в 1 часі) потоку. Щільність розподілу f(t) випадкової величини Т(інтервал часу між сусідніми подіями у потоці) f(t)= le- lt (t> 0) . Закон розподілу з такою густиною називається показовим (експоненційним). Знайдемо чисельні значення випадкової величини Т: математичне очікування (середнє значення) та дисперсію left">

Проміжок часу Тміж сусідніми подіями у найпростішому потоці розподілено за показовим законом; його середнє значення та середнє квадратичне відхилення рівні , де l – інтенсивність потоку. Для такого потоку ймовірність появи на елементарній ділянці часу ∆t рівно однієї події потоку виражається як . Цю ймовірність ми називатимемо «елементом ймовірності появи події».

Для нестаціонарного пуассонівського потоку закон розподілу проміжку Т не буде показовим. Вигляд цього закону залежатиме, по-перше, від того, де на осі otрозташована перша з подій, по-друге, від виду залежності. Однак, якщо змінюється порівняно повільно і його зміна за час між двома подіями невелика, то закон розподілу проміжку часу між подіями можна наближено вважати показовим, вважаючи в цій формулі величину, що дорівнює середньому значенню на тій ділянці, яка нас цікавить.

4.3.3. Пуассонівські потокиподій та

безперервні марківські ланцюги

Розглянемо деяку фізичну систему S=(S1,S2,…Sn)яка переходить зі стану в стан під впливом якихось випадкових подій (виклики, відмови, постріли). Будемо собі це уявляти так, ніби події, що переводять систему зі стану в стан, є потоками подій.

Нехай система Sу момент часу tперебуває у стані Siі може перейти з нього в стан Sjпід впливом якогось пуасонівського потоку подій з інтенсивністю lij: як тільки з'являється перша подія цього потоку, система миттєво переходить з Siв Sj..gif" width="582" height="290 src=">

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

Нехай є фізична система S=(S1,S2,…Sn), В якій протікає марківський випадковий процес з безперервним часом (безперервний ланцюг Маркова). Припустимо, що lij=const, тобто всі потоки подій найпростіші (стаціонарні пуассонівські). Записавши систему диференціальних рівнянь Колмогорова для ймовірностей станів та проінтегрувавши ці рівняння за заданих початкових умов, ми отримаємо p1(t),p2(t),…pn(t), за будь-якого t. Поставимо наступне питання, що відбуватиметься із системою Sпри t® ¥. Чи будуть функції pi(t) прагнути до якихось меж? Ці межі, якщо вони є, називаються граничними ймовірностями станів. Можна довести теорему: якщо кількість станів S звісно і з кожного стану можна перейти (за те чи інше число кроків) у кожний інший, то граничні ймовірності станів існують і не залежать від початкового стану системи. Припустимо, що встановлена умова виконана і граничні ймовірності існують (i=1,2,…n), .

Таким чином, при t® ¥ в системі Sвстановлюється певний граничний стаціонарний режим. Сенс цієї ймовірності: вона є нічим іншим, як середнє відносне час перебування системи у цьому стані. Для обчислення piв системі рівнянь Колмогорова, що описують ймовірності станів, потрібно покласти всі ліві частини (похідні) рівними 0. Систему лінійних алгебраїчних рівнянь, що виходять, треба вирішувати спільно з рівнянням .

4.3.5. Схема загибелі та розмноження

Ми знаємо, що маючи у розпорядженні розмічений граф станів, можна легко написати рівняння Колмогорова для ймовірностей станів, а також написати та вирішити рівняння алгебри для фінальних ймовірностей. Для деяких випадків вдається останні рівняння вирішити заздалегідь, у буквеному вигляді. Зокрема, це вдається зробити, якщо граф станів системи є так званою «схемою загибелі та розмноження».

https://pandia.ru/text/78/060/images/image044_6.gif" width="73" height="45 src="> (4.4)

З другого, з урахуванням (4.4), отримаємо:

https://pandia.ru/text/78/060/images/image046_5.gif" width="116" height="45 src="> (4.6)

і взагалі, для будь-якого k (від 1 до N):

https://pandia.ru/text/78/060/images/image048_4.gif" width="267" height="48 src=">

звідси отримаємо вираз для р0.

(4. 8)

(дужку ми звели в ступінь -1, щоб не писати двоповерхових дробів). Решта ймовірності виражені через р0 (див. формули (4.4) - (4.7)). Зауважимо, що коефіцієнти при p0 у кожній з них є не що інше, як послідовні члени ряду, що стоїть після одиниці у формулі (4.8). Отже, обчислюючи р0, ми вже знайшли ці коефіцієнти.

Отримані формули дуже корисні при вирішенні найпростіших завдань теорії масового обслуговування.

Обчислювальні технології

Том 13, Спеціальний випуск 5, 2008

Дослідження напівмарківського потоку подій

А. А. Назаров, С. В. Лопухова Томський державний університет, Росія e-mail: [email protected] pmk. tsu. ru, [email protected] ru

І.Р. Гарайшина

Філія Кемеровського державного університетуу м. Анжеро-Судженську, Росія e-mail: [email protected]

У підписаній роботі, semimarkovian process is considered. Limiting model is considered. Результати analytical treatment of limiting model are compared with results, obtained by asymptotical method.

Вступ

Існує проблема розширення класу математичних моделей потоків однорідних подій. Найчастіше класичні моделі випадкових потоків подій неможливо знайти адекватні реальним інформаційним, телекомунікаційним потокам. p align="justify"> Моделей пуассоповського і найпростішого потоків часто буває недостатньо для більш правдоподібного, наближеного до реальності опису вхідних потоків для систем масового обслуговування. Незважаючи на те, що існують потоки фазового типу і модульовані пуассонівські потоки, які більш адекватні реальним ситуаціям, великий інтерес представляють моделі напівмарківського потоку, окремим випадком яких є потоки марківського відновлення і всі перераховані вище потоки. Методи дослідження таких моделей досить складні та призводять до значних математичних проблем. Тому поряд із завданням розширення класів потоків існує проблема розвитку методів їхнього дослідження.

1. Математична модель

Випадковим потоком однорідних подій (потоком) називатимемо впорядковану послідовність

t\< ¿2 < ■ ■ ■

випадкових величин tm – моментів настання подій у потоці.

Нехай задана напівмарківська матриця A(x) з елементами Aklk2(x), Матрця P = lim A(x) є стохастичною, тому при заданому початковому розподілі

вона визначає деякий ланцюг Маркова k (tm) з дискретним часом, яку називатимемо вкладеним у напівмарківський потік ланцюгом Маркова,

А. А. Назаров, С. В. Лопухова, І. Р. Гарайшина

Випадковий потік однорідних подій називатимемо напівмарківським, якщо ймовірнісний закон формування послідовності (1) визначається початковим розподілом та рівностями

Ак1к2(х) = Р(к(Ьт+1) = к2, Ьт+1 - Ьт< х ^^т) = к\ }

за всіх т > 1.

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

Завданням дослідження даної роботи є встановлення розподілу ймовірностей Р(п, Ь) = Р(п(Ь) = п) при стаціонарному функціонуванні ергодичної ланцюга Маркова до (1т). Очевидно, процес п(Ь) - немарківський, тому визначимо ще два випадкові процеси: г(Ь) - довжину інтервалу від моменту часу Ь до моменту наступу чергової події в потоці, що розглядається, до(Ь) - безперервний зліва процес з безперервним часом, значення якого на інтервалі (Ьт,Ьт+1) постійні і визначаються рівностями до (Ь) = до (Ьт+1).В силу зроблених визначень випадковий процес (к(Ь), п(Ь), г(Ь)) є тривимірним марківським процесом із безперервним часом.

Зауважимо, що випадковий процес до(Ь) не є напівмарківським у класичному визначенні , оскільки напівмарківський процес Б(Ь) безперервний праворуч і, як зазначено в , для його перехідних ймовірностей не існує диференціальних еволюційних рівнянь Колмогорова, тоді як запропонований вище процес (к(Ь), п(Ь), г(Ь)) - марківський, тому для його розподілу ймовірностей

Р(к, п, г,Ь) = Р(к(Ь) = к, п(Ь) = п, г(Ь)< г} (2)

неважко скласти систему диференціальних рівнянь Колмогорова дР (к, п, г, Ь) дР (к, п, г, Ь) дР (к, п, 0, Ь)

^ дГ (і,1Ь - 1, 0,Ь) А (\ 2-^-

дЬ дг дг ^ дг

Позначимо

Н(к, і, г, г) = ^ е"іПР(к, п, г, Ь),

де ] = ¡~ ~~ уявна одиниця. Для цих функцій із системи диференціальних рівнянь Колмогорова можна записати

дН (к, і, г, Ь) дН (к, і, г, Ь) дН (к, і, 0, Ь), і ^ дН (і, і, 0, Ь)

дЬ дг дг ^ дг

Позначимо Н (і,г,Ь) = (Н (1,і,г,Ь) ,Н (2,і,г,Ь),...) рядок вектор-функції, тоді систему рівнянь (3) перепишемо в матричному вигляді

дН(і,г,г) _ дН(і,г,г) дН(і,0,г) Мц,г ч п т

дг дг + дг 1 [) "" [ )

рішення якої задовольняє початковій умові H(u,z, 0) = R(z), де I - одинична матриця, а стаціонарний розподіл R(z) двовимірного марківського процесу (k(t), z(t)) є розв'язанням задачі Коші

<Ш = <Ш(1-Мг)),

і визначається рівністю R(z) = seiт/(Р - A(x))dx, де aei = Тут г - вектор-

рядок стаціонарного розподілу ймовірностей значень вкладеного ланцюга Маркова

k(tm); E - одиничний вектор-стовпець та матриця A = (P - A(x))dx.

2. Догранична модель

Нехай маємо диференціальне рівняння (4), розв'язок H(u,z,t) якого задовольняє початковій умові H(u, z, 0) = R(z). Тоді перетворення Фур'є - Стілтьєса

ф>(u,a,t) = / ejaz dz H (u, z, t) вектор-функції H (u,z,t) задовольняє рівнянню

дф(і,а,Ь). . дН (і, 0,Ь), .*. . гЛ, .

т = ~заф(щ а, +-(е?іА*(а) - /) (5)

та початковій умові

ф(і,а, 0) = R*(a) = ^ е>а2

де А*(а) = J е>а"2dA(z). Рішення рівняння (5) має вигляд про

ф(і, а,1) = е~заЬ [II*(а) + I (¿>іА*(а) - I) dт]. (6)

Спрямувавши Ь в нескінченність у виразі (6), отримаємо перетворення Фур'є по т

дН (і, 0, т) ^ ^ "л

з вектор-функції---. Виконавши зворотне перетворення Фур'є, визначимо,

I e-j *A*(aj) 1 da.

А. А. Назаров, С. В. Лопухова, І. Р. Рарайшшіа

Тепер рівність (6) можна записати у вигляді

ф(ща,г) = е-аЬ Я*(а) +

+ - / е]ат I е~зутК*(у) (/ - е>іА*(у)) 1 Ау (е"іА*(а) - /)<*г). (7)

Знаючи, що Н(і, ж,г) = Н(і,г) = ф(і, 0,1), отримаємо вираз для вектор-функції Н(і,г):

Тоді розподіл ймовірностей Р(п, г) числа подій, що настали за час г, є

ції Н(і,Ь) = МеЕіп(Ь = Н(і,Ь)Е, воно має вигляд

1 З а1 Г 1 - е-™Ь

Р(п,1) = - е~зипНШ)Е(1і = - / -^-5

I - А*(у) А*(у)п-1Ейу, (8)

I - А * (у) Е<1у

Висновок

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

МеГап(1) = ^«(ге^+^ае^+^аез*)

де коефіцієнти 831 а2, аз3 для напівмарківського потоку визначаються аналогічно тому, як це зроблено в роботах . Отримані рівності (8) визначають розподіл ймовірностей Р(п,г) числа подій, що настали в стаціонарному напівмарківському потоці, заданому напівмарківською матрицею А(х) та її перетворенням А*(х) Фур'є - Стілтьєса чисельні значення ймовірностей Р(п, г) для досить широкого клае матриць А * (х) і значень г. Але можливості чисельної реалізації обмежені обчислювальними ресурсами. Для досить великих значень г природно застосувати метод асимптотичного аналізу напівмарківського потоку аналогічно тому, як це виконано для маркового потоку відновлення в роботі і просіяного потоку марковського відновлення в роботі . Наявність чисельного алгоритму (8) дозволяє визначити сферу застосування асимптотичних результатів. Для розглянутих потоків з трьома станами вкладеного ланцюга Маркова відстань Колмогорова - Смирнова між розподілами,

отриманими асимптотично і за формулами (8), не перевищує 2-3% для певних значень t = Т, це дозволяє стверджувати, що при t> Т ефективно застосування асимптотичних результатів, а при t< Т целесообразно использовать формулы (8), полученные в данной работе.

Список літератури

Королюк B.C. Стохастичні моделі систем. Київ: Наук, думка, 1989. 208 с.

Назаров A.A., Лопухова C.B. Дослідження потоку марківського відновлення асимптотичним способом другого порядку // Матер. Міжнар. наук. конф. "Математичні методи підвищення ефективності функціонування телекомунікаційних мереж". Гродно, 2007. С. 170-174.

Лопухова C.B. Вивчення напівмарківського потоку асимптотичним способом третього порядку // Матер. VI Міжнар. науково-практ. конф. "Інформаційні технології та математичне моделювання". Томськ: Вид-во Том. ун-ту, 2007. Ч. 2. С. 30-34.

Мета лекції: освоєння понять потік подій, найпростіший потік подій, Марківський процес.

1. Потік подій. Властивості потоків подій. Найпростіший потік подій. Формула Пуассон.

2. Процес обслуговування як Марківський процес.

3. Одноканальна СМО з очікуванням.

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

Прикладами можуть бути:

Потік дзвінків на телефонній станції;

Потік збоїв комп'ютера;

Потік пострілів, спрямованих на мету, і т.д.

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

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

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

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

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

У системах телекомунікацій потік прийнято вважати простим.

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

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

Параметромпотоку називається межа

де – ймовірність того, що на інтервалі з'являться заявки.

Інтенсивністю потоку називається середнє число подій в одиницю часу.

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

Для стаціонарного та ординарного потоку λ=μ.

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

Найпростіший потік підпорядковується пуасонівському закону розподілу

де – інтенсивність потоку;

Кількість подій, що з'являються за час .

Найпростіший потік можна встановити функцією розподілу проміжку між сусідніми викликами

F(t)=P(z t),

P(z>t) рівносильна ймовірності того, що в проміжку довжиною t не надійде жодного виклику.

F(t)=P(z>t)=1- (t)=1-

Цей закон розподілу випадкової величини називається показовим.

Властивості та характеристики найпростішого потоку:

а) для найпростішого потоку математичне очікування та середньоквадратичне відхилення величини проміжку z дорівнюють між собою MZ= σz=1/λ;

б) Математичне очікуваннята дисперсія числа викликів i за проміжок часу t рівні між собою Mi = Di = t.

Збіг цих величин використовують практично під час перевірки реального потоку для відповідності його найпростішому.

СМО - система, що передбачає наявність у ній 2х процесів: надходження заявок та обслуговування заявок.

Умовно схема подається у вигляді

І накопичувач До

Обслуговуючий прилад

Процес надходження заявок – процес за часом.

Потік подій – послідовність моментів часу настання будь-яких подій.

З будь-якої СМО пов'язані 3 потоки:

1) вхідний потік. Послідовність моментів часу надходження заявок

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

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

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

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

Потік рекурентний, Якщо інтервали часу між подіями - випадкові величини, розподілені по тому самому закону.

Потік зв-ся однорідним, якщо він х-ся лише безліччю (ti) настали подій. Неоднорідний– якщо він описується безліччю (ti, fi), де ti – моменти часу настання подій, fi – ознака заявки.

Самі СМО поділяються на СМО з відмовами та СМО з чергами. СМО з чергами поділяється на з обмеженою чергою та з необмеженою чергою. Окремий випадок – обмежений час очікування у черзі.

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

1) FIFO (first in – first out) – у порядку надходження;

2) LIFO (last in – first out) – першою обслуговується останньою;

3) SIRO (service in random order) – у випадковому порядку;

4) – пріоритетні системи. (Абсолютний і відносний пріоритети. При відносному заявки вибудовуються за значенням пріоритету - спочатку високі, потім нижче.)

Для короткої характеристики СМО Д.Кендал ввів символіку (нотацію)

m – число обслуговуючих каналів;

n – кількість місць очікування (ємність накопичувача).

k – у джерел.

A і B характеризують відповідно вхідний потік та потік обслуговування, задаючи функцію розподілу інтервалів між заявками у вхідному потоці та функцію розподілу часів обслуговування.

А і можуть приймати значення:

D – детерміноване розподілення;

М – показове;

Е r - Розподіл Ерланга;

H r – гіперпоказова;

G - Розподіл загального виду.

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

9. Найпростіший потік, його властивості та значення при дослідженні смо.

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

1) Потік стаціонарнийякщо ймовірність надходження заданого числа подій протягом інтервалу часу фіксованої довжини залежить тільки від тривалості інтервалу і не залежить від його розташування на часовій осі.

2) Потік ординарнийякщо ймовірність появи двох або більше подій протягом елементарного інтервалу часу
→0 є величина нескінченно мала порівняно з ймовірністю появи однієї події цьому інтервалі.

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

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

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

ймовірність того, що за інтервал часу τ станеться рівно mподій.

Умова відсутність наслідку (заявки надходять незалежно одна від одної) найбільш істотно для найпростішого потоку.

пуассонівського розподілу.

Імовірність того, що за не відбудеться жодної події

Імовірність, що за час відбудеться хоча б одна подія

Іноді зручніше аналізувати систему, розглядаючи інтервали між подіями T:

Це показовий закон з інтенсивністю .

Математичне очікування та середнє квадратичне для T:

Властивість відсутність післядії дозволяє використовувати дослідження найпростішого потоку апарат Марківських ланцюгів.

Введемо стану системи в такий спосіб – вважаємо систему, що у стані S, якщо у момент часу t у системі перебуває S заявок.

Визначимо можливість для системи, стан якої визначається лише надходження заявок, що в момент
система залишиться у тому стані. Очевидно, ця ймовірність визначається тим, що за інтервал
не надійде жодної заявки

(S = 0, 1, 2 ...)

Розкладаючи в ряд, отримаємо:

Імовірність отримання хоча б однієї заявки

Аналогічні співвідношення можна одержати, розглядаючи процес обслуговування заявок.

Найпростіші чи близькі до них потоки часто трапляються практично.

При підсумовуванні досить великої кількості потоків з післядією, виходить потік з післядією. У найпростішому потоці приблизно 68% невеликих інтервалів

При ймовірнісному просіюванні найпростішого потоку виходить найпростіший потік

10. Безперервно-стохастичні моделі (Q-схеми). Одноканальна СМО із блокуванням. Побудоваграфа станів.

При побудові моделей такого роду зазвичай використовуються розгляду моделюваних об'єктів, як Систем Масового Обслуговування (СМО).

Таким чином, можуть бути представлені різні за своєю фізичною природою процеси – економічні, технічні, виробничі тощо.

У СМО можна виділити два стохастичні процеси:

Надходження заявок на обслуговування;

Обслуговування заявок.

Потік подій- Послідовність подій, що відбуваються одна за одною в деякі моменти часу. У СМО виділятимемо два потоки:

Вхідний потік: безліч моментів надходження до системи заявок;

Потік обслуговування: багато моментів закінчення обробки системою заявок.

У випадку СМО елементарного виду може бути представлено так