Цепи Маркова (1121219), страница 53
Текст из файла (страница 53)
2.671,=,+1=+.(2.9.20)Процесс скачков вверх (A(t)), который подсчитывает количество допущенных к обслуживанию посетителей в M/M/1/1-цепи, проводит в любом изсостояний i = 1, 2, . . . время SAi , равное сумме Li + Ri независимых слагаемых Li ∼ Exp( ) (Li — время обслуживания i-го допущенного клиента)и Ri ∼ Exp( ) (время до прибытия следующего клиента); после этого A(t)прыгает в состояние i + 1. Функцию распределения f SAi случайных величинSAi , i > 1, можно найти с помощью свертки:0fLi (y)fRi (x − y) dy =e−xZxe(− )ye−0dy =xe−−(x−y)(e− 2 xe− x ,xdy =− e− x),6= ,iZx= .(2.9.21)fSA (x) =Zx0В случае r = c = 1 (1 сервер, одноместный буфер) ситуация довольнопроста: Q(t) принимает 2 значения: 0 (незанятый сервер) и 1 (занятыйсервер).
Цепь, стартующая, скажем, из состояния пустоты с Q(0) = 0, проводит случайное время S0 ∼ Exp( ) в этом состоянии, а затем совершаетскачок в состояние 1. Спустя время S1 ∼ Exp( ) цепь совершает скачокобратно в 0 и т. д.=откуда=Рис. 2.66337В этом случае уравнения детального баланса таковы:Формулы, аналогичные (2.9.9) – (2.9.12), могут быть установлены дляM/M/∞-и M/M/r/∞-моделей; детали мы опустим.До этого момента мы рассматривали модели с бесконечными буферами:для таких моделей любой клиент рано или поздно будет обслужен, хотя,возможно, ему придется подождать. В моделях с конечным буфером клиенты не принимаются (или рассматриваются как «утерянные»), если буферполон.
Такие модели называются модели с потерями (loss models). Обозначим их M/M/r/c: марковские прибытия, марковский сервис, r серверови буфер размера c > r (т. е. число мест ожидания равно c − r). Здесь идетречь о M/M/r/c-цепях. Таким образом, в момент t размер очереди Q(t),т. е. число клиентов в системе, удовлетворяет неравенству 0 6 Q(t) 6 c;если 0 6 Q(t) 6 r, то все клиенты обслуживаются, если Q(t) > r, то r клиентов обслуживаются и Q(t) − r ожидают.Рассмотрим процесс прибытия клиентов, допущенных к обслуживанию, который для простоты обозначим тоже через (A(t)). Этот процесс«вложен» в «формальный» процесс прибытий (N(t)), который является пуассоновским (он также называется внешним процессом прибытий).Более точно, клиент, прибывающий в момент (N(t)), допускается к обслуживанию тогда и только тогда, когда на момент прибытия Q(t) 6 c.Ниже приведена диаграмма M/M/r/c-цепи:§ 2.9.
Применения к теории очередей. Марковские очередиГлава 2. Цепи Маркова с непрерывным временем336Исключение составляет начальное время пребывания S A0 ∼ Exp( ) (времядо первого прибытия в пустой очереди). Времена пребывания S A0 , SA1 , . . . ,очевидно, независимы. Процесс (A(t)) не является марковским, но принадлежит к классу процессов восстановления, многие свойства которыхпохожи на свойства ц.м.н.в.; мы изучим эти процессы в следующих томах.Аналогично процесс (D(t)) скачков вниз, подсчитывающий отбытияв M/M/1/1-цепи, проводит в каждом из состояний i = 0, 1, 2 .
. . время S Di ,равное сумме Ri + Li+1 ; вероятностное распределение случайной величиныASDi совпадает с распределением Si и задается уравнением (2.9.21). (В этомDслучае S0 не является исключением.) Процесс (D(t)) является процессомвосстановления. Заметим, что (A(t)) и (D(t)) зависимы (а именно, слагаемое Ri вносит вклад в SAi и SDi ).Ключевой момент из доказательства теоремы Бурке очевидным образом применяется и тут: можно повторить без существенных измененийдоказательство теоремы 2.9.2 а) для M/M/1/1-цепи. Таким образом, в состоянии равновесия процесс допущенных прибытий (A(t)) и процесс уходов(B(t)) стохастически эквивалентны. Действительно, каждый из этих процессов в равновесии есть стационарная модификация одного и того жеr,c.1(Xs = i) ds −−→k=0k!+rr!1−r −1 −1×i∧r (i−r) ∧0(i ∧ r)! rkXr−10п.
н.,1tZt0п. н.1(Xs = i) ds −−→ii!e− .Ztа в случае системы M/M/∞ выполнено соотношение...,Эти уравнения могут быть легко решены, скажем, при r = c: −1Xrii= ,.i=0 , i = 0, . . . , r,0=1t< r вы-=rc−1 = rr−1...,r+1 , . . . ,339Теорема 2.9.5. Для M/M/r/∞-очереди с параметром =полнено соотношение1,i!i!i=0(2.9.22)i=0i!r!Формулы (2.9.22) называются формулами Эрланга. При r < c мы получаем i 0,i = 0, . . . , r,i! i= ,i=,i=r+1,...,c,0r!ri−r(2.9.23)Xrc−r i −1ir X+.0=iМы завершим этот параграф элегантным примером, показывающим,как много можно получить, умело используя свойство потери памяти.Пример 2.9.6. Рассмотрим M/M/∞-очередь с пронумерованнымисерверами 1, 2, .
. . По прибытии посетитель выбирает свободный серверс наименьшим номером, и этот сервер его обслуживает. Какую частьвремени сервер s занят, s = 1, 2, . . .?Решение. Для сервера 1 имеем стандартную систему с потерямиM/M/1/1. Поэтому доля времени, в течение которого сервер занят, равнаi=1rВ этом случае выполнена первая часть теоремы Бурке. Подводя итог,получим такой результат.Теорема 2.9.4. Пусть (Q(t)) — M/M/r/c-цепь, Q(t) = Q(0) + A(t) − D(t),где (A(t)) — процесс прибытий клиентов, допущенных к обслуживанию, и (D(t)) — процесс уходов.
Тогда а) (Q(t)) — положительновозвратный и обратимый процесс со стационарным распределением= ( i) вида (2.9.23), причем распределение Q(t) сходится к : длявсех i = 0, . . . , c и любого начального распределения выполняетсяравенствоlim P (Q(t) = i) = i ;p1 =.Для сервера 2 интенсивность прибытия уменьшится до p 1 ; как и в предыдущем случае, доля времени, в течение которого сервер 2 занят, равнаp2 =p1p1 +2=( + )+2.Чтобы найти долю времени p1,2 , в течение которого оба сервера заняты,используем M/M/1-систему с потерями, имеющую интенсивность прибытия p1 и интенсивность обслуживания 2 :t→∞б) в состоянии равновесия (A(t)) ∼ (D(t)).Однако свойство независимости, провозглашенное для M /M/1/∞-цепей в утверждении б) теоремы 2.9.2, здесь отсутствует, потому что процессприбытий клиентов, допущенных к обслуживанию (A(t + T) − A(T), t > 0),коррелирует с Q(T), где Q(T) — длина очереди в момент T.Приведем теорему о предельных пропорциях для марковских очередей(без доказательства), это следствие теоремы 2.7.19.+=r=r0процесса восстановления, определяемого распределением времени пребывания вида (2.9.21), которое одинаково для обоих процессов.
Тем не менее,эти процессы зависимы, так как упомянутая корреляция между S Ai и SDiприсутствует и в состоянии равновесия.Формулы, аналогичные (2.9.16), могут быть получены для общей цепис потерями M/M/r/c. В этом случае уравнения детального баланса приr 6 c имеют вид§ 2.9. Применения к теории очередей. Марковские очередиГлава 2. Цепи Маркова с непрерывным временем338p1,2 =p1.p1 + 2Далее, для сервера 3 интенсивность прибытия будет равна p 1,2 , и долявремени, в течение которого сервер занят, равнаp3 =p1,2p1,2 +2=( + )+2.Глава 2. Цепи Маркова с непрерывным временем−( + )2...0...0........................0...0...0−( + 2 )...0...0s000...−( + s )...0000......0........................000...0...sN+s00 0 ...
.0 ... −s20Цепь, очевидно, неприводима, поэтому существует единственное стационарное распределение. Чтобы найти его, используем уравнения детальногобаланса:i qii+1 = i+1 qi+1i , 0 6 i < N + s.Запишем подробнее:=1=20,12,т. e.1=0т. e.2=1,2=2022,s=s=sss−1........................................................s+1,т. e.,sт. e.=s+1s−1=ssss= ... =0s!s,s+1= ...
=0s!ss,.............................................................N+sПример 2.9.7. Посетители приходят в парикмахерский салон согласнопуассоновскому процессу с параметром > 0. В парикмахерской работаетs парикмахеров и имеется N мест для ожидания; каждый парикмахерработает (с одним посетителем) при условии, что есть посетитель, и тепосетители, которые пришли в момент, когда не было свободных мест(т. e. число посетителей было равно N + s), уходят и более не возвращаются. Всякий зашедший клиент ожидает в очереди и затем обслуживаетсяпо правилу «первый пришел — первый обслужен», время обслуживанияэкспоненциально с параметром > 0; времена обслуживания различныхклиентов независимы.
После обслуживания клиент уходит и более не возвращается.Задайте модель цепи Маркова для числа Xt посетителей в парикмахерской в момент t > 0. Найдите стационарное распределение этойцепи и поясните, почему оно единственно. Покажите, что в стационарномсостоянии ц.м.н.в. (Xt) обратима во времени, т. е. для всех T > 0 цепи(Xt , 0 6 t 6 T) и (Yt , 0 6 t 6 T) одинаково распределены, Yt = XT −t и X0 ∼ .Решение. Ц.м.н.в. (Xt) является процессом рождения и гибели напространстве состояний {0, 1, .
. . , N + s}; интенсивности равны(i для i = 1, . . . , s,qii+1 = , qii−1 =s для i = s + 1, . . . , s + N.1pk−1 + (k − 1)0−Здесь p1,...,k−1 — доля времени, в течение которого серверы 1, . . . , k − 1заняты:pk−1.p1,...,k−1 =p1,...,k−1.p1,...,k−1 +pk =341и величины Xk независимы между собой.Итак, Q-матрица имеет размерность (N + s + 1) × (N + s + 1) и равнаИ так далее: для сервера k доля времени занятости равна§ 2.9. Применения к теории очередей. Марковские очереди340N+s−1=sN+s,т. e.N+s=N+s−1s= ...
=0s!sNN+s.Таким образом, уравнения детального баланса имеют единственное нормированное решение:Рис. 2.68k=1ll!nkn, если Xk ∼ Exp( k)=0n!nmin(X1 , . . . , Xl) ∼ ExpXsl=0Мы использовали тот факт, чтоXl=0n=0s!sn−snnsl+s!sNXl=1ll −1,, при n = 1, . . . , s,, при n = s + 1, . .
. , s + N.342Глава 2. Цепи Маркова с непрерывным временем343при t > 0 (так как g(t) > P (на (0, t) не происходит деления) = e − t) и удовлетворяет мультипликативному соотношениюg(t + u) = g(t)g(u), t, u > 0.Тогда g(t) = e t , t > 0, для некоторого ∈ R. Наконец, = ( − 1).Аналогичным образом можно получить дифференциальное уравнениедля вероятностной производящей функции ϕ t (s) = EsMt величины Mt .А именно, ϕt (s) удовлетворяет следующему дифференциальному уравнению:Xdk−ϕt (s) +ϕt (s) =pk [ϕt (s)] , ϕ0 (s) = s.(2.10.1)k>1(равенство k = 0 означает, что клетка погибает). Такому же механизмуподчиняется каждая из рассматриваемых живых клеток, независимо отдругих.Пусть Mt — число живых клеток в растворе к моменту времени t >> 0.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
