3. Основы теории случайных процессов. Карлин (1971) (1186156), страница 78
Текст из файла (страница 78)
Но случайная величина У по предположению не зависит от предыдущих длительностей операций обслуживания и длины очереди. В силу стационарного характера пуассоновского потока число поступлений Ф за время обслуживания ') Именно если операция обслуживания окаачнвается в момент А то система наблюдается в момент ) + О (после ухода обслуженного требования).— Прим, перев а) Условие Хв = О говорит о том, что рассматривается система, в которой в момент Г = О отсутствуют требования. — Прим. аерев.
Гл. 44, Процессос жассоаоео обслужааааил 470 зависит только от )с и пе зависит ни от длины очереди, ни от момента начала обслуживания. Отсюда следует, что (Х„) — цепь Маркова. Вероятностное распределение величины Лг можно найти, налагая условие на значение )г и применяя формулу полной вероятно- сти ) () о Далее, число требований, поступающих за время и, является случайной величиной с пуассоновскнм распределением, имеющим параметр у,о. Следовательно, Р (йУ = П ~ (Г = О) = Е Ха —, (У.П)", -га поэтому Р;; =- Р (Ха ы = У ~ Х„= г) = Р (Лс = У вЂ” г'+ 1) = = ( Р (Л' = у — г + 1 ! )г = о) Ь (и) с(п= ( е '"' ."" . , Ь (и) с(о, о о у эг' — 1 (1~~1), Ргу=О, У(У вЂ” 1 (У в1).
й„= ~ е '" —, Ь(о)с(п, Г=О, 1, 2, (г,о)с о (й„— вероятность того, что за время обслуживания одного требо- вания поступит е требований), то уг, уг, уг, угг угс, й, О й, уго уго О Р— (4.4) О Если требование покидает систему, оставляя ее свободной, то ее состояние остается нулевым до тех пор, пока не поступит н не начнет обслуживаться очередное требование. Таины образом, нулевое и первое состояния эквивалентны относительно переходов в другие состояния. Если обозначить б 4.
Метод влооеенных цепей Маркова 47! р= )~~ей,= ~ е '"~)~~ — '," Ь(о)е(о г-о о т-о = Л ~ оЬ (о) с(о =- ЛМ (!т). о Величина среднее время обслуживания одного требования средний интервал между моментами поступления требования называется нагрузкой системы. Найдем теперь предельное распределение для данной цепи Маркова в случае р ( !. А.
Стационарное распределение вложенной цепи Маркова Найдем вектор п=(пь пь ...), п,)О, ~не=!, г=о такой, что Хп;Рп=пн 1=0, 1, 2, е-о где матрица !!РеД = Р определена равенством (4.4). Если выразить зти уравнения через величины йь то они примут вид т ю и, = пА + ~~~ и, И,, „, ! = О, 1, 2, .... т=! Найдем производяшую функцию п(з) = Х п,з' с-о через функцию К (з) = ~ ь,зе, г-о Умножая записанное выше равенство на з', получим еы зЪе = попая'+ ~~ и йе-ге~8' яе М+~а + г-о (=О, 1, 2, Детальный анализ цепи Маркова (4.4) уже был проведен в ~ 5 гл.
3. Там было доказано, что цепь является возвратной положи- тельной, возвратной нулевой или невозвратной в зависимости от того, р < 1, р = 1 или р ) ! соответственно, где Гж 14 Процессы лсассоаого обслужпаонмя 472 с+! Суммируя по !' и учитывая, что,о п,усе!, является сверткой, пол=о лучим ,~~ пса' = п(з) = -'~еК (з)+ !К (з) и (з) пейн!,' (К (з) ьо!. с-о Отсюда ° наК (а) (а 1) я(з) = а — К (а) Эта формула определяет производящую функцию стационарного распределения с точностью до постоянного множителя ло. Поскольку к(!)= Яй,= 1, то дробь а — К(а! а — ! ! — К(а) а †! а †! ! ! стоящая в знаменателе выражения для п(з), стремится при з ! к величине 1 — К'(1).
Найдем К'(1) — среднее число требований, поступающих за время обслуживания одного требования: К (!) = ~) гй, = АМ (!Г) = ' „' = р с ! (р, очевидно, является нагрузкой системы), где — =М(А) — сред- 1 !е няя длительность интервала между моментами поступления. Поскольку р < 1, стационарное распределение существует и, следовательно, п(1) = 1. Но из полученной формулы следует поэтому па= 1 р.
Таким образом производящая функция стационарного распределения равна К (5) (и — 1) !) а — К (а) Величина 1 — р является стационарной вероятностью того, что си- стема свободна. '! Данное еыражение для я(а) назыаакл формулой Поаячека — Хинчина.— Прим. нерее, д 4. Метод влаженнмк целей Маркова 4тз Б. Средняя длина очереди для системы (М/б/1) в стационарном режиме В заключение данного параграфа найдем среднюю длину очереди и среднее время ожидания поступившим требованием начала обслуживания для системы, находящейся в стационарном режиме. Дифференцируя п(з), нелегко непосредственно получить выражение для М(д), где г/ — состояние вложенной цепи Маркова, находящейся в стационарном режиме.
Изберем для получения М(т/) другой метод. Если д — число требований в очереди после ухода некоторого требования, а !/' — число требований в очереди после следующего ухода, то д -д-1+6+й, где /!т — число поступивших за время обслуживания требований, а 1, если !/=О, 6= О, если д)О, В стационарном режиме величина !/' имеет такое же распреде- ление, что и !/. Таким образом, М(!/') = М(д) и М(6) -1 — М(6/) -1 — р. (4.5) Из этого же выражения, поскольку бо = 6, имеем е/" = !то -1- 6 -1- (ту — «о -1- 2дб + 26 (й/ — «+ 2!/ (/!г — «. Так как дб = 0 (см.
определение 6), то д' = !/о-1-6+ й/(й! — «-)-(1 — Л/)+ 26(6/ — «+24(/!/ — «, Но величина /к' (число требований, поступивших за время обслу- живания) не зависит от т/ и, следовательно, от 6. Усредняя полученное равенство и учитывая (4.5), получаем М(г/' ) = М(т/о)+ 1 — р+ М [6/(!!/ — «] + + 1 — р + 2 (1 — р) (р — «+ 2М (!/) (р — «. Поскольку М(!/' )=М (д') в силу предположения о стационарно- стн, то м (йг (йт — «1 2 (р -!) Далее, К(з) = ~)~~~ йлз" = ]г е-"!'-'Ь (о)т(п, л о о М(ту(Л! — «] =- ~~~~~ п(п — «й„= К"(« л-о Ге.
)в'. Процессы массового обслуживании Ксс (з) = Ла ~ вае ""П еЬ (е) с(о, о Следовательно, М [Л (Лс — ! )) = Л' ~ его (е) е(о = Ле (о' (йг) + (М ()г)]а) = о' (ЛХ) + ри, о поскольку Таким образом р = ЛМ(й). + ог(Л)г) + р' 2 (1 — р) (4.6) В. Среднее время ожидания должна равняться среднему числу требований, поступивших за этот период, умноженному на среднюю длительность интервала 1 между требованиями, т.
е. величине — М(с)). Но поскольку рас- Л сматривается стационарный режим, то в силу (4.6) м()(у)+м()')=- —,' ~~+ ',~,',~~+„'1. Деля на )с-' = М()с) и вспоминая, что — = р, из последнего соот- Л р ношения получим М (1Г) ог (Л1') + р' М (Р) 2р (1 — р) или (4.7) Из формул (4.6) и (4.7) следует один несколько неожиданный факт. Именно: при заданных средних интервалах между поступлениями и длительностях обслуживания можно уменьшить сред- В условиях стационарности можно найти среднее время ожидания требования. Предположим, что требование ожидает время В' начала своего обслуживания, которое продолжается время йс.
Предположим, что, когда требование покидает систему, в очереди остается с) требований. Это означает, что за время (Тг + (с поступило с) требований пуассоновского потока. В силу стационарности сумма (среднее время ожидания) + (среднее время обслуживания требования) = М((уг)+ М((г) Э б. Энспоненииально распределенное время обслуживания 475 вне длину очереди и время ожидания, уменьшая дисперсию времени обслуживания. Очевидно, что наилучшим в этом отношении случаем является постоянное время обслуживания. Г.
Распределение времени ожидания В тех же предположениях, что и выше, найдем преобразование Лапласа распределения времени ожидания. Пусть (пз) — равновесные вероятности, производящая функция которых п(з) была найдена выше. Если требование ожидает время ))т начала обслуживания н обслуживается время )г, то вероятность того, что после его ухода останется с) требований, равная и., совпадает с вероятностью поступления д требований за время ))т + )с. Поскольку входящий поток — пуассоновский с параметром Х, то па= )Г е ы — (А!)ос(С((), о где С(!) — функция распределения величины Ч7+ )с.
Отсюда и п(з) = ~ позе= ~ е мп "с(С(!)= С(Х(1 — з)), а-о где С(з) — преобразование Лапласа функции С(!) '). Но С(!)— функция распределения суммы независимых случайных величин Я7 и !', функции распределения которых равны В'(() и В(() соответственно.
Преобразование Лапласа для суммы ))с и )т равно произведению соответствуютцих преобразований. Следовательно, п(з) = Ф(Х(! — з)) В(Х(1 — з) т, или л ) Ф(и) = В (и) й 5. ЭКСПОНЕНПИАЛЬНО РАСПРЕДЕЛЕННОЕ ВРЕМЯ ОБСЛУЖИВАНИЯ (6/мЛ) Другой моделью, которая может быть изучена с помощью метода вложенных цепей Маркова, является модель с произвольным распределением О(и) интервалов между моментами поступлений и экспоненциально распределенным (с параметром р) временем обслуживания. ') Такое преобразование часто называют преобразованием Лапласа — Стильтьеса. — Прим.
перев. 47б Гл. 44 Процессы ыапоаоео обслкяспаааня В этом случае примем, что переходы вложенной цепи Маркова определяются моментами поступления новых требований, а ее состояние до следующего перехода — длина очереди перед вновь поступившим требованием. Если с! — состояние системы после некоторого момента поступления, а с)' — состояние после следующего момента поступления, то (5.1) где Л' — число обслуженных требований за рассматриваемый отрезок времени. В силу свойства «отсутствня последействияа у экспо. ненциального распределения (см, теорему 2.2 гл. 7) число У требований, обслуженных за время между моментами поступлений, зависит только от длины этого интервала и величины д и пе зависит от времени, в течение которого уясе обслуживалось очередное требование.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
