Средние число занятых каналов. СМО с ожиданием (очередью)

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

Относительная пропускная способность равна:

Абсолютная пропускная способность:

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

21. Многоканальная СМО с ожиданием

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

Состояния системы нумеруются по числу заявок, связанных системой:

нет очереди:

Все каналы свободны;

Занят один канал, остальные свободны;

Заняты каналов, остальные нет;

Заняты все каналов, свободных нет;

есть очередь:

Заняты все n каналов; одна заявка стоит в очереди;

Заняты все n каналов, r заявок в очереди;

Заняты все n каналов, r заявок в очереди.

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

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

Обозначим среднее число занятых каналов . Каждый занятый канал обслуживает в среднем заявок в единицу времени, а СМО в целом обслуживает в среднем А заявок в единицу времени. Разделив одно на другое, получим:

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

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

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

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

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

Так же, как и в случае одноканальной СМО с ожиданием, отметим, что это выражение отличается от выражения для средней длины очереди (5.59) только множителем , т. е.

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

23/24. Системы с неограниченной длиной очереди. Мы рассмотрели канальную СМО с ожиданием, когда в очереди одновременно могут находиться не более m заявок.

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

Вероятности состояний получим из формул предельным переходом (при ). Заметим, что сумма соответствующей геометрической прогрессии сходится при и расходится при > 1. Допустив, что < 1 и устремив в формулах (5.56) величину m к бесконечности, получим выражения для предельных вероятностей состояний:

Вероятность отказа, относительная и абсолютная пропускная способность. Так как каждая заявка рано или поздно будет обслужена, то характеристики пропускной способности СМО составят:

Среднее число заявок в очереди получим при из (5.59):

асреднее время ожидания - из (5.60):

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

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

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

Рассмотрим СМО подобного типа, предполагая, что ограничение времени ожидания является случайной величиной.

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

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

нет очереди:

Все каналы свободны;

Занят один канал;

Заняты два канала;

Заняты все n каналов; есть очередь:

Заняты все n каналов, одна заявка стоит в очереди;

Заняты все n каналов, r заявок стоят в очереди и т. д.

Граф состояний и переходов системы показан на рис. 5.10.

Разметим этот граф, как и раньше; у всех стрелок, ведущих слева направо, будет стоять интенсивность потока заявок . Для состояний без очереди у стрелок, ведущих из них справа налево, будет, как и раньше, стоять суммарная интенсивность потока обслуживании всех занятых каналов. Что касается состояний с очередью, то у стрелок, ведущих из них справа налево, будет стоять суммарная интенсивность потока обслуживании всех n каналов плюс соответствующая интенсивность потока уходов из очереди. Если в очереди стоят r заявок, то суммарная интенсивность потока уходов будет равна

Как видно из графа, имеет место схема размножения и гибели; применяя общие выражения для предельных вероятностей состояний в этой схеме (используя сокращенные обозначения , запишем:

Отметим некоторые особенности СМО с ограниченным ожиданием сравнительно с ранее рассмотренными СМО с «терпеливыми» заявками.

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

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

Для СМО с «нетерпеливыми» заявками понятие «вероятность отказа» не имеет смысла - каждая заявка становится в очередь, но может и не дождаться обслуживания, уйдя раньше времени.

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

На каждую из этих заявок действует «поток уходов» с интенсивностью . Значит, из среднего числа заявок в очереди в среднем будет уходить, не дождавшись обслуживания, заявок в единицу времени и всего в единицу времени в среднем будет обслуживаться

заявок. Относительная пропускная способность СМО будет составлять:

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

Среднее число заявок в очереди. Соотношение (5.64) позволяет вычислить среднее число заявок в очереди , не суммируя бесконечного ряда (5.63). Из (5.64) получаем:

а входящее в эту формулу среднее число занятых каналов можно найти как математическое ожидание случайной величины Z, принимающей значения 0, 1, 2, ..., n с вероятностями , :

25. Игры с противоположными интересами. Основные понятия. Платежная матрица.

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

Игра-мероприятие, состоящее из ряда действий сторон.

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

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

Стороны, участвующие в конфликте наз. игроками, а исход конфликта-проигрышем(выигрышем).

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

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

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

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

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

А, В	В 1	В 2	…	В n
А 1	a 11	a 12	…	a 1n
А 2	a 21	a 22	…	a 2n
…	…	…	…	…
А m	a m1	a m2	…	a mn

Строки этой матрицы соответствуют стратегиям игрока A , а столбцы – стратегиям игрока B .

26. Нижняя и верхняя цена игры. Принцип минимакса.

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

Выбранная таким образом стратегия гарантирует одной стороне максимально возможный выигрыш (А) при самой неблагоприятной для него стратегии для любой стороны.

А: оценивает для каждой своей стратегии минимально возможный выигрыш αij..

αi= min αij i=1,m

βj= max αij j=1,n

α= max αi i=1,m

α= max min αij i=1,m, j=1,n –нижняя цена игры

β= min max αij i=1,m, j=1,n –верхняя цена игры

Стратегия игрока А, доставляющая максимальный выигрыш, называется максимальной стратегией. Стратегия В, доставляющая минимальной проигрыш, называется минимальной стратегией.

Величина υ=α=β наз. чистой ценой игры.

27. Игры с седловой точкой.

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

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

При наличии седловой точки, решением игры является пара оптимальной стратегии (A * ij , B * ij), соответствующая этой точке.

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

1. Если А выбрал оптим. стратегию, то независимо от стратегии В, его выигрыш будет не меньше чистой цены игры.

2. Если В выбрал оптим. стратегию, то какой бы стратегии не придерживался бы А, выигрыш В не превысит чистой цены игры.

28. Решение игры в смешанных стратегиях. Активные стратегии. Теорема об активных стратегиях.

Рассмотрим α ≠β, α<β, α<υ<β.

В случае, если α ≠β, то у такой игры нет седловой точки В этом случае принцип минимакса или максимина не подходит.

(Решение игр 2х2)

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

Активными называются те стратегии, которые доминируют над другими.

Рассмотрим игру 2хn

Наносим на оси цену игрока В.

Из самой высокой точки опускаем перпендикуляр.

Самая высокая точка нижней ломаной является точкой пересечения прямых, соответствующих активным стратегиям В*1 и В*2.

Таким образом исходная игра сокращается до игры 2х2.

Решаем игру и находим вероятности активных стратегий. Вероятности активных стратегий.

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

36. Игра 2*2.Аналитический и графический способы решения.

В общем случае игра 2 2 определяется матрицей

Прежде всего необходимо проверить, есть ли у данной игры седловая точка. Если да, то игра имеет решение в чистых стратегиях, причём оптимальными стратегиями игроков 1 и 2 соответственно будут чистая максиминная и чистая минимаксная стратегии. Если же игра с матрицей выигрышей А не имеет чистых стратегий, то оба игрока имеют только такие оптимальные стратегии, которые используют все свои чистые стратегии с положительными вероятностями. В противном случае один из игроков (например 1) имеет чистую оптимальную стратегию, а другой – только смешанные. Не ограничивая общности, можно считать, что оптимальной стратегией игрока 1 является выбор с вероятностью 1 первой строки. Далее, по свойству 1 следует, что а 11 = а 12 =  и матрица имеет вид

Легко видеть, что для матриц такого вида одна из стратегий игрока 2 является доминируемой. Следовательно, по свойству 4 этот игрок имеет чистую стратегию, что противоречит предположению.

Пусть Х = (, 1   ) – оптимальная стратегия игрока 1. Так как игрок 2 имеет смешанную оптимальную стратегию, из свойства 1 получим, что (см. также свойство 7)

Отсюда следует, что при   0 столбцы матрицы А не могут быть пропорциональны с коэффициентом пропорциональности, отличным от единицы. Если же коэффициент пропорциональности равен единице, то матрица А принимает вид

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

;

.

Аналогичные рассуждения приводят нас к тому, что оптимальная стратегия игрока 2 Y = ( , 1 -  ) удовлетворяет системе уравнений

.

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

Первый случай.

Рассмотрим игру (2х2) с матрицей без седловой точки.

Решением игры являются смешанные страте­гии игроков и , где

х 1 - вероятность применения первым игроком первой стратегии,

х 2 - вероятность применения первым игроком второй стратегии,

у 1 - вероятность применения вторым игроком первой стратегии,

у 2 - вероятность применения вторым игроком второй стратегии.

Очевидно, что

Найдем решение игры графическим методом (рис.1).

На оси ОХ отложим отрезок, длина которого равна единице.

Левый конец (х = 0) соответствует стратегии первого игрока А 1 , правый
(х = 1) - стратегии А 2 .

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

Через концы отрезка проведем прямые, перпендикулярные оси ОХ, на которых будем откладывать выигрыш при соответствующих чистых стратегиях. Если игрок В применяет стратегию В 1 , то выиг­рыш при использовании первым игроком стратегий А 1 и А 2 соста­вит соответственно а 11 и а 21 . Отложим эти точки на прямых и соединим их отрезком В 1 В 1 . Если игрок А применяет смешанную стратегию, то выигрышу соответствует некоторая точка М, лежа­щая на этом отрезке.

Аналогично строится отрезок В 2 В 2 , соответствующий страте­гии В 2 игрока В.

Определение 20. Ломаная линия, составленная из частей от­резков, интерпретирующих стратегии игрока В, расположенная ниже всех отрезков, называется нижней границей выигрыша , полу­чаемого игроком А .

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

В игре (2х2) обе стратегии являются активными.

Ломаная В 1 КВ 2 является нижней границей выигрыша (рис. 2), получаемого игроком А. Точка К, в которой он максимален, опре­деляет цену игры и ее решение.

Найдем оптимальную стратегию первого игрока. Запишем систему уравнений

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

(1)

(2)

Составляя аналогичную систему

и учитывая условие

можно найти оптимальную стратегию игрока В:

(3)

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

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

Рассмотрим игру 2xn

Решаем игру 2х2 и находим вероятности активых стратегий. Вероятностям пассивных стратегий присваиваем нули.

Рассмотрим игру mx2

	В1	В2
А1	a 11	a 12
А2	a 21	a 22
…	…..	……
Аn	a m1	a m2

Нижняя точка верхней ломаной соответствует активным стратегиям ai и aj.

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

38. игры m x n сведение решения игры m x n к задаче линейного програмирования. Основная теорема теории игр.

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

В качестве показателей эффективности СМО с ожиданием, кроме уже известных показателей - абсолютной А и относительной Q пропускной способности, вероятности отказа P отк. , среднего числа занятых каналов (для многоканальной системы) будем рассматривать также следующие: L сист. - среднее число заявок системе; Т сист. - среднее время пребывания заявки в системе; L оч. - среднее число заявок в очереди (длина очереди); Т оч. - среднее время пребывания заявки в очереди; Р зан.. - вероятность того, что канал занят (степень загрузки канала).
Одноканальная система с неограниченной очередью. На практике часто встречаются одноканальные СМО с неограниченной очередью (например, телефон-автомат с одной будкой). Рассмотрим задачу.
Имеется одноканальная СМО с очередью, на которую не наложены никакие ограничения (ни по длине очереди, ни по времени ожидания). Поток заявок, поступающих в СМО, имеет интенсивность λ, а поток обслуживании - интенсивность μ. Необходимо найти предельные вероятности состояний и показатели эффективности СМО.
Система может находиться в одном из состояний S 0 , S 1 , S 2 , …, S k , по числу заявок, находящихся в СМО: S 0 - канал свободен; S 1 - канал занят (обслуживает заявку), очереди нет, S 2 - канал занят, одна заявка стоит в очереди; ... S k - канал занят, (k-1) заявок стоят в очереди и т.д.
Граф состояний СМО представлен на рис. 8.

Рис. 8
Это процесс гибели и размножения, но с бесконечным числом состояний, в котором интенсивность потока заявок равна λ, а интенсивность потока обслуживании μ.
Прежде чем записать формулы предельных вероятностей, необходимо быть уверенным в их существовании, ведь в случае, когда время t→∞, очередь может неограниченно возрастать. Доказано, что если ρ<1, т.е. среднее число приходящих заявок меньше среднего числа обслуженных заявок (в единицу времени), то предельные вероятности существуют. Если ρ≥1, очередь растет до бесконечности.

Для определения предельных вероятностей состояний воспользуемся формулами (16), (17) для процесса гибели и размножении (здесь мы допускаем известную нестрогость, так как ранее эти формулы были получены для случая конечного числа состояний системы). Получим (32)
Так как предельные вероятности существуют лишь при ρ < 1, то геометрический ряд со знаменателем
ρ < 1, записанный в скобках в формуле (32), сходится к сумме, равной . Поэтому
(33)
и с учетом соотношений (17)

найдем предельные вероятности других состояний
(34)
Предельные вероятности p 0 , p 1 , p 2 , …, p k ,… образуют убывающую геометрическую профессию со знаменателем р < 1, следовательно, вероятность р 0 - наибольшая. Это означает, что если СМО справляется с потоком заявок (при ρ < 1), то наиболее вероятным будет отсутствие заявок в системе.
Среднее число заявок в системе L сист. определим по формуле математического ожидания, которая с учетом (34) примет вид
(35)
(суммирование от 1 до ∞, так как нулевой член 0p 0 =0).
Можно показать, что формула (35) преобразуется (при ρ < 1) к виду
(36)
Найдем среднее число заявок в очереди L оч. Очевидно, что
(37)
где L об. - среднее число заявок, находящихся под обслуживанием.
Среднее число заявок под обслуживанием определим по формуле математического ожидания числа заявок под обслуживанием, принимающего значения 0 (если канал свободен) либо 1 (если канал занят):

т.е. среднее число заявок под обслуживанием равно вероятности того, что канал занят:
(38)
В силу (33)
(39)
Теперь по формуле (37) с учетом (36) и (39)
(40)
Доказано, что при любом характере потока заявок, при любом распределении времени обслуживания, при любой дисциплине обслуживания среднее время пребывания заявки в системе (очереди) равна среднему числу заявок в системе (в очереди), деленному на интенсивность потока заявок, т.е.
(41)
(42)
Формулы (41) и (42) называются формулами Литтла. Они вытекают из того, что в предельном, стационарном режиме среднее число заявок, прибывающих в систему, равно среднему числу заявок, покидающих ее: оба потока заявок имеют одну и ту же интенсивность λ.
На основании формул (41) и (42) с учетом (36) и (40) среднее время пребывания заявки в системе определится по формуле:
(43)
а среднее время пребывания заявки в очереди
(44)
Многоканальная СМО с неограниченной очередью . Рассмотрим задачу. Имеется n-канальная СМО с неограниченной очередью. Поток заявок, поступающих в СМО, имеет интенсивность λ, а поток обслуживании - интенсивность μ. Необходимо найти предельные вероятности состояний СМО и показатели ее эффективности.

Система может находиться в одном из состояний S 0 , S 1 , S 2 ,…, S k ,…, S n ,…, - нумеруемых по числу заявок, находящихся в СМО: S 0 - в системе нет заявок (все каналы свободны); S 1 - занят один канал, остальные свободны; S 2 - заняты два канала, остальные свободны;..., S k - занято k каналов, остальные свободны;..., S n - заняты все n каналов (очереди нет); S n+1 - заняты все n каналов, в очереди одна заявка;..., S n+r - заняты все n каналов, r заявок стоит в очереди,....

Граф состояний системы показан на рис. 9. Обратим внимание на то, что в отличие от предыдущей СМО, интенсивность потока обслуживаний (переводящего систему из одного состояния в другое справа налево) не остается постоянной, а по мере увеличения числа заявок в СМО от 0 до n увеличивается от величины m до nm, так как соответственно увеличивается число каналов обслуживания. При числе заявок в СМО большем, чем n, интенсивность потока обслуживании сохраняется равной nm.

Рис. 9
Можно показать, что при r/n < 1 предельные вероятности существуют. Если r/n > 1, очередь растет до бесконечности. Используя формулы (16) и (17) для процесса гибели и размножения, можно получить следующие формулы для предельных вероятностей состояний n-канальной СМО с неограниченной очередью
(45)
(46)
(47)
Вероятность того, что заявка окажется в очереди,
(48)
Для n-канальной СМО с неограниченной очередью, используя прежние приемы, можно найти:
среднее число занятых каналов
(49)
среднее число заявок в очереди
(50)
среднее число заявок в системе
(51)
Среднее время пребывания заявки в очереди и среднее время пребывания заявки в системе, как и ранее, находятся по формулам Литтла (42) и (41).
Замечание. Для СМО с неограниченной очередью при r < 1 любая заявка, пришедшая в систему, будет обслужена, т.е. вероятность отказа P отк = 0, относительная пропускная способность Q = 1, а абсолютная пропускная способность равна интенсивности входящего потока заявок, т.е. А = l.

СМО с ограниченной очередью

СМО с ограниченной очередью. СМО с ограниченной очередью отличаются от рассмотренных выше задач лишь тем, что число заявок в очереди ограничено (не может превосходить некоторого заданного т). Если новая заявка поступает в момент, когда все места в очереди заняты, она покидает СМО необслуженной, т.е. получает отказ.
Очевидно: для вычисления предельных вероятностей состояний и показателей эффективности таких СМО может быть использован тот же подход, что и выше, с той разницей, что суммировать надо не бесконечную прогрессию (как, например, мы делали при выводе формулы (33)), а конечную.
Среднее время пребывания заявки в очереди и в системе, как и ранее, определяем по формулам Литтла (44) и (43).
СМО с ограниченным временем ожидания. На практике часто встречаются СМО с так называемыми "нетерпеливыми" заявками. Такие заявки могут уйти из очереди, если время ожидания превышает некоторую величину. В частности, такого рода заявки возникают в различных технологических системах, в которых задержка с началом обслуживания может привести к потере качества продукции, в системах оперативного управления, когда срочные сообщения теряют ценность (или даже смысл), если они не поступают на обслуживание в течение определенного времени.

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

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

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

Система может находиться в одном из состояний s 0 , s 1 , s 2 ,…,s k ,…,s n , нумеруемых по числу заявок, находящихся в СМО: s 0 – в системе нет заявок (все каналы свободны); s 1 – занят один канал, остальные свободны; s 2 – заняты два канала, остальные свободны;…; s k – занято k каналов, остальные свободны;…; s n – заняты все n каналов (очереди нет); s n +1 – заняты все n каналов, в очереди одни заявка;…; s n + r – заняты все n каналов, r заявок в очереди.

Граф состояний приведен на рис. 7

… …

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

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

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

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

(31)

,…, ,…, (32)

,…,

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

(33)

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

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

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

,

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

,

Среднее время обслуживания заявки

Среднее время ожидания обслуживания

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

При n=1

Т.к.

;

При n=2

Т.к.

,

Пример 7. К двум продавцам поступает на обслуживание поток покупателей с интенсивностью 220 человек в час. Каждый из продавцов затрачивает на обслуживание покупателя в среднем 30 секунд. Определите среднюю длину очереди и показатели занятости продавцов.

Решение. , ,

– интенсивность загрузки

– среднее число занятых обслуживанием каналов

– средняя длина очереди

– доля времени простоя продавцов

– доля времени занятости одного из двух продавцов

– доля времени занятости двух продавцов

Пример 8. В универсаме к узлу расчета поступает поток покупателей с интенсивностью . Средняя продолжительность обслуживания контролером-кассиром одного покупателя . Определить минимальное количество контролеров-кассиров n мин , при котором очередь не будет расти до бесконечности и соответствующие характеристики обслуживания при n=n мин .

Решение. По условию , . Очередь не будет возрастать до бесконечности при условии , т.е. при . Таким образом, минимальное количество контролеров-кассиров n min =3 .Р отк =0 , относительная пропускная способность Q=1 , а абсолютная пропускная способность равна интенсивности входящего потока заявок, т.е. .

Для нашей задачи абсолютная пропускная способность узла расчета A=1,35 1/мин или 81 1/ч , т.е. 81 покупатель в час.

Анализ характеристик обслуживания свидетельствует о значительной перегрузке узла расчета при наличии трех контролеров-кассиров.

Более сложные задачи теории массового обслуживания

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

До сих пор мы занимались только простейшими СМО, для которых все потоки событий, переводящий их из состояния в состояние, были простейшими. А как быть, если они не простейшие? Насколько реально это допущение? Насколько значительны ошибки, к которым оно приводит, когда оно нарушается? На все эти вопросы мы попытаемся ответить здесь.

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

1. n -канальная СМО с отказами, с простейшим потоком заявок и произвольным распределением времени обслуживания. В предыдущем параграфе мы вывели формулы Эрланга (20.4), (20.5) для финальных вероятностей состояний СМО с отказами. Сравнительно недавно (в 1959 г.) Б. А. Севастьянов доказал, что эти формулы справедливы не только при показательном, но и при произвольном распределении времени обслуживания.

^ 2. Одноканальная СМО с неограниченной очередью, простейшим потоком заявок и произвольным распределением времени обслуживания. Если на одноканальную СМО с неограниченной очередью поступает простейший поток заявок с интенсивностью λ, а время обслуживания имеет произвольное распределение с математическим ожиданием t об = 1/μ. и коэффициентом вариации v μ , то среднее число заявок в очереди равно

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

(21.2)

Где, как и ранее, ρ = λ/μ., a v μ - отношение среднего квадратического отклонения времени обслуживания к его математическому ожиданию. Формулы (21.1), (21.2) носят название формул Полячека - Хинчина.

Деля L оч, и L сист на λ, получим, согласно формуле Литтла, среднее время пребывания заявки в очереди и среднее время пребывания в системе:

(21.3)

(21.4)

Заметим, что в частном случае, когда время обслуживания - показательное, v μ = 1 и формулы (21.1), (21.2) превращаются в уже знакомые нам формулы (20.16), (20.20) для простейшей одноканальной СМО. Возьмем другой частный случай - когда время обслуживания вообще не случайно и v μ = 0. Тогда среднее число заявок в очереди уменьшается вдвое по сравнению с простейшим случаем. Это и естественно: если обслуживание заявки протекает более организованно, «регулярно», то СМО работает лучше, чем при плохо организованном, беспорядочном обслуживании.

^ 3. Одноканальная СМО с произвольным потоком заявок и произвольным распределением времени обслуживания. Рассматривается одноканальная СМО с неограниченной очередью, на которую поступает произвольный рекуррентный поток заявок с интенсивностью λ и коэффициентом вариации v λ интервалов между заявками, заключенным между нулем и единицей: 0 < v λ < 1. Время обслуживания Т об также имеет произвольное распределение со средним значением t об = 1/μ и коэффициентом вариации v μ , тоже заключенным между нулем и единицей. Для этого случая точных аналитических формул получить не удается;

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

Доказано, что в этом случае

Если входящий поток - простейший, то обе оценки - верхняя и нижняя - совпадают, и получается формула Полячека - Хинчина (21.1). Для грубо приближенной оценки средней длины очереди М. А. Файнбергом (см. ) получена очень простая формула:

(21.6)

Среднее число заявок в системе получается из L оч простым прибавлением ρ - среднего числа обслуживаемых заявок:

L сист = L оч + ρ. (21.7)

Что касается средних времен пребывания заявки в очереди и в системе, то они вычисляются через L оч и L сист по формуле Литтла делением на λ.

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

Возникает естественный вопрос: а как же обстоит дело с многоканальными немарковскими СМО? Со всей откровенностью ответим: плохо. Точных аналитических методов для таких систем не существует. Единственное, что мы всегда можем найти, это среднее число занятых каналов k = ρ. Что касается L оч, L сист, W оч, W сист, то для них таких общих формул написать не удается.

Правда, если каналов действительно много (4-5 или больше), то непоказательное время обслуживания не страшно: был бы входной поток простейшим. Действительно, общий поток «освобождений» каналов складывается из потоков освобождений отдельных каналов, а в результате такого наложения («суперпозиции») получается, как мы знаем, поток, близкий к простейшему. Так что в этом случае замена непоказательного распределения времени обслуживания показательным приводит к сравнительно малым ошибкам. К счастью, входной поток заявок вомногих задачах практики близок к простейшему.

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

Как же подобрать такие одноканальные СМО - «лучшую» и «худшую»? Это можно сделать по-разному. Оказывается, заведомо худший вариант можно получить, если расчленить данную n -канальную СМО на п одноканальных, а общий поступающий на них простейший поток распределять между этими одноканальными СМО в порядке очереди: первую заявку - в первую СМО, вторую - во вторую и т. д. Мы знаем, что при этом на каждую СМО будет поступать поток Эрланга n -го порядка, с коэффициентом вариации, равным 1/ . Что касается коэффициента вариации времени обслуживания, то он остается прежним. Для такой одноканальной СМО мы уже умеем вычислять время пребывания заявки в системе W сист; оно будет заведомо больше, чем для исходной n -канальной СМО. Зная это время, можно дать «пессимистическую» оценку и для среднего числа заявок в очереди, пользуясь формулой Литтла и умножая среднее время на интенсивность λ общего потока заявок. «Оптимистическую» оценку можно получить, заменяя n -канальную СМО одной одноканальной, но с интенсивностью потока обслуживании в n раз большей, чем у данной, равной nμ . Естественно, при этом параметр ρ тоже должен быть, изменен, уменьшен в n раз. Для такой СМО время пребывания заявки в системе W сист уменьшается за счет того, что обслуживание продолжается в n раз меньше времени. Пользуясь измененным значением , коэффициентом вариации входящего потока v λ и времени обслуживания v μ , мы можем приближенно вычислить среднее число заявок в системе . Вычитая из него первоначальное (не измененное) значение ρ, мы получим среднее число заявок в очереди . Обе характеристики будут меньше, чем для исходной n -канальной СМО (будут представлять собой «оптимистические» оценки). От них, деля на λ, можно перейти к «оптимистическим» оценкам для времени пребывания в СМО и в очереди.

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

Состояния системы нумеруются по числу заявок, связанных системой:

нет очереди:

Все каналы свободны;

Занят один канал, остальные свободны;

Заняты каналов, остальные нет;

Заняты все каналов, свободных нет;

есть очередь:

Заняты все n каналов; одна заявка стоит в очереди;

Заняты все n каналов, r заявок в очереди;

Заняты все n каналов, m заявок в очереди.

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

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

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

Вероятность отказа . Поступившая заявка получает отказ, если заняты все n каналов и все m мест в очереди:

(5.57)

Относительная пропускная способность дополняет вероятность отказа до единицы:

Абсолютная пропускная способность СМО:

(5.58)

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

Обозначим среднее число занятых каналов . Каждый занятый канал обслуживает в среднем заявок в единицу времени, а СМО в целом обслуживает в среднем А заявок в единицу времени. Разделив одно на другое, получим:

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

(5.59)

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

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

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

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

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

(5.60)

Так же, как и в случае одноканальной СМО с ожиданием, отметим, что это выражение отличается от выражения для средней длины очереди (5.59) только множителем , т. е.

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

Системы с неограниченной длиной очереди .

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

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

Вероятности состояний получим из формул (5.56) предельным переходом (при ). Заметим, что сумма соответствующей геометрической прогрессии сходится при и расходится при > 1. Допустив, что < 1 и устремив в формулах (5.56) величину m к бесконечности, получим выражения для предельных вероятностей состояний:

(5.61)

Вероятность отказа, относительная и абсолютная пропускная способность. Так как каждая заявка рано или поздно будет обслужена, то характеристики пропускной способности СМО составят:

Среднее число заявок в очереди получим при из (5.59):

а среднее время ожидания - из (5.60):

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

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

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

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

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

В теории СеМО фундаментальным является понятие состояния сети. Важнейшая характеристика сетей МО − вероятности их состояний. Для определения вероятностей состояний СеМО исследуют протекающий в сети случайный процесс. В качестве моделей протекающих в СеМО процессов также наиболее часто используют марковские и полумарковские.

3.3. Система массового обслуживания как модель

1.5. Сети массового обслуживания

Марковским процессом с непрерывным временем описывают функционирование экспоненциальных СеМО.

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

Теория экспоненциальных СеМО наиболее разработана, и ее широко применяют как для исследования сетей ПД так и для исследования мультипроцессорных вычислительных систем (ВС). Разработаны практические формулы расчета вероятностно-временных характеристик (ВВХ) таких сетей и систем.

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

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

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

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

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

Для наглядного представления СеМО используется граф, вершины которого (узлы) соответствуют отдельным СМО , а дуги отображают связи между узлами.

Переход заявок между узлами происходит мгновенно в соответствии с переходными вероятностями , p ij - вероятность того, что заявка после обслуживания в узле i перейдет в узел j . Естественно, если узлы непосредственно не связаны между собой, то p ij = 0. Если из i- го узла переход только в один какой-либо узел j , то p ij = 1.

СеМО классифицируют по нескольким признакам (рис. 4).

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

l j = a ij l i ,

где a ij - коэффициент пропорциональности, или относительно источника

l j = a j l 0 ,.

Коэффициент a j называют коэффициентом передачи, он характеризует долю заявок, поступающих в j- й узел от источника заявок, либо - среднее число прохождений заявкой через данный узел за время нахождения заявки в сети.

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

Сеть всегда линейна, если в ней заявки не теряются и не размножаются.

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

Рис. 4. Классификация сетей массового обслуживания

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

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

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

Законом распределения длительности обслуживания в узлах;

Приоритетами;

Маршрутами (путями движения заявок в сети).

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

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

Таким образом, экспоненциальной будем называть СеМО , отвечающую требованиям:

Входные потоки СеМО пуассоновские;

Во всех N СМО время обслуживания заявок имеет экспоненциальную функцию распределения вероятностей, и заявки обслуживаются в порядке прихода;

Переход заявки с выхода i -й СМО на вход j -й является независимым случайным событием, имеющим вероятность p ij ; p i0 - вероятность ухода заявки из CeМО.

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