Марковские случайные процессы

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

Марковский процесс - дискретный или непрерывный случайный процесс X (t ), который можно полностью задать с помощью двух величин:

· вероятности P (x ,t ) того, что случайная величина x (t ) в момент времени t равна x , и

· вероятности P (x 2 , t 2 |x 1 ,t 1) того, что если x при t = t 1 равен x 1 , то при t = t 2 он равен x 2 .

Вторая из этих величин называется вероятностью перехода из состояния x 1 при t = t 1 в состояние x 2 при t = t 2 .

Цепями Маркова называют дискретные по времени и значению Марковские

процессы.

Пример 1

Предположим, что речь идет о последовательных бросаниях монеты при игре "в орлянку "; монета бросается в условные моменты времени t = 0, 1, ... и на каждом шаге игрок может выиграть ±1 с одинаковой вероятностью 1/2, таким образом в момент t его суммарный выигрыш есть случайная величина ξ(t) с возможными значениями j = 0, ±1, ... При условии, что ξ(t) = k, на следующем шаге выигрыш будет уже равен ξ(t+1) = k ± 1, принимая указанные знчения j = k ± 1 c одинаковой вероятностью 1/2. Условно можно сказать, что здесь с соответствующей вероятностью происходит переход из состояния ξ(t) = k в состояние ξ(t+1) = k ± 1.

19.5.1. Формулы и определения Марковских цепей

Обобщая этот пример, можно представить себе "систему" со счетным числом возможных "фазовых" состояний, которая с течением дискретного времени t = 0, 1, ... случайно переходит из состояния в состояние.

Пусть ξ(t) есть ее положение в момент t в результате цепочки случайных переходов ξ(0) - ξ(1) - ... - ξ(t) - ... ... (1)

Формально обозначим все возможные состояния целыми i = 0, ±1, ... Предположим, что при известном состоянии ξ(t) = k на следующем шаге система переходит в состояние ξ(t+1) = j с условной вероятностью

p kj = P(ξ(t+1) = j|ξ(t) = k) ... (2)

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

P(ξ(t+1) = j|ξ(0) = i, ..., ξ(t) = k) = P(ξ(t+1) = j|ξ(t) = k) при всех t, k, j ... (3) - марковское свойство.

Такую вероятностную схему называют однородной цепью Маркова со счетным числом состояний - ее однородность состоит в том, что определенные в (2) переходные вероятности p kj , ∑ j p kj = 1, k = 0, ±1, ..., не зависят от времени, т.е.

P(ξ(t+1) = j|ξ(t) = k) = P ij - матрица вероятностей перехода за один шаг не зависит от n. Ясно, что P ij - квадратная матрица с неотрицатель-ными элементами и единичными суммами по строкам. Такая матрица (конечная или бесконечная) называется стохастической матрицей. Любая стохастическая матрица может служить матрицей переходных вероятностей.

Практический пример 1.

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

1) после осуществления доставки в А следующая доставка в 30 случаях осуществляется в А, в 30 случаях - в В и в 40 случаях - в С;

2) после осуществления доставки в В следующая доставка в 40 случаях осуществляется в А, в 40 случаях - в В и в 20 случаях - в С;

3) после осуществления доставки в С следующая доставка в 50 случаях осуществляется в А, в 30 случаях - в В и в 20 случаях - в С.

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

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

Например, р 12 = 0.4 - это вероятность того, что после доставки в район В следующая доставка будет производиться в районе А. Допустим, что каждая доставка с последующим перемещением в следующий район занимает 15 минут. Тогда, в соответствии со статистическими данными, через 15 минут 30% из курьеров, находившихся в А, будут в А, 30% будут в В и 40% - в С. Так как в следующий момент времени каждый из курьеров обязательно будет в одном из округов, то сумма по столбцам равна 1. И поскольку мы имеем дело с вероятностями, каждый элемент матрицы 0<р ij <1. Наиболее важным обстоятельством, которое позволяет интерпретировать данную модель как цепь Маркова, является то, что местонахождение курьера в момент времени t+1 зависит только от местонахождения в момент времени t.

Теперь зададим простой вопрос: если курьер стартует из С, какова вероятность того, что осуществив две доставки, он будет в В, т.е. как можно достичь В в 2 шага? Итак, существует несколько путей з С в В за 2 шага:

1) сначала из С в С и потом из С в В;

2) С-->B и B-->B;

3) С-->A и A-->B.

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

P = P(CA)*P(AB) + P(CB)*P(BB) + P(CC)*P(CB)

Подставляя числовые значения:

P = 0.5*0.3 + 0.3*0.4 + 0.2*0.3 = 0.33

Полученный результат говорит о том, что если курьер начал работу из С, то в 33 случаях из 100 он будет в В через две доставки. Ясно, что вычисления просты, но если Вам необходимо определить вероятность через 5 или 15 доставок - это может занять довольно много времени.

Рассмотрим более простой способ вычисления подобных вероятностей. Для того, чтобы получить вероятности перехода из различных состояний за 2 шага, возведем матрицу P в квадрат:

Тогда элемент (2, 3) - это вероятность перехода из С в В за 2 шага, которая была получена выше другим способом. Заметим, что элементы в матрице P 2 также находятся в пределах от 0 до 1, и сумма по столбцам равна 1.

Т.о. если Вам необходимо определить вероятности перехода из С в В за 3 шага:

1 способ. p(CA)*P(AB) + p(CB)*P(BB) + p(CC)*P(CB) = 0.37*0.3 + 0.33*0.4 + 0.3*0.3 = 0.333, где p(CA) - вероятность перехода из С в А за 2 шага (т.е. это элемент (1, 3) матрицы P 2).

2 способ. Вычислить матрицу P 3:

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

Легко заметить, что элементы каждой строки стремятся к некоторым числам. Это говорит о том, что после достаточно большого количества доставок уж не имеет значение в каком округе курьер начал работу. Т.о. в конце недели приблизительно 38,9% будут в А, 33,3% будут в В и 27,8% будут в С. Подобная сходимость гарантировано имеет место, если все элементы матрицы переходных вероятностей принадлежат интервалу (0, 1).

Теория массового обслуживания

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

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

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

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

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

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

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

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

Для простейшего потока частота поступлений требований в сис­тему подчиняется закону Пуассона, т.е. вероятность поступления за время t ровно к требований задается формулой:

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

1) ординарностью,

2) стационарностью и

3) отсутствием после­действия.

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

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

Отсутствие последействия означает, что число требований, по­ступивших в систему до момента t, не определяет того, сколько требований поступит в систему за промежуток времени от t до t + Dt

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

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

т.е. вероятность того, что время обслуживания не превзойдет неко­торой величины t, определяется формулой (5.2), где µ - параметр экспоненциального закона распределения времени обслуживания требований в системе, т.е. величина, обратная среднему времени обслуживания

Системы массового обслуживания классифицируются:

1. В зависимости от условий ожидания начала обслуживания:

· СМО с потерями (отказами)

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

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

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

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

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

2. По числу каналов обслуживания СМО делятся на:

Одноканальные;

Многоканальные.

3. По месту нахождения источника тре­бований СМО подразделяются на:

разомкнутые, когда источник требования находится вне сис­темы;

замкнутые, когда источник находится в самой системе.

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

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

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

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

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

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

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

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

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

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

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

1. Вероятность того, что все обслуживающие каналы свободны,

(5.14)

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

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

(5.16)

4. Вероятность того, что все обслуживающие каналы заняты,

(5.17)

5. Вероятность отказа

(5.18)

6. Средняя длина очереди

7. Среднее число свободных от обслуживания каналов

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

Требуется определить характеристики работы фирмы.

Решение. Данная система относится к типу СМО с ожида­нием и ограниченной длиной очереди. Найдем параметры системы, приняв за единицу времени один час:

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

Вероятность того, что в се машины заняты, определяется по формуле (5.17) и составляет

Тогда вероятность отказа в принятии заказа на перевозку, рассчитываемая по формуле (5.18) будет равна

, а средняя длина очереди в соответствии с формулой (5.19) составит

Тогда вероятность отказа в принятии заказа на перевозку, рас­считываемая по формуле (5.18), будет равна

а средняя длина очереди в соответствии с формулой (5.19) составит

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

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

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

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

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

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

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

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

(Теория очередей)

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

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

1.1 Компоненты и классификация моделей массового обслуживания

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

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

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

Примерами систем массового обслуживания могут служить:

· магазины;

· ремонтные мастерские;

· почтовые отделения;

· посты технического обслуживания автомобилей, посты ремонта автомобилей;

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

· аудиторские фирмы;

· отделы налоговых инспекций, занимающиеся приемкой и проверкой текущей отчетности предприятий;

· телефонные станции и т.д.

Основными компонентами системы массового обслуживания любого вида являются:

· входной поток поступающих требований или заявок на обслуживание;

· дисциплина очереди;

· механизм обслуживания.

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

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

Первым пришел - первый обслуживаешься;

Пришел последним - обслуживаешься первым;

Случайный отбор заявок;

Отбор заявок по критерию приоритетности;

Ограничение времени ожидания момента наступления обслужи вания (имеет место очередь с ограниченным временем ожидания обслуживания, что ассоциируется с понятием «допустимая дли на очереди»).

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

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

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

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

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

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

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

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

· количеством и производительностью обслуживающих каналов;

· дисциплиной очереди;

· мощностью источника требований.

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

· вероятность немедленного обслуживания поступившей заявки;

· вероятность отказа в обслуживании поступившей заявки;

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

· средний процент заявок, получивших отказ в обслуживании;

· среднее время ожидания в очереди;

· средняя длина очереди;

· средний доход от функционирования системы в единицу времени и т.п.

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

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

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

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

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

В системах с ограниченным ожиданием может ограничиваться:

Длина очереди;

Время пребывания в очереди.

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

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

Одноканальные системы;

Многоканальные системы.

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

Определим характеристики систем массового обслуживания.

1.2. Одноканальная СМО с отказами

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

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

где – интенсивность обслуживания, tоб – среднее время обслуживания одного клиента.

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

Абсолютная пропускная способность (А) - среднее число заявок, которое может обслужить система массового обслуживания в единицу времени: Вероятность отказа в обслуживании заявки будет равна вероятности состояния «канал обслуживания занят»:

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

Пример. Пусть одноканальная СМО с отказами представляет собой один пост ежедневного обслуживания для мойки автомобилей. Заявка - автомобиль, прибывший в момент, когда пост занят, - получает отказ в обслуживании. Интенсивность потока автомобилей λ 1,0 (автомобиль в час). Средняя продолжительность обслуживания - tоб=1,8 часа.

Требуется определить в установившемся режиме предельные значения:

a) относительной пропускной способности q;

b) абсолютной пропускной способности А;

c) вероятности отказа Ротк;

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

Определим интенсивность потока обслуживания: Вычислим относительную пропускную способность: Величина q означает, что в установившемся режиме система будет обслуживать примерно 35% прибывающих на пост автомобилей.

Абсолютную пропускную способность определим по формуле: А=λ×q=1×0,356=0,356.

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

Вероятность отказа:

Ротк=1-q=1-0,356=0,644.

Это означает, что около 65% прибывших автомобилей на пост ЕО получат отказ в обслуживании.

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

Аном= (автомобилей в час). Оказывается, что Аном в раза больше, чем фактическая пропускная способность, вычисленная с учетом случайного характера потока заявок и времени обслуживания.

1.3 . Одноканальная СМО с ожиданием и ограниченной очередью

Рассмотрим теперь одноканальную СМО с ожиданием.

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

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

Обозначим Рn - вероятность того, что в системе находится n заявок. Эта величина вычисляется по формуле:

Здесь - приведенная интенсивность потока. Тогда вероятность того, что канал обслуживания свободен и в системе нет ни одного клиента, равна: .

С учетом этого можно обозначить

Определим характеристики одноканальной СМО с ожиданием и ограниченной длиной очереди, равной (N-1):

· вероятность отказа в обслуживании заявки: Pотк=РN=

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

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

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

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

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

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

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

Пример. Специализированный пост диагностики представляет собой одноканальную СМО. Число стоянок для автомобилей, ожидающих проведения диагностики, ограниченно и равно 3, то есть (N- 1)=3. Если все стоянки заняты, т. е. в очереди уже находится три автомобиля, то очередной автомобиль, прибывший на диагностику, в очередь на обслуживание не становится. Поток автомобилей, прибывающих на диагностику имеет интенсивность λ=0,85 (автомобиля в час). Время диагностики автомобиля распределено по показательному закону и в среднем равно =1,05 час.

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

Интенсивность потока обслуживаний автомобилей:

Приведенная интенсивность потока автомобилей определяется как отношение интенсивностей λ и μ, т.е.

Вычислим вероятности нахождения п заявок в системе:

P1=r∙P0=0,893∙0,248=0,221;

P2=r2∙P0=0,8932∙0,248=0,198;

P3=r3∙P0=0,8933∙0,248=0,177;

P4=r4∙P0=0,8934∙0,248=0,158.

Вероятность отказа в обслуживании автомобиля:

Pотк=Р4=r4∙P0≈0,158.

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

q=1–Pотк=1-0,158=0,842.

Абсолютная пропускная способность поста диагностики

А=λ∙q=0,85∙0,842=0,716 (автомобиля в час).

Среднее число автомобилей, находящихся на обслуживании и в очереди (т.е. в системе массового обслуживания):

Среднее время пребывания автомобиля в системе:

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

Wq=Ws-1/μ=2,473-1/0,952=1,423 часа.

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

Lq=λ∙(1-PN)∙Wq=0,85∙(1-0,158)∙1,423=1,02.

Работу рассмотренного поста диагностики можно считать удовлетворительной, так как пост диагностики не обнаруживает автомобили в среднем в 15,8% случаев (Ротк=0,158).

1.4. Одноканальная СМО с ожиданием и неограниченной очередью

Перейдем теперь к рассмотрению одноканальной СМО с ожиданием без ограничения на вместимость блока ожидания (т.е. Ν → ∞). Остальные условия функционирования СМО остаются без изменений.

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

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

Pn=(1-r)rn, n=0,1,2,…,

где r = λ/μ <1.

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

среднее число находящихся в системе клиентов (заявок) на обслуживание:

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

среднее число клиентов в очереди на обслуживание:

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

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

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

вероятности состояний системы (поста диагностики);

среднее число автомобилей, находящихся в системе (на обслуживании и в очереди);

среднюю продолжительность пребывания автомобиля в системе

(на обслуживании и в очереди);

среднее число автомобилей в очереди на обслуживании;

среднюю продолжительность пребывания автомобиля в очереди.

Решение. Параметр потока обслуживания и приведенная интенсивность потока автомобилей ρ определены в предыдущем примере:

μ=0,952; ρ=0,893.

Вычислим предельные вероятности системы по формулам

P0=1-r=1-0,893=0,107;

P1=(1-r)·r=(1-0,893)·0,893=0,096;

P2=(1-r)·r2=(1-0,893)·0,8932=0,085;

P3=(1-r)·r3=(1-0,893)·0,8933=0,076;

P4=(1-r)·r4=(1-0,893)·0,8934=0,068;

P5=(1-r)·r5=(1-0,893)·0,8935=0,061 и т.д.

Следует отметить, что Р0 определяет долю времени, в течение которого пост диагностики вынужденно бездействует (простаивает). В нашем примере она составляет 10, 7%, так как Р0=0,107.

Среднее число автомобилей, находящихся в системе (на обслуживании и в очереди):

ед.

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

Среднее число автомобилей в очереди на обслуживание:

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

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

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

A=λ∙q=0,85∙1=0,85.

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

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

В нашем примере при N=3+1=4 и r=0,893,

m=λ∙P0∙ r4=0,85∙0,248∙0,8934=0,134 автомобиля в час.

При 12-часовом режиме работы поста диагностики это эквивалентно тому, что пост диагностики в среднем за смену (день) будет терять 12∙0,134=1,6 автомобиля.

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

1.5. Многоканальная СМО с отказами

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

Процесс массового обслуживания, описываемый данной моделью, характеризуется интенсивностью входного потока λ, при этом параллельно может обслуживаться не более n клиентов (заявок). Средняя продолжительность обслуживания одной заявки равняется 1/μ. Режим функционирования того или иного обслуживающего канала не влияет на режим функционирования других обслуживающих каналов системы, при чем длительность процедуры обслуживания каждым из каналов является случайной величиной, починенной экспоненциальному закону распределения. Конечная цель использования параллельно включенных обслуживающих каналов заключается в повышение (по сравнению с одноканальной системой) скорости обслуживания требований за счет обслуживания одновременно n клиентов.

Стационарное решение системы имеет вид:

,где ,

Формулы для вычисления вероятностей называются формулами Эрланга.

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

вероятность отказа:

ак как заявка получает отказ, если приходит в момент, когда все каналов заняты. Величина Ротк характеризует полноту обслуживания входящего потока;

вероятность того, что заявка будет принята к обслуживанию (она же – относительная пропускная способность системы) дополняет Ротк до единицы:

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

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

Величина характеризует степень загрузки СМО.

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

Требуется вычислить значения:

Вероятности числа занятых каналов ВЦ;

Вероятности отказа в обслуживании заявки;

Относительной пропускной способности ВЦ;

Абсолютной пропускной способности ВЦ;

Среднего числа занятых ПЭВМ на ВЦ.

Определите, сколько дополнительно надо приобрести ПЭВМ, чтобы увеличить пропускную способность ВЦ в 2 раза.

Определим параметр μ потока обслуживаний:

Предельные вероятности состояний найдем по формулам Эрланга:

Вероятность отказа в обслуживании заявки

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

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

Среднее число занятых каналов – ПЭВМ

Таким образом, при установившемся режиме работы СМО в среднем будет занято 1,5 компьютера из трех – остальные полтора будут простаивать. Работу рассмотренного ВЦ вряд ли можно считать удовлетворительной, так как центр не обслуживает заявки в среднем в 18% случаев (Р3= 0,180). Очевидно, что пропускную способность ВЦ при данных λ и μ можно увеличить только за счет увеличения числа ПЭВМ.

Определим, сколько нужно использовать ПЭВМ, чтобы сократить число не обслуженных заявок, поступающих на ВЦ, в 10 раз, т.е. чтобы вероятность отказа в решении задач не превосходила 0,0180. Для этого используем формулу вероятности отказа:

Составим следующую таблицу:

n
P0	0,357	0,226	0,186	0,172	0,167
Pотк	0,673	0,367	0,18	0,075	0,026

Анализируя данные таблицы, следует отметить, что расширение числа каналов ВЦ при данных значениях λ и μ до 6 единиц ПЭВМ позволит обеспечить удовлетворение заявок на решение задач на 99,22%, так как при n = 6 вероятность отказа в обслуживании (Ротк) составляет 0,0078.

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

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

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

Решение будет действительным, если выполняется следующее условие:

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

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

;

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

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

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

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

Пример. Механическая мастерская завода с тремя постами (каналами) выполняет ремонт малой механизации. Поток неисправных механизмов, прибывающих в мастерскую, - пуассоновский и имеет интенсивность λ=2,5 механизма в сутки, среднее время ремонта одного механизма распределено по показательному закону и равно tоб=0,5 сут. Предположим, что другой мастерской на заводе нет, и, значит, очередь механизмов перед мастерской может расти практически неограниченно.

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

Вероятность состояний системы;

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

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

Среднюю продолжительность пребывания заявки в очереди;

Среднюю продолжительность пребывания заявки в системе.

Определим параметр потока обслуживаний

Приведенная интенсивность потока заявок

ρ=λ/μ=2,5/2,0=1,25,

при этом λ/μ ∙с=2,5/2∙3=0,41<1.

Поскольку λ/μ∙с<1, то очередь не растет безгранично и в системе наступает предельный стационарный режим работы.

Вычислим вероятности состояний системы:

Вероятность отсутствия очереди у мастерской

Ротк≈Р0+Р1+Р2+Р3≈0,279+0,394+0,218+0,091=0,937.

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

Ls=Lq+ =0,111+1,25=1,361.

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

Средняя продолжительность пребывания механизма в мастерской (в системе)

суток.

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

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

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

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

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

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

Рассмотрим следующий пример.

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

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

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

Если абстрагироваться от реального наполнения моделей СМО (мастерская, аптека, АТС, лифты в доме и т. д.), СМО можно описать, задавая следующие ее составляющие (рис. 9.1):

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

2.Дисциплину очереди.

3.Механизм обслуживания.

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

Рис. 9.1. Модель теории массового обслуживания

В некоторых системах «очередь» отсутствует.

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

Приоритет может быть абсолютным или относительным.

СМО могут быть открытыми и закрытыми. В первой - поток заявок не зависит от состояния самой СМО (сколько каналов занято), во

второй - зависит. Пример - наладка группы станков одним рабочим. Здесь интенсивность «требований» со стороны станков зависит от того, сколько их уже неисправно.

Классификация СМО не ограничивается приведенными разновидностями.

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

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

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

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

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

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

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

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

ний, поступивших в систему за, не зависит от того, сколько требований поступило за промежуток.

Другими словами, прошлое не влияет на настоящее! По сути, это означает, что требования, образующие поток, появляются в те или иные моменты времени независимо друг от друга (как, например, поток пассажиров, входящих в метро).

Пусть случайная величинаобозначает число требований на интервале .

Поток называется ординарным, если

Заметим, что

где

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

Поток требований называется простейшим, если он стационарен, ординарен и не имеет последействия. Потоки такого типа часто встречаются на практике. Термин «простейший» связан с простым математическим описанием этих потоков.

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

Стационарность и отсутствие последействия налицо, ординарность (т. е. условие (9.1)) вытекает из равенства

которое можно проверить по правилу Лопиталя.

Параметр X здесь характеризует интенсивность потока. Действительно,

Простейший поток еще называют стационарным пуассоновским.

Пример 1. Рассмотрим наладку станков одним рабочим. Предполагается, что все станки находятся приблизительно в одинаковом состоянии (последнее обеспечивает стационарность потока поломок). Вероятность поломки одного станка невелика (двух, трех и т. д. - тем более) - отсюда следует ординарность. Кроме того, если станков много, а среднее время ремонта мало, то можно считать, что поток поломок не имеет последействия. Другими словами, он является простейшим.

Решение. Пусть интенсивностьполомки/ч. По формуле (9.2)

прии t =1 найдем вероятность k поломок в течение часа

Составим табл. 9.1. Таблица 9.1

k

....

p k (1)

0,05

0,15

0,22

0,22

0,17

0,05

....

Следующее важное понятие ТМО - это время обслуживания.

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

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

Параметр(аналогично параметрувходящего потока) определяет интенсивность обслуживания; величина является средним временем обслуживания t одной заявки:

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

Далее коротко опишем я-канальную систему массового обслуживания с отказами. Это «классическая» задача ТМО, возникшая из практических нужд телефонии и решенная в начале ХХ века датским математиком Эрлангом. Задача ставится так.

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

ленно приступает к обслуживанию. В противном случае заявка получает отказ и покидает систему.

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

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

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

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

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

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

. - вероятность того, что занято ровно k каналов, и, в частности, Р 0 - вероятность простоя системы;

. - коэффициент занятости каналов в процентах (%);

.
- коэффициент простоя каналов

в процентах (%). Обозначим

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

а вероятностиприимеют вид

Формулы (9.6), (9.7) для вероятностей Р к называются формулами Эрланга - в честь основателя ТМО. С их помощью можно вычислить остальные интересующие нас характеристики СМО. Так, вероятность Действительно, для того чтобы пришедшая заявка получила отказ, необходимо, чтобы все я каналов были заняты. Итак,

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

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

Среднее число занятых каналовпо определению математического ожидания с учетом формул (9.6) и (9.7) равно

Отметим, что, зная вероятность отказав обслуживании

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

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

Отсюда заключаем, что на АТС в среднем занято 2 линии из 5, каждая линия загружена всего на 39 %, теряется приблизительно 4 вызова из 100. Таким образом, АТС работает не слишком эффективно, и вполне можно сократить общее число линий и (или) увеличить интенсивность потока заявок.

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

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

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

Таким образом, загрузка каждого из двух оставшихся продавцов немного вырастет (с 0,53 до 1/2 . 1,2 = 0,6 рабочего дня), зато «коэффициент полезного действия» аптеки упадет с 0,79 до 0,6, поскольку в сложившейся ситуации будет обслужено лишь 60 % ((1 - 0,4) . 100 %) потенциальных клиентов, а не 79 % как ранее при трех продавцах.

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

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

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

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

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

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

Основными элементами СМО являются:

Входящий поток заявок (требований) на обслуживание;

Очередь заявок на обслуживание;

Приборы (каналы) обслуживания;

Выходящий поток обслуженных заявок (рисунок 8.5).

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

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

Рисунок 8.5 - Обобщенная схема СМО

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

Каковы вероят­ность появления задержки или очереди и ее величина? Сколько време­ни требование находится в очереди и каким образом минимизировать его задержку?

Какова вероятность потери требования (клиента)?

Ка­кова должна быть оптимальная загрузка обслуживающих каналов? При каких параметрах системы достигаются минимальные потери прибы­ли?

К этому перечню можно добавить еще целый ряд задач.

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

Часто входной поток заявок представляется в виде про­стейшего потока, обладающего свойством стационарности, от­сутствия последствия и ординарности.

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

Для простейшего потока поступление заявок в СМО описы­вается законом распределения Пуассона

Р к (τ ) ,

где Р к (τ ) -вероятность поступления к заявок за время τ ;

λ - интенсивность входного потока.

Важное для исследования свойство, которым обладает пуассоновский поток, заключается в том, что процедура разделения и объединения дает снова пуассоновские потоки. Тогда, если входной по­ток формируется из N независимых источников, каждый из которых порождает пуассоновский поток интенсивностью λ i (i = 1, 2, ..., N), то его интенсивность будет определяться по формуле

λ = λ l + λ 2 +...+ λ N .

В случае разделения пуассоновского потока на N независимых по­токов получим, что интенсивность потока λ i будет равна r i λ ,где r i - доля i-го потока во входном потоке требований.

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

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

1. СМО с отказами - формирование очереди не разрешено, поэтому заявка, пришедшая в момент, когда все каналы заняты, получает отказ и теряется. Пример: АТС (выполнение заказов к определенному сроку), система ПВО объекта (цель в зоне об­стрела пребывает мало времени).

2. СМО с неограниченным ожиданием - поступившая заяв­ка, застав все обслуживающие приборы занятыми, становится в очередь и дожидается обслуживания. Число мест для ожидания (длина очереди) не ограничено. Не ограничивается и время ожидания. Пример: предприятия бытового обслуживания, такие как мастерские по ремонту часов, обуви.

3. СМО смешанного типа. В этих системах имеется очередь,
на которую накладываются ограничения. Например: на макси­мальную длину очереди (I тип – с ограниченной ДО) или на время ожидания заявки в очереди (П тип – с ограниченным ВО). Примерами СМО I-го типа являются мастер­ские по ремонту радиоаппаратуры с ограниченными площадями для ее хранения. Торговые точки по продаже фруктов, овощей, которые могут храниться ограниченное время, являются смешан­ными СМО II -го типа.

Порядок поступления заявок на обслужива­ние называется дисциплиной обслуживания.

В СМО с очередью могут быть следующие варианты дисцип­лины обслуживания:

а) в порядке поступления заявок (первым пришел – первым обслужился) - магазины, предприятия бытового обслуживания;

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

в) в соответствии с приоритетом (участники ВОВ в поликлинике);

г) в случайном порядке (в системе ПВО объекта при отра­жении воздушного налета противника).

Основным параметром процесса обслужи­вания считается время обслуживания заявки каналом (обслуживающим прибором j) – t j (j=1,2,…,m).

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

F(t) = l – e - μt ,

где m - положительный параметр, определяющий интенсивность обслужи­вания требований;

где Е (t) - математическое ожидание случайной величины обслуживания тре­бования t j .

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

Если СМО состоит из неоднородных каналов, то , если
же все каналы однородные, то .

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

Одноканальные;

Многоканальные.

Структура СМО и характерис­тика ее элементов приведены на рисунке 8.6.

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

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

Рисунок 8.6 – Структура и характеристика элементов СМО

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

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

среднее время ожидания в очереди,

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

среднее время пребывания в СМО и др.

В качестве критерия оптимизации применяют:

Максимум прибыли от эксплуатации СМО;

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

Обеспечение заданной пропускной способности.

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

Вопросы для самопроверки

1. Понятие о математических моделях и моделировании.

2. Что представляет собой экономико-статистическая модель и производственная функция?

3. Применение графических и графоаналитических моделей в управлении.

4. Использование корреляционного анализа для выявления связи между параметрами

5. Виды и методы построения регрессионных моделей.

6. Статистическое исследование причинно-следственных связей.

7. Классификация математических моделей по четырем аспектам детализации (по В.А. Кардашу).

8. Классификация моделей по применяемому математическому аппарату. Понятие о балансовых моделях.

9. Этапы моделирования. Проверка модели на адекватность.

10. Понятие о системах массового обслуживания (СМО). Составные части СМО.

11. СМО с отказами и с очередью. Разновидности очередей.

12. Одноканальные и многоканальные СМО. Дисциплины обслуживания

13. Моделирование СМО. Показатели, получаемые при экспериментах на модели СМО.

14. Критерии оптимизации систем массового обслуживания.