методичка

Глава 9. Цепи Маркова

Для m=3, получим

V(3)=	34 0,7				0,3 59	34				41,3 + 7,8		83,1
		4		+		=	4		+		=	.
				0,6	0,4 26				35,4 +10,4		49,8

Выводы. Ожидаемая прибыль за три перехода составит 83,1 у. е., если процесс начал развиваться из состояния ε1, и 49,8 у. е., если процесс начал развиваться из ε2. Ожидаемая средняя прибыль за один переход составит

Vср(3)= 13 49,883,1 = 16,627,7 .

Если m=4, получим

V(4)=	34 0,7				0,3	83,1	34			58,17 +14,94		107,11
		4		+			=	4		+		=	73,78	.
				0,6	0,4	49,8				49,86	+19,92

Выводы. Ожидаемая прибыль за четыре перехода составит 107,11 у. е., если процесс начал развиваться из состояния ε1, и 73,78 у. е., если процесс начал развиваться из ε2. Ожидаемая средняя прибыль за один переход составит

Vср(4)=	1	107,11				26,7775
	4		73,78		=	18,445	.

Финальные вероятности находят из системы уравнений:

							pP = p						, где p=[p1					p2 ...		pn ].
										= 1
				p1 + p2 +...+pn
	Тогда
					p		0,7 0,3		=		p		p				0,7p +0,6p					= p
			p				] 0,6	0,4		[				2 ], или				1			2	1
			[	1		2					1						0,3p +0,4p					= p .
																		1	+ p		2	2
							p + p =1											p			=1
							1	2										1	2
		2			1																	n
	Откуда p1 =		, p2	=		. Стационарное ожидаемое вознаграждение g= ∑ qipi.
		3			3
											2				1							k =1
	Следовательно, g=q1p1+q2p2= 34												+ 4			= 24 . Таким образом, если система
											3			3

работает в течение многих переходов и неизвестно ее текущее состояние, то ожидаемая прибыль за один шаг процесса составит 24 у. е.

■

71

ГЛАВА 10. ЭЛЕМЕНТЫ ТЕОРИИ МАССОВОГО ОБСЛУЖИВАНИЯ

Уравнения Колмогорова. Предельные вероятности состояний

Решение задания № 5.1.1-5.1.30

Исходные данные: λ01=1; λ02=2; λ10=2; λ13=2; λ20=3; λ23=1; λ31=3;

λ32=2; R1=10; R2=6; r1=4; r2=2.

1) Возможные состояния системы: S0 – оба узла исправны;

S1 – первый узел ремонтируется;

S2 – второй узел ремонтируется;

S3 – оба узла ремонтируются.

Размеченный граф системы изображен на рис. 7.

λ10		S0		λ20
	λ01		λ02
S1				S2
	λ13		λ23
λ31				λ32

S3

Рис. 7

2) Составим систему уравнений Колмогорова по правилу, согласно которому слева в уравнениях стоит предельная вероятность данного состояния pi умноженная на суммарную интенсивность всех потоков, ведущих из данного состояния, а справа – сумма произведений интенсивностей всех потоков, входящих в i-ое состояние, на вероятности тех состояний, из которых эти потоки исходят.

(λ01 + λ02 )p0				= λ10 p1 + λ20 p2
(λ10 + λ13 )p1 = λ01 p0 + λ31 p3 .
(λ20 + λ23 )p2 = λ02 p0 + λ32 p3
(λ		+ λ	)p	= λ p		+ λ p	2
	31	32	3	13	1	23

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

Тогда, дополняя эту систему уравнением p0 + p1 + p2 + p3 =1, получим

	(1+ 2)p0 = 2 p1 +3 p2																	3 p			= 2 p +3 p													p								+ p		+ p		2	+ p =1
				+ 2)p1 = p0																							2									0							1					3
									+3 p3											0				1
	(2																				=	p		+3 p														3 p				− 2 p			−3 p			= 0
				+1)p		= 2 p				+		2 p						4 p																																				.
	(3				2				0						3					1			0			3										0							1				2
																								+ p3											− p							+ 4 p				−3 p = 0
				+ 2)p3 = 3 p1 +1p2														2 p2 = p0
	(3																	p		+ p			+ p			+ p			=1							0							1					3
	p		0	+ p	+ p		2	+ p			3	=1							0		1				2		3								− p0									+ 2 p2 − p3 = 0
				1
Решим систему методом Гаусса:
	1			1		1				1					1				1 1					1				1			1											1 1 1 1							1
	3			− 2		−3 0									0				0 −5					−6 −3																		0 1 3 0							1
																															−3
	−1 4					0				−3				0					0 5					1 − 2							1											0 5 1 − 2							1
	−1 0					2 −1								0					0 1						3			0			1											0 5 6 3									3
		1 1 1								1					1					1 1 1									1				1										1 1 1 1								1
		0 1				3				0					1					0 1				3					0				1										0 1 3 0								1
		0 0			−14				− 2						− 4					0 0				−14 − 2								− 4											0 0 7 1								2		.
		0 0 −9								3					− 2					0 0				0			−60				−8												0 0 0 15								2
Таким образом
																														p				=			2
																																0
																																				5
															p0 + p1 + p2 + p3 =1															p =						1
																		p1 +3 p2								=1					1					5 .
																					7 p		+ p			= 2
																														p				=		4
																						2			3							2
																							15 p3			= 2										15
																																				2
																														p				=
																																				15
																															3

Поэтому в предельном, стационарном режиме система S0 в среднем 40% времени будет находиться в состоянии (оба узла исправны) ( p0 = 52 = 0,40) , 20% времени – в состоянии S1 (первый узел ремонтируется, второй работает) ( p1 = 15 = 0,20) , 27% времени – в состоянии S2 (второй узел

73

Раздел II. Решения типовых задач

ремонтируется, первый работает) ( p2 = 154 ≈ 0,27) и 13% времени – в

состоянии S3 (оба узла ремонтируются) ( p3 = 152 ≈ 0,13) .

3) В среднем первый узел исправно работает долю времени, равную p0 + p2 , а второй узел – p0 + p1 . В тоже время первый узел находится в

ремонте в среднем долю времени, равную p2 + p3 , а второй узел – p2 + p3 .

Поэтому средний чистый доход в единицу времени от эксплуатации системы, т. е. разность между доходами и затратами, равен

W = (p0 + p2 )R1 + (p0 + p1 ) R2 −(p1 + p3 )r1 −(p2 + p3 )r2 =

=(0,40 + 0,27) 10 + (0,40 + 0,20) 6 −(0,20 + 0,13) 4 −(0,27 + 0,13) 2 =

=6,7 +3,6 −1,32 −0,8 =10,3 − 2,12 = 8,18 ден. ед.

4)Уменьшение вдвое среднего времени ремонта каждого из узлов означает увеличение вдвое интенсивности потока “окончания ремонтов” каждого

узла, т. е. теперь λ′10=4; λ′20=6; λ′31=6; λ′32=4, так как λ10=2; λ20=3; λ31=3;

λ32=2.

линейных

алгебраических

уравнений,

описывающая

Система

стационарный режим системы S, примет вид

(λ01 + λ02 )p0 = λ'10 p1 + λ'20 p2

(λ'10 +λ13 )p1 = λ01 p0 + λ'31 p3 .

(λ'20 +λ23 )p2 = λ02 p0 + λ'32 p3

(λ'

+λ' )p

= λ

p +

λ

23

p

2

31

32

3

13

1

Тогда, дополняя эту систему уравнением p0 + p1 + p2 + p3

=1, имеем

(1 + 2)p0 =

4 p1 + 6 p2

3 p

= 4 p

+

6 p

p

+ p

+

p

2

+

p

=1

+ 2)p1 =

2

0

1

3

p0 + 6 p3

0

1

(4

= p

+

6 p

3 p

− 4 p −6 p

= 0

+1)p

=

2 p

+ 4 p

6 p

.

(6

2

1

0

3

0

1

2

0

3

= 2 p0 + 4 p3

−p

+ 6 p

−6 p

= 0

+ 4)p3 =

7 p2

(6

3 p1 +1p2

p

+ p + p

+ p

=1

0

1

3

p

+ p

+ p

2

+ p =1

0

1

2

3

− 2 p0 +

7 p2 − 4 p3 = 0

0

1

3

Решая систему

74

			Глава 10. Элементы теории массового обслуживания
	1	1	1	1			1				1 1		1	1			1									1 1			1	1					1
	3 − 4		− 6 0				0				0 −7 −9 −3								−3							0 −7			−9		−3
																																			−3
	−1 6		0 − 6				0				0 7		1 −5				1									0 0			56 56						14
	− 2 0		7 − 4				0				0 2		9 − 2				2									0 0 − 45 20									−8
		1 1		1	1				1			1 1 1 1							1								1 1 1 1				1
		0 7		9	3				3			0 7 9 3							3								0 7 9 3				3
																																	,
		0 0		4	4				1			0 0 4 4							1								0 0 4 4				1
		0 0		− 45	20				−8			0	0 0	260					13								0 0		0 20		1
получим
																			p			=		3
																					0
																							5
																							3
							p0 + p1 + p2 + p3 =1
									7 p1 +9 p2 +3 p3 = 3										p1			=
																							20 .
											4 p2 + 4 p3 =1								p		2	=		1
																							5
													20 p3	=1
																							1
																			p			=
																							20
																				3

Таким образом

p0 = 53 = 0,60; p1 = 203 = 0,15; p2 = 15 = 0,20; p3 = 201 = 0,05.

Учитывая, что затраты на ремонт первого и второго узла составляют r′1=8 ден. ед.; r′2=4 ден. ед., (так как r1=4; r2=2), вычислим средний чистый доход в единицу времени

W '= (p0 + p2 )R1 + (p0 + p1 ) R2 −(p1 + p3 )r'1 −(p2 + p3 )r'2 =

=(0,60 + 0,20) 10 + (0,60 + 0,15) 6 −(0,15 + 0,05) 8 − (0,20 + 0,05) 4 =

=8 + 4,5 −1,6 −1 =12,5 − 2,6 = 9,9 ден. ед.

	Так как W=8,18<W′=9,9 (примерно на	9,9 −8,18	100 =	1,72		100 ≈ 21% ), то
		8,18			8,18

ускорение ремонтов узлов экономически целесообразно.

■

75

Раздел II. Решения типовых задач

Многоканальная СМО с отказами

Решение задания № 5.2.1-5.2.30

Состояния системы массового обслуживания (СМО), пронумеруем по числу заявок, находящихся в системе (в данном случае оно совпадает с числом занятых каналов):

ε0 – в СМО нет ни одной заявки, ε1 – в СМО находится одна заявки (один канал занят, остальные

свободны), ε2 – в СМО находится две заявки (два канала заняты, остальные

свободны),

...

εn – в СМО находится n заявок (все n каналов заняты). Граф состояний СМО представлен на рис. 8.

	λ		λ		λ	λ		λ		λ
ε0		ε1		ε2		…	εn-2		εn-1		εn
	μ		2μ		3μ	(n-1)μ (n-1)μ nμ

Рис. 8

Приведем основные расчетные соотношения для n-канальной СМО с отказами (задача Эрланга):

- формулы для расчета финальных вероятностей:

n

ρ

k

−1

1

λ

1

p0

=

∑

=

, где ρ =

,

μ =

;

(1)

n

k

μ

k =0

k!

∑

ρ

tоб

k!

k =0

pk

=

ρk p0

, k =1,

2,

..., n ;

(2)

k!

- Pотк – вероятность того, что пришедшая заявка получит отказ (не будет обслуженной):

Pотк=pn;

(3)

- Q – относительная пропускная способность (средняя доля пришедших заявок, обслуживаемых системой):

Q=1-pn;

(4)

76

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

- A – абсолютная пропускная способность (среднее число заявок,

обслуживаемых в единицу времени):
A=λQ;				(5)
- Nз – среднее число занятых каналов:
n		A
N з = ∑kpk =			;	(6)
k =0		μ
- Nп – среднее число простаивающих каналов:
n
Nп = ∑(n − k)pk	= n − N з ;			(7)

k=0

-kз – коэффициент загрузки каналов:

kз =	N з	;	(8)
	n

- kп – коэффициент простоя каналов:

kп =	Nп	.	(9)
	n

Оценим эффективность функционирования АТС при следующих числовых значениях переменных величин: n=6 (каналов), λ=4 (заявки в мин.), tоб=1,5 (мин.) и q=80 %.

Определим		параметр		ρ =	λ	= λ tоб = 4 1,5 = 6		( μ =		1	=	1	=	2	).
					μ					tоб				3
											1,5
Вычисления в соответствии с формулами (1) - (9) сведем в таблицу:
								pk
k		ρk		k!		ρk/k!					kpk
1		2		3		4		5			6
0		1		1		1,0	0,0041				0,0000
1		6		1		6,0	0,0246				0,0246
2		36		2		18,0	0,0738				0,1476
3		216		6		36,0	0,1476				0,4428
4		1296		24		54,0	0,2214				0,8856
5		7776		120		64,8	0,2656				1,3280
6		46656		720		64,8	0,2656				1,5936
∑						244,6	1,0027				4,4222

77

Раздел II. Решения типовых задач

Вычисления начинаются с заполнения первых четырех столбцов. Сумма элементов четвертого столбца дает знаменатель выражения (1) для определения p0. Тогда

n

k

−1

1

1

p0

=

∑

ρ

=

=

= 0,0041 .

n

ρ

k

244,6

k =0 k!

∑

k!

k =0

Далее находим

элементы пятого столбца, умножая на величину p0

соответствующие элементы четвертого столбца. Вычислив значения pk, рассчитывают элементы последнего столбца. Элементы пятого столбца суммируют для контроля вычислений. Их сумма должна быть равна единице (с допустимыми в пределах точности расчетов отклонениями). Сумма элементов шестого столбца есть в соответствии с выражением (6) среднее число занятых каналов:

Nз=4,42.

Используя выражения (7) - (9), находим:

- среднее число простаивающих каналов:

Nп=n-Nз=6-4,42=1,58; - коэффициент загрузки каналов:

kз = Nnз = 4,642 = 0,737 ;

- коэффициент простоя каналов:

kп=1-kз=1-0,737=0,263.

Последнее число в пятом столбце дает вероятность отказа:

Pотк=p6=0,2656.

Тогда относительная пропускная способность:

Q=1-p6=1-0,2656=0,7344,

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

A=λQ=4 0,7344=2,9376.

Анализ полученных результатов. Значение p0=0,0041 означает, что в среднем 0,4 % всего времени работы все 6 каналов одновременно будут

78

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

свободны. В среднем будут постоянно заняты Nз=4,42 каналов связи. Как показывает коэффициент загрузки kз=0,737, в среднем каждый канал занят 73,7 % рабочего времени. В тоже время величина Pотк=0,2656 говорит о том, что из каждых 100 вызовов 26,56 % получат отказ. Относительная пропускная способность Q=0,7344 говорит о том, что 6 каналов не гарантируют удовлетворение q=80 % поступающих заявок.

Рассчитаем характеристики СМО для n=7:

k	ρk	k!	ρk/k!	pk	kpk
1	2	3	4	5	6
0	1	1	1,0	0,0033	0,0000
1	6	1	6,0	0,0200	0,0200
2	36	2	18,0	0,0600	0,1200
3	216	6	36,0	0,1200	0,3600
4	1296	24	54,0	0,1799	0,7196
5	7776	120	64,8	0,2159	1,0795
6	46656	720	64,8	0,2159	1,2954
7	279936	5040	55,5	0,1849	1,2943
∑			300,1	0,9999	4,8888

- вероятность того, что в системе нет ни одной заявки

p0 = 3001 ,1 = 0,0033 ;

-среднее число занятых каналов Nз=4,89;

-среднее число простаивающих каналов Nп=n-Nз=7-4,89=2,11;

-коэффициент загрузки каналов

kз = Nnз = 4,789 = 0,699 ;

-коэффициент простоя каналов kп=1-kз=1-0,699=0,301, т.е. доля простаивающих каналов составит 30,1 %;

-вероятность отказа Pотк=p7=0,1849;

-относительная пропускная способность Q=1-p7=1-0,1849=0,8151, т.е. в среднем 81,51 % заявок будут удовлетворены;

-абсолютная пропускная способность A=λQ=4 0,8151=3,2604. Выводы. Для удовлетворения q=80 % заявок необходимо 7 каналов.

Вэтом случае доля простаивающих каналов составит 30,1 %.

■

79

Раздел II. Решения типовых задач

Одноканальная СМО с неограниченной очередью

	Решение задания № 5.3.1-5.3.30	1
	Пусть λ=2 (состава в час), tоб=20 (мин.)=			(часа), n=2, tоб=2 (мин.).
		3

Состояния системы, пронумеруем по числу заявок, находящихся в системе массового обслуживания (СМО):

ε0 – канал свободен, ε1 – канал занят (обслуживает одну заявку), очереди нет,

ε2 – канал занят, одна заявка стоит в очереди,

...

εk – канал занят, k-1 заявок стоят в очереди,

...

Финальные вероятности состояний системы, которые существуют при условии ρ<1, определим из соотношений:

−1				1			−1
p0 = (1 + ρ + ρ2 +... + ρk +...)	=						=1 − ρ ,	(1)
		1		−
					ρ

где ρ =

λ

, μ =

1

(заметим,

что ряд в формуле (1)

представляет собой

tоб

μ

геометрическую прогрессию);

pk

= ρk p0 = ρk (1 − ρ), k =1,

2, ...

(2)

Тогда, т. к. μ =

1

= 3, ρ =

λ

=

2

<1, то p0 =1 − ρ =

1

.

tоб

3

3

μ

Найдем среднее число заявок в СМО Lсист.

Пусть случайная величина X (число заявок в системе) принимает возможные значения 0, 1, 2, ..., k, ... с вероятностями p0, p1, p2, ..., pk, ... . Ее математическое ожидание, используя соотношения (2), равно

∞

Lсист = 0 p0 +1 p1 + 2 p2 +... + k pk +... = ∑kpk

k =1

∞	∞
= ∑kρk (1 − ρ)= ρ(1 − ρ) ∑kρk −1.
k =1	k =1

Заметим, что kρk-1 – производная по ρ от выражения ρk. Поэтому

	∞	∞	d
	Lсист = ρ(1 − ρ) ∑kρk −1	= ρ(1 − ρ) ∑		ρk .
			dρ
	k =1	k =1

Меняя местами операции дифференцирования и суммирования, получим

80