Цепи Маркова (1121219), страница 52
Текст из файла (страница 52)
е. число клиентов N(t) в очереди на момент t > 0 (включая тех, ктов данный момент обслуживается). Это удобно записать в виде329328−00.... −( + )0 . .Q=... .2−( + 2 )0...... .........(2.9.4)Модель в) мы опишем как очередь M/M/r/∞ из r серверов (или,упрощенно, M/M/r).
Например, пусть в парикмахерской работает r парикмахеров: все они заняты, если Q(t) > r, в противном случае (т. e. когда0 6 Q(t) < r) (r − Q(t)) из них бездельничают.В этих моделях благодаря уравнению (2.9.1) траектория Q(t) находитсяпод траекторией A(t); см. рис. 2.63.330Глава 2. Цепи Маркова с непрерывным временем§ 2.9. Применения к теории очередей. Марковские очереди331Из условия нормировкиXi=0i> 0Рис.
2.63i(2.9.5)= (1 − ) i , i > 0, гдеlim P (Q(t) = j) = (1 − )(2.9.8)j(2.9.9)независимо от начального распределения.Среднее время возвращения в 0 равноm0 =6= ,1(2.9.6)0 q0=(2.9.10)( − )и задает среднее время цикла на сервере (время бездействия плюс времязанятости). См. рис. 2.64.= .= .t→∞( + )hi = hi+1 + hi−1 , i > 1.Решение системы (2.9.6) имеет общий вид iA+B, еслиhi =A + Bi,если=1Подытожим результаты.Теорема 2.9.1. Если < , то M/M/1-цепь положительно возвратна и обратима с геометрическим стационарным распределением = ( i) из уравнения (2.9.8).
Значит, цепь стремится к равновесному распределению:Тогда h0 = 1 и (hQ) j = 0 ∀ j > 1. Иными словами,h0 = 1, −11−hi = P i (попасть в 0), i > 0.0Начнем наш анализ с модели а) и уделим ей большую часть времени.Соответствующая ц.м.н.в. называется M/M/1-цепью. Рассмотрим вероятности попадания в 0:=i>0следует, чтоX i1=В случае, если интенсивность прибытия не превышает интенсивностиобслуживания, т. е.
6 , для минимального неотрицательного решениясистемы (2.9.6) мы имеем B = 0, A = 1,hi ≡ 1, i > 0,Тогда среднее время занятости равно(2.9.7)Для того чтобы найти стационарное распределение, применим уравнения детального баланса i = i+1 , i > 0, т. e. ii = ... =i+1 =0.1=( − )−1=1.−(2.9.11)Наконец, в состоянии равновесия среднее время ожидания для посетителяравноEW = E [E (W | Q)] =Xi>0E (W | Q = i)i==Xii>0(1 − )t→∞m0 −и M/M/1-цепь невозвратна.
Это означает, что процесс стремится к +∞(бесконечно растущая очередь):P i lim Q(t) = +∞ = 1.Рис. 2.64> , то A = 0, B =и в этом случае M/M/1-цепь возвратна. Однако если= 1, i, i > 0,hi =i=( − ),(2.9.12)332Глава 2. Цепи Маркова с непрерывным временеми среднее время пребывания (ожидание плюс обслуживание) равноEW +11−=(2.9.13)333revто (Qrevt ) ∼ (Q(t)). Далее, б) для процессов (A t ) и (Dt) число скачков наинтервале (0, T) одинаково, так же как и количество скачков процессов(A rev(Drevt ) и (At) на этом интервале. Наконец, пусть числоrevскачковt ) и (Dt)AArevна интервале (0, T) равно n, моменты скачков H1 , H2 , .
. . (скачкиDDвверх (Arevt , 0 6 t < T)) связаны с моментами скачков H 1 , H2 , . . . (моменты«уходов» (Dt , 0 6 t < T)) через «условное» уравнение(H1D , . . . , HnD | n скачков в (Dt) на [0, T)) =revrev= (T − HnA , . . . , T − H1A | n скачков в (Arevt ) на [0, T)).(средняя длина промежутка занятости).Смысл условия < , или < 1, очевиден: скорость работы сервиса превышает скорость прибытия клиентов. Иными словами, если математическое ожидание интервала между прибытиями 1 / больше, чемматематическое ожидание 1/ промежутка времени обслуживания, тоM/M/1/∞-очередь «устойчива» и достигает равновесия, каково бы нибыло начальное распределение.
Иными словами, устойчивость в среднемвлечет устойчивость почти наверное.Теперь приведем самое удивительное следствие из теоремы 2.8.10.< , и рассмотримТеорема 2.9.2. Предположим, чтоM/M/1-цепь (Q(t)) в стационарном состоянии. Тогда а) в разложении(2.9.14)Q(t) = Q(0) + A(t) − D(t)§ 2.9. Применения к теории очередей.
Марковские очередиТраектория (Qt+T , t > 0) есть зеркальное отражение траектории (Q revt , t 6 0),см. рис. 2.65.revrevrevrevQrevt = QT −t и Qt = Q0 + At − Dt , t > 0,Рис. 2.65revНо для (Qrevt ) длина предыдущей очереди (Qt , t 6 0) не зависит отrevпоследующих прибытий (At , t > 0) (как обычно, положим Arev0 = 0). Тогдав изначальной M/M/1-цепи (Q(t)) величины (D(t), 0 6 t < T) в прошломне зависят от настоящей и будущей длины очереди (Q t+T , t > 0).Теорема 2.9.2 известна под названием теоремы Бурке.
Она играетважную роль в теории массового обслуживания, когда клиенты переходятот одного узла (станции) к другому, по пути присоединяясь к различнымочередям. В свою очередь, сети массового обслуживания представляютособый интерес в ряде применений, особенно в исследовании телекоммуникаций, компьютерных и транспортных сетей.Для = M/M/1-цепь имеет нулевую возвратность. Действительно,если ( i) — инвариантная мера, топроцесс уходов (D(t)) эквивалентен процессу прибытия A(t), т. е.количество обслуженных клиентов эквивалентно по распределениюколичеству пришедших; иными словами, (D(t)) ∼ ПП ( ); б) для всехT > 0 процесс (D(t), 0 6 t < T), равный количеству обслуженных клиентов до момента T, не зависит от (Q(t + T), t > 0), т. е.
от длиныочереди после T.Опять-таки удивительно то, что (D(t)) зависит от , а не от , ивдобавок то, что очередь после заданного момента времени развиваетсянезависимо от количества обслуженных клиентов до этого момента времени. (Например, если до сих пор вы редко наблюдали уходящих клиентов,то это ничего не говорит о том, насколько ненасыщен уровень очередив настоящее время, и о том, сколь высок он в будущем. Объяснение этогофакта то же самое: в стационарном состоянии процессы (A t) и (Dt) специфически зависят друг от друга, что и создает такой эффект (в частности,Qt = Q0 + At − Dt всегда неотрицательно).Д о к а з а т е л ь с т в о.
Утверждение а) формально следует из теоремы2.8.10. Вспомним, что ключевые моменты в доказательстве теоремы 2.8.10состоят в том, что 1) при условии < процесс (Q(t)) обратим, и 2) длятраектории Q(t) все скачки вверх становятся скачками вниз при обращениивремени. Иными словами, а) если (Qrevt ) — обращение процесса (Q(t))относительно момента времени T,0=1,2i=i− 1 +i+1 ,i > 1.Поэтому i = i+1 , i > 0 (т.Pe. мера ( i) удовлетворяет уравнениям детального баланса). Итак,i = ∞, кроме случая i ≡ 0.
В этом случаеiP i lim N(t) = +∞ = 0, но процесс не имеет стационарного распределеt→∞Наконец, уравнения детального баланса для M /M/r/∞-цепи таковы:= i i , i = 1, . . . , r,i=ri+1 , i = r, r + 1, . . .i−1(2.9.17)and His Brothers12 .i!00=i> 0i!Иными словами, стационарное распределениеi(2.9.16)= ( i) будет пуассонов-r! ri−rj>1< ∞,0= 1+i=1i!+r!j>1−1 Xr−1=jrji=0ir1+i!r! 1 − /rXrirrX−1,(2.9.19),i>1,задаютсяуравнением(2.9.18).iУсловие < r, или < r , имеет тот же смысл: система в среднемв состоянии справиться с клиентами.Следовательно, если < r, то M/M/r/∞-цепь положительно возвратнаи обратима.
Опять таки, она, очевидно, неприводима. Добавим также,что для нее все еще справедлива теорема Бурке. Поэтому имеет местоследующая теорема.Теорема 2.9.3. Предположим, что < r . Тогда M/M/r/∞-цепь(Q(t)) положительно возвратна и обратима и имеет стационарноераспределение , задаваемое уравнениями (2.9.18) и (2.9.19). Следовательно, при любом начальном распределении= .ским с параметром : i = e . Мы видим, что независимо от значенийi!и цепь M/M/∞ положительно возвратна и (очевидно) неприводима.Поэтому сходимостьlim P (Qt = i) = i−(2.9.18)X i −1= e− ,и= .0 , i = r + 1, . .
. ,t→∞имеет место независимо от начального распределения.Мы видим, что M/M/∞-очередь устойчива для всех , > 0.Теорему Бурке очевидным образом можно обобщить и на случай этоймодели. Как результат мы получим, что в состоянии равновесия а) процессы прибытий (At) и уходов (Dt), которые составляют разложениеQt = Q 0 + A t − D t ,стохастически эквивалентны: (At) ∼ (Dt) ∼ ПП ( ) и б) для всех T > 0,процесс уходов (Dt , 0 6 t < T) до момента T не зависит от длины очередив момент T и после него (Qt+T , t > 0).с названием фильма Л.
Висконти «Рокко and His Brothers».i=i−rirиследовательно,i = 1, . . . , r,X jАнализ моделей б) и в) аналогичен. Модель M/M/∞ с бесконечнымчислом серверов относительно проста. В этом случае уравнения детальногобаланса имеют видi , i = 1, 2, . . . ,i− 1 = i0,i!Мы видим, что при < r существует корректно определенное стационарноераспределение = ( i), а именно(Из серии «Фильмы, которые не вышли на большой экран».)i=iЕдинственное решение имеет видt→∞12 Ср.335ния и длина очереди осциллирует между 0 и ∞.
Если > , то M /M/1-цепьневозвратна и неограниченно возрастает:п. н.P lim Qt = ∞ = 1, т. e. Qt −−→ ∞ при t → ∞.(2.9.15)§ 2.9. Применения к теории очередей. Марковские очередиГлава 2. Цепи Маркова с непрерывным временем334lim P (Q(t) = i) =t→∞i,i = 0, 1, . . .Далее, в разложенииQ(t) = Q(0) + A(t) − D(t)при Q(0) ∼ процесс уходов (D(t)) стохастически эквивалентен процессу прибытий (A(t)). Иными словами, в состоянии равновесия(D(t)) ∼ ПП ( ). Наконец, для всех T > 0, процесс (D(t), 0 6 t < T), считающий уходы до момента T, не зависит от (Q(t + T), t > 0), т. е.от очереди после момента T.00Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
