Входной поток. Входной поток информации

12.37 Руководство по входной/выходной информации ПО Руководство по входной/выходной информации ПО объясняет пользователю как представить, ввести входную информацию и как интерпретировать выходную информацию, в каком режиме (пакетном или интерактивном) работает система

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

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

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

Элементами СМО являются:

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

Входящий поток - это совокупность заявок на обслуживание. Часто заявка отождествляется с ее носителем. Например, поток неисправной радиоаппаратуры, поступающий в мастерскую объединения, представляет собой поток заявок - требований на обслуживание в данной СМО.

Как правило, на практике имеют дело с так называемыми рекуррентными потоками, - потоками, обладающими свойствами:

• стационарности;
• ординарности;
• ограниченного последействия.

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

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

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

здесь - интенсивность потока.

Название потока - пуассоновский - происходит от того, что для этого потока вероятность появления заявок за интервал определяется законом Пуассона:

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

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

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

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

Часто встречаются системы, у которых поток входных заявок зависит от количества заявок, находящихся в обслуживании. Такие СМО называют замкнутыми (иначе - разомкнутыми ). Например, работа мастерской связи объединения может быть представлена моделью замкнутой СМО. Пусть эта мастерская предназначена для обслуживания радиостанций, которых в объединении . Каждая из них имеет интенсивность отказов . Входной поток отказавшей аппаратуры будет иметь интенсивность :

где - количество радиостанций, уже находящихся в мастерской на ремонте.

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

Важной характеристикой входного потока является коэффициент вариации :

где - математическое ожидание длины интервала;

Среднеквадратическое отклонение случайной величины (длины интервала) .

Для простейшего потока

Для большинства реальных потоков .

При поток регулярный, детерминированный.

Коэффициент вариации - характеристика, отражающая степень неравномерности поступления заявок.

Каналы (приборы) обслуживания . В СМО могут быть один или несколько обслуживающих приборов (каналов). Согласно с этим СМО называют одноканальными или многоканальными.

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

• линии связи;
• мастера ремонтных органов;
• взлетно-посадочные полосы;
• транспортные средства;
• причалы;
• парикмахеры, продавцы и др.

Основная характеристика канала - время обслуживания. Как правило, время обслуживания - величина случайная.

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

где - интенсивность обслуживания, ;

Математическое ожидание времени обслуживания.

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

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

При исследовании СМО выпадает из рассмотрения сущность обслуживания, качество обслуживания .

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

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

• СМО с отказами;
• СМО с ожиданием.

СМО с ожиданием характеризуются наличием очередей. Очередь может иметь ограниченную или неограниченную емкость: .

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

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

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

Выходящий поток - это поток обслуженных заявок, покидающих СМО.

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

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

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

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

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

Рис.2. Классификация входного потока

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

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

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

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

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

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

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

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

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

(1.1)

где λ - интенсивность поступления заявок в систему.

Если интервалы распределены по экспоненциальному закону, то процесс пуассоновский. Такие процессы называются М-процессами (Марковскими).

Кроме закона Пуассона часто применяется закон распределения Эрланга.

(1.2)

СМО с отказами

Одноканальная СМО содержит один канал (n = 1), и на ее вход поступает пуассоновский поток заявок П вх интенсивность (среднее число событий в единицу времени) которого inП вх =λ. Так как интенсивность входящего потока может изменяться во времени, то вместо λ записывают λ (t). Тогда время обслуживания каналом одной заявки Т об распределено по показательному закону и записывается в виде: , где λ - интенсивность отказов.

Состояние СМО характеризуется простаиванием или занятостью ее канала, т.е. двумя состояниями: S 0 - канал свободен и простаивает, S 1 - канал занят. Переход системы из состояния S 0 в состояние S 1 осуществляется под воздействием входящего потока заявок П вх, а из состояния S 1 в состояние S 0 систему переводит поток обслуживании П об: если в данный момент времени система находится в некотором состоянии, то с наступлением первого после данного момента времени СМО переходит в другое состояние. Плотности вероятностей перехода из состояния S 0 в S 1 и обратно равны соответственно λ и µ. Граф состояний подобной СМО с двумя возможными состояниями приведен на рис.3.

Рис.3. Граф состояний одноканальной СМО с отказами.

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

Таким образом, подобная СМО может находиться в одном из следующих (n+1) состояний: s 0 - все n каналов свободны; s 1 - занят только один из каналов, остальные (n-1) каналов свободны; s i - заняты i - каналов, (n-i) каналов свободны; s n - заняты все n каналов. Граф состояний такой СМО приведен на рис.4.

Рис.4. Граф состояний многоканальной СМО с отказами.

При этом имеет место а

Пользуясь общим правилом составления дифференциальных уравнений Колмогорова, можно для приведенных на рис.2 и рис.3 графов состояний составить системы дифференциальных уравнений:

например, для одноканальной СМО (рис.2) имеем:

для многоканальной СМО (рис.3) соответственно имеем:

Решив первую систему уравнений, можно найти значения p 0 (t) и p 1 (t) для одноканальной СМО и построить графики при трех случаях:

СМО с ожиданием

Система массового обслуживания имеет один канал. Входящий поток заявок на обслуживание - простейший поток с интенсивностью λ. Интенсивность потока обслуживания равна µ (т.е. в среднем непрерывно занятый канал будет выдавать µ обслуженных заявок). Длительность обслуживания - случайная величина, подчиненная показательному закону распределения. Поток обслуживаний является простейшим пуассоновским потоком событий. Заявка, поступившая в момент, когда канал занят, становится в очередь и ожидает обслуживания.

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

Рис.6. Граф состояний одноканальной СМО с ожиданием

Состояния СМО имеют следующую интерпретацию:

S 0 - канал свободен;

S 1 - канал занят (очереди нет);

S 2 - канал занят (одна заявка стоит в очереди);

S n - канал занят (n-1 заявок стоит в очереди);

S N - канал занят (N-1 заявок стоит в очереди).

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

(1.11)

где ρ=λ/µ; n - номер состояния.

Решение приведенной выше системы уравнений (1.10) для нашей модели СМО имеет вид:

(1.12)

(1.13)

Следует отметить, что выполнение условия стационарности для данной СМО необязательно, поскольку число допускаемых в обслуживающую систему заявок контролируется путем введения ограничения на длину очереди (которая не может превышать N-1), а не соотношением между интенсивностями входного потока, т.е. не отношением λ/µ=ρ. Определим характеристики одноканальной СМО с ожиданием и ограниченной длиной очереди, равной (N-1): вероятность отказа в обслуживании заявки:

(1.14)

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

(1.15)

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

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

(1.17)

среднее время пребывания заявки в системе:

средняя продолжительность пребывания клиента (заявки) в очереди:

(1.19)

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

. (1.20) .

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

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

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

(1.32)

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

(1.31) .

Элементы теории массового обслуживания

§ 1. Введение

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

Основными характеристиками систем массового обслуживания являются следующие случайные величины:

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

доля времени, в течение которого система простаивает (из-за отсутствия клиентов).

Функциональные возможности систем массового обслуживания определяются следующими факторами:

распределение моментов распределения клиентов;

распределение продолжительности обслуживания;

конфигурация обслуживающей системы (последовательное, параллельное или параллельно-последовательное обслуживание);

дисциплина в очереди (обслуживание в порядке поступления, обслуживание в обратном порядке, случайный отбор клиентов);

вместимость блока ожидания (ограниченная или неограниченная);

емкость или мощность источника требования (ограниченная и неограниченная);

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

Основными факторами являются первые два.

Любая система массового обслуживания состоит из следующих основных элементов:

входной поток клиентов;

обслуживающий прибор;

дисциплина в очереди.

§ 2 . Входной поток клиентов

Рассмотрим последовательности случайных величин

Предположим, что t o = 0 – начальный момент функционирования системы; t 1 = t o + τ 1 , t 2 = t 1 + τ 2 , …, t k = t k -1 + τ k , …., где τ k – независимые случайные величины, имеющие показательное распределение с параметром λ.

Здесь t 1 – момент поступления первого клиента, τ 1 – промежуток времени между началом работы системы и моментов прихода первого клиента, τ 2 – промежуток времени между моментами прихода первого и второго клиентов, и т.д.

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

Свойства простейшего потока

1. Сдвиг потока на величину Т

Пусть имеется простейший поток
с параметром λ.

Сдвигая поток на величину Т , получаем поток
, который также будет являться простейшим потоком с тем же параметром λ. Например, если T находится между и , то новый поток выглядит так:

, ….

2. Слияние двух потоков

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

с
параметрами λ (1) , λ (2) соответственно. Будем говорить, что поток образовался в результате слияния двух потоков, если множество {t k } есть объединение множеств {t k (1) }, {t k ( 2) } и элементы множества {t k } упорядочены в порядке возрастания.

П
оток, получившийся в результате слияния двух независимых простейших потоков, является тоже простейшим потоком с параметром λ = λ (1) + λ (2) , где λ (j) – параметр потока

3. Разделение простейшего потока

Пусть имеется простейший поток с параметром λ,

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

P(ξ i = 1) = p , P(ξ i = 0) = q , p  0, q  0, p + q = 1.

Такие случайные величины называются бернуллиевскими (с параметром p ). Процедура разделения потока {t k } состоит в следующем: число t i отнесем к первому потоку, если ξ i = 1; если же ξ i = 0, то число t i отнесем ко второму потоку. Такую операцию разделения потока на два назовем бернуллиевской (с параметром p ).

Потоки, полученные в результате бернуллиевского разделения простейшего потока, являются независимыми простейшими потоками с параметрами λ (1) = λp, λ (2) = λq соответственно.

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

Ч
ерез X(t) в дальнейшем будем обозначать число клиентов в системе в момент t , т.е.

Свойства пуассоновских процессов

Приращение пуассоновского процесса однородное .

Обозначим через X ((a ,b ]) = X (b ) – X (a ) приращение процесса, которое может быть интерпретировано как число клиентов, поступающих в систему в промежутке (a ,b ]. Однородность означает выполнение условия:

P(X ((a ,b ]) = k) = P(X ((0,b -a ]) = k) = P(X (b -a ) = k),

т.е. распределение вероятностей числа клиентов, поступающих в систему в промежутке (a ,b ], зависит только от длины этого промежутка.

Приращения пуассоновского процесса независимы .

Рассмотрим промежуток (0, b ] и предположим, что он разбит на непересекающиеся промежутки (0, b 1 ], (b 1 , b 2 ], , (b N -1 , b N ]. Пусть b 0 = 0. Тогда X ((b 0 , b 1 ]), X ((b 1 , b 2 ]), , X ((b N -1 , b N ]) – число клиентов, поступающих в систему в соответствующие периоды времени. Эти величины независимы, т.е.

P(X ((b 0 , b 1 ]) = i 1 , , X ((b N -1 , b N ]) = i N) =

P(X ((b 0 , b 1 ]) = i 1)  P(X ((b N-1 , b N ]) = i N).

Доказательства этих свойств можно найти в .

Задачи к § 2.

2.1. Имеются две случайные величины  1 и  2 . Они независимые и имеют показательное распределение с параметрами  1 и  2 соответственно. Введем следующую случайную величину:  = min{ 1 ,  2 }. Доказать, что эта величина имеет показательное распределение с параметром = 1 + 2 .

2.2. Даны две независимые случайные величины  1 и  2 , имеющие пуассоновское распределение с параметром  1 и  2 соответственно. Пусть случайная величина  = 1 + 2 . Доказать, что эта величина имеет распределение Пуассона с параметром  = 1 + 2 .

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

2.4. Посетители приходят в ресторан в соответствии с пуассоновским потоком со средней частотой 20 посетителей в час. Ресторан открывается в 11.00.

а) вероятность того, что в 11.12 в ресторане окажется 20 посетителей при условии, что в 11.07 в ресторане было 18 посетителей;

б) вероятность того, что новый посетитель прибудет в ресторан в интервале между 11.28 и 11.30, если известно, что предыдущий посетитель прибыл в ресторан в 11.25.

2.5. Продукция берется со склада, вмещающего 80 единиц складируемой продукции, в соответствии с пуассоновским потоком с интенсивностью 5 единиц продукции вдень.

а) вероятность того, что в течении первых двух дней со склада будет взято 10 единиц продукции;

б) вероятность того, что к концу четвертого дня на складе не останется ни одной единицы продукции.

§

3. Процесс гибели и размножения

Построим процесс гибели и размножения X (t ) «конструктивно».

Рассмотрим две последовательности и. Первая - отвечает за поступление клиентов в систему (размножение), а вторая - за обслуживание клиентов (гибель):

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

Процесс X (t) строится так. Пусть
, где
. Тогда на интервале
процесс X (t) сохранит свое значение , где
,

.

В момент t 1 значение процесса X (t ) либо увеличится, либо уменьшится на единицу в соответствии с тем, какой из двух моментов
наступит раньше:

Мы положили, таким образом, значение процесса X (t) в точке t 1 равным ; тогда эволюция процесса X (t ) на интервале
, где
и
, подчиняется тому же закону закону: X (t ) не меняется на этом интервале в момент t 2

увеличивается на единицу, если
, и уменьшается на единицу в противном случае.

Если же
, то значение процесса X (t ) увеличивается на единицу в случайный момент
.

Построенный таким образом процесс
, называется однородным по времени процессом гибели и размножения; его распределения полностью определяются набором параметров, и начальным распределением X(0):

Удобно использовать следующую диаграмму для представления развития процесса X (t):

Стрелочки сверху соответствуют динамике процесса размножения: из i -го состояния процесс переходит в (i +1)-е состояние с интенсивностью ; стрелочки снизу соответсвуют динамике процесса гибели: с интенсивностью процесс из i -го состояния переходит в (i -1)-е состояние.

Набор функций

описывает распределение процесса X (t ); ниже мы приведем систему уравнений, которым удовлетворяют эти функции.

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

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

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

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

Пусть X (t ) процесс гибели и размножения с теми же параметрами процесса , а также параметрами
. Очевидно, что

P(X (t )  )  P(X + (t )  ) .

Поэтому из леммы получаем следствие.

Следствие . Если для произвольного процесса гибели размножения X(t) выполнено условие
, то для любого
справедливо P(X(t)  ) = 1, т.е. процесс конечен.

Доказательство леммы можно найти в .

Задачи к § 3

3.1. Рассмотрим процесс гибели и размножения, для которого

Требуется изобразить диаграмму, отвечающую этому процессу.

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

3.3. Пусть в условиях задачи 3.2

телефон имеет память на одного клиента: если клиент звонит и телефон занят, но память телефона свободна, то автомат предлагает положить трубку и ждать звонка. Когда телефон освободится, звонок прозвучит;

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

коммутатор (см п.2)) имеет память на одного клиента;

каждый телефон (см.п.2)) имеет память на одного клиента.

Для всех вышеперечисленных случаев изобразить диаграмму, отвечающему процессу X (t ).

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

а)  k =k  +  ,  >0,  >0, k = 0, 1, ...

б)  0 = 1,  k +1 = (k +1) k , k = 0, 1, ...

в)  k =  k , k = 0, 1, ...  > 0.

§ 4. Дифференциальные уравнения, отвечающие процессу гибели и размножения

Предположим, что X (t ) – процесс гибели и размножения с характеристиками и. Пусть для некоторых конечных чисел A и B имеют место неравенства  i  A + Bi , i = 0, 1, ...Это условие гарантирует конечность процесса X (t ). При этом мы условимся, что в каждое состояние приходит верхняя стрелочка слева (даже в состояние 0), при этом интенсивность рождения λ может равняться нулю (например, λ –1 = = 0); из каждого состояния выходит нижняя стрелочка влево, и интенсивность гибели μ тоже может равняться нулю (например, λ –1 = 0). Доопределение таким образом диаграммы не меняет суть дела, однако в дальнейших рассуждениях будет полезно. Рассмотрим диаграмму, отвечающую нашему процессу X (t ):

Обозначим, как и ранее, через

P k (t ) = P (Х (t ) = k ), k = 0,1,…,

вероятности того, что в фиксированный момент t число клиентов X (t ) будет равно k.

Теорема 1. Характеристики процесса X (t ), определенное выше, удовлетворяет следующей системе дифференциальных уравнений

где k = 0,1,…, и начальным условиям

Нелишне пояснить, что первая строка (при k = 0) системы уравнений (1) имеет вид

Доказательство. Обозначим через P k (t + Δ) = P (X (t + Δ) = k ).

Воспользуемся определением производной функции одной переменной:

.

Рассмотрим такие события:

A 0 (t , Δ) = {на отрезке [t , t +Δ] процесс X (t ) не совершил ни одного скачка};

A 1 (t , Δ) = {на отрезке [t , t +Δ] процесс X (t ) совершил ровно один скачок};

A 2 (t , Δ) = {на отрезке [t , t +Δ] процесс X (t ) совершил два скачка и более}.

Тогда очевидно, что

Обозначим далее через

; через
три показательные случайные величины с параметрами
. Пусть все эти величины независимы. Тогда верно Тогда очевидно, чтостационарном (установившемся) режиме. P k (t ) = P (в системе в момент t находится k клиентов).

Найдите решение системы дифференциальных уравнений, а также стационарные вероятности.

4.2. Для процессов гибели и размножения из задачи 3.3 выписать дифференциальные уравнения, связывающие вероятности P k (t ) = P (в системе в момент t находится k клиентов).

Найти стационарные вероятности.

24. Входящий поток требований

24.1 Структура СМО

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

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

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

где Т - среднее значение интервала между поступлением очередных требований.

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

Простейший поток обладает такими важными свойствами:

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

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

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

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

Практически любой поток требований, поступающий в систему обслуживания, является случайным процессом. Действительно, если мы примем t =0 за начальный момент, то во многих потоках (кроме того случая, когда требования поступают строго по расписанию) либо нельзя, либо довольно трудно точно предсказать момент поступления очередного требования, а также моменты поступления последующих требований. Например, нельзя точно указать моменты прихода клиентов в ателье, пациентов в больницу, поступления вызовов на АТС, оборудования в ремонтную мастерскую и т. д.

Следовательно, моменты поступления заявок, равно и интервалы между ними, есть, вообще говоря, независимые случайные величины. Тогда процесс поступления требований в систему массового обслуживания следуя рассматривать как вероятностный или случайный процесс. Обозначим такой процесс через Х(t ). Эта функция определяет число требований, поступивших в систему за промежуток времени . Для каждого фиксированного t функция Х(t ) есть случайная величина. Действительно, если выбрать промежутки времени даже одинаковой продолжительности, то в этом случае нельзя быть уверенным в том, что в каждый из этих промежутков поступит одно и то же число требований.

За промежуток времени может не поступить ни одной заявки, а может поступить 1, 2,... заявок. Но какой бы продолжительности промежутки времени мы не выбирали, число заявок будет только целым.

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

1. При всяком фиксированном t функция Х(t ), принимает целые неотрицательные значения 0, 1, 2,...,R,... и с возрастанием не убывает.

2. Число требований, поступивших за промежуток вре­мени , зависит от длины этого промежутка, т. е. от значе­ния t.

3. Реализации процесса представляют собой ступенчатые линии, чем-то непохожие одна на другую. Из теории случайных процессов известно, что процесс будет полностью определен с вероятностной точки зрения, если будут известны все его много­мерные законы распределения:

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

Стационарность (лучше однородность во времени);

Отсутствие последействия (марковость), иногда говорят об отсутствии памяти;

Ординарность.

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

Поток требований называется стационарным или однородным во времени, если вероятность поступления определенного количе­ства требований в течение определенного промежутка времени за­висит только от длины промежутка, а не от его временного положения (иначе говоря, не зависит от начала отсчета). Таким обра­зом, для стационарного потока вероятность того, что за промежу­ток поступит ровно R требований, равна вероятности поступле­ния R требований за промежуток [а, а + t ] , где а>0 , т. е.

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

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

В некоторых потоках число требований, поступивших в систему после произвольного момента времени, не зависит от числа ранее поступивших требований и моментов их поступления, т. е. интер­валы между поступлениями требований считаются независимыми величинами и между ними нет связи. Будущее состояние системы не зависит от прошлого ее состояния. Поток, обладающий таким свойством, называют потоком без последействия или марковским. Свойство отсутствия последействия (отсутствия памяти) присуще многим реальным потокам. Например, поток вызовов на АТС является потоком без последействия, поскольку, как правило, оче­редной вызов поступает независимо от того, когда и сколько было вызовов до этого момента.

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

Если Р R >2 (h ) -вероятность появления за промежуток h более одного требования, то для ординарного потока должно быть:

,

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

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

Случайный процесс X (t ) (0≤ t <∞) целочисленными значениями называется процессом Пуассона, если он является процессом с независимыми приращениями или если любое приращение процесса за промежуток времени h распределено по закону Пуассона с параметром λ h , где λ>0 т.е.

В частности, если t =0, X(0)=0 , то (3) переписывается сле­дующим образом:

(4)

Здесь V r (h) означает вероятность того, что интересующее нас событие произойдет ровно R раз за промежуток времени h (с точки зрения теории массового обслуживания V r (h) опреде­ляет вероятность того, что за промежуток времени h в систему обслуживания поступит ровно R требований).

Смысл параметра X легко выяснить, если найти математиче­ское ожидание пуассоновского процесса: М [Х(t )]=М. При t = 1 получаем М[Х(1)]=1. Следовательно, есть среднее число заявок за единицу времени. Поэтому величину λ часто называют интенсивностью или плотностью потока.

Из определения процесса Пуассона немедленно вытекают три свойства, идентичные указанным выше:

1) Независимость приращений. В независимости приращений для процесса Пуассона заключается отсутствие последействия- марковость процесса.

2) Однородность во времени. Это означает, что вероятности V r (h) не зависят от начального момента t рассматриваемого промежутка , а зависят только от длины промежутка h :

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

Итак, одновременное поступление двух и более требований за малый промежуток времени h маловероятно, поэтому

что указывает на ординарность процесса Пуассона.

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