Теория массового обслуживания (стр. 3 )

ГЛАВА 4. МАРКОВСКИЕ СЛУЧАЙНЫЕ ПРОЦЕССЫ С ДИСКРЕТНЫМИ СОСТОЯНИЯМИ И НЕПРЕРЫВНЫМ ВРЕМЕНЕМ

Рассмотрим случайный процесс , принимающий дискретные значения в случайные моменты времени . Такой случайный процесс называется дискретным случайным процессом. Примерами дискретного случайного процесса могут служить:

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

– процесс квантования непрерывного случайного процесса по уровням;

– процесс изменения состояний счетчика случайного числа частиц и т. д.

Реализация дискретного случайного процесса дана на рис. 4.1.

Рис. 4.1. Реализация дискретного случайного процесса

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

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

. (4.1)

Вместо вероятности перехода системы из состояния в на -м шаге марковской цепи будем рассматривать вероятность – вероятность перехода из состояния в в течение .

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

. (4.2)

Привяжем вероятность перехода к конкретному моменту времени перехода , тогда она будет иметь вид , а формула (4.2) будет теперь выглядеть так:

. (4.3)

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

, (4.4)

где – величина более высокого порядка малости чем .

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

Рис. 4.2. Возможные переходы системы из состояния

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

- поток самолетов, требующих посадки, ремонта, обслуживания;

- поток отказов подсистемы ВС;

- поток заявок на АТС;

2) внутренней причины, заключающейся в том, что время пребывания системы в данном состоянии (например, в состоянии ) – случайная величина, распределенная по показательному закону

. (4.5)

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

. (4.6)

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

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

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

. (4.7)

Вероятность того, что на интервале не появится ни одного внешнего воздействия (ни одной “точки” в пуассоновском потоке точек) равна

. (4.8)

Раскладывая в ряд экспоненту (4.8) и удерживая первые два члена, получим

, (4.9)

где – бесконечно малая величина порядка более чем .

Подставляя (4.9) в (4.7), получим

. (4.10)

Наконец, подставляя (4.10) в формулу (4.3) при , окончательно получим

. (4.11)

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

. (4.12)

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

(4.13)

(по аналогии с (4.9)).

Подставляем (4.13) в (4.12), а полученный результат в формулу (4.4) при , окончательно получим:

. (4.14)

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

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

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

(4.15)

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

. (4.16)

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

(4.17)

Пример 4.1. Техническая система (ТС) в процессе функционирования может находиться в трех возможных состояниях:

- функционирует в основном режиме в среднем часов;

- функционирует в резервном режиме вследствие возникновения неисправности до устранения неисправности, которое длится в среднем часов;

- вышла из строя (прекратила функционирование).

ТС подвергается негативному внешнему воздействию в виде пуассоновского потока воздействий с интенсивностью (), вследствие чего ТС с вероятностью переходит из состояния в состояние , а с вероятностью - из состояния в состояние .

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

Решение. Представим случайный процесс, протекающий в ТС , в виде марковского случайного процесса с дискретными состояниями и непрерывным временем изменения этих состояний. Размеченный граф состояний системы представлен на рис. 4.3.

Рис. 4.3. Размеченный граф состояний ТС

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

, .

Интенсивности переходов и связаны с воздействием на ТС внешнего пуассоновского потока негативных воздействий с интенсивностью , поэтому они определяются выражениями

, .

Матрица интенсивностей переходов ТС из одного состояния в другие возможные состояния имеет следующий вид:

().

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

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

Рис. 4.4. Размеченный граф состояний пуассоновской системы

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

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

Рассмотрим систему в два близких момента и (рис. 4.5). В момент система могла находиться в одном из своих возможных состояний с вероятностью . Рассмотрим переходы системы в состояние в момент и найдем вероятность этого состояния по формуле полной вероятности [1]

, (4.18)

где – вероятность перехода системы из состояния в момент в в момент .

Рис. 4.5

Выделим из суммы (4.18) -й член

. (4.19)

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

Второй шаг: определение вероятности .

Рассмотрим всевозможные переходы системы из состояния в момент в состояния в момент (рис. 4.6).

Рис. 4.6

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

. (4.20)

Отсюда искомая вероятность равна

. (4.21)

Выразим вероятность через интенсивность в соответствии с формулой (4.5)

. (4.22)

Подставляя (4.22) в (4.21), окончательно получим:

. (4.23)

Третий шаг: формирование производной вероятности состояния .

Подставим в формулу (4.19) для вероятности выражение (4.23) для и выразим, кроме того, вероятность перехода по формуле (4.5)

. (4.24)

Сформируем производную вероятности состояния в левой части выражения (4.24)

. (4.25)

Переходя к пределу при в левой и правой частях (4.25), окончательно получим

. (4.26)

Получили систему дифференциальных уравнений Колмогорова для вероятностей состояний пуассоновской системы, которые решаются при следующих начальных условиях:

при .

Например, .

В качестве дополнительного -го уравнения используется нормирующее условие для вероятностей состояний

. (4.27)

Применение формул (4.26), (4.27) для решения конкретной задачи определения вероятностей состояний пуассоновской системы покажем на примере.

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

Рис. 4.7

Напишем сначала уравнение для вероятности , пользуясь формулой (4.26)

. (4.28)

Проанализируем полученный результат с точки зрения взаимно - однозначного соответствия (4.16) формулы (4.28) и размеченного графа состояний пуассоновской системы (рис. 4.7).

Число членов в правой части (4.28) равно числу стрелок на графе (рис. 4.7), соединяющих состояние с остальными состояниями (четыре стрелки – четыре члена).

Каждый член в правой части (4.28) равен произведению вероятности состояния, из которого выходит стрелка на интенсивность перехода по этой стрелке.

Знак члена в правой части (4.28) определяется направлением стрелки:

- входящая в стрелка соответствует знаку плюс;

- выходящая из стрелка соответствует знаку минус.

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