2. Системы массового обслуживания. Матвеев_ Ушаков (1984) (2. Системы массового обслуживания. Матвеев_ Ушаков (1984).djvu), страница 7

Центральное мес- то в теории регенерирующих процессов занимает предельная теорема. Определение 3. Циклом длины г называется пара (г, Ь(т)), где г — неотрицательная случайная величина, (~(1), й= [О, г[) — случайный процесс со значениями в измери- мом пространстве (Х, В). Определение 4. Случайный процесс (о(!), !»н[0, со)) со значениями в (Х, В) называется регенерирующим с момен- тами (точками) регенерации О<!»(..., если существует такая последовательность независимых циклов ((гм Ь»(1)), ге>1), для которой выполнены условия: 1) г»=!» — 6»-ь й> 1, (о=О; 2) Р(㻠—— 0) <1, Р(г,<оо) =1; 3) все циклы, начиная со второго, гтохастичсски эквивалентны; 4) К(1) =ь»(! — (»-а), если !е=[!» ь (»), й>1.

Замечание. Отметим, что последовательность (г,, й>1) образует рекуррентный процесс восстановления с запаздывани- ем, задаваемый функциями А~(1) = Р(»1<(), А (1) = Р(а<!), г» а, й> 2. 2.2. Для теории регенерирующих процессов центральный вопрос — найти условие существования предела !пп РД(!)енВ), ВенВ, н вычислить его значение. Предельное распределение при определенных условиях удается вычислить через соответствующее распределение на отдельном цикле регенерации. Обозначим !»в(1) =Р(о(!» 1+!)с=В, г»)(), й>2. 2.3.

Предельная теорема для регенерирующих процессов. Существование предела (1) связано с выполнением одного из условий: У1) функция рв(1) интегрнруема на любом конечном интервале; У2) существует такой номер и, что А,(() — функция распределения случайной величины !а=г,+...+». — абсолютно непрерывна. Теорема 4. Если Л(!) -- пеарифнетическая трхр., и выполнено одно из условий У! или У2, то для ресенерирдюгцего процесса ~ (1) 1пп Р(с(т')»и В) =.

а; Рв(и) ° .'и, а ' = Ма, 㻠— а, й >2, ~-вао 33 2 В Ф Матвеев, В Г ушаков 2.4. Примеры применения предельной теоремы для регенерирующнх процессов. Пример 1. Рассмотрим процесс восстановления т(г), заив даваемый не арифметический ф.р. А((). Пусть 1„= ~!~гм гг — а, й=! моменты восстановлений. Рассмотрим длины интервалов $((), начинающихся с произвольно взятого момента времени 1 до ближайшего последующего момента восстановления, н п(1), начинаюшихся с момента восстановления, непосредственно предшествовавшего моменту времени г, и заканчивающихся в момент й Найдем стационарное распределение этих процессов. 3 а м е ч а н и е. Наш пример можно интерпретировать как модель движения автобуса мимо остановки. Тогда в(1) — время ожидания автобуса в момент (, !1(() — время отсутствия автобуса относительно момента времени й Решение.

Легко проверить, что в(() и т)(1) — регенерируюшие процессы. Покажем, что к 1пп Р Ц (1) ( х) = 1пп Р (т1 (1) ( х) = а ( [1 — А (и)1 г(и, а — ' = Ма. !~а ! ~ ц~ Действительно, для процесса ~(1) р(и) =РЯ(и) <х, г!>и) =Р(и<г!<и+х) = = А (х+ и) — А (и+ О) . Условия теоремы 4 выполнены и ° В 11ш Р Я (!) ( х) = а ~ [А;(х + и) — А (и'+ О) 1!(и = со к = а ) [1 — А (и)) !(и. а Для процесса т1(!) Р (и) =- Р (т1 (и) ( х, г ) и) = Р (и ( х, г ) и) = 1 — А(и+ О), и( х, О, и >х. Условия теоремы также легко проверяются, поэтому .! 1пп Р (т1(1) ( х) = а ) [1 — А (и)) с(и. ! о П р н м е р 2 (продолжение).

Предположим, что независимо от процесса восстановления рассматривается пуассоновский поток Х(Ь, !). Рассмотрим процесс Л(Ь, т1(1)). Требуется определить распределение этого процесса при !- со. 3 а м е ч а н и е. Если интерпретировать Х(Ь, г) как поток пассажиров и предположить, что прибывающий автобус вмещает всех пассажиров, то !.(Ь, т!(!)) — количество пассажиров, собравшихся на остановке к моменту времени Е Решение. В данном случае процесс ),(Ь, т!(г)) — регенернрующий, Р~ (и) = Р (Х (Ь, и) = Ь, г, ) и) = е "" [1 — А (и)]. (Ьи)ь Н Условия теоремы 4 выполнены, поэтому ря = 1пп Р(Х(Ь, !(()) = Ь) =а ~ е — '" [1 — А(и)]йс. с 3 И о 3.

Марковские процессы. О п р е д е л е н и е 5. Марковским процессом называется случайный процесс Х(!), (еиТс:(х, со значениями из измеримого пространства (Е, В), удовлетворяющий марковскому свойству, т. с. для каждого набора 1~<тр<...<т»+~<... моментов времени из Т и любого множества ВенВ Р(Х(!» и) енВ!Х(1~), ..., Х(1,) ) = Р(Х(1„„~) енВ!Х(1„) ). Примером марковского процесса служит случайный процесс (!.(а, !), (~0) пуассоновского потока событий, который называют пуассоновским процессом. Марковское свойство этого процесса легко проверяется с учетом основного свойства показательного распределения. Специальный класс марковских процессов — процессы гибели и размножения — рассматривается в гл.

1, $1. Марковский процесс Х(!), (еиТ, у которого Тс(1, 2, ...), называют цепью Маркова. То же название связывают с марковским процессом с не более чем счетным множеством значений. Такие цепи Маркова рассматриваются в п. 4 настоящего параграфа. При исследовании СМО, когда характеристики системы не описываются марковским процессом, вводят дополнительные компоненты, чтобы сделать получаемый векторный случайный процесс марковским.

4. Цепи Маркова. Приведем некоторые понятия и факты теории цепей Маркова. Будем рассматривать однородные цепи Маркова Х((), (е-:Т, с множеством состояний Е=(0, 1, 2, ...) и либо дискретным, Т=(1, 2, ...), либо непрерывным Т= [О, со) временем. Для описания цепей Маркова особую роль играет набор Р~,' — вероятностей перехода из состояния й в состояние п за время. Е Они удовлетворяют уравнению Колмогорова †Чспмс »эО 35 Важным понятием является стационарное распределение п=(пь, пь ".), пл>0, й>0, ~У' пл.=1, которбе по определению л=а для всех и> 0 и !енТ удовлетворяет соотношениям и„= ~' плР«л. л>о 11епь Маркова называется эргодической, если для всех состоя- ний й 1пп Рл„= пл, п )~0. Мы будем рассматривать обычно неразложимые (неприводимые) цепи Маркова, т, е, такие, у которых для любой пары состояний й и и существует (е-:Т, такое, что Рл„') О.

Цепь Маркова называется сжимающей, если для каждой пары состояний й и и существует состояние тп и время (е=Т, такие, что Р, ')0 и Р„„,')О. Для неразложимых цепей Маркова с дискретным временем зто понятие эквивалентно непериодичности цепи. Однородная сжимающая цепь Маркова с конечным множеством состояний всегда эргодическая.

Если цепь Маркова сжимающая, то для л1обых состояний я и и существует предел !!гп Р,„'. Если кроме сжимаемости цепь неразложима и имеет стационарное распределение, то она эргодическая и 1!гп Рл„ = = п„>0 для всех й и и из Е. Если у сжимающей цепи Маркова не существует стационарного распределения, то для всех пар состояний я и и!!гп Рл„= О, л При исследовании СМО часто необходимо выяснить условия существования стационарного распределения. При этом бывает полезной теорема (приводимая ниже без доказательства), содержащая достаточные условия существованич стационарного распределения цепей Маркова. Т е о р е м а 5. Для того чтобы однородная неразложимая сжимающая цепь Маркова имела стационарное распределение, достаточно существования зе.Т, конечного множества Еьс Е, действительного числа е)0 и набора неотрицательных чисел хь, хп ..., таких, что ~ Р'„.х; «(хл — е, (еТ Еь, гмо Ж, !< гьо 5.

Задачи. 36 3 а д а ч а 1. Найти функцию восстановления, если и а) А(/) = ~ ие "с(и; о б) А(/) = р (1 — е — '" ') + д (! — е —" ~), р -1- е = 1, 3 а д а ч а 2. Поток автобусов на остановку — рекуррентный, определяемый ф.р. А(/), поток пассажиров — квазипуассоновскнй с параметрами (Ь, Ф(е)), Е(1) — число пассажиров на остановке в момент времени й Показать, что 1 — о (Π— ОФ 1е)) Ь(1 — ПЗ(.))Ми ' 3 а д а ч а 3.

Периоды работы некоторого устройства чередуются с периодами его восстановления и образуют независимые рекуррентные процессы восстановления, определяемые функциями распределения А (Г) и Ь(/) соответственно. Предположим, что А(!) и В(/) — неарифметические ф.р. Найти стационарную вероятность того, что устройство находится в рабочем состоянии. $5. ФОРМУЛА ЛИПЛА 1. Вывод формулы Литтла.

Для СМО достаточно обшего вида будем рассматривать усредненные характеристики и по- пытаемся установить для стационарного режима зависимость между интенсивностью входяшего потока, временем пребыва- ния в системе одного требования и количеством требований, находящихся в системе. 1.1. Введем обозначения: т(Г) — входящий поток требований; и(/) — поток требований, покидающих СМО; /. (г) =т(Г) — )о(г) — число требований, находяШихся в СМО в момент времени Г, а'=м(1)/1 — оценка интенсивности входящего потока на интер- вале (О, /).

1.2. Оценим время пребывания в СМО отдельного требова- ния. Для каждого фиксированного требования а определим У„' — количество времени, проведенного им в СМО на интер- вале (О, /), тогда у' = ~У~ — суммарное количество времени, а проведенного в СМО на интервале (О, !) требованиями, посту- пившими в систему на этом интервале. Заметим, что, зная траектории процессов ч(!) и н(/), можно вычислить реализацию Т' по формуле у' = ~ Е(и)с/и. о Теперь можно получить У'=Т'/т(Г) — оценку среднего количества времени, проведенного в СМО на интервале (О, /) некото- 37 рым требованием, поступившим в систему на этом интервале.

1.3. Оценку среднего числа требований, находившихся в СМО на интервале (О, 1), можно также получить через величину Т'. В' = у",1 = Г' ~ В (и) Йс. о 1.4. Предположим, что существуют пределы 1пп а'=11гп — = а, о (!) о ев ! г 1пп 1.' =1!гп — ~ й(и) ди = 1., тогда существует и предел о» со 1!щи =1нп = $', э(1) причем из Е'=а'Р следует 1 =аУ (формула Литтла). 3 а м е ч а н и е. Последнее соотношение показывает, что в стационарном режиме среднее число требований, находящихся в СМО, равно произведению интенсивности входящего потока на среднее время пребывания в системе одного требования. 2.

Аналоги формулы Литтла. Аналогично доказываются формулы: а) А!=а%7 где У вЂ” средняя длина очереди, В' — среднее время ожидания в очереди; б) М=аВ, где М вЂ” среднее число работающих приборов,  — среднее время обслуживания одного требования на одном приборе. 5 6. СТАТИСТИЧЕСКОЕ МОДЕЛИРОВАНИЕ СМО 1. Существо статистического моделирования. 1.1.

Анализ реальной системы может основываться на результатах натурных экспериментов или исследованиях моделей рассматриваемой системы. Следует различать физические и математические модели, а также моделирующие алгоритмы для имитационного (статистического, машинного) моделирования на ЭВМ. В этой книге СМО, как математические модели реальных систем, исследуются аналитическими методами теории вероятностей. Как правило, основные задачи сводятся к рассмотрению соответствующих случайных процессов и определению их свойств, распределений или числовых характеристик. В ходе машинного моделирования для конкретных наборов параметров имитируются траектории случайных процессов, точнее их значения в некоторых точках. По реализациям траекторий статистическими методами оцениваются значения искомых характеристик.