Процесс гибели и размножения

В теории массового обслуживания широкое распространение имеет специальный класс случайных процессов — так называе­мый процесс гибели и размножения. Название этого процесса свя­зано с рядом биологических задач, где он является математиче­ской моделью изменения численности биологических популяций.

^-23 ^*-1,* Рис. 15.4

^■*Д-+1 Л-л -I,*

Ч+и Я.,

Рассмотрим упорядоченное множество состояний системы Sq, Si, S2,.., St- Переходы могут осуществляться из любого со-

При записи системы (15.10) одно "лишнее" уравнение

МЫ ИСКЛЮ-

Граф состояний процесса гибели и размножения имеет вид, показанный на рис. 15.4.

 

 

 

 

 

 

 

-Ьо	^01	S,	^•1-2 _
^-10	х2,

Глава 15

Элементы теории массового обслуживания

 

Решая систему (15.14), (15.15), можно получить

стояния только в состояния с соседними номерами, т.е. из со­стояния S_k возможны переходы только либо в состояние S_k.\, либо в состояние S^+i¹.

Предположим, что все потоки событий, переводящие систему по стрелкам графа, простейшие с соответствующими интенсивно-стями k_k)k+i или Х_к+1ук.

По графу, представленному на рис. 15.4, составим и решим алгебраические уравнения для предельных вероятностей со­стояний (их существование вытекает из возможности перехода из каждого состояния в каждое другое и конечности числа со­стояний).

В соответствии с правилом составления таких уравнений (см. 15.13) получим: для состояния Sq

MlPo = hoP\ > (15.12)

для состояния S\ - (Xi2⁺ho)Pi ~ MiPo⁺^2\P2, которое с учетом (15.12) приводится к виду

h2Pl=^2lP2- (15.13)

Аналогично, записывая уравнения для предельных вероятно­стей других состояний, можно получить следующую систему уравнений:

^oiPo - ^-\oPi>

 

^■01 ^12^-01^я-1,д--- ^12^-01

А>=

^-л,л-1---^')1^

^21Л10

21ЛЮ,

^л-1,л---^-12^01

Pl—^LP0,P2=~m "А), -,Рп=

(15.16)

Ро-

(15.17)

К-]\К

МО

... Ki\K

21л10

21л10

Чл-1

Легко заметить, что в формулах (15.17) для р\, Р2,..., р„ коэф­фициенты при ро есть слагаемые, стоящие после единицы в фор­муле (15.16). Числители этих коэффициентов представляют про­изведение всех интенсивностей, стоящих у стрелок, ведущих сле­ва направо до данного состояния S_k (k=l, 2,..., «), а знаменатели — произведение всех интенсивностей, стоящих у стрелок, веду­щих справа налево до состояния S_k. ^ 15.4. Процесс гибели и размножения представлен графом (рис. 15.5). Найти предельные вероятности состояний.

 

So

--------------------- >■ *7-

S,

---------------------»■

ь

Рис. 15.5

Решение. По формуле (15.16) найдем

 

<

^k-lkPk-l ~ ^k,k+lPk'

„ и 1 21

= 0,706,

 

/

^•n-lnPn-l ~ ^n,n+lPn,

к которой добавляется нормировочное условие

Po + Pi + P2+-+Pn = ^l (15.15)

¹ При анализе численности популяций считают, что состояние S_k со­ответствует численности популяции, равной к, и переход системы из состояния S_k в состояние S_k+i происходит при рождении одного члена популяции, а переход в состояние S_k..\ — при гибели одного члена попу­ляции.

по (15.17) - я = j 0,706 = 0,176, Р2=~ 0,706=0,118, т.е. в уста­новившемся, стационарном режиме в среднем 70,6% времени система будет находиться в состоянии So, 17,6% — в состоянии Si и 11,8% — в состоянии ^2>

СМО с отказами

В качестве показателей эффективности СМО с отказами будем рассматривать:

А — абсолютную пропускную способность СМО, т.е. среднее число заявок, обслуживаемых в единицу времени;

Глава 15

Элементы теории массового обслуживания

 

(15.19)

Q — относительную пропускную способность, т.е. среднюю долю пришедших заявок, обслуживаемых системой;

Р_0ТК — вероятность отказа, т.е. того, что заявка покинет СМО необслуженной;

к — среднее число занятых каналов (для многоканальной системы).

Одноканальная система с отказами. Рассмотрим задачу.

Имеется один канал, на который поступает поток заявок с ин­тенсивностью X. Поток обслуживании имеет интенсивность ц.¹. Найти предельные вероятности состояний системы и показатели ее эффективности.

Система S (СМО) имеет два состояния: So — канал свободен, Si — канал занят. Размеченный граф состояний представлен на рис. 15.6.

 

 

 

 

 

3,		X		S,
	И

Рис. 15.6

В предельном, стационарном режиме система алгебраических уравнений для вероятностей состояний имеет вид (см. правило составления таких уравнений на с. 343).

(15.18)

MA = ^/>о>

т.е. система вырождается в одно уравнение. Учитывая нормиро­вочное условие р₀ + pi=l, найдем из (15.18) предельные вероятно­сти состояний

и. X

Х + ц Х + ц

которые выражают среднее относительное время пребывания сис­темы в состоянии Sq (когда канал свободен) и Si (когда канал

¹ Здесь и в дальнейшем предполагается, что все потоки событий, пе­реводящие СМО из состояния в состояние, будут простейшими. К ним относится и поток обслуживании — поток заявок, обслуживаемых одним непрерывно занятым каналом. Среднее время обслуживания / ^ обрат­но по величине интенсивности ц, т.е. / об.^Л¹-

занят), т.е. определяют соответственно относительную пропуск­ную способность Q системы и вероятность отказа Р_тк:

Q=-T—» (15.20)

Дтк = т---- • (15.21)

Х + ц '

Абсолютную пропускную способность найдем, умножив отно­сительную пропускную способность Q на интенсивность потока отказов

А=-^-. (15.22)

X + \i '

^ 15.5. Известно, что заявки на телефонные переговоры в телевизи­онном ателье поступают с интенсивностью X, равной 90 заявок в час, а средняя продолжительность разговора по телефону Г_об.=2 мин. Определить показатели эффективности работы СМО (телефонной связи) при наличии одного телефонного номера.

Решение. Имеем Х=90 (1/ч), t _об.=2 мин. Интенсивность по­тока обслуживании ц= 1/ 1 _об = 1/2=0,5 (1/мин)=30 (1/ч). По (15.20) относительная пропускная способность СМО (>=30/(90+30)=0,25, т.е. в среднем только 25% поступающих заявок осуществят пере­говоры по телефону. Соответственно вероятность отказа в обслу­живании составит Р_тк=0,75 (см. (15.21)). Абсолютная пропускная способность СМО по (15.29) ^=900,25=22,5, т.е. в среднем в час будут обслужены 22,5 заявки на переговоры. Очевидно, что при наличии только одного телефонного номера СМО будет плохо справляться с потоком заявок. ►

Многоканальная система с отказами. Рассмотрим классическую задачу Эрланга.

Имеется п каналов, на которые поступает поток заявок с ин­тенсивностью X. Поток обслуживании имеет интенсивность ц. Найти предельные вероятности состояний системы и показатели ее эффективности.

Система S (СМО) имеет следующие состояния (нумеруем их по числу заявок, находящихся в системе): So, S_x, Si,..., S^, ■■■ S_n, где S/c — состояние системы, когда в ней находится к заявок, т.е. занято к каналов.

Глава 15

Элементы теории массового обслуживания

 

будут представлять

Граф состояний СМО соответствует процессу гибели и раз­множения и показан на рис. 15.7.

 

 

 

 

 

 

 

 

 

^0	X	Д|	А.	Ь	X	X k\i	sk	X _ X "5+1)ц V	\
И	%

Рис. 15.7

Поток заявок последовательно переводит систему из любого левого состояния в соседнее правое с одной и той же интенсив­ностью X. Интенсивность же потока обслуживании, переводящих систему из любого правого состояния в соседнее левое состояние, постоянно меняется в зависимости от состояния. Действительно, если СМО находится в состоянии 52 (два канала заняты), то она может перейти в состояние S\ (один канал занят), когда закончит обслуживание либо первый, либо второй канал, т.е. суммарная интенсивность их потоков обслуживании будет 2ц. Аналогично суммарный поток обслуживании, переводящий СМО из состоя­ния.% (три канала заняты) в S2, будет иметь интенсивность Зц, т.е. может освободиться любой из трех каналов и т.д.

В формуле (15.16) для схемы гибели и размножения получим для предельной вероятности состояния

X"

-1

•+...+ -

1 + —+ ■

Ро=

к\»к

(15.23)

nlix")

2!ц²

X"

где члены разложения —, ------------- j

я'ц"

И 2!ц'

собой коэффициенты при ро в выражениях для предельных веро­ятностей р\, Р2,..., Рк, —, Рп- Величина

X

р=-

(15.24)

И

называется приведенной интенсивностью потока заявок или интен­сивностью нагрузки канала. Она выражает среднее число заявок, приходящее за среднее время обслуживания одной заявки. Теперь

Р² Р* р"

Pi-PPo, Pi=Y\P^ •••> Pk=jjPo, -, РгГ^Ро- (15.26)

Формулы (15.25) и (15.26) для предельных вероятностей полу­чили названия формул Эрланга¹ в честь основателя теории массо­вого обслуживания.

Вероятность отказа СМО есть предельная вероятность того, что все п каналов системы будут заняты, т.е.

л

Р₀тк ^{= Е}-:Ро- (15.27)

Относительная пропускная способность — вероятность того, что заявка будет обслужена:

е = 1-Р_отк = 1-^-/>₀. (15.28)

Абсолютная пропускная способность:

A = XQ = \\l-£p₀\. (15.29)

Среднее число занятых каналов к есть математическое ожи­дание числа занятых каналов:

_ л

к = 5Ж,

к=0

где рк — предельные вероятности состояний, определяемых по
формулам (15.25), (15.26). >

Однако среднее число занятых каналов можно найти проще, если учесть, что абсолютная пропускная способность системы А есть не что иное, как интенсивность потока обслуженных систе­мой заявок (в единицу времени). Так как каждый занятый канал обслуживает в среднем ц заявок (в единицу времени), то среднее число занятых каналов

к = — (15.30)

¹ Эрланг А.К. (конец XIX в. — начало XX в.) — датский инженер, ма­тематик.

Глава 15

Элементы теории массового обслуживания

 

(15.31)

или, учитывая (15.29), (15.24):

¹->

^ 15.6. В условиях задачи 15.5 определить оптимальное число телефонных номеров в телевизионном ателье, если условием оп­тимальности считать удовлетворение в среднем из каждых 100 заявок не менее 90 заявок на переговоры:

Решение. Интенсивность нагрузки канала по формуле (15.25) р=90/30=3, т.е. за время среднего (по продолжительности) телефонного разговора Г₀б.⁼2 мин. поступает в среднем 3 заявки на переговоры.

Будем постепенно увеличивать число каналов (телефонных номеров) п=2, 3, 4,... и определим по формулам (15.25), (15.28), (15.29) для получаемой л-канальной СМО характеристики обслу­живания. Например, при л = 2 р₀ =(l + 3 + 3²/2М = 0,118» 0,12;

Q = \- (з²/2!)-0,118 = 0.471 * 0,47; ^=90-0,471=42,4 и т.д. Значение характеристик СМО сведем в табл. 15.1.

Таблица 15.1

 

 

Характеристика обслуживания	Число каналов (телефонных номеров)
Относительная пропу­скная способность Q	0,25	0,47	0,65	0,79	0,90	0,95
Абсолютная пропуск­ная способность А	22,5	42,4	58,8	71,5	80,1	85,3

По условию оптимальности Q £ 0,9, следовательно, в телевизи­онном ателье необходимо установить 5 телефонных номеров (в этом случае Q = 0,90 — см. табл. 15.1). При этом в час будут об­служиваться в среднем 80 заявок (А = 80,1), а среднее число заня­тых телефонных номеров (каналов) по формуле (15.30) к = = 80,1/30 = 2,67> ^ 15.7. В вычислительный центр коллективного пользования с тремя ЭВМ поступают заказы от предприятий на вычислительные работы. Если работают все три ЭВМ, то вновь поступающий заказ

не принимается, и предприятие вынуждено обратиться в другой вычислительный центр. Среднее время работы с одним заказом составляет 3 ч. Интенсивность потока заявок 0,25 (1/ч). Найти предельные вероятности состояний и показатели эффективности работы вычислительного центра.

Решение. По условию л=3, А=0,25_(1/ч), Г₀б⁼³ (ч)- Интен­сивность потока обслуживании \i=l/t _об = 1/3=0,33. Интенсив­ность нагрузки ЭВМ по формуле (15.24) р=0,25/0,33=0,75. Найдем предельные вероятности состояний:

по формуле (15.25) _/7₀=(1+0,75+0,75²/2!+0,75³/3!)-¹=0,476;

по формуле (15.26) ^,=0,75-0,476=0,357; />₂=(0,75²/2!)-0,476= =0,134; />₃=(0,75³/3!)-0,476=0,033, т.е. в стационарном режиме ра­боты вычислительного центра в среднем 47,6% времени нет ни одной заявки, 35,7% — имеется одна заявка (занята одна ЭВМ), 13,4% — две заявки (две ЭВМ), 3,3% времени — три заявки (заняты три ЭВМ).

Вероятность отказа (когда заняты все три ЭВМ), таким обра­зом, Р_тк~Рз^=:0,033.

По формуле (15.28) относительная пропускная способность центра Q = 1-0,033 = 0,967, т.е. в среднем из каждых 100 заявок вычислительный центр обслуживает 96,7 заявок.

По формуле (15.29) абсолютная пропускная способность цен­тра А = 0,250,967 - 0,242, т.е. в один час в среднем обслуживается 0,242 заявки.

По формуле (15.30) > среднее число занятых ЭВМ к = = 0,242/0,33 = 0,725, т.е. каждая из трех ЭВМ будет занята обслу­живанием заявок в среднем лишь на 72,5/3 = 24,2%.

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

⇐ Предыдущая1234Следующая ⇒

Поделиться:

Воспользуйтесь поиском по сайту: