Процессы рождения и гибели

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

Согласно рассматриваемой задаче, процесс S(t) является дискретным с положительными и отрицательными скачками и с бесконечным в общем случае числом состояний. Будем полагать, что переход из одного состояния в другое осуществляется через случайное время, распределенное по экспоненциальному закону. Основываясь на свойстве ординарности пуассоновского процесса, можно утверждать, что переход осуществляется только в соседние состояния. Далее, если в момент t система находится в каком-либо состоянии с номером j (S(t) = j,j = 1, 2, ...), то вероятность перехода на единицу вверх у—>У+1 в малом интервале времени (t, t+ At) равна А,. At+ о(Д/), а вероятность перехода на единицу вниз j —*? j -1 равна р ? А/+o(At). Отсутствие перехода соответственно имеет вероятности:

Процесс изменения числа клиентов за малый интервал времени показан на рис. 14.23.

Диаграмма изменения числа клиентов за малый интервал времени

Рис. 14.23. Диаграмма изменения числа клиентов за малый интервал времени

Вероятность перехода вверх или вниз больше чем на единицу есть бесконечно малая величина «(А/1) по сравнению с рассматриваемым интервалом времени. Числа А.,-, ц, называются коэффициентами рождения и гибели и представляют собой интенсивности поступления клиентов и их обслуживания соответственно. Индексы показывают зависимость процесса от числа клиентов (номера состояния)у. Например, если в очереди много клиентов, то вероятность прихода нового клиента может уменьшиться, а интенсивность обслуживания — увеличиться. Когда цу= 0, процесс называется чистым, или простым, процессом рождения. Когда Xj= 0, процесс называется чистым, или простым, процессом гибели.

Обозначим через Pj(t) вероятность нахождения в системе у клиентов в момент t. Тогда вероятность того, что число клиентов в системе останется неизменным за время At, можно рассчитать как

Граф изменения состояний процесса рождения и гибели при малом At = dt изображен на рис. 14.24, а, при большом — на рис. 14.24, б. Над дугами указаны соответственно вероятности и интенсивности переходов из состояния в состояние. В состоянии равновесия время нахождения системы в состоянии у пропорционально Pj. Когда процесс находится в состоянии у, он может в среднем А, - раз в единицу времени перейти в состояние у + 1 и |ду- раз в состояние у — 1.

Граф процесса рождения и гибели при малом (а) и большом (б)

Рис. 14.24. Граф процесса рождения и гибели при малом (а) и большом (б)

промежутке времени

Чтобы определить, в какой момент времени в системе не останется ни одного клиента, удобно принять состояние j = 0 поглощающим. Рассмотрение системы начинается с произвольного момента, когда в ней имеется какое-то количество клиентов, т.е. предполагается, что в начальный момент система находится в некотором состоянииу(), где 0 < у'0 < оо.

Следовательно, начальные условия имеют вид

В соответствии с правилами составления дифференциальных уравнений процесса по графу уравнения для абсолютных вероятностей имеют вид

В поглощающем состоянии X = Х0 0 =0, и уравнение (14.80) примет вид

В общем случае, когда состояние j = 0 не является поглощающим, дифференциальное уравнение для этого состояния будет иметь вид:

Уравнение (14.80) можно записать в матричном виде: где

матрица интенсивностей переходов для процесса рождения и гибели с К+1 состоянием; р(/) = [/?0(/) /?, (/) ••• pK(t)] —вектор абсолютных вероятностей К+1 состояний. Решение уравнений для абсолютных вероятностей (14.83) имеет вид

Рассмотрим частные случаи процесса рождения и гибели.

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

Рис. 14.25. Граф изменения состояний простого процесса рождения

Граф процесса показан на рис. 14.25. Порождающая матрица имеет вид:

Для j=0, согласно (14.82), имеем дифференциальное уравнение

Решение этого уравнения имеет вид

Для всех у >0 в соответствии с (14.80) получим

Уравнение (14.86) представим как

Интегрируя (14.87), получаем

Полученное общее решение (14.88) позволяет вычислить вероятности всех состояний:

Вычисляя рекуррентно вероятности состояний, получаем общую формулу для всех вероятностей состояний:

Как и следовало ожидать, число рождений в интервале (0, /) распределено по Пуассону с параметром Xt. Математическое ожидание числа клиентов для простого процесса рождения Е(п) = Xt, а дисперсия var(п) = ol = Xt.

Для иллюстрации методов решения в (14.85), (14.86) использовалось непосредственное интегрирование уравнений. Решение (14.21) аналогичных уравнений было получено с использованием преобразования Лапласа.

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

Рис. 14.26. Граф изменения состояний простого процесса гибели

Граф процесса изображен на рис. 14.26. Порождающая матрица имеет вид

Для j = К, согласно (14.80),

Решение (14.89) очевидно:

Для также, согласно (14.80), имеем

Представим уравнение (14.90) в виде Интегрируя (14.91), получаем

Используя (14.92), вычислим вероятности всех состояний:

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

Как видно, вероятность имеет биномиальное распределение (11.27) с параметром р = . Согласно (11.34), математическое

ожидание числа клиентов при простом процессе гибели

Дисперсия вычисляется в соответствии с (11.35) как

Простой усеченный процесс рождения-гибели. Рассмотрим процесс рождения и гибели с двумя состояниями 0 и 1. Граф изменения состояний простого процесса рождения и гибели изображен на рис. 14.27. Порождающая процесс матрица имеет вид

Граф простого усеченного процесса рождения и гибели

Рис. 14.27. Граф простого усеченного процесса рождения и гибели

При использовании (14.83) дифференциальные уравнения для абсолютных вероятностей примут вид

Как видно из (14.96) и (14.97),

Следовательно, pQ (t) + р] (t) = const = 1 или Подставив (14.98) в (14.96), получим

Уравнение можно записать в виде

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

Аналогичные решения были получены с использованием преобразования Лапласа (13.31) и (13.32).

Известны также решения для процесса рождения—гибели в общем случае, при любом числе состояний и различных интенсивностях переходов [5, 33]. Полученные формулы достаточно громоздки, поэтому здесь не приводятся.

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

Стационарное состояние процесса рождения—гибели. Стационарные вероятности состояний pj, j = 0,1,2,... можно интерпретировать как часть времени, которое процесс проводит в состоянии j при длительном наблюдении.

Граф процесса рождения и гибели с конечным числом состояний

Рис. 14.28. Граф процесса рождения и гибели с конечным числом состояний

Рассмотрим поведение процесса в стационарном состоянии для случая, когда состояние j = 0 не поглощающее, число состояний конечно и равно К +1 (рис. 14.28). Конечность и связность всех состояний гарантируют нам, что для рассматриваемой системы существует стационарный режим и соответственно финальные вероятности. Известно также, что стационарный процесс рождения и гибели обратим, в частности усеченный процесс рождения и гибели [39]. Для получения выражений абсолютных вероятностей состояний в стационарном режиме функционирования можно воспользоваться несколькими способами.

Так как в стационарном состоянии производные по времени равны нулю, то (14.82) для финальной вероятности состояния j = 0 будет иметь вид

т.е. среднее число переходов в единицу времени из состояния 0 в состояние 1, равное Х0р0, равно среднему числу переходов в единицу времени из состояния 1 в состояние 0, равное ц, рх.

Из (14.80) получим уравнение для финальных вероятностей состояния у' = 1:

Как видно, количество входов также равно количеству выходов, что соответствует уравнению (13.19) глобального баланса.

Уравнение (14.102) с учетом (14.101) можно записать в виде: Алрх = х2р2, Для у = 2 получим Х2р2 = ц 3р3. Далее аналогично для любого j — 0, К можно записать уравнение финальных вероятно- стей :Ху_,ру._, ]Р].

Как видно, в стационарном состоянии потоки через разрез графа на рис. 14.28 сбалансированы. Это вытекает из свойства обратимости процесса, свойства локального баланса (13.38) и древовидной структуры графа.

Таким образом, финальные вероятности р0, р{, ... , Pj, ..., рк удовлетворяют системе уравнений, составленных из условия баланса потоков через разрезы:

При решении полученной системы уравнений необходимо учесть условие нормировки: + /?, + р2 н------ рк =1.

Система (14.103) легко решается, так как возможно все вероятности выразить через р0. Из первого уравнения выразим р{ через р0:

Из второго уравнения с учетом (14.104) получим И вообще для любого j = 0,K

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

Отсюда

Рассмотрим теперь случай с бесконечным числом состояний.

Для такой системы финальные вероятности существуют только если Xj < для всех у. Ряд (14.106) для вычисления финальной вероятности начального состояния будет бесконечным:

Другие финальные вероятности можно вычислить, используя (14.105).

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

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >