Поток с ограниченным последствием.
(Поток Пальма)
Поток с ограниченным последствием это такой поток, если промежутки времени между последовательными событиями независимы.
Простейший поток является частным случаем потока Пальма, когда независимые промежутки времени между последовательными событиями распределены по показательному закону.
Поток заявок, покидающих какую-либо систему массового обслуживания, может быть разбит на два: поток обслуженных и поток не обслуженных заявок.
Для потока не обслуженных заявок Пальма доказал следующую теорему:
Пусть на схему массового обслуживания поступает поток заявок типа Пальма, причём заявка, заставшая все каналы занятыми, получает отказ (не обслуживается). Если при этом время обслуживания имеет показательный закон распределения, то поток не обслуженных заявок является также потоком Пальма.
Примером потоков с ограниченным последствием являются так называемые потоки Эрланга, образуемые “просеиванием” простейшего потока. Пусть на вход системы обслуживания поступает простейший поток требований. Если теперь исключить из потока каждое второе требование, то оставшиеся требования образуют поток, называемый потоком Эрланга первого порядка
. Поток Эрланга второго порядка получится, если сохранить в простейшем потоке каждое третье требование. Вообще потоком Эрланга k-го порядка называется поток, получаемый из простейшего, если сохранить каждые (k+1)-е требования, исключив остальные.С точки зрения этого определения простейший поток является потоком Эрланга нулевого порядка.
В теории вероятности доказывается, что плотность распределения fk(t) величины Tk (интервал между событиями в потоке Эрланга k-го порядка) имеет вид:

при К=0
![]()
Поток Эрланга любого порядка, представляет собой поток Пальма, поскольку из независимости двух соседних промежутков между требованиями в простейшем потоке с неизбежностью следует независимость сумм этих промежутков для любого числа слагаемых в потоке Эрланга любого порядка.
Время обслуживания
Эффективность системы обслуживания зависит от производительности собственно системы обслуживания, т.е. от числа каналов и быстродействия каждого из них. В связи с этим время обслуживания заявки Тоб является важной характеристикой системы. Время обслуживания заявок в реальных системах может меняться от одного требования к другому. Поэтому это время можно считать случайной величиной.
Введём закон распределения времени обслуживания:
![]()
и плотность его распределения:
![]()
Для практики наибольший интерес представляет случай, когда продолжительность времени обслуживания имеет показательный закон распределения, т.е.
![]()
- математическое ожидание времени обслуживания
.
В данном случае если в какой-то момент происходит обслуживание требования, то закон распределения оставшегося времени обслуживания не зависит от того, сколько времени обслуживание уже продолжалось. Тогда плотность распределения времени обслуживания:
![]()
Поскольку показательный закон распределения достаточно удовлетворительно соответствует большому количеству реальных систем обслуживания, в практических случаях обычно используется допущение о показательном законе распределения времени обслуживания. При этом существенно упрощается математический аппарат, применяемый для исследования систем массового обслуживания.
Непрерывно-стохастические модели
(Q-схемы).
Особенности непрерывно-стохастического подхода рассмотрим на примере использования в качестве типовых математических схем систем массового обслуживания (англ. queuing system), которые будем называть Q-схемами. Системы массового обслуживания представляют собой класс математических схем, разработанных в теории массового обслуживания и различных приложениях для формализации процессов функционирования систем, которые по своей сути являются процессами обслуживания. В качестве процесса обслуживания могут быть представлены различные по своей природе процессы функционирования экономических, производственных, технических и других систем, например: потоки поставок продукции некоторому предприятию, потоки деталей и комплектующих изделий на сборочном конвейере цеха, заявки на обработку информации ЭВМ от удалённых терминалов и т.д. При этом характерным для работы таких объектов является случайное появление заявок (требований) на обслуживание и завершение обслуживания в случайные моменты времени, т.е. стохастический характер процесса их функционирования.
В любом элементарном типе обслуживания можно выделить две основные составляющие: ожидание обслуживания заявкой и собственно обслуживание заявки. Это можно изобразить в виде некоторого прибора П
i (рис.14), состоящего из накопителя заявок Нi, в котором может одновременно находиться li=Потоком событий называется последовательность событий, происходящих одно за другим в какие-то случайные моменты времени. Различают потоки однородных и неоднородных событий. Поток событий называется однородным, если он характеризуется только моментами поступления этих событий (вызывающими моментами) и задаётся последовательностью
{tn}={0≤t1≤t2…≤tn}, где tn- момент наступления n-го события – неотрицательное вещественное число. Однородный поток событий также может быть задан в виде последовательности промежутков времени между n-м и (n-1)-м событиями {τn}, которая однозначно связана последовательностью вызывающих моментов {tn},где τ
n=tn-tn-1, n>1 t0=0, т.е. τ1=t1. 
Рис.14 Прибор обслуживания заявок. (П
i)Н
i – накопитель заявокwi –
поток заявокК
i – каналUi –
поток обслуживанийyi –
выходной поток
Потоком неоднородных событий называется последовательность
{tn, fn},где
tn – вызывающие моменты; fn – набор признаков события. Например, применительно к процессу обслуживания для неоднородного потока заявок может быть задана принадлежность к тому или иному источнику заявок, наличия приоритета, возможность обслуживания тем или иным типом канала и т.п.Рассмотрим поток, в котором события разделены интервалами времени τ
1, τ2… , которые вообще являются случайными величинами. Пусть интервалы τ1, τ2… независимы между собой. Тогда поток событий называется потоком с ограниченным последствием.Поток событий называется ординарным, если вероятность того, что на малый интервал времени ∆t, примыкающий к моменту времени t, попадает больше одного события P
>1 (t, ∆t) , пренебрежимо мала по сравнению с вероятностью того, что на это же интервал времени ∆t попадает равно одно событие P1(t, ∆t) т.е. P1(t, ∆t) >> P>1(t, ∆t). Если для любого интервала ∆t событиеP0(t, ∆t)+ P1(t, ∆t)+ P>1(t, ∆t)=1
Как сумма вероятностей событий, образующих полную группу и несовместных, то для ординарного потока событий
P0(t, ∆t)+ P1(t, ∆t)≈1 P>1(t, ∆t)≈0(∆t).
Стационарным потоком событий называется поток, для которого вероятность появления того или иного числа событий на интервале времени τ зависит лишь от длины этого участка и не зависит от того, где на оси времени 0t взят этот участок.
Рассмотрим на оси времени 0t ординарный поток событий и найдём среднее число событий, наступающих на интервале времени ∆t, примыкающим к моменту времени t. Получим
0 ∙P0(t)(t, ∆t)+1∙P1(t, ∆t)= P1(t, ∆t).
Тогда среднее число событий, наступающих на участке времени ∆t в единицу времени, составит (P
1(t, ∆t))/∆t. Рассмотрим предел этого выражения при ∆t→0. Если этот предел существует, то он называется интенсивностью (плотностью) ординарного потока событийlim ((P1
(t, ∆t))/∆t) = λ(t)интенсивность потока может быть любой неотрицательной функцией времени, имеющей размерность обратную размерности времени. Для стационарного потока его интенсивность не зависит от времени и представляет собой постоянное значение, равное среднему числу событий, наступающих в единицу времени λ
(t)=f=const.Обычно в приложениях при моделировании различных систем применительно к элементарному каналу обслуживания K
i можно считать, что поток заявок wi Є W, т.е. интервалы времени между моментами появления заявок (вызывающие моменты) на входе Ki, образует надмножество неуправляемых переменных, а поток обслуживания Ui Є V, т.е. интервалы времени между началом и окончанием обслуживания заявки, образует подмножество управляемых переменных.Заявки, обслуженные каналом K
i и заявки, покинувшие прибор Пi по различным причинам не обслуженными (например, из-за переполнения накопителя Нi), образуют входной поток yi Є Y, т.е. интервалы времени между моментами выхода заявок образуют подмножество выходных переменных.Процесс функционирования прибора обслуживания П
i можно представить как процесс изменения состояний его элементов во времени Zi(t). Переход в новое состояние для Пi означает изменения количество заявок, которое в нём находится (в канале Кi и в накопителе Пi). Таким образом вектор состояний для Пi имеет вид:![]()
![]()
![]()
![]()
где - состояние накопителя Нi ( = 0 – накопитель пуст, =1 – в накопителе имеется одна заявка, ……, =
- накопитель полностью заполнен);
- ёмкость накопителя Нi измеряется числом заявок, которые могут в нём поместится;
- канал занят и т.д.).
В практике моделирования систем, имеющих более сложные структурные связи и алгоритмы поведения, для формализации используются не отдельные приборы обслуживания, а Q-схемы, образуемые полипозицией многих элементарных приборов обслуживания Пi. Если каналы Кi различных приборов обслуживания соединены параллельно, то имеет место многоканальное обслуживание (многофазное обслуживание) (многофазная Q-схема). Таким образом, для задания Q-схемы необходимо использовать оператор сопряжения R, отражающий взаимосвязь элементов структуры (каналов и накопителей) между собой.
Связи между элементами Q-схемы изображают в виде стрелок (линий потока, отражающих направление движения заявок). Различают разомкнутые и замкнутые Q-схемы. В разомкнутой Q-схеме выходной поток обслуженных заявок не может снова поступить на какой-то элемент, т.е. обратная связь отсутствует, а в замкнутых Q-схемах имеются обратные связи, по которым заявки движутся в направлении, обратном движению вход-выход.
Собственными (внутренними) параметрами Q-схемы будет являться количество фаз Lф , количество каналов в каждой фазе Lki, j=lτ Lф, количество накопителей каждой фазы LHK, К= lτ Lф, ёмкость i-го накопителя
. Следует отметить, что в теории массового обслуживания в зависимости от ёмкости накопителя применяют следующую терминологию для систем массового обслуживания: системы с потерями (
=0, т.е. накопитель в приборе Пi отсутствует, а имеется только канал обслуживания Кi), системы с ожиданием (
→∞, т.е. накопитель Нi имеет бесконечную емкость, и очередь заявок не ограничивается (
→∞) системы смешанного типа (с ограниченной ёмкостью накопителя Нi). Всю совокупность собственных параметров Q-схемы обозначим как подмножество Н.
Для задания Q-схемы также необходимо описать алгоритмы её функционирования, которое определяют набор правил поведения заявок в системе в различных неоднозначных ситуациях. В зависимости от места возникновения таких ситуаций различают алгоритмы (дисциплины) ожидания заявок в накопителе Нi и обслуживания заявок по каналам Кi каждого элементарного обслуживающего прибора Пi Q-схемы. Неоднородность заявок, отражающая процесс в той или иной реальной схеме, учитывается с помощью введения классов приоритетов.
В зависимости от динамики приоритетов в Q-схемах различают статические и динамические приоритеты. Статические приоритеты назначаются заранее и не зависят от состояния Q-схемы, т.е. они являются фиксированными в пределах решения конкретной задачи моделирования. Динамические приоритеты возникают в моделировании в зависимости от возникающих ситуаций. Исходя из правил выбора заявок из накопителя Нi на обслуживание каналом Кi, можно выделить относительные и абсолютные приоритеты. Относительный приоритет означает, что заявка с более высоким приоритетом, поступившая в накопитель Нi ожидает окончания обслуживания предшествующей заявки калом Кi и только после этого занимает канал (при этом вытесненная из Кi заявка с более низким приоритетом может либо покинуть систему, либо может быть снова записана на какое-то место в Нi).
При рассмотрении алгоритмов функционирования приборов обслуживания П
i (каналов Кi и накопителей Нi) необходимо также задать набор правил, по которым заявки покидают Нi и Кi : для Нi – либо правила переполнения, по которым заявки в зависимости от заполнения Нi покидают систему, либо правила ухода, связанные с истечением времени ожидания заявки в Нi ; для Кi – правила выбора маршрутов или направлений ухода. Кроме того, для заявок необходимо знать правила, по которым они остаются в канале Кi или не допускаются до обслуживания каналом Кi, т.е. правила блокировок канала. При этом различают блокировки Кi по выходу и входу.Такие блокировки отражают наличие управляющих связей, в Q-схеме, регулирующий поток заявок в зависимости от состояний Q-схемы. Весь набор возможных алгоритмов поведения заявок в Q-схеме можно представить в виде некоторого оператора алгоритмов поведения заявок.
Таким образом, Q-схема, описывающая процесс функционирования системы массового обслуживания любой сложности, однозначно задаётся в виде
Q=<W, V, H, Z, R, A>.
При ряде упрощающих предположений относительно надмножеств входящих потоков W и потоков обслуживания V (выполнение условий стационарности, ординарности и ограниченного последствия), оператора сопряжения элементов структуры R (однофазное одноканальное обслуживание в разомкнутой системе), подмножества собственных параметров Н (обслуживание с бесконечной
ёмкостью накопителя), оператора алгоритмов обслуживания заявок А (бесприоритетное обслуживание без прерываний и блокировок) для оценки вероятностно-временных характеристик можно аналитический аппарат, разработанный в теории массового обслуживания. При принятых предположениях в обозначениях Д. Канделла будет иметь место классическая система обслуживания типа М/М/l (одноканальная система с Марковским входящим потоком заявок и Марковским потоком обслуживания). Рассмотрим на примере основные аналитические соотношения для элементарной Q-схемы.Допустим, что процесс обслуживания начинается при отсутствии заявок в накопителе. Тогда состояния системы массового обслуживания описываются следующей системой уравнений
Pn(t+∆t)= Pn
(t)[1-(λ + μ) ∆t]+ Pn-1 λ ∆t+ Pn+1 (t ) μ ∆t, n≥1.P0(t+∆t)= P0
(t)(1-λ∆t)+ P1 (t ) μ ∆t.где P
n(t) – вероятность нахождения системы в состоянии Zn Є Z в момент времени t, т.е. когда в ней имеется n заявок.Эти уравнения следуют из того, что вероятность нахождения в системе n заявок в момент времени (t+∆t) равно вероятности нахождения в системе n заявок в момент t, умноженной на вероятность того, что за время ∆t в систему не поступит ни одной заявки и ни одна заявка не будет обслужена, плюс вероятность нахождения в системе (n-1) заявок в момент t
, умноженная на вероятность того, что за время ∆t поступит одна заявка и ни одна заявка не будет обслужена, плюс вероятность нахождения в системе (n+1) заявок в момент t, и не поступит ни одной заявки. Вероятность того, что за время ∆t не поступит ни одной заявки и ни одна заявка не покинет систему, равна(1 - λ∆t)∙(1 - μ ∆t) ≈ 1 – (λ + μ)∆t.
Кроме того, в первом уравнении
λ∆t(1 - μ ∆t) ≈ λ∆t; μ ∆t(1 – λ∆t) ≈ μ∆t.
Перенеся P
n(t) влево и устремив ∆t к нулю, получим систему дифференциальных уравнений:
Найдём выражение математического ожидания числа заявок, находящихся в накопителе для стационарного состояния ρ
=λ/μ < 1. Οπировняв нулю производные по времени и исключив, таким образом, время t из уравнений, получим систему алгебраических уравнений:

Пусть в первом уравнении n=1. Тогда (1+ρ
)P1= P1+ ρP0.Подставив сюда значение ρ из второго уравнения, находим P
2=ρ2∙P0.Повторяя эти операции, получаем P
n=ρn∙P0.Причём
, т.к. это сумма вероятностей того, что в системе нет ни одной заявки, имеется одна заявка, две заявки и т.д.
поэтому 
или 
откуда P
0=1-ρ. Ρλεдовательно, Pn=ρn(1-ρ). Οξλученное выражение представляет собой геометрическое распределение.Математическое ожидание числа заявок, находящихся в системе (приборе):
.
Дисперсия (колебание числа заявок, ожидающих обслуживания):
![]()

при этом

Следовательно,

Математическое ожидание числа заявок, находящихся в накопителе:

Среднее время ожидания заявок в накопителе

Обобщенные модели (А-схемы)
Наиболее известным общим подходом к формальному описанию процессов функционирования систем является подход, предложенный Н.П. Бусленко. Этот подход позволяет описывать поведение непрерывных дискретных, детерминированных и стохастических систем, т.е. по сравнению с рассмотренными является обобщенным (универсальным) и базируется на понятии агрегативной системы, представляющей собой формальную схему общего вида, которую будем называть А-схемой.
Анализ существующих средств моделирования на ЭВМ, неизбежно приводит к выводу, что комплексные решения проблем, возникающих в процессе создания и машинной реализации модели, возможно лишь в случае, если моделирующие системы имеют в своей основе единую формальную математическую схему, т.е. А-схему.
Такая схема должна одновременно выполнять несколько функций, являться адекватным математическим описанием объекта моделирования, т.е. системы S, служить основой для построения алгоритмов и программ при машинной реализации модели М, позволять в упрощенном варианте (для частных случаев) проводить аналитические исследования. Это противоречивое требование.
По традиции, установившейся в математике и в прикладной математике в частности, при агрегативном подходе сначала дается формальное определение объекта моделирования - агрегативной системы, которая является математической схемой, отображающей системный характер изучаемых объектов.
В качестве элемента А-схемы выступает агрегат, а связь между агрегатами (внутри системы S и с внешней средой E) осуществляется с помощью оператора сопряжения R. Очевидно, что агрегат сам может рассматриваться как А-схема, т.е. может разбиваться на элементы, агрегата следующего уровня.
Любой агрегат характеризуется следующими множествами: моментов времени Т, входных Х и выходных Y сигналов, состояний Z в каждый момент времени t. Состояние агрегата в момент времени
обозначается как
, а входные и выходные сигналы как
и
соответственно.
Будем полагать, что переход агрегата из состояния
в состояние
за малый интервал времени, т.е. имеет место скачок
. Переход агрегата из состояния
в состояние
определяются собственными (внутренними) параметрами самого агрегата
и входными сигналами ![]()
В начальный момент времени
состояния z, имеют значения, равные
, т.е.
, задаваемое законом распределения процесса
в момент времени
, а именно
. Предположим, что процесс функционирования агрегата в случае воздействия входного сигнала
описывается случайным оператором
. Тогда в момент поступления в агрегат
входного сигнала
можно определить состояние
![]()
Обозначим полуинтервал времени
как
, а полуинтервал
как
. Если интервал времени
не содержит ни одного момента поступления сигналов, то для
состояние агрегата определяется случайным оператором
в соответствии соотношением
![]()
Совокупность случайных операторов
рассматривается как оператор переходов агрегата в новое состояние. При этом процесс функционирования агрегата состоит из скачков состояний
в момент поступления входных сигналов х (оператор
) и изменений состояний между этими моментами
и
(оператор
). На оператор
не накладывается никаких ограничений, поэтому допустимы скачки состояний
в момент времени, не являющиеся моментами поступления входных сигналов х. В дальнейшем моменты скачков
будем называть особыми моментами времени
, а состояния
- особым состоянием А-схемы. Для описания скачков состояний
в особые моменты времени
будем использовать случайный оператор W, представляющий собой частный случай оператора
, т.е.
.
Во множестве состояний Z, выделяется такое подмножество
, что если
достигает
, то это состояние является моментом выдачи выходного сигнала, определяемого оператором выходов
.