Лекція 6. Неперервно-стохастичні моделі (q-схеми).

1. Основні поняття q – схем.

    Застосування цього підходу розгланемо на прикладі використання математичних схем систем масового обслуговування.     Для всіх цих моделей характерним є випадковий процес їх функціонування. Розглянемо одноканальну систему масового обслуговування (рис.6.1).

Рис. 6.1. Одноканальна система масового обслуговування.

де Yi-вихідний потік, ui-час обслуговування заявки, wi-час очікування обслуговування заявкою, λi- кількість заявок, які поступають в одиницю часу, ni- кількість заявок в системі, ni=li+pi, де pі- коефіцієнт завантаження, li- кількість заявок в черзі.

    Потік подій називається однорідним, якщо він характеризується тільки моментами наступлення цих подій, {t_n} 0=t₁<t₂<...<t_n і ніяк не характеризує самі події. Однорідний потік подій може також задаватися проміжками часу між послідовними подіями { _n},  ₁=t₁-t₀,  ₂=t₂-t₁, ...,  _n=t_n-t_n-1.     Потік неоднорідних подій - це послідовність, яка характеризується двома параметрами {t_n,f_n}, t_n- моменти часу наступлення події, f_n- набір ознак цієї події.     Потік подій називається потоком з обмеженою післядією, якщо сумісна функція густини інтервалів  _i може бути представлена наступним чином:

f(z1,z2,...,zn)=f(z1)f(z2)...f(zn).

    Потік подій називається ординарним, якщо lim[ψ(t₀,t)/t]=0 при t→0, де функція ψ(t₀,t) - ймовірність появи двох і більше подій на проміжку часу t.     Нехай заданий цілочисельний вектор k=(k₁, k₂,...,k_n), і вектор t=(t₁, t₂,..., t_n). Визначимо p_k(t₀,t) як ймовірність появи k₁ подій на проміжку часу від t₀ до t₁, k₂ подій на проміжку часу від t₁ до t₂ і т.д. Якщо ця функція не залежить від t₀, а визначається тільки векторами t і k, то потік називається стаціонарним. Для стаціонарного потоку справедливим є співвідношення f(z₂)=f(z₃)=...=f(z_n), де n>1.

де m-середнє значення проміжку часу між моментами наступлення подій. f(z) - функція густини закону розподілу проміжків часу. m=1/λ, де λ - інтенсивність вхідного потоку.

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

    Математичне сподівання:          Розподіл інтервалів часу  _i:     M( ₁)=b/3 - математичне сподівання  ₁.     Якщо ймовірність p_k(t₀,t) поступлення k заявок в інтервалі часу (t₀,t₀+t) не залежить від чередування подій до моменту t₀, тобто, якщо умовна ймовірність p_k(t₀,t), яка обчислена при будь-якому припущенні послідовності подій до моменту t₀ дорівнює безумовній ймовірності тої ж події, то потік називається потоком без післядії.     Єдиним стаціонарним ординарним потоком без післядії є найпростіший потік або потік Пуасона, для якого функція розподілу кількості подій на проміжку часу t дорвнює:     p_k(t₀,t)=((λt)^k / k!)*e^-λt,     f(z)=λ*e^-λt,     f(z₁)=λ*e^-λt.

2. Q - схема типу M|M|1 (за класифікацією Кендела).

    Ця система може бути описана процесом розмноження і загибелі з постійними інтенсивностями народження λ і загибелі μ. Процес представляє процес розмноження і загибелі, якщо він є однорідним ланйюгом маркова x(t) з множиною станів {0,1,...}, якщо події розмноження і загибелі є незалежними подіями і якщо виконуються наступні умови:     В1: P[за проміжок часу  t відбудеться народження 1 заявки при умові, що в популяції к заявок]=λ  t+О( t).

    D1: P[за проміжок часу  t відбудеться загибель 1 заявки при умові, що в популяції к заявок]=μ  t+О( t).     B2: P[за проміжок часу  t не відбудеться народження жодної заявки при умові, що в популяції к заявок]=1-λ  t+О( t).     D2: P[за за проміжок часу  t не відбудеться загибелі жодної заявки при умові, що в популяції к заявок]=1-μ  t+О( t).     Згідно з цим припущенням кратні народження, кратні загибелі і одночасні народження і загибелі на протязі малого проміжку часу заборонені в тому відношенні, що ймовірність таких кратних подій має порядок О( t). Будемо шукати ймовірність того, що об’єм популяції в момент часу t дорівнює k:     p_k(t)=P[x(t)=k].     Розглянемо зміни об’єму популяції в проміжку часу (t,t+ t), використовуючи динаміку Чепмена-Колмогорова.     Будемо вважати, що в момент часу t+ t популяція нараховує к заявок і цей стан будемо позначати E_k. Розглянемо можливі переходи в стан к на проміжку часу (t,t+ t) (рис 6.2).

Рис. 6.2. Переходи системи на проміжку часу (t,t+ t).

    P_k(t+ t)=P_k-1(t)*P_k-1,k+P_k(t)P_k,k+P_k+1(t)P_k+1,k      k=1,       P_i,j -ймовірність переходу із стану і в стан j.     P₀(t+ t)=P₀(t)P_0,0+P₁(t)P_1,0.       - умова нормування.     Згідно умов процесу розмноження і загибелі В1,В2,D1,D2 ймовірность знаходження системи в момент часу t+ t в стані к є:     P_k(t+ t)=P_k-1(t)(λ  t+O( t))+P_k(t)(1- λ t-O( t))(1-μ t-O( t))+P_k+1(t)*(μ t+O( t))     P₀(t+ t)=P₀(t)(1-λ t-O( t))+P₁(t)(μ t+O( t))     Розкриємо дужки і члени, які містять О( t), згрупуємо і позначимо через О( t).     P_k(t+ t)=P_k-1(t)λ t+P_k(t)(1-λ t- μ t)+P_k+1(t) μ t+O( t)     (P_k(t+ t)-P_k(t))/ t=P_k-1(t)λ-P_k(λ+μ)+P_k+1(t)μ+O( t)/ t.     Оскільки O( t) має вищий порядок меншості за  t, то границя О( t)/ t→0 при  t→0.          Для стаціонарного режиму отримуємо:     (λ + μ)P_k(t)- λP_k-1(t)- μP_k+1(t)=0     λP₀(t)-μP₁(t)=0.     Вивід цієї системи рівнянь можна зробити простіше, використовуючи метод локального балансу. Розглянемо діаграму станів (рис.6.3).

Рис. 6.3. Диаграма станів системи.

    Інтенсивність потоку в стан E_k дорівнює:     P_k-1(t) λ + P_k+1(t) μ      Інтенсивність потоку із стану E_k дорівнює:     P_к(t) μ + P_k(t) λ     Тоді швидкість зміни стану дорівнює:     dP_k(t)/dt=-(λ + μ)P_k(t)+P_k-1(t) λ + P_k+1(t) μ     dP₀/dt=-P₀(t) λ + P₁(t) μ      Використовуючи умову нормування і позначаючи ρ=λ/μ < 1, отримаємо:     (1+ρ)P_k-ρP_k-1-P_k+1 = 0     ρP₀-P₁ = 0          Середня кількість заявок N в системі:          де l - середня кількість заявок в черзі.     Час перебування заявки в черзі:          Середній час перебування заявки в системі: