Елтаренко Исследование операцыи 2007

n(t)

Ls

0	t1	t2	t
	Рис. 1.3. График изменения числа заявок в СМО во времени

Сравнивая выражения для Ls и Ws , можем записать связь между

ними:
				Ls	эфф Ws .				(1.1)
Аналогично для средней длины очереди получим:
				Lq	эфф Wq .				(1.2)
Ws	и Wq отличаются временем обслуживания.
				Ws	Wq	,			(1.3)
где	(t) t	dt – среднее время обслуживания.
	0
Таким образом, вычислив Ls					и Pотк , можно, используя (1.1), (1.2),
(1.3), вычислить все основные характеристики:
	L , P		ýôô	W	L	ýôô	W	W	.
	s	îòê		s	s		q	s
Отметим также следующие соотношения:
			Ls	Lq	эфф Ws		Wq ;
				Ws	Wq	;
				(Ls		Lq)	.
				эфф
					10

Чтобы найти Ls , необходимо определить Pn (вероятности того, что в СМО находится ровно n заявок), так как

Ls	nPn .
	n 0

Таким образом, задача определения характеристик СМО сводится к определению вероятностей Pn ( n 0, 1, 2, ).

1.2. Потоки заявок

В СМО входной поток заявок случайный. Если же заявки посту-

пают через определенный интервал времени T		const, то такой по-
ток называется регулярным.
Остановимся на общем случае, когда для его описания требуется
задать f t – плотность функции распределения интервала между
поступлением заявок, и	– интенсивность,	определяемая числом

заявок в единицу времени.

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

1.2.1. Простейший (пуассоновский) поток

Свойства потока:

– стационарность: число заявок за интервал t зависит только от величины t и не зависит от расположения интервала t на временной

оси. Для стационарного потока		const;
– безпоследействие: число заявок в интервал t1			не зависит от чис-
ла заявок за другой интервал t2 , если они не пересекаются;
– ординарность: вероятность поступления в			интервал времени
t t	0 больше одной заявки стремится к нулю.
Исходя из этих свойств, получим распределение Пуассона.
Выберем конечный интервал t , на нем t :
	t		t
		11

Из свойства ординарности:
P	t – вероятность того, что за			t	поступит 1 заявка;
1
P0 1	t – вероятность того, что за				t не поступит заявок.
Разделим интервал t на n равных участков:
	t
					t
		t	t n .
Вероятность того, что за интервал t				наступит ровно m заявок,
равна:
	P	Cm	P n m	P	m .
	m	n	0	1

Учитывая свойство безпоследействия:

Pm

Pm

P	t	n	, P 1	t	n
1			0

n n 1 n m 1 t

m

1

t n m

m!

n

n

nm 2 n t m 1

t

n

nm nm 1

n

nm

m!

1

t m

n

lim Pm

lim

t

m

1

t

n

;

(1.4)

n

m!

n

n

n

t

n

lim 1

t

n

lim 1

t

n

t

e

t

.

(1.5)

n

n

Подставляя (1.5) в (1.4), получим:

P

t

m

e t – вероятность того, что за время t

поступит ровно

m

m!

m заявок.

12

Обозначим t a , тогда P	am e a ;	const (используется
m	m!

свойство стационарности). Полученное Pm определяет распределение Пуассона, отсюда и название потока заявок.

Вероятности Pm рассчитываются на основе Pm 1 :

P	e t ;
0
P		t e t				t P ;
1						0
P		t 2			e t		t	P ;
2	2					2			1
P		t	P .
3	3			2

Математическое ожидание числа заявок за интервал t:

M m	mP			m t m e t	t e t	t m 1
		m	m 0 m!		m 0 m 1 !
	m 0
t	e t		t m	.
	m 0	m!

et

M(m) t .

Дисперсия числа заявок за интервал t:

2 t

m

t

t

2

2 t m

D m

m t

e

e

m 2m t

t

m!

m!

m 0

m 0

e t

m2

t m

2 t m

t m

t 2 e t

m!

m!

m 0

m 0

e t

m

t

t m 1

t 2.

m 1 !

m 0

Произведем замену m

m 1:

13

D m

e t

m 1 t

t m

t 2

m!

m 0

t m

t

t

m

e t

m t

e t

t 2

;

m!

m!

m 0

m 0

t

2

t

D(m) t .

Отметим полученную отличительную особенность пуассоновского распределения – математическое ожидание равно дисперсии.

Определим плотность функции распределения интервала времени между моментами поступлениями заявок в пуассоновском потоке:

f t dt P dt e t	dt .
0
Откуда следует, что искомая функция f	t	e t (экспоненци-

альное распределение). Математическое ожидание и дисперсия этого распределения равны:

M t	t e t dt				te	t d t			te t		e t dt	1	e t		1	;
											0			0
	0			0		1				0						С
		1	2		t
D t	t			e dt				.
							2
	0

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

Отметим, что вероятность того, что за малый промежуток времени t поступит заявка, равна

f t dt et dt .

Операции с пуассоновскими потоками:

а) суперпозиция (объединение) двух или нескольких пуассоновских потоков образует пуассоновский поток;

14

б) операция случайного просеивания (разделения) пуассоновского потока дает на выходе пуассоновские потоки. При разделении потока должно быть задано дискретное распределение вероятностей, с которыми заявки из основного (входного) потока попадают в каждый из выходных потоков. Суть операции: каждая заявка из входного потока переходит в один из выходных в соответствии с заданным распределением.

При случайном просеивании заявок сохраняются все его свойства (ординарности, безпоследействия, стационарности).

1.2.2. Потоки Эрланга

Пусть имеем пуассоновский поток: f t et :

t

Проведем регулярное (не случайное) просеивание потока. Если будем исключать каждую вторую заявку, то получим поток Эрланга второго порядка. Если оставлять каждую третью, то получим поток Эрланга третьего порядка и т.д.

Плотность распределения интервала времени между заявками потока Эрланга второго порядка равна:

	f		t dt	t	e t dt	2t t dt .
		2		1!

Плотность функции распределения потока Эрланга 2-го порядка

(рис. 1.4):

f	2	t	2t	t .

Для потока k порядка получим:

f

t dt

t k

1

e

t

dt

t

k 1

e t dt;

k

k

1 !

k

1 !

f

t

t

k

1

e

t .

k

k

1 !

15

fk t

f2 t

f3 t

t

Рис.1.4. Плотность функции распределения Эрланга

Математическое ожидание интервала времени между заявками потока Эрланга порядка k равно:

M t k ,

где – интенсивность пуассоновского потока, из которого сгенерирован поток Эрланга (порождающего пуассоновского потока).

Дисперсия интервала времени между заявками потока Эрланга порядка k равна:

D t k 2 .

Интенсивность потока Эрланга э равна:

э k эk .

Выразим функцию распределения, математическое ожидание и дисперсию через э .

fk t	эk	эkt	k 1	e	э	kt	;
	k	1!

	M t		1		;
					э
D t		k				1		.
		k2 2
						k	2
			э				э
	16

Аппроксимация произвольного потока заявок

потоком Эрланга

Пусть задана произвольная плотность функции распределения t – интервал времени между заявками для произвольного закона с

M t и D t .

Для потока Эрланга:

M t

1

M 2

t

k

ý

k k

. (1.6)

D t

D t

ý

Пример.

Пусть задан поток неизвестного распределения с интенсивностью

	15 заявок/ч, M t				4 мин.; D t	1 мин.2
	Данный			поток	можно аппроксимировать			потоком Эрланга
	M 2 t		42	16 порядка с интенсивностью				15, который гене-
	D t		1				э
рируется				из пуассоновского		потока с		интенсивностью
15			16	240 заявок/ч.

1.2.3. Верификация потоков заявок

При исследовании СМО необходимо в первую очередь проанализировать входной поток заявок с целью определения его характеристик. Для этого производится регистрация в той или иной форме моментов поступления заявок за длительный период времени. По этим данным можно построить гистограмму распределения числа заявок за заданный отрезок времени, например, 1 ч, или распределение интервала времени между поступлением заявок в СМО.

Рассмотрим вопросы анализа потока заявок на примере. Пусть в течение N 121ч вели наблюдение за поступлением заявок, в результате получили распределение числа заявок в час, приведенное в табл. 1.1 и на рис. 1.5 (n – количество заявок, поступивших за 1 час, mn – число часов из 121, в которые зарегистрировано поступление ровно n заявок).

17

																				Таблица 1.1
								Распределение числа заявок в час
						n	0			1		2		3			4	5		6
						mn	10			31		40		20			10	4		6
				mn
				40
				30
				20
				10
						0	1			2	3				4		5	6		n
						Рис. 1.5. Гистограмма распределения числа заявок
	Вычислим среднее число заявок в час:
				6		mn	10 0			31 1 40 2					20 3			10 4		5 6 6
	n			n 0 n																		2,207.
						N									121
	Среднеквадратичное отклонение:
								S2			6			2	mn
												n	n				2,147.
								n							N
										n	0

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

Проверим гипотезу по критерию согласия, сначала – по критерию Пирсона (табл. 1.2):

n 2,207 – интенсивность потока.

Отметим, что в каждом интервале mn должно быть не менее 6. Если меньше, то необходимо объединить интервалы.

18

Таблица 1.2

Расчеты для проверки гипотезы по критерию Пирсона

n	0	1	2	3	4	5		6
mn	10	31	40	20	10	4		6
Pn	0,110	0,242	0,267	0,195	0,110		0,076
NPn	13,3	29,2	36,3	23,6	13,3		9,1

объединили

интервалы

Pn – вероятности поступления за 1 ч ровно n заявок, соответствующие распределению Пуассона:

P	e 2,2		0,110;		P		t e 2,2		2,2 0,110	0,242;
0					1
P	2,2 P		0,267; P				2,2	P	0,195; P	2,2 P 0,110;
2	2	1			3		3	2	4	4	3
P	1 P		P	P		P	P .
5		0	1	2	3		4
						Критерий Пирсона
2	5	mn		NPn	2
						,	6	1	1 4 (число степеней свобо-
	т 0		NPn

ды).

2	10	13,3 2		10	9,1	2	3,11.
расч.		13,3			9,1

да).

2

табл.

0,2 – уровень значимости (вероятность ошибки второго ро-

5,898 (распределение Пирсона приведено в приложении 1).

Сравниваем	2	и	2 . Если расчетное больше табличного, то
	расч.		табл.

распределение не пуассоновское, но мы ошибаемся с вероятностью

0,2. Если расчетное меньше табличного, то не можем отвергнуть гипотезу, что это пуассоновское распределение.

19