Модели, описываемые процессами рождения и гибели

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

,

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

Ранее было получено:

. (1а)

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

.

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

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

.

Для нахождения можно использовать систему линейных уравнений

, (2)

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

, (3)

где с – постоянная. Из (1б) находим, что

.

Отсюда в (3) и получается следующая система рекуррентных уравнений:

(4)

Уравнению (4) можно дать следующую интерпретацию. Его левая часть представляет собой интенсивность перехода из состояния n в состояние , и эта величина балансируется правой частью, представляющей собой интенсивность перехода из состояния в состояние . Граф переходов, отвечающий уравнениям баланса (4), изображен на рис. 2.

Рис. 2. Диаграмма уравнений баланса для процесса рождения и гибели

Стационарные вероятности теперь вычисляются рекуррентно:

, (5)

где

, . (6)

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

(7)

Сходится, то, обозначая его сумму через , получим

. (8)

ПРОСТЕЙШАЯ СИСТЕМА

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

,

где . Если , то ряд сходится и

.

Таким образом, стационарная вероятность того, что в системе находится заявок,

. (9)

Стационарное распределение (9) является геометрическим распределением. Его среднее легко вычисляется:

. (10)

Среднее время ответа можно легко вычислить из (10), используя первую из формул Литтла.

Среднее число заявок в системе

.

Применяя первую формулу Литтла, найдем среднее время пребывания заявки в системе:

.

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

.

Следовательно, среднее число заявок, находящихся на обслуживании, равно

,

отсюда

.

По второй формуле Литтла найдем среднее время пребывания заявки в очереди:

.

N-КАНАЛЬНАЯ СМО С ОТКАЗАМИ (задача Эрланга)

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

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

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

– вероятность отказа, т.е. того, что заявка покинет СМО не обслуженной;

– среднее число занятых каналов.

Состояния системы будем нумеровать по числу заявок, находящихся в системе (в данном случае оно совпадает с числом занятых каналов):

– в СМО нет ни одной заявки;

– в СМО находится одна заявка (один канал занят, остальные свободны);

…

– в СМО находится k заявок (k –каналов заняты, остальные свободны);

…

– в СМО находится n заявок (все n каналов заняты).

Граф состояний СМО соответствует схеме размножения и гибели.

Из в систему переводит поток с интенсивностью (как только приходит заявка система переходит из состояния в состояние ). Тот же поток заявок переводит систему из любого левого состояния в соседнее правое.

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

А теперь, зная все интенсивности, воспользуемся уже готовыми формулами для финальных вероятностей в схеме рождения и гибели

. (1)

Члены разложения представляют собой коэффициенты при в выражениях для :

. (2)

Заметим, что в формулы (1) и (2) интенсивности и входят не по отдельности, а только в виде отношения . Обозначим и будем называть величину “приведенной интенсивностью потока заявок”. Ее смысл – среднее число заявок, приходящее за среднее время обслуживания одной заявки. Тогда

, (4)

. (5)

Формулы (4) и (5) для финальных вероятностей состояний называются формулами Эрланга.

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

. (6)

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

. (7)

Абсолютную пропускную способность мы получим, умножая интенсивность потока заявок на :

. (8)

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

.

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

, (9)

или учитывая (8),

.

Дата добавления: 2015-07-26