Поняття марківського випадкового процесу

 

Процес роботи СМО є випадковим процесом.

Під випадковим (імовірнісним або стохастичним) процесом розуміється процес зміни в часі стану якої-небудь системи відповідно до імовірнісних закономірностей.

Процес називається процесом з дискретними станами, якщо його можливі стани S₁, S₂, S₃... можна наперед перерахувати, а перехід системи із стану в стан відбувається миттєво (стрибком). Процес називається процесом з безперервним часом, якщо моменти можливих переходів системи із стану в стан не фіксовані наперед, а випадкові.

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

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

Приклад марківського процесу: система S - лічильник у таксі. Стан системи у момент t характеризується числом кілометрів (десятих доль кілометрів), пройдених автомобілем до даного моменту. Хай у момент t лічильник показує S₀. Вірогідність того, що у момент t > t₀ лічильник покаже те або інше число кілометрів (точніше, відповідне число рублів) S₁, залежить від S₀, але не залежить від того, в які моменти часу змінювалися свідчення лічильника до моменту t₀. Багато процесів можна приблизно вважати марківськими. Наприклад, процес гри в шахи; система S - група шахових фігур. Стан системи характеризується числом фігур супротивника, що збереглися на дошці в момент t₀. Вірогідність того, що у момент t > t₀ матеріальна перевага буде на стороні одного з супротивників, залежить в першу чергу від того, в якому стані знаходиться система в даний момент t₀ а не того, коли і в якій послідовності зникли фігури з дошки до моменту t₀.

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

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

Рівняння для аналізу СМО

Основні рівняння СМО

 

Закон Бернуллі. В основі аналізу СМО лежить біноміальний закон Бернуллі, який дозволяє розраховувати ймовірність появи події "А" точно К разів при п незалежних іспитах (тільки для дискретних випадкових взаємно несумісних незалежних подій):

 

,                                 (1)

;                      (2)

 

де п - кількість незалежних іспитів; Р_n(К) - ймовірність появи подій "А" точно К разів при п незалежних іспитах; р - ймовірність появи однієї події "А"; q =1- р — ймовірність протилежної події (не появи події "А"); К — кількість появи події "А" при и спостереженнях;  - сполучення по К елементів із п спостережень.

У принципі закон Бернуллі (і закони Лапласа та Пуассона, що з нього випливають) може використовуватись для визначення конструкції СМО - кількості каналів обслуговування та середнього строку обслуговування однієї вимоги.

Якщо прийняти К = 0, 1,2..., n, то отримаємо повну групу взаємно несумісних подій, для якої сума відповідних ймовірностей

 

.                                (3)

 

Формула Стірлінга. Формула Бернуллі дуже складна для обчислення, тому використовується формула Стерлінга

 

 (4)

 

у якій точність розрахунків збільшується при .

Формула Лапласа. Подальші перетворення формули Бернуллі дозволяють отримати формулу Лапласа

 

,                     (5)

 

де

Із формули Лапласа випливає, що при або при К= К_о (тут К_о - найімовірніша кількість подій "А") отримуємо

 

=К₀ -пр = 0; К₀ =пр          (6)

 

і ймовірність найімовірнішого числа подій К_о дорівнює

 

 (7)

 

З точністю до  (тобто з ймовірністю 0,997) можна вважати, що всі події відбудуться, якщо виконується умова К — К_о , або

Формула Пуассона. При великій кількості незалежних іспитів (n» 1), малій ймовірності одного з іспитів (тут ) формула Лапласа дає помилки, і тому використовують асимтотичну формулу Пуассона

,            (8)

 

де .

Ймовірність появи події "А" не більше за т разів

 

 (9)

 

Ймовірність того, що подія "А" при п іспитах зовсім не з'являється .

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

 

,                    (10)

 

де  — середня кількість телефонних дзвінків за одиницю часу;  — середи відмов пристрою за одиницю часу;  — середня кількість розпаду радіоактивних атомів за одиницю часу;  — середня кількість електронів, яка попадає на анод за одиницю часу;  - середня кількість зміни знаку при телеграфних повідомленнях за одиницю часу; п_т = Т= п - число подій за досить великий період часу Т.

Ймовірність появи одного телефонного дзвінка, однієї відмови пристрою і т.п.

 

            (11)

Постійна величина формули Пуассона  і формула Пуассона набуває вигляду

 

 .                (12)

Диференційні рівняння СМО

 

Стан СМО визначається:

· в одноканальній СМО з очікуванням - довжиною черги i;

· у багатоканальній СМО з відмовами - кількістю зайнятих каналів і(у цій СМО черги немає: якщо всі канали зайняті то вимога не обслуговується і зникає);

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

Розглянемо досить велику кількість N таких ідентичних СМО. Позначимо через Р_і ймовірність того, що СМО знаходиться на час t у стані S_i, а через  - зміну ймовірності Рі за малий проміжок часу t.

У СМО вважається, що потік вимог підкоряється пуассонівському закону. Тому за малий термін t на жодну з N СМО не може надійти більше однієї вимоги, та жодна з N СМО за цей час не може обслужити більше за одну вимогу. Ймовірністю надходження або закінчення обслуговування двох або більшої кількості вимог за час t у N СМО можна знехтувати, бо ця ймовірність дуже мала (дорівнює нулю). Тобто СМО переходить із стану S_i, у стан S_{i +1} або стан S_i-1. СМО не може перейти, наприклад, із стану S_i, у стани S_i+2, або S_i-2

Тоді згідно з законом Пуассона (ймовірність появи точно k подій із п можливих за проміжок часу t) при умовах k= 1, t = t ймовірність появи точно однієї події дорівнює

 (13)

 

Таким чином, ймовірність надходження точно однієї події дорівнює

 

,                                 (14)

 

де  - інтенсивність надходження вимог.

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

 

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

 

Як показники ефективності СМО| з|із| відмовами розглядатимемо|розглядуватимемо|:

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

Q — відносну пропускну спроможність, тобто середню частку|долю| заявок, що прийшли, обслуговуються системою;

Р_отк— вірогідність|ймовірність| відмови, тобто того, що заявка покине СМО| не обслуженою;

k— середнє число зайнятих каналів (для багатоканальної системи).