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

	2
Чем меньше	расч. , тем с большей уверенностью мы можем гово-

рить, что это пуассоновское распределение.

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

Рассмотрим еще один критерий согласия.

Критерий Колмогорова

Для проверки гипотезы необходимо заполнить табл. 1.3.

Таблица 1.3

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

	n		0	1	2	3	4	5-6
F * n			0,083	0,342	0,675	0,844	0,925	1,0
F n			0,110	0,352	0,619	0,814	0,924	1,0
			0,027	0,010	0,056	0,030	0,001	0,0

F * n– функция распределения, полученная из экспериментальных данных;

F n – теоретическая функция распределения, соответствующая пуассоновскому распределению:

F * 0

m0

10

0,083, F* 1

F* 0

m1

и т.д.

N

121

N

F 0 P , F 1 P P

, F 2 P P P .

0

0

1

0

1

2

D max

F* n

F n

max

0,056 –

максимальное откло-

нение теоретической и экспериментальной функций распределения. Статистика для проверки гипотезы рассчитывается по формуле:

расч.	D N , в нашем примере			расч.	0,056 121 0,616.

20

В приложении 2 приведено распределение Колмогорова. P расч. –

вероятность того, что расхождение между теоретическим и экспериментальным произошло из-за случайных факторов.

Для рассматриваемого примера P . P 0,616 0,850, т.е. с

расч

вероятностью 0,850 экспериментальное распределение расходится с пуассоновским из-за случайных факторов.

Вопросы и задания

1.Какие свойства характерны для пуассоновских потоков?

2.Какие операции можно производить над пуассоновскими потоками, чтобы результирующие потоки тоже были пуассоновскими?

3.Докажите, что в результате суперпозиции двух и более пуассоновских потоков заявок результирующий поток будет тоже пуассоновский.

4.Какой поток описывают потоки Эрланга при стремлении их порядка к бесконечности?

5.Для ответа на какие вопросы следует использовать критерий Колмогорова и на какие – критерий Пирсона?

6.При исследовании потока заявок регистрировалось количество заявок, поступающих каждый час. В результате наблюдений в течение 100 ч получили следующие данные:

Число заявок в час	0	1	2	3	4	5	6
Кол-во наблюдений	8	14	36	17	10	8	7

Используя критерии Пирсона и Колмогорова проверить гипотезу о том, что поток заявок является Пуассоновским потоком.

1.3. Марковские процессы

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

21

Пусть в объекте моделирования определены состояния S0 , S1 , S2 , , Sn , например, в системе массового обслуживания:

S0 – в СМО нет заявок,

S1 – в СМО одна заявка,

S2 – в СМО две заявки и т.д.

C течением времени СМО переходит из одного состояния в другое.

Рассмотрим марковские процессы с дискретными состояниями (число состояний конечно или счетно). При этом выделим:

а) марковские процессы с дискретным временем перехода (моменты перехода заранее определены);

б) марковские процессы с непрерывным временем перехода (момент перехода не определен, случаен).

Отметим, что марковские процессы обладают свойством безпоследействия.

1.3.1. Марковские процессы с дискретными состояниями и дискретным временем перехода

Пусть система находится в состоянии Si , где i 1, 2, , n .

Для задания марковского процесса необходимо определить матрицу вероятностей перехода из одного состояния в другое.

Пример матрицы переходов:

		S0	S1
P	S0	0,3	0,7
ij
	S1	0,5	0,5

Для заданной матрицы граф переходов имеет вид:

22

Так как на каждом следующем шаге система переходит в другое

n

состояние, то Pij 1.

j 0

Пусть задан вектор вероятностей в первый момент времени:

	0	P0	, P0 .
P
		0	1

Какова вероятность нахождения системы в состоянии i после первого перехода?

n

P1

P0P (i

1, 2, , n) .

(1.6)

i

j ji

j

0

В векторном виде (1.6):

1

0

Pij

.

P

P

На шаге k получим уравнение:

k

k 1

0

Pij

k .

P

P

Pij

P

(1.7)

Если P const (не зависит от шага), то процесс называется од-

ij

нородным.

При устремлении k к бесконечности получим вектор предельных вероятностей:

lim		k
	P		P .
k

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

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

Пример неприводимой матрицы переходов:

23

	S0	S1	S2	S3
S0	0,3	0,7	0	0
S1	0,4	0	0,6	0,5	.
S2	0,3	0	0,5	0,7
S3	0	0	0,2	0,8

1.3.2. Марковские процессы с дискретными состояниями и непрерывным временем перехода

Пусть система может находиться в состояниях Si ( i 0,1, , n ). Время перехода – случайная величина.

ij – интенсивность перехода из состояния Si			в S j .
За время		t вероятность перехода Pij t	ij t .
Если	ij	const (не зависит от времени), то это однородный мар-

ковский процесс.

Рассмотрим случай с двумя состояниями:

		P t		1	01 t			01		t	.
		ij			10 t			1	10 t
Составим конечно–разностное уравнение для определения Pi												t .
Для первого состояния:
P t	t	P	t 1		01		t	P t		10	t	(1.8)
0		0						1
P t	t	P t	1		10	t		P t		01	t .	(1.9)
1		1						0
					24

Из (1.8) получим:
		P t					t			P t						P t				01		t P t		10	t
		0							0								0						1				,
								t															t
				dP0			t			P t							P t					.
															01						10
					dt				0								1
Из (1.9) получим
					dP t
							1			P t							P			t			.
															10						01
						dt			1								0
Следует иметь в виду, что в любой момент t P t																									P t
																							1		0
Примем за начальное состояние системы																							P 0	1, P 0
																							0		1
гда решением дифференциального уравнения (1.10) будет:
	P	t							10						01					e 01			10 t
0							10		01						10		01
	P t 1 P t														01			1 e					01 10 t .
1									0
									10								01
Графически (1.12) и (1.13) представлены на рис. 1.6.
		1
	01
10		01							P0 t

10

10 01

P t

1

t

0

(1.10)

(1.11)

1.

0, то-

(1.12)

(1.13)

Рис.1.6. Решение системы уравнений марковского процесса

25

При стремлении t к бесконечности получим предельные вероят-

ности: P	lim P t , P		lim P t .
0	0	1		1
Для определения		P	и P	приравняем производные из системы
		0	1
уравнений (1.10) и (1.11) к нулю:
					dP t				0
						0
						dt
					dP t				0.
						1
						dt
Получим:
				P		10		P	01
				1				0
				P		P		1 .
				1		0

Рассмотрим случай для четырех состояний (рис. 1.7). Для простоты изображения размеченного графа t будем опускать.

Рис.1.7. Размеченный граф

Система уравнений для данного графа приведена ниже.

P0 t t		P0 t 1	01 t	03 t P2 t 20 t
dP0	P0	t 01	03 P2 t
dt				20

26

dP

1

P

P t

P t

13

01

21

dt

1

0

2

dP2

P2

t

P3

t

dt

20

21

32

dP3

P t

P

P

.

32

13

03

dt

3

1

0

В общем случае, когда число состояний

Si i

1, , n , система

уравнений примет вид:

dP

n

n

i

Pi t

Pk

t

ki .

dt

ij

j

0

k

0

i

j

k

j

Эту систему уравнений по имени автора называют системой уравнений Колмогорова.

	Для определения предельных вероятностей				dPi	0 получим сис-
					dt
	тему линейных уравнений:
		n		n
	Pi t	ij		Pk t ki ( i 1, 2, , n ),
	j	0	k	0
	i	j	k	j

n

Pi 1 .

i0

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

Процессами гибели и размножения называются марковские процессы, имеющие размеченный граф, приведенный на рис.1.8.

Рис.1.8. Размеченный граф процессов гибели и размножения

27

ij − интенсивности размножения,									ji − интенсивности гибели.
Для	нахождения			вектора					предельных				вероятностей
P (i 1, 2, , n) составим систему уравнений:
i
	P	01		P	10	(по Колмогорову),							(1.14)
	0			1
	P		12	10				P	01	P	21	.	(1.15)
		1						0		2
Подставляя (1.14) в (1.15), получим:
		P	12	P	10			P	10	P	21
		1		1				1		2
		P	12	P	21		.
		1		2

Для всех последующих состояний уравнения будут иметь одинаковый вид:

Pi

i,i 1

Pi 1 i 1,i ( i 1, 2, , n ).

Чтобы определить

все предельные вероятности,

воспользуемся

n

условием:

Pi

1 . Для этого выразим Pi

через P0 :

i

0

P

12

P

01

12

P .

(1.16)

2

1

0

21

10

21

Введем обозначение

i,i

1

, тогда (1.14) и (1.16) запишутся в

i

i

1,i

виде: P

1

P ;

P

1

2

P .

1

0

2

0

Все оставшиеся вероятности выражаются через P0 :

i

P

P .

i

j 0

j 1

В результате получим выражение для P0 :

n

i

1

P0

1

j

.

i 1 j

1

Определив P0 , можем рассчитать все Pi .

28

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

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

				S0		S1		S2			S3
		S0			0	4		0		0
	ij	S1			6	0		3		0		.
		S2			0	5		0		2
		S3			0	0		3		0
Расчет предельных вероятностей:
		P		4 P		2 P ;
		1		6	0	3		0
	P	3 P			3 2 P				2 P ;
2		5	1		5	3	0	5			0
	P	2 P			2	2 P			4		P ;
					3			15
3		3	2			5	0				0

	P0	1	2	2	4		1;
			3	5	15

P	3 , P		2	3	2 , P		2	3	6	, P	4 3			4	.
0	7	1	3	7	7	2	5	7	35	3	15		7	35

Вопросы и задачи

1. Определить предельные вероятности состояний в марковской цепи, описываемой следующей матрицей вероятностей переходов. В начальный момент система находится в первом состоянии

	S1		S2	S3
S1	0,3		0,3	0,4
S2	0,0		1,0	0,0
S3	0,0		0,0	1,0
		29