Рассмотрим одноканальную систему
массового обслуживания (СМО) с ожиданием.
Пусть входящий поток заявок на обслуживание -
простейший поток с интенсивностью l
.
Интенсивность потока обслуживания равна m . Длительность обслуживания - случайная величина, подчиненная показательному закону распределения. Поток обслуживаний является простейшим пуассоновским потоком событий. Заявка, поступившая в момент, когда канал занят, становится в очередь и ожидает обслуживания. Предположим, что СМО не может вместить более N заявок, т.е. заявки, не попавшие в ожидание, покидают СМО. Состояния СМО имеют следующую интерпретацию:
Канал свободен;
Канал занят, очереди нет;
Канал занят, одна заявка в очереди;
..............................
Канал занят, n-1 заявка в очереди;
Канал занят, N-1 заявка в очереди.
Стационарный процесс в данной системе будет описываться следующей системой алгебраических уравнений:
, n=0,
...................................
-( , 0 ................................... n - номер состояния. Система уравнений имеет следующее
решение:: Если , n=1, 2, ..., N, Выполнение условия стационарности r
< 1 не обязательно, поскольку
число допускаемых в СМО заявок контролируется
путем введения ограничения на длину очереди.
Определим характеристики одноканальной СМО с
ожиданием и ограниченной длиной очереди, равной
(N-1): 2) относительная пропускная способность
СМО: 3) абсолютная пропускная способность
СМО: 4) среднее число находящихся в СМО
заявок: 5) среднее время пребывания заявки в СМО: 6) средняя продолжительность пребывания
клиента (заявки) в очереди: 7) среднее число заявок в очереди (длина
очереди): Задача 1
. Специализированный пост
диагностики представляет собой одноканальную
СМО. Число стоянок для автомобилей, ожидающих
проведения диагностики, ограниченно и равно 3.
Если все стоянки заняты, то очередной автомобиль,
прибывший на диагностику, в очередь на
обслуживание не становится. Поток автомобилей,
прибывающих на диагностику, распределен по
закону Пуассона и имеет интенсивность l
= 0.85 (автомобиля в час). Время
диагностики автомобиля распределено по
показательному закону и в среднем составляет 1.05
час. Требуется определить вероятностные
характеристики поста диагностики, работающего в
стационарном режиме. > lambda:=0.85;
2) Зададим среднее время обслуживания и
выразим интенсивность потока обслуживания
автомобилей: > t:=1.05:mu:=1/t;
3) Найдем приведенную интенсивность
потока автомобилей как отношение интенсивностей
l
и m
, т.е.. > rho:=lambda/mu;
4) Вычислим финальные вероятности
системы: > N:=4:P:=(1-rho)/(1-rho^(N+1));P:=rho*P;P:=rho^2*P;P:=rho^3*P;P:=rho^4*P;
5) Вероятность отказа в обслуживании
автомобиля:: > P:=P;
Отсюда следует, что пост диагностики не
обслуживает автомобили в среднем в 15.8% случаев. > q:=1-P;
7) Абсолютная пропускная способность
поста диагностики (автомобиля в час): > A:=lambda*q;
8) Среднее число автомобилей в СМО: > L[s]:=rho*(1-(N+1)*rho^N+N*rho^(N+1))/((1-rho)*(1-rho^(N+1)));
9) Среднее время пребывания автомобиля в
СМО: > W[s]:=L[s]/(lambda*(1-P[N]));
10) Средняя продолжительность пребывания
заявки в очереди на обслуживание: > W["q"]:=W[s]-1/mu;
11) Среднее число заявок в очереди (длина
очереди): > L["q"]:=lambda*(1-P[N])*W["q"];
Для статистического моделирования
работы поста диагностики составим следующую
процедуру: > p:=proc(k) global
t_och1,t_och2,t_och3,sm_t_obs,post,otk,obsl:local t1,t_okon,t,rn_post,och,per: Принятые обозначения: Повторите опыт 50 раз в цикле, найдите
оценки характеристик СМО, сравните их с
теоретическими значениями. Задача 2
: Система (в нашем случае вычислительная система) изменяет свои состояния под действием потока заявок (заданий) -поступающие заявки (задания) увеличивают очередь. Число заданий в очереди плюс число заданий, которые обрабатываются ЭВМ (т.е. число заданий в системе), - это характеристика состояния системы . Очередь уменьшается, как только одна из ЭВМ заканчивает обработку (обслуживание) задания. Тотчас же на эту ЭВМ из очереди поступает стоящее впереди (или по какому-либо другому приоритету) задание и очередь уменьшается. Таким образом, число заданий в системе растет благодаря потоку заданий , а уменьшается благодаря окончанию обслуживания с помощью ЭВМ. Устройства обработки заявок в теории СМО называют каналами обслуживания. В этой теории поток заданий (заявок на обслуживание) характеризуется интенсивностью Л. - средним количеством заявок, поступающих в единицу времени (скажем, в час). Среднее время обслуживания (обработки) одного задания /о, определяет так называемую интенсивность потока обслуживания ц,
Такой подход позволит определить число бригад при различной интенсивности потока и продолжительности обслуживания.
В универсальном магазине (в отделе самообслуживания) на выходе планируется разместить кассы сканирования для приема от покупателей денег за товары. Интенсивность потока покупателей равна 6 чел. /мин. Интенсивность обслуживания составляет 1,4 чел./мин. Допустимая длина очереди не должна превышать трех человек.
Учитывая, что увеличение числа заявок (заданий) в системе (т.е. номера состояния) происходит под воздействием их потока с интенсивностью /, а уменьшение - под воздействием потока обслуживания с интенсивностью г, изобразим размеченный граф состояний нашей системы (рис. 3.3).
Наиболее общей является ситуация, когда интенсивность потока покупателей носит случайный характер, то есть подчиняется распределению Пуассона , а время обслуживания подчиняется закону обратного экспоненциального распределения . Не будем заниматься выводом формул, отметим лишь, что
В связи с тем что потоки заявок в системе рассчитаны для средних суток, то расчеты длины очереди L и среднего времени ожидания обслуживания Тож, как и другие качественные параметры, будут сделаны неверно, так как интенсивность потока в различные часы суток различна и может меняться до 5 раз. Конечно, можно рассчитать эти параметры за каждый час отдельно, но и это будет неверно, так как СМО будет находиться в постоянном переходном процессе. В этом случае входной поток будет нестационарным и с последействием, так как математическое ожидание числа заказов в единицу времени будет меняться в 3- 5 раз, а число заказов, поступивших, например, в 18 часов, зависит от того, сколько их было фактически за каждый предыдущий час.
Пример 3.1. Пусть одноканальная СМО с отказами представляет собой один пост ежедневного обслуживания (ЕО) для мойки автомобилей. Заявка - автомобиль, прибывший в момент, когда пост занят, - получает отказ в обслуживании. Интенсивность потока автомобилей Л = 1,0 (автомобиль в час). Средняя продолжительность обслуживания - 1,8 часа. Поток автомобилей и поток обслуживании являются простейшими.
Параметр потока обслуживания л и приведенная интенсивность потока автомобилей р определены в примере 3.2
Заметим, что подобный расчет требуется не только при проектировании системы обслуживания он необходим при каждом серьезном изменении интенсивностей потоков заявок, их маршрутизации, трудоемкости обработки, требований к качеству обслуживания . Таким образом, необходимыми расчетными средствами должны быть оснащены не только проектировщики, но и управляющий персонал реально эксплуатируемых систем обслуживания.
О Пример. В пункте химчистки имеется три аппарата для чистки. Интенсивность потока посетителей А, = 6 (посетителей в час). Интенсивность обслуживания посетителей одним аппаратом i = 3 (посетителей в час). Среднее количество посетителей, покидающих очередь, не дождавшись обслуживания, VBS (посетитель в час). Найти абсолютную пропускную способность пункта.
Расчет производится на один год с учетом сложившихся в базисном году среднесуточного потока заявок на ремонт и интенсивности обслуживания 1 скважины.
Величину р называют приведенной плотностью потока требований или интенсивностью нагрузки, р - это среднее число требований, приходящееся на среднее время обслуживания одного требования.
СМОЬ СМО2 и СМО3 представляют собой пг, п2- и п3- канальные системы с неограниченной очередью и интенсивностью потоков обслуживании // , ju2 и //з, соответственно. Время повторного обслуживания заявки в
Одноканальная СМО с ожиданием. Система массового обслуживания имеет один канал. Входящий поток заявок на обслуживание - простейший поток с интенсивностью X. Интенсивность потока обслуживания равна ц (т. е. в среднем непрерывно занятый канал будет выдавать ц обслуженных заявок). Длительность обслуживания - случайная величина , подчиненная показательному закону распределения. Поток обслуживании является простейшим пуассо-новским потоком событий . Заявка, поступившая в момент, когда канал занят, становится в очередь и ожидает обслуживания.
Производительность канала -интенсивность простейшего потока обслуживании П0б (среднее число заявок, обслуживаемое каналом за единицу времени при непрерывной работе) in П0б = ju = onst 100 заявок/день
Суть упрощений при описании реального предпринимательского процесса моделью СМО состоит в следующем. Во-первых, все однотипные запросы и волеизъявления дотребителей о продаже им того или иного товара или оказании некоторых конкретных услуг представляются в виде так называемого потока заявок на обслуживание. Во-вторых, сложный процесс заключения коммерческого договора купли-продажи , оказания возмездных услуг и их исполнения коммерческим предприятием моделируется аналогично в виде потока обслуживания. При этом модельным аналогом конкретного работника предприятия, который обслуживает потребителя, или конкретного аппарата самообслуживания (колонка АЗС, телефонный канал АТС и т.п.) является так называемый канал обслуживания . В-третьих, вводят допущение о том, что все существенные характеристики как потока заявок, так и потока обслуживания сосредоточены только в единственном их параметре, который называют интенсивностью потока . При этом под интенсивностью потока понимают число событий в соответствующем потоке в единицу времени. Например, под интенсив-
Пример 3.4. Пусть -канальная СМО представляет собой вычислительный центр (ВЦ) с тремя (п = 3) взаимозаменяемыми ПЭВМ для решения поступающих задач. Поток задач , поступающих на ВЦ, имеет интенсивность Л = 1 задаче в час. Средняя продолжительность обслуживания 7обсл =1,8 час. Поток заявок на решение задач и поток обслуживания этих заявок являются простейшими.
Полученные выше результаты относились к ситуации, когда интенсивность k потока заявок на восстановление не зависит от числа k находящихся в ремонтном органе необслуженных заявок. В противном случае говорят о замкнутых системах обслуживания. При ограниченном числе R источников заявок обычно считают, что А/ = А(Л - А). Методы расчета марковских систем подобного вида хорошо известны (формулы Энгсета). Рассчитывать немарковские системы значительно сложнее. Особенно труден анализ системы, где интенсивность отказов зависит от объема ЗИПа s (запас s рассматривается как холодный резерв, не подверженный отказам). Между тем этот случай достаточно типичен. Если считать, что в рабочей системе установлены R источников заявок, то интенсивность отказов будет оставаться постоянной и равной АЛ, пока в системе восстановления не скопится k > s заявок. Тогда интенсивность потока заявок начнет убывать по закону А = X. Методика расчета подобной СМО вида M/G/l/(R + s) была предложена автором в статье , оказалась весьма громоздкой и к тому же неприменимой для многоканальных систем восстановления. Однако ап-проксимационные методы, описанные в главе 3, без труда обобщаются и на этот случай. Здесь мы отметим особенности его реализации
Найдем способ расчета стационарных вероятностей состояний одношналъной системы с указанной зависимостью интенсивности потока от числа заявок в ней и произвольным распределением длительности обслуживания B(t).
Сам К.Эрланг изучал эту задачу в следующих предположениях поток требований - пуассоновский с интенсивностью J длительность обслуживания распределена по показательному закону , причем средняя продолжительность обслуживания. При названных предположениях К.Эрланг показал, что если число обслуживающих устройств равно /7 , то при стационарном пуас-соновском В качестве показателей эффективности СМО с отказами будем рассматривать: 1) A
- абсолютную пропускную способность СМО
, т.е. среднее число заявок, обслуживаемых в единицу времени; 2) Q
- относительную пропускную способность
, т.е. среднюю долю пришедших заявок, обслуживаемых системой; 3) P_{\text{otk}}
- вероятность отказа
, т.е. того, что заявка покинет СМО необслуженной; 4) \overline{k}
- среднее число занятых каналов
(для многоканальной системы). Рассмотрим задачу. Имеется один канал, на который поступает поток заявок с интенсивностью \lambda
. Поток обслуживании имеет интенсивность \mu
. Найти предельные вероятности состояний системы и показатели ее эффективности. Примечание.
Здесь и в дальнейшем предполагается, что все потоки событий, переводящие СМО из состояния в состояние, будут простейшими. К ним относится и поток обслуживании - поток заявок, обслуживаемых одним непрерывно занятым каналом. Среднее время обслуживания обратно по величине интенсивности \mu
, т.е. \overline{t}_{\text{ob.}}=1/\mu
. Система S
(СМО) имеет два состояния: S_0
- канал свободен, S_1
- канал занят. Размеченный граф состояний представлен на рис. 6. В предельном, стационарном режиме система алгебраических уравнений для вероятностей состояний имеет вид (см. выше правило составления таких уравнений) \begin{cases}\lambda\cdot p_0=\mu\cdot p_1,\\\mu\cdot p_1=\lambda\cdot p_0,\end{cases}
P_0=\frac{\mu}{\lambda+\mu},\quad p_1=\frac{\lambda}{\lambda+\mu}\,
Q=\frac{\mu}{\lambda+\mu}\,
P_{\text{otk}}=\frac{\lambda}{\lambda+\mu}\,.
Абсолютную пропускную способность найдем, умножив относительную пропускную способность Q
на интенсивность потока отказов A=\frac{\lambda\mu}{\lambda+\mu}\,.
Пример 5.
Известно, что заявки на телефонные переговоры в телевизионном ателье поступают с интенсивностью \lambda
, равной 90 заявок в час, а средняя продолжительность разговора по телефону мин. Определить показатели эффективности работы СМО (телефонной связи) при наличии одного телефонного номера. Решение.
Имеем \lambda=90
(1/ч), \overline{t}_{\text{ob.}}=2
мин. Интенсивность потока обслуживании \mu=\frac{1}{\overline{t}_{\text{ob.}}}=\frac{1}{2}=0,\!5
(1/мин) =30
(1/ч). По (20) относительная пропускная способность СМО Q=\frac{30}{90+30}=0,\!25
, т.е. в среднем только 25% поступающих заявок осуществят переговоры по телефону. Соответственно вероятность отказа в обслуживании составит P_{\text{otk}}=0,\!75
(см. (21)). Абсолютная пропускная способность СМО по (29) A=90\cdot0.\!25=22,\!5
, т.е. в среднем в час будут обслужены 22,5 заявки на переговоры. Очевидно, что при наличии только одного телефонного номера СМО будет плохо справляться с потоком заявок. Рассмотрим классическую задачу Эрланга
. Имеется n
каналов, на которые поступает поток заявок с интенсивностью \lambda
. Поток обслуживании имеет интенсивность \mu
. Найти предельные вероятности состояний системы и показатели ее эффективности. Система S
(СМО) имеет следующие состояния (нумеруем их по числу заявок, находящихся в системе): S_0,S_1,S_2,\ldots,S_k,\ldots,S_n
, где S_k
- состояние системы, когда в ней находится k
заявок, т.е. занято k
каналов. Граф состояний СМО соответствует процессу гибели и размножения и показан на рис. 7. Поток заявок последовательно переводит систему из любого левого состояния в соседнее правое с одной и той же интенсивностью \lambda
. Интенсивность же потока обслуживании, переводящих систему из любого правого состояния в соседнее левое состояние, постоянно меняется в зависимости от состояния. Действительно, если СМО находится в состоянии S_2
(два канала заняты), то она может перейти в состояние S_1
(один канал занят), когда закончит обслуживание либо первый, либо второй канал, т.е. суммарная интенсивность их потоков обслуживании будет 2\mu
. Аналогично суммарный поток обслуживании, переводящий СМО из состояния S_3
(три канала заняты) в S_2
, будет иметь интенсивность 3\mu
, т.е. может освободиться любой из трех каналов и т.д. В формуле (16) для схемы гибели и размножения получим для предельной вероятности состояния P_0={\left(1+ \frac{\lambda}{\mu}+ \frac{\lambda^2}{2!\mu^2}+\ldots+\frac{\lambda^k}{k!\mu^k}+\ldots+ \frac{\lambda^n}{n!\mu^n}\right)\!}^{-1},
где члены разложения \frac{\lambda}{\mu},\,\frac{\lambda^2}{2!\mu^2},\,\ldots,\,\frac{\lambda^k}{k!\mu^k},\,\ldots,\, \frac{\lambda^n}{n!\mu^n}
, будут представлять собой коэффициенты при p_0
в выражениях для предельных вероятностей p_1,p_2,\ldots,p_k,\ldots,p_n
. Величина \rho=\frac{\lambda}{\mu}
P_0={\left(1+\rho+\frac{\rho^2}{2!}+\ldots+\frac{\rho^k}{k!}+\ldots+\frac{\rho^n}{n!}\right)\!}^{-1},
P_1=\rho\cdot p,\quad p_2=\frac{\rho^2}{2!}\cdot p_0,\quad \ldots,\quad p_k=\frac{\rho^k}{k!}\cdot p_0,\quad \ldots,\quad p_n=\frac{\rho^n}{n!}\cdot p_0.
Формулы (25) и (26) для предельных вероятностей получили названия формул Эрланга
в честь основателя теории массового обслуживания. Вероятность отказа СМО есть предельная вероятность того, что все я каналов системы будут заняты, т.е. P_{\text{otk}}= \frac{\rho^n}{n!}\cdot p_0.
Относительная пропускная способность - вероятность того, что заявка будет обслужена: Q=1- P_{\text{otk}}=1-\frac{\rho^n}{n!}\cdot p_0.
Абсолютная пропускная способность: A=\lambda\cdot Q=\lambda\cdot\left(1-\frac{\rho^n}{n!}\cdot p_0\right)\!.
Среднее число занятых каналов \overline{k}
есть математическое ожидание числа занятых каналов: \overline{k}=\sum_{k=0}^{n}(k\cdot p_k),
Однако среднее число занятых каналов можно найти проще, если учесть, что абсолютная пропускная способность системы A
есть не что иное, как интенсивность потока обслуженных
системой заявок (в единицу времени). Так как каждый занятый канал обслуживает в среднем \mu
заявок (в единицу времени), то среднее число занятых каналов \overline{k}=\frac{A}{\mu}
Или, учитывая (29), (24):
\overline{k}=\rho\cdot\left(1-\frac{\rho^n}{n!}\cdot p_0\right)\!.
Пример 6.
В условиях примера 5 определить оптимальное число телефонных номеров в телевизионном ателье, если условием оптимальности считать удовлетворение в среднем из каждых 100 заявок не менее 90 заявок на переговоры. Решение.
Интенсивность нагрузки канала по формуле (25) \rho=\frac{90}{30}=3
, т.е. за время среднего (по продолжительности) телефонного разговора \overline{t}_{\text{ob.}}=2
мин. поступает в среднем 3 заявки на переговоры. Будем постепенно увеличивать число каналов (телефонных номеров) n=2,3,4,\ldots
и определим по формулам (25), (28), (29) для получаемой n-канальной СМО характеристики обслуживания. Например, при n=2
имеем З_0={\left(1+3+ \frac{3^2}{2!}\right)\!}^{-1}=0,\!118\approx0,\!12;\quad Q=1-\frac{3^2}{2!}\cdot0,\!118=0,\!471\approx0,\!47;\quad A=90\cdot0,\!471=42,\!4
и т.д. Значение характеристик СМО сведем в табл. 1. По условию оптимальности Q\geqslant0,\!9
, следовательно, в телевизионном ателье необходимо установить 5 телефонных номеров (в этом случае Q=0,\!9
- см. табл. 1). При этом в час будут обслуживаться в среднем 80 заявок (A=80,\!1)
, а среднее число занятых телефонных номеров (каналов) по формуле (30) \overline{k}=\frac{80,\!1}{30}=2,\!67
. Пример 7.
В вычислительный центр коллективного пользования с тремя ЭВМ поступают заказы от предприятий на вычислительные работы. Если работают все три ЭВМ, то вновь поступающий заказ не принимается, и предприятие вынуждено обратиться в другой вычислительный центр. Среднее время работы с одним заказом составляет 3 ч. Интенсивность потока заявок 0,25 (1/ч). Найти предельные вероятности состояний и показатели эффективности работы вычислительного центра. Решение.
По условию n=3,~\lambda=0,\!25
(1/ч), \overline{t}_{\text{ob.}}
=3 (ч). Интенсивность потока обслуживании \mu=\frac{1}{\overline{t}_{\text{ob.}}}=\frac{1}{3}=0,\!33
. Интенсивность нагрузки ЭВМ по формуле (24) \rho=\frac{0,\!25}{0,\!33}=0,\!75
. Найдем предельные вероятности состояний: – по формуле (25) p_0={\left(1+0,\!75+ \frac{0,\!75^2}{2!}+ \frac{0,\!75^3}{3!}\right)\!}^{-1}=0,\!476
; – по формуле (26) p_1=0,!75\cdot0,\!476=0,\!357;~p_2=\frac{0,\!75^2}{2!}\cdot0,\!476=0,\!134;~p_3=\frac{0,\!75^3}{3!}\cdot0,\!476=0,\!033
; Вероятность отказа (когда заняты все три ЭВМ), таким образом, P_{\text{otk}}=p_3=0,\!033
. По формуле (28) относительная пропускная способность центра Q=1-0,\!033=0,\!967
, т.е. в среднем из каждых 100 заявок вычислительный центр обслуживает 96,7 заявок. По формуле (29) абсолютная пропускная способность центра A=0,\!25\cdot0,\!967=0,\!242
, т.е. в один час в среднем обслуживается. 0,242 заявки. По формуле (30) среднее число занятых ЭВМ \overline{k}=\frac{0,\!242}{0,\!33}=0,\!725
, т.е. каждая из трех ЭВМ будет занята обслуживанием заявок в среднем лишь на \frac{72,\!5}{3}= 24,\!2%.
. При оценке эффективности работы вычислительного центра необходимо сопоставить доходы от выполнения заявок с потерями от простоя дорогостоящих ЭВМ (с одной стороны, у нас высокая пропускная способность СМО, а с другой стороны - значительный простой каналов обслуживания) и выбрать компромиссное решение. Задача 1.
На диспетчерский пульт поступает поток заявок, который является потоком Эрланга второго порядка. Интенсивность потока заявок равна 6 заявок в час. Если диспетчер в случайный момент оставляет пульт, то при первой же очередной заявке он обязан вернуться к пульту. Найти плотность распределения времени ожидания очередной заявки и построить ее график. Вычислить вероятность того, что диспетчер сможет отсутствовать от 10 до 20 минут. Решение
. Поскольку поток Эрланга второго порядка является стационарным потоком с ограниченным последействием, то для него справедлива формула Пальма где f1(θ)-
плотность распределения вероятностей для времени ожидания первого ближайшего события; По условиям задачи поток заявок является Эрланговским порядка =2. Тогда из (1) и (2) получим f1(θ)=3е-6θ(1+6
θ),
θ≥0.
(3) Построим график функции f1(θ)
. При θ
<0
имеем f1(θ)
=0
. При θ
=0
, f1(0)=3
. Рассмотрим предел При вычислении предела для раскрытия неопределенности типа использовано правило Лопиталя . По результатам исследований строим график функции f1(θ)
(Рис. 1). Обратим внимание на размерности времени в тексте задачи: для интенсивности это заявки в час, для времени-минуты. Перейдем к одним единицам времени: 10 мин=1/6 час, 20 мин=1/3 час. Для этих значений можно вычислить f1(θ)
и уточнить характер кривой Следовательно, искомая вероятность равна Этот интеграл легко вычисляется по частям, если положить Ответ: вероятность того, что диспетчер сможет отсутствовать от 10 до 20 минут равна 0,28. Задача 2.
Дисплейный зал имеет 5 дисплеев. Поток пользователей простейший. Среднее число пользователей, посещающих дисплейный зал за сутки, равно 140. Время обработки информации одним пользователем на одном дисплее распределено по показательному закону и составляет в среднем 40 минут. Определить, существует ли стационарный режим работы зала; вероятность того, что пользователь застанет все дисплеи занятыми; среднее число пользователей в дисплейном зале; среднее число пользователей в очереди; среднее время ожидания свободного дисплея; среднее время пребывания пользователя в дисплейном зале. Решение.
Рассматриваемая в задаче СМО относится к классу многоканальных систем с неограниченной очередью. Число каналов =5. Найдем λ-интенсивность потока заявок: где Найдем -интенсивность потока обслуживания: тогда Таким образом, классификатор данной системы имеет вид СМО (5, ∞; 5,85; 1,49). Вычислим Р*- вероятность того, что пользователь застанет все дисплеи занятыми. Очевидно, она равна сумме вероятностей таких событий: все дисплеи заняты, очереди нет (р5); все дисплеи заняты, один пользователь в очереди (р6); все дисплеи заняты, два пользователя в очереди (р7) и так далее. Поскольку для полной группы событий сумма вероятностей этих событий равна единице, то справедливо равенство Р*=р5+р6+р7+…=1 - ро - р1 - р2 - р3 - р4.
Найдем эти вероятности: ро
=0,014; р1
=3,93*0,014; р2
=7,72*0,014; р3
=10,12*0,014; р4
=9,94*0,014. 2. среднее число пользователей в дисплейном зале
3. среднее время ожидания свободного дисплея
4. среднее время пребывания пользователя в дисплейном зале
Ответ: стационарный режим работы дисплейного зала существует и характеризуется следующими показателями Р*
=0,54; пользователя; пользователя; ; . Из временных диаграмм видно, что необходимо научиться моделировать интервалы Т
i
. Применим метод обратных функций. Поскольку случайная величина Тi
распределена по показательному закону с параметром λ
=5, то плотность распределения имеет вид f
(τ)=5е-5τ
. Тогда значение F(Ti)
функции распределения вероятностей определяется интегралом Известно, что область значений функции распределения F
(T
)
есть отрезок . Выбираем из таблицы случайных чисел число и определяем Т
i
из равенства , откуда . Однако, если . Поэтому можно сразу получать из таблицы случайных чисел реализации . Следовательно, Таблица 1. ИСПЫТАНИЕ №1 № зая-вки Сл. число -ln ri
Момент поступления заявки Момент окончания обслужив. Счетчик заявок № зая-вки Сл. число -ln ri
Момент поступления заявки Момент окончания обслужив. Счетчик заявок № зая-вки Сл. число -ln ri
Момент поступления заявки Момент окончания обслужив. Счетчик заявок Таким образом, по результатам трех испытаний число обслуженных заявок составило соответственно: х1
=9, х2
=9, х3
=8. Найдем среднее число обслуженных заявок: Ответ: среднее число заявок, обслуженных СМО
за 4 минуты, равно 8,6(6). Рассмотрим способы моделирования на ЭВМ потоков заявок, поступающих в систему массового обслуживания. Сначала остановимся на достаточно простом и вместе с тем наиболее распространенном случае, когща в систему поступает ординарный стационарный поток однородных событий с ограниченным последействием (поток типа Пальма). Любой поток типа Пальма может быть задан функцией плотности случайных интервалов между последовательными моментами - поступления заявок. Для моделирования его на ЭВМ достаточно построить необходимое число реализаций потока, т. е. таких неслучайных последовательностей моментов поступления заявок в систему, интервалы между которыми являлись бы возможными значениями случайных величин описываемых функцией плотности Процедура построения последовательности состоит в следующем. Сначала формируется Функция плотности может быть определена через по формуле Пальма (4.4). Тогда, исходя из наличия в ЭВМ электронного или алгоритмического датчика случайных чисел с равномерным распределением в интервале (0,1), приступаем к формированию Для этого одним из способов, рассмотренных в главе П, преобразуем случайное число в случайное число имеющее функцию плотности Получив полагаем В дальнейшем процедура получения любого совпадает с процедурой формирования т. е. очередное случайное число преобразуется в случайное число имеющее функцию плотности и Рассмотрим некоторые примеры, часто встречающиеся при решении практических задач методом статистического моделирования. Пример 1. Простейший (пауссоновский) поток. Как отмечалось выше, простейший (пауссоновский) поток является стационарным ординарным потоком однородных событий без последействия, т. е. одним из возможных частных случаев потоков типа Пальма. Функция плотности для простейшего потока имеет вид показательного распределения (4.6): где - интенсивность потока, определяющая среднее значение числа заявок, поступающих в единицу времени. Чтобы определить функцию плотности для первого интервала, воспользуемся формулой Пальма. После несложных вычислений получаем: Отсюда следует, что функция плотности первого интервала для простейшего потока имеет тот же вид, что и Этим свойством в общем случае, не обладают другие потоки типа Пальма. Таким образом, для формирования реализаций простейшего потока необходимо иметь последовательность случайных чисел имеющих показательное распределение (4.6) с параметром К. Методику получения такой последовательности мы рассматривали в главе II. В соответствии с (2.15) случайные числа могут быть получены по формуле где - случайные числа с равномерным распределением в интервале (0,1). Последовательность моментов поступления заявок будет следующей: Пример 2. Поток с равномерным распределением интервалов Функция плотности рассматриваемого потока имеет вид равномерного распределения: Можно показать, что среднее значение (математическое ожидание) случайной величины равно Поэтому среднее число заявок, поступивших в единицу времени (интенсивность потока): Определим функцию плотности для первого интервала. По формуле Пальма аналогично формуле (4.11): Заметим, что среднее значение длительности первого интервала может быть получено как математическое ожидание случайной величины, имеющей функцию плотности (4.16): Перейдем к формированию первого интервала Для этого, имея случайные числа с равномерным законом распределения в интервале (0,1), необходимо получить случайное число соответствующее функции плотности (4.16). Преобразуем соотношение (4.16) следующим образом. Подставим в него вместо величины ее значение из равенства (4.15). Тогда можно записать функцию плотности Необходимо отметить, что потоки, рассмотренные в примерах 1 и 2, отличаются благоприятной особенностью: интегралы в формуле Пальма и формулах преобразования случайных чисел берутся в конечном виде. В общем случае эти интегралы могут оказаться неберущимися. Кроме того, функции плотности иногда задаются таблично по (результатам обработки статистического материала. На практике в такого рода ситуациях пользуются приближенными методами. Интеграл в формуле Пальма вычисляется обычно для заданного набора численными методами. Это не оказывается существенно на объеме вычислений, так как формула Пальма применяется только один раз для данного потока. Преобразование случайных чисел выполняется, как правило, методом кусочной аппроксимации функции плотности в соответствии с соотношениями (2.23), (2.24) и (2.25).
, n=N,
,
1) вероятность отказа в обслуживании заявки:
;
;
;
;
Решение
:
1) Интенсивность прибытия автомобилей на
обслуживание:
6) Относительная пропускная способность поста
диагностики:
t_och1:=0:t_och2:=0:t_och3:=0:post:=0:otk:=0:obsl:=0:t_okon:=0:sm_t_obs:=0:och:=0:rn_post:=rand(1..1200):
for t from 1 by 1 to k do
t1:=rn_post():
if och=1 then t_och1:=t_och1+1 fi:
if och=2 then t_och2:=t_och2+1 fi:
if och=3 then t_och3:=t_och3+1 fi:
if t1>=1 and t1<=17 and t_okon=0 and och>=0 and och<=3 then per:=1 fi:
if t1>=1 and t1<=17 and t_okon>0 and och>=0 and och<3 then per:=2 fi:
if t1>=1 and t1<=17 and t_okon>0 and och=3 then per:=3 fi:
if t1>17 and t_okon>0 then per:=4 fi:
if t1>17 and t_okon=0 and och>0 then per:=5 fi:
if per=1 then t_okon:=stats():
sm_t_obs:=sm_t_obs+t_okon:obsl:=obsl+1:post:=post+1 fi:
if per=2 then t_okon:=t_okon-1:obsl:=obsl+1:och:=och+1:post:=post+1 fi:
if per=3 then t_okon:=t_okon-1:otk:=otk+1:post:=post+1 fi:
if per=4 then t_okon:=t_okon-1 fi:
if per=5 then t_okon:=stats(): sm_t_obs:=sm_t_obs+t_okon:och:=och-1 fi
od end:
t_och1,t_och2,t_och3 - количество минут, когда в очереди 1, 2
и 3 машины соответственно;
sm_t_obs - затрачено всего минут на обслуживание;
post - прибыло машин на обслуживание; otk - количество
отказов в обслуживании; obsl - обслужено машин;
t_obsl - продолжительность обслуживания машины,
инициализируется как случайная величина,
распределенная по закону Пуассона с
математическим ожиданием 65 минут (1 час 5 минут);
t1 - случайная величина, с одинаковой вероятностью
принимающая целые значения из интервала от 1 до
12000. Если t1>=0 и t1<=17, то считаем, что на пункт
диагностики поступила заявка (интенсивность 0.85
заявки в час = 17/12000 заявки в минуту);
t - параметр цикла (количество минут).
Проведем опыт продолжительностью в 5000 минут:
> p(5000);print("Поступило на
обслуживание автомобилей
",post);print("Обслужено ",obsl);
print("Отказано в обслуживании ",otk);
print("Затрачено на обслуживание
",sm_t_obs,"мин."); print(t_och1," мин. 1 машина в
очереди");print(t_och2,"мин. 2 машины в очереди");
print(t_och3," мин. 3 машины в очереди");
1) Модифицируйте процедуру для вычисления
числовых характеристик СМО. Задайте
продолжительность опыта в 1000 минут и повторите
опыт, например, 5 раз. Затем вычислите средние
значения каждой характеристики СМО. Сравните
опытные данные с вероятностными
характеристиками СМО.
2) Смоделируйте работу СМО для случая, когда
автомобиль обслуживается ровно 1 час 5 минут, а
все остальные параметры остаются прежними.
Сравните полученные данные с результатами
предыдущего пункта.
3) Так как интенсивность поступления заявок равна
0.85 машины в час, то в среднем промежуток времени
между поступлениями заявок составляет 1/0.85=100/85
часа, или около 71 минуты. Задайте интервал между
поступлениями заявок с помощью функции stats() и проведите ряд испытаний работы СМО.
Сравните средние значения характеристик,
полученных опытным путем, с вероятностными
характеристиками.
4) Задайте интенсивность обслуживания в 70 минут, а
число стоянок для машин равной 4, и проведите
испытания работы поста диагностики. Повторите
опыт для случая, когда интенсивность
обслуживания составляет 60 минут, а число стоянок
2. Как изменятся характеристики поста
диагностики?
5) Смоделируйте работу поста диагностики при
условии, что число стоянок не ограниченно.Одноканальная система (СМО) с отказами
т.е. система вырождается в одно уравнение. Учитывая нормировочное условие p_0+p_1=1
, найдем из (18) предельные вероятности состояний
которые выражают среднее относительное время пребывания системы в состоянии S_0
(когда канал свободен) и S_1
(когда канал занят), т.е. определяют соответственно относительную пропускную способность Q
системы и вероятность отказа P_{\text{otk}}:
Многоканальная система (СМО) с отказами
называется приведенной интенсивностью потока заявок
или интенсивностью нагрузки канала
. Она выражает среднее число заявок, приходящее за среднее время обслуживания одной заявки. Теперь
где p_k
- предельные вероятности состояний, определяемых по формулам (25), (26).
т.е. в стационарном режиме работы вычислительного центра в среднем 47,6% времени нет ни одной заявки, 35,7% - имеется одна заявка (занята одна ЭВМ), 13,4% - две заявки (две ЭВМ), 3,3% времени - три заявки (заняты три ЭВМ).
Чтобы произвести расчеты, необходимо разрешить элементы ActiveX!
λ
- интенсивность потока;
- порядок потока;
(θ)
- функция распределения вероятностей для времени между двумя соседними событиями потока Эрланга - го порядка (Э).
Известно, что функция распределения для потока Э имеет вид
. (2)
.
Из последнего соотношения при λ=6 будем иметь
Эти ординаты указаны на графике над соответствующими точками кривой.
Из курса теории вероятностей известно, что вероятность попадания случайной величины Х
в отрезок [α, β] численно равна площади под кривой плотности распределения вероятностей f(х)
. Эта площадь выражается определенным интегралом
U=1+6θ
и dV=е-6θ
dθ
. Тогда dU=6
dθ
и V=
.
Используя формулу 
получим
(час.) - среднее время между двумя последовательными заявками входящего потока пользователей. Тогда 
польз./час.
, где М[Т обсл.]=40 мин=0,67 часа - среднее время обслуживания одного пользователя одним дисплеем,
польз/час.
Вычислим коэффициент загрузки СМО 
. Известно, что для СМО такого класса стационарный режим существует, если отношение коэффициента загрузки системы к числу каналов меньше единицы. Находим это отношение 
.
Следовательно, стационарный режим существует. Предельное распределение вероятностей состояний вычисляется по формулам
Поскольку =5, имеем
Вынося за скобки общий множитель, получим
Р*=1-0,0148*(1+3,93+7,72+10,12+9,94)=1-0,014*32,71=1-0,46=0,54.
Используя формулы для вычисления показателей эффективности? найдем:
Вх
-входящий поток заявок, здесь ti
-моменты поступления заявок; Ti
-интервалы времени между двумя последовательными заявками. Очевидно, что ti
=ti
-1
+Т
i
.
К1-первый канал обслуживания;
К2-второй канал обслуживания; здесь жирные линии на временной оси обозначают интервалы занятости канала. Если оба канала свободны, то заявка становится под обслуживание в канал К1, в случае его занятости заявка обслуживается каналом К2.
Если заняты оба канала, то заявка покидает СМО необслуженной.
Вых ОБ-выходящий поток обслуженных заявок.
Вых ПТ-выходящий поток потерянных заявок за счет отказов СМО (случай занятости обоих каналов).
Статистические испытания продолжаются в течение временного интервала . Очевидно, что любое превышение времени tmax
влечет за собой сброс заявки в выходящий поток Вых ПТ. Так на рис. 3 заявка №10, пришедшая в систему в момент t10
, не успевает обслужиться до момента tmax
, так как t10+Тобсл.>tmax
. Следовательно, она не принимается свободным каналом К1 на обслуживание и сбрасывается в Вых ПТ, получая отказ.
Рис. 3
.
е-5Т
i
=
ri
, или –5Т
i
=
lnri
, откуда . Результаты вычислений удобно заносить в таблицу.
Для проведения испытания №1 были взяты случайные числа из приложения 2, начиная с первого числа первой строки. Далее выборка осуществлялась по строкам. Проведем еще два испытания.
Обратите внимание на выборку случайных чисел из таблицы приложения 2, если в испытании №1 последнее случайное число для заявки №16 было 0,37 (первое случайное число во второй строке), то испытание №2 начинается со следующего за ним случайного числа 0,54. Испытание №2 содержит последним случайное число 0,53 (пятое число в третьей строке). Следовательно, третье испытание начнется с числа 0,19. Вообще в пределах одной серии испытаний случайные числа из таблицы выбираются без пропусков и вставок по определенному порядку, например, по строкам.
Таблица 2
ИСПЫТАНИЕ №2
i
ri
Тi
ti=ti-1+Ti
ti+0,50К1
Таблица №3
ИСПЫТАНИЕ №3
i
ri
Т
i
ti=ti-1+Ti
ti+0,50
i
ri
Т
i
ti=ti-1+Ti
ti+0,50К1
Отчетность
