Марківський випадковий процес

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

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

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

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

СМО з відмовами

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

Є каналів обслуговування, на які надходить потік заявок з інтенсивністю . Потік обслуговуванні має інтенсивність (величина, зворотна середньому часу обслуговування ). Потрібно знайти ймовірності станів СМО і характеристики її ефективності. Так як обидва потоку - заявок та звільнень - найпростіші, процес, що протікає в системі, буде марківським. Розглянемо її як систему з кінцевим безліччю станів:

-вільні всі канали;

- зайнятий рівно один канал;

…

- зайняті каналів;

- зайняті всі каналів.

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

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

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

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

Звідси отримаємо диференціальне рівняння для :

.

 

Аналогічно складаються диференціальні рівняння для ймовірностей інших станів. Нехай .

Знайдемо - імовірність того, що в момент система буде у стані . Ця ймовірність обчислюється як ймовірність суми трьох подій:

1) в момент система була в стані і не вийшла з нього за час ;

2) у момент система була в стані , а за час перешли в стан ;

3) у момент система була в стані , а за час перешли в стан .

Тоді

.

Диференціальне рівняння для :

.

Рівняння для ймовірності :

.

Отримано систему рівнянь для ймовірностей:

Ці рівняння називаються рівняннями Ерланга.

Що буде відбуватися з ймовірностями станів при ? Чи будуть ймовірності прагнути до кінцевих меж? Якщо ці межі існують і не залежать від початкового стану системи, то їх називають фінальними ймовірностями станів. У теорії випадкових процесів доводиться, що якщо число станів системи звичайно і з кожного з них за кінцеве число кроків можна перейти в будь-яке інше, то фінальні ймовірності існують. При в системі встановлюється граничний стаціонарних режим, в ході якого система змінює свої стани випадковим чином, але їх ймовірності вже не залежать від часу. Фінальну ймовірність стану можна витлумачити як середній відносний час перебування системи в цьому стані. Якщо фінальні ймовірності постійні, то їх похідні дорівнюють нулю. Щоб знайти фінальні ймовірності, замінимо в системі диференціальних рівнянь все ймовірності їх границями , а всі похідні вважаємо рівними нулю. Отримуємо систему алгебраїчних рівнянь:

Для цих ймовірностей виконується умова .

Вводимо позначення і розв'яжемо систему відносно невідомих ймовірностей:

Використовуючи умову , отримаємо ,

звідси , отримуємо фінальні ймовірності

.

Отримані формули називають формулами Ерланга. Ці формули дозволяють одержати показники ефективності роботи СМО.

Імовірність простою каналів обслуговування, коли немає заявок, виходить з формул Ерланга для фінальних ймовірностей:

. (2.62)

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

. (2.63)

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

 

. (2.64)

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

. (2.65)

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

. (3.66)

Частка каналів, що зайняті обслуговуванням:

. (2.67)