лекции(II курс)

		(2)	(2)
(1)	(1)	(1)	(1)
(1)	(1)	(1)		(3)

На четвертом шаге алгоритма получили дерево G5, которое соединяет все вершины исходного графа. Таким образом, дерево G5 , будет минимальным остовным деревом графа G.

Контрольные вопросы.

1)Задача Эйлера. Основные определения.

2)Матричные способы задания графов.

3)Достижимость и связность. Эйлеров и гамильтонов графы.

4)Деревья и циклы.

51

ЭЛЕМЕНТЫ ТЕОРИИ СЛУЧАЙНЫХ ПРОЦЕССОВ И ТЕОРИИ МАССОВОГО ОБСЛУЖИВАНИЯ.

Теория случайных процессов (случайных функций) это раздел математиче- ской науки, изучающий закономерности случайных явлений в динамике их развития.

1. Определение случайного процесса и его характеристики.

Понятие случайного процесса является обобщением понятия случайной величины, рассмотренной ранее.

Определение. Случайным процессом X(t) называется процесс, значение которого при любом значении аргумента t является случайной величиной.

Другими словами, случайный процесс представляет собой функцию, которая в результате испытания может принять тот или иной конкретный вид, неизвестный заранее. При фиксированном t = t0X(t0) представляет собой обычную случайную величину, т.е. сече-

ние случайного процесса в момент t0.

Случайный процесс можно записать в виде функции двух переменных X(t, ω), ãäå ω Ω, t T, X(t, ω) Ξ è ω−элементарное событие, Ω−пространство элементарных событий, T − множество значений аргумента t, Ξ−множество возможных значений слу- чайного процесса X(t, ω).

Определение. Реализацией случайного процесса X(t, ω) называется неслучайная функция x(t), в которую превращается случайный процесс X(t) в результате испытания (при фиксированном ω), т.е. конкретный вид, принимаемый случайным процессом X(t),

его траектория.

Таким образом, случайный процесс X(t, ω) совмещает в себе черты случайной вели- чины и функций. Если зафиксировать значение аргумента t, случайный процесс превращается в обычную случайную величину, если зафиксировать ω, то в результате каждо-

го испытания он превращается в обычную неслучайную функцию. В дальнейшем будем опускать аргумент ω, он будем подразумеваться по умолчанию.

X

T

0

T

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

Тогда случайный процесс X(t) при данном t определяется плотностью вероятности φ(x, t).

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

Определение. Математическим ожиданием случайного процесса X(t) называется неслучайная функция ax(t), которая при любом значении переменной t равна математическому ожиданию соответствующего сечения случайного процесса X(t), ò.å. ax(t) = M[X(t)].

Определение. Дисперсией случайного процесса X(t) называется неслучайная функция Dx(t), при любом значении переменной t равная дисперсии соответствующего сече- ния случайного процесса X(t), ò.å. Dx(t) = D[X(t)].

52

Определение. Средним квадратическим отклонением σx(t) случайного процесса

называется арифмитическое значение корня квадратного из его дисперсии, т.е. σ

√ x

Dx(t).

X(t) (t) =

Математическое ожидание случайного процесса характеризует среднюю траекторию всех возможных его реализаций, а его дисперсия или среднее квадратическое отклонение

разброс реализаций относительно средней траектории.

Но введенных ваше характеристик случайного процесса оказывается недостаточно, т.к.

они определяются только одномерным законом распределения.

Например, на рисунке изображены два случайных процесса X1(t) è X2(t) с примерно одинаковыми математическими ожиданиями и дисперсиями

X X

		T			T
0	T1	T2	0	T1	T2

Если для случайного процесса X1(t) характерно медленное изменение значений реализации с изменением t, òî äëÿ X2(t) это изменение происходит значительно быстрее. Другими словами, для случайного процесса X1(t) характерна тесная вероятностная зависимость между двумя его сечениями X1(t) è X2(t), в то время как для случайного процесса X2(t) эта зависимость практически отсутствует. Указанная зависимость между сечениями характеризуется корреляционной функцией.

Определение. Корреляционной функцией случайного процесса X(t) называется неслу- чайная функция

Kx(t1, t2) = M[(X1(t) − ax(t1))(X(t2) − ax(t2))]

(1)

двух переменных t1 è t2, которая при каждой паре переменных t1 è t2 равна ковариации соответствующих сечений X(t1) è X(t2) случайного процесса.

Корреляционная функция Kx(t1, t2) характеризует не только степень тесноты линейной зависимости между двумя сечениями, но и разброс этих сечений относительно математи- ческого ожидания ax(t). Поэтому рассматривается также нормированная корреляционная функция случайного процесса.

Определение. Нормированной функцией случайного процесса X(t) называется функция

ρx(t1, t2) =	Kx(t1, t2)	.	(2)
	σx(t1)σx(t2)

Пример.

Случайный процесс определяется формулой X(t) = X cos(ωt), ãäå X− случайная величина. Найти основные характеристики этого процесса, если M(X) = a, D(X) = σ2.

Решение. На основании свойств математического ожидания и дисперсии, имеем:

ax(t) = M(X cos(ωt)) = cos(ωt)M(X) = a cos(ωt),

Dx(t) = D(X cos(ωt)) = cos2(ωt)D(X) = σ2 cos2(ωt).

Корреляционную функцию найдем по формуле (1)

Kx(t1, t2) = M[(X cos(ωt1) − a cos(ωt1))(X cos(ωt2) − a cos(ωt2)] =

53

= cos(ωt1) cos(ωt2) · M[(X − a)(X − a)] = cos(ωt1) cos(ωt2) · M[(X − a)2] =

вспоминая известную формулу для дисперсии D(X) = M(X − a)2, ãäå a = M(X), окон- чательно получим:

= cos(ωt1) cos(ωt2) · D(X) = σ2 cos(ωt1) cos(ωt2).

Нормированную корреляционную функцию найдем по формуле (2)

σ2 cos(ωt1) cos(ωt2)

ρx(t1, t2) = (σ cos(ωt1))(σ cos(ωt2) ≡ 1.

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

2. Основные понятия теории массового обслуживания.

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

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

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

работает с недогрузкой или простаивает.

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

В качестве показателей эффективности СМО используется: среднее число заявок (имеется в виду математическое ожидание соответствующих сл. вел.); среднее время ожидания обслуживания; вероятность отказа в обслуживании без ожидания; вероятность того, что число заявок в очереди превысит определенное значение, и т.п.

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

54

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

3. Понятие марковского процесса. Цепи Маркова.

Андрей Андреевич Марков(1856 1922) русский математик, академик.

Процесс работы СМО представляет собой случайный процесс.

Определение. Процесс называется процессом с дискретными состояниями, если его возможные состояния S1, S2, . . . можно заранее перечислить, а переход системы из со-

стояния в состояние происходит мгновенно (скачком).

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

Процесс работы СМО представляет собой случайный процесс с дискретными состояниями и непрерывным временем.

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

Математический анализ работ СМО существенно упрощается, если процесс этой рабо-

ты марковский.

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

процесса в будущем зависят только от того, когда и как система пришла в состояние. Определение. Цепью Маркова называется последовательность испытаний, в каж-

дом из которых появляется только одно из k несовместных событий Ai из полной груп- пы. При этом условная вероятность pij(s) того, что в s -ом испытании наступит событие Aj при условии, что в (s - 1) - ом испытании наступило событие Ai, не зависит

от результатов предшествующих испытаний.

Независимые испытания являются частным случаем цепи Маркова. События называются состояниями системы, а испытания изменениями состояний системы.

Пример марковского процесса: система S−счетчик в такси. Состояние системы в момент t характеризуется числом километров, пройденных автомобилем до данного момен-

та. Пусть в момент t0 счетчик показывает S0. Вероятность того, что в момент t > t0 счетчик покажет то или иное число километров (точнее, соответствующее число рублей) S1, зависит от S0, но не зависит от того, в какие моменты времени изменялись показания счетчика до момента t0.

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

Определение. Цепью Маркова с дискретным временем называется цепь, изменение состояний которой происходит в определенные фиксированные моменты времени. Цепью Маркова с непрерывным временем называется цепь, изменение состояний которой

возможно в любые случайные моменты времени.

Определение. Однородной называется цепь Маркова, если условная вероятность pij перехода системы из состояния i в состояние j не зависит от номера испытания. Вероятность pij называется переходной вероятностью.

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

		p11	p12	. . . p1k
P1	=	p21	p22	. . .	p2k
			p. . .	.. .. ..	p. . .
		p. . .
		k1 k2			kk

55

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

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

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

Пример. По заданной матрице перехода построить граф состояний.

P1			0, 1	0, 2	0	0, 7
	=		0	0, 4	0, 6	0
				0, 1	0
		0, 4				0, 5
			0	0	0, 5	0, 5

Т.к. матрица четвертого порядка, то, соответственно, система имеет 4 возможных состояния.

(0,2)	s1	(0,7)
s2	(0,4)
		s4
(0,6)		(0,5)
(0,1)	S3	(0,5)

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

Пример. Построить граф состояний следующего случайного процесса: устройство S

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

Решение. Возможные состояния системы: S0 оба узла исправны; S1 первый узел ремонтируется, второй исправен; S2 второй узел ремонтируется, первый исправен; S3оба узла ремонтируются. Получим граф системы:

S0

S1	S2

S3

Стрелка, направленная, например из S0 â S1, означает переход системы в момент отказа первого узла, из S1 â S0 переход в момент окончания ремонта этого узла. Отсутствие стрелок из S0 â S3 è èç S1 â S2 объясняются независимостью неисправленности узлов.

56

Пусть Pij(n) вероятность того, что в результате n испытаний система перейдет из состояния i в состояние j, r некоторое промежуточное состояние между состояниями i и j. Вероятности перехода из одного состояния в другое pij(1) = pij.

Тогда вероятность Pij(n) может быть найдена по формуле, называемой равенством Маркова:

∑k

Pij(n) = Pir(m)Prj(n − m),

r=1

ãäå m число шагов (испытаний), за которое система перешла из соcтояния i в соcтояние r. В принципе, равенство Маркова есть ни что иное как несколько видоизменная формула полной вероятности. Зная переходные вероятности (т.е. зная матрицу перехода P1), можно найти вероятности перехода из состояния в состояние за два шага Pij(2), т.е. матрицу P2, зная ее - найти матрицу P3, è ò.ä.

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

Тогда в общем виде можно записать:

Pn = P1n

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

Пример. Задана матрица переходов P1. Найти матрицу P3.

					0, 1		0, 9		)
				P1 = ( 0, 3			0, 7
	0, 1		0, 9		0, 1		0, 9	)	= (	0, 28	0, 72
P2 = ( 0, 3			0, 7	) · ( 0, 3			0, 7			0, 24	0, 76 )
P3 = (	0, 1	0, 9		· (	0, 28	0, 72		)	= (	0, 244	0, 756	)
	0, 3	0, 7 )			0, 24	0, 76				0, 252	0, 748

Определение. Матрицы, суммы элементов всех строк которых равны единице, называются стохастическими. Если при некотором п все элементы матрицы P n не равны

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

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

цепи Маркова также называются регулярными.

Теорема. (теорема о предельных вероятностях) Пусть дана регулярная цепь Маркова с n состояниями и P ее матрица вероятностей перехода. Тогда существует предел

lim P n = P (∞) и матрица P (∞) имеет вид:

n→∞

	u1	u2	. . . un
P (∞) =	u1	u2	. . .	un
	1	2		n
		.u. .	.. .. ..
	.u. .			.u. .

Т.е. матрица состоит из одинаковых строк.

Теперь о величинах ui. Числа u1, u2, . . . , un называются предельными вероятностя-

ìè. Эти вероятности не зависят от исходного состояния системы и являются компонентами собственного вектора матрицы P T (транспонированной к матрице P ). Этот вектор

57

полностью определяется из условий:

P	T	·	−→	=	−→	∑	i = 1
			u		u ,	u		.

Пример. Найдем предельные вероятности для рассмотренного выше примера.

0, 1 0, 9	),	P T = (	0, 1 0, 3		)
P = ( 0, 3 0, 7			0, 9 0, 7
0, 1 0, 9		u1	u1	)
P1 = ( 0, 3 0, 7 )		· ( u2 )	= ( u2
u1 = 0, 1 u1 + 0, 3 u2;
{ u2 = 0, 9 ·· u1 + 0, 7 ··			u2;
0, 9 · u1 = 0, 3 · u2; u2 = 3 · u1.
С учетом того, что u1 + u2 = 1, получаем
u1 + 3u2 = 1;	u1 = 0, 25;		u2 = 0, 75.
Окончательно,			).
	0, 25 0, 75
P (∞) = ( 0, 25 0, 75

4. Потоки событий.

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

Характер событий, образующих поток может быть различным, а если события отлича-

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

Однородный поток можно изобразить последовательностью точек на оси, соответствующей времени:

T1 T2 Tn

Поток характеризуется интенсивностью λ частотой появления событий или средним

числом событий, поступающих в СМО в единицу времени.

Определение. Поток называется регулярным, если события следуют одно за другим через определенные равные промежутки времени.

Например, поток изделий на конвейере сборочного цеха (с постоянной скоростью дви-

жения) является регулярным.

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

В частности, интенсивность стационарного потока есть величина постоянная: λ(t) = λ.

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

58

Определение. Поток событий называется потоком без последствий, если для любых двух непересекающихся участков времени τ1 è τ2 число событий, попадающих на

один из них, не зависит от числа событий, попадающих на другие.

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

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

Определение. Поток событий называется ординарным, если вероятность попадания на малый (элементарный) участок времени t двух ли более событий пренебрежи-

мо мала по сравнению с вероятностью попадания одного события.

Другими словами, поток событий ординарен, если события появляются в нем поодиночке, а не группами. Например, поток поездов, подходящих к станции, ординарен, а

поток вагонов не ординарен.

Определение. Поток событий называется простейшим (или стационарным пуассоновским), если он одновременно стационарен, ординарен и не имеет последствий.

Регулярный поток не является простейшим, т.к. обладает последствием: моменты появления событий в таком потоке жестко зафиксированы.

Название простейший объясняется тем, что СМО с простейшими потоками имеет наиболее простое математическое описание. Кроме того, в этом случае число событий, попадающих на любой фиксированный интервал времени, распределено по распределению Пуассона.

В соответствии с этим законом распределения математическое ожидание числа точек, попадающих на участок времени , имеет вид:

a = λτ,

ãäå λ плотность потока (среднее число событий в единицу времени). Вероятность того, что за время τ произойдет ровно m событий, равна

Pm(τ) = (λτm)!m e− .

Вероятность того, что в течение данного времени не произойдет ни одного события, равна:

P0(τ) = e− .

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

F (t) = P (T < t).

В соответствии с законом распределения Пуассона, получаем:

F (t) = 1 − e− ; f(t) = λe−t.

Математическое ожидание, дисперсия и среднее квадратическое отклонение этой вели-

	чины соответственно равны:	1		1		1
	a =		; D =		; σ =		.
		λ		λ2		λ

Пример. В бюро обслуживания в среднем поступает 12 заявок в час. Считая поток заказов простейшим, определить вероятность того, что: а) за 1 минуту не поступит ни одного заказа, б) за 10 минут поступит не более трех заказов.

59

Решение. Сначала найдем плотность (интенсивность) потока, выразив ее в количестве заявок в минуту. Очевидно, эта величина равна

λ = 1260 = 0, 2.

Далее находим вероятность того, что за время τ = 1 мин не поступит ни одной заявки

по формуле:

P0(τ) = e− = e−0;2 ≈ 0, 819.

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

P (m ≤ 3) = ∑3 (λτ)m e− = e−2 + 2e−2 + 2e−2 + 4/3e−2 = 19/3e−2 = 0, 8571. m!

m=0

Пример. В ресторан прибывает в среднем 20 посетителей в час. Считая поток посетителей простейшим, и зная, что ресторан открывается в 11.00, определите: а) вероятность того, что в 11.12 в ресторан придет 20 посетителей при условии, что в 11.07 их было 18 б) вероятность того, что между 11.28 и 11.30 в ресторане окажется новый посетитель, если

известно, что предшествующий посетитель прибыл в 11.25.

Решение. Для ответ на первый вопрос фактически надо найти вероятность того, что в промежуток от 11.07 до 11.12 ( τ = 5 мин.) придет ровно 2 посетителя. При этом мы знаем

интенсивность потока посетителей λ = 20/60 = 1/3 посетителей в минуту. Конечно,

данная величина носит условный характер, т.к. посетители не могут приходить по частям. Искомая вероятность равна:

		(	31 · 5)2		−31 ·5	≈ 0, 2623.
	P2(5) =		2!	e

Теперь перейдем ко второму вопросу. Нам не сказано, сколько именно новых посетителей

будет в промежутке от 11.28 до 11.30, главное чтобы был хоть один. Эта вероятность равна 1 −P0(2) = 1 −e−23 ≈ 0, 4866. Здесь P0(2)−вероятность того, что в этом промежутке

не будет ни одного посетителя.

Если поток событий нестационарен, то его плотность уже не является постоянной ве-

личиной, а зависит от времени.

Определение. Мгновенной плотностью потока событий называется предел отношения среднего числа событий, приходящегося на элементарный отрезок времени (t, t +

t), к длине этого участка, которая стремится к нулю.

λ(t) = lim a(t + t) − a(t)

t→0 t

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

Определение. Нестационарным пуассоновским потоком называется ординарный поток однородных событий без последствий с переменной плотностью λ(t).

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

60