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

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

Марковский процесс - дискретный или непрерывный случайный процесс 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. Вероятность того, что занято к обслуживающих каналов при условии, что число требований, находящихся в системе, не превосходит числа обслуживающих каналов системы,

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

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

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

, .

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

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

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

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

5.10. Задача: Марковская модель рождения и гибели

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

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

Постановка задачи синтеза модели.

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

, , (5.79)

где - вероятности перехода.

Уравнение (5.79) справедливо также и для безусловных вероятностей состояний

. (5.80)

Рассмотрим дискретную последовательность процесс , в которой допускаются как положительные, так и отрицательные скачки. Эта последовательность называется процессом рождения и гибели и определяется следующими постулатами: 1) если в момент времени система находится в состоянии , то вероятность перехода в малом интервале времени равна ; 2) если в момент времени система находится в состоянии , то вероятность перехода в интервале времени равна ; 3) вероятность перехода в состояние, отличное от двух соседних, есть ; 4) вероятность сохранения прежнего состояния равна
; 5) состояние является поглощающим; если изображающая точка попала в это состояние, то процесс прекращается.

Решение . На основании постулатов 1-5 записываем уравнение (5.80):

, (5.81)

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

. (5.82)

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

(5.83)

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

, , (5.84)

где , . (5.85)

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

Всякая СМО включает 4 элемента:

1) источник требований (ИТ);

2) входящий поток требований;

3) система обслуживания, которая включает в себя:

· очередь,

· обслуживающее устройство (каналы обслуживания);

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

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

К основным характеристикам СМО относятся:

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

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

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

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

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

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

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

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

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

· СМО с отказами (потерями) – требования получившие отказ (каналы заняты) теряются;

· СМО с ожиданием - требования становятся в очередь и ожидают обслуживания, такие СМО делятся на:

o СМО с ограниченной длиной очереди;

o СМО с неограниченной длиной очереди;

o СМО с ограниченным временем ожидания.

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

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

· многоканальные.

3. По месту нахождения источника требования (ИТ) СМО делятся на два вида:

· разомкнутые – ИТ вне системы;

· замкнутые – ИТ в составе системы.

4. По дисциплине обслуживания (в зависимости от порядка выбора заявок на обслуживание) выделяют:

· СМО с приоритетом – вначале обслуживаются заявки с более высоким приоритетом;

· СМО без приоритета – приоритет в обслуживании заявок отсутствует.

Методы и модели исследования СМО можно разделить на

· аналитические;

· статистические.

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

Простейший поток требований

В настоящее время достаточно хорошо разработана ТМО применительно к простейшему (Пуассоновскому) потоку заявок на обслуживание.

Для простейшего потока частота поступления требований в систему подчиняется закону Пуассона, то есть вероятность поступления за время t ровно k требований задается формулой , где λ – параметр потока (число требований, поступающих в единицу времени).

Основные свойства простейшего потока:

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

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

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

Время обслуживания требований в системе

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

Наиболее часто рассматривается как случайная величина (СВ), которая подчиняется экспоненциальному закону распределения.

Для этого закона функция распределения вероятности имеет вид: , т.е. вероятность того, что время обслуживания не превосходит некоторой величины t , определяется формулой , где μ – параметр экспоненциального закона распределения времени обслуживания требований в системе – т.е. величина, обратная среднему времени обслуживания одного требования , т.е. .

Теория массового обслуживания представляет собой область прикладной математики, использующую методы теории случайных процессов и теории вероятностей для исследования различной природы сложных систем. Теория массового обслуживания непосредственно не связана с оптимизацией. Назначение ее состоит в том, чтобы на основе результатов наблюдений за «входом» в систему предсказать ее возможности и организовать наилучшее обслуживание для конкретной ситуации и понять, как последнее отразится на стоимости системы в целом. Для систем, относящихся к системам массового обслуживания, существует определенный класс задач, решение которых позволяет ответить на актуальные для сегодняшнего времени вопросы. С какой интенсивностью должно проходить обслуживание или должен выполняться процесс при заданной интенсивности и других параметрах входящего потока требований, чтобы минимизировать очередь или задержку в подготовке документа или другого вида информации? Каковы вероятность появления задержки или очереди и ее величина? Сколько времени требование находится в очереди и каким образом минимизировать его задержку? Какова вероятность потери требования (клиента)? Какова должна быть оптимальная загрузка обслуживающих каналов? При каких параметрах системы достигаются минимальные потери прибыли? К этому перечню можно добавить еще целый ряд задач.
Система массового обслуживания (СМО) включает следующие структурообразующие объекты: источник требований; входной поток требований (поступление заявок); очередь; обслуживающую систему как совокупность каналов обслуживания заявок; выходной поток (об-служенные заявки или удовлетворенные требования). Рассмотрим их модели.
Источник требований. По месту нахождения источника, формиру-ющего требования, СМО делятся на разомкнутые, когда источник на-ходится вне системы, и замкнутые, когда источник находится внутри системы.?
Входной поток требований. Подавляющее большинство теоретиче-ских разработок по исследованию систем массового обслуживания вы-полнено для условия, когда входной поток требований является пуассоновским (простейшим). Этот поток обладает рядом важных свойств. Он стационарен, ординарен и не имеет последствий.
Следующее важное для исследования свойство, которым обладает пуассоновский поток, заключается в том, что процедура разделения и объединения дает снова пуассоновские потоки.
В случае разделения пуассоновского потока на N независимых по-токов получим, что интенсивность потока Х(будет равна гХ, где г.-доля /-го потока во входном потоке требований.
Очередь. Очереди, определяемые как множество требований, ожи-дающих обслуживания, представляются несколькими моделями: оче-редь с отказами, с ограниченным временем ожидания (заявка ждет определенное время), ограниченной длиной и, наконец, неограничен-ным временем ожидания. Порядок поступления заявок на обслужива-ние называется дисциплиной очереди. Требования могут принимать
ся по мере поступления, случайным порядком, с приоритетом, по принципу «последняя - первой», по определенным каналам.
Процесс обслуживания. Основным параметром процесса обслужи-вания считается время обслуживания требования каналом у - f. (/ = 1, 2,..., т). Величина тв каждом конкретном случае определяется рядом факторов: интенсивностью поступления заявок, квалификацией ис-полнителя, технологией работ, окружающей средой и т.д. Законы рас-пределения случайной величины Ту могут быть самыми различными, но наибольшее распространение в практических приложениях получил экспоненциальный закон распределения.
Важнейшее свойство экспоненциального распределения заключа-ется в следующем.
Выходной поток обслуженных требований. Выходной поток - это поток результатов деятельности, представленных выполненными тре-бованиями в виде той или иной продукции или услуги. К основным параметрам выходного потока относятся интенсивность выхода из си-стемы обслуженных требований и характер распределения времени между моментами выпуска продукции. В общем случае эти параметры определяются моделью входного потока, дисциплиной очереди и мо-делью обслуживания. Для СМО с параллельными каналами и одно-фазным обслуживанием существует теорема о том, что при пуассоновском входном потоке с параметром X и одинаковым для каждого канала распределением времени обслуживания с параметром ц в стационарном состоянии выходной поток имеет пуассоновское распределение с параметром g. В многофазных системах выходной поток одного канала служит входным потоком для другого канала.
Особенность моделей СМО связана с достаточно строгим математи-ческим описанием функционирования систем, что достигается благода-ря их унификации по ряду признаков. Так, в зависимости от модели ожидания требованием начала обслуживания различают следующие СМО:
системы с потерями или отказами;
системы с ожиданием;
системы с ограниченным временем ожидания (ВО);
системы с ограниченной длиной очереди (ДО).
По числу каналов обслуживания системы делятся на одноканальные (т = 1) и многоканальные (т > 1). Одной из форм классификации СМО служит кодовая классификация Д. Кендалла. В соответствии с этой классификацией характеристику СМО записывают в виде трех, четырех или пяти символов. Например, а/Ь/с, где а - тип распределения входного потока требований, Ъ - тип распределения времени обслуживания, с - число каналов обслуживания. Для пуассоновского и экспоненциального распределений принимают символ М, для любого произвольного распределения - символ в. Например, запись М/М/2 означает, что входной поток требований пуассоновский, время обслуживания распределено по экспоненциальному закону, в системе имеются два канала. Четвертый символ () указывает допустимую длину очереди, пятый (е) - порядок отбора требований.
Модели СМО могут быть детерминированными или вероятност-ными. В первом случае параметры и переменные модели - это посто-янные величины, во втором - случайные.
Исследование СМО заключается в нахождении показателей, харак-теризующих качество и условия работы обслуживающей системы и показателей, отражающих экономические последствия принятых ре-шений согласно первым показателям. К показателям первой группы относятся следующие.
Рассмотрим приемы вычисления показателей первой группы на
примере наиболее распространенной модели СМО (М/М/т > 2) с ожиданием, содержащей т параллельных обслуживающих каналов. Здесь поступающие требования не теряются и оставляют систему лишь после обслуживания. Каналы выполняют однородные операции, и время обслуживания каждым каналом * распределено по экспоненциальному закону с параметром т (10.5), а входящий поток - пуассоновский с параметром X (10.1); дисциплина очереди не регламентирована, и отсутствует ограничение на число поступающих требований. Модель СМО представляется в виде системы уравнений для стационарного состояния.
Пример. Требуется провести оценку эффективности централизации нескольких отделов или служб с однородными функциями. В качестве объекта рассматриваются две службы такси, которые приобрела компания «Автосервис». Заявки клиентов между службами распределяются поровну. Спрос на такси к диспетчеру поступает с частотой 10 вызовов в час. Среднее время обслуживания одного клиента составляет 11,5 мин. Вызовы такси распределены во времени по пуассоновскому закону, а продолжительность обслуживания одного клиента - по экспоненциальному закону. Каждая служба такси оснащена двумя автомобилями.
Возникает вопрос об экономической целесообразности централи-зации управления таксопарком. Для этого необходимо сравнить два варианта:
1) вариант с независимым обслуживанием системами типа (М/М/2) при51= 10 вызовов/ч,т = 11,5мин. ит = 2;
2) вариант с одной очередью типа (М/М/4) при X = 10 2 = 20 вызовов /ч, т - 11,5 мин. и /и = 4.
Приведенные оценки показывают, что централизация служб позволяет сократить среднее время ожидания клиентом вызванного по телефону такси примерно вдвое. Это не гарантия, что клиент откажется от заказа, но существенное сокращение времени ожидания. В дальнейшем, кроме создания единой службы такси, необходимо рассматривать вопросы увеличения парка такси. При решении задач с размерностью т > 5 методами теории массового обслуживания потребуется автоматизированное вычисление.
Подводя итоги, отметим, что теория массового обслуживания предоставляет исследователю множество разнообразных моделей и методов решения задач по повышению эффективности обслуживания по-
требителей, клиентов. Для ее изучения следует обратиться к фундаментальным трудам отечественных (А.Я. Хинчин, Б.В. Гнеденко, Н.П. Бусленко, И.Н. Коваленко) и зарубежных (А. Эрланг, Т.А. Саати, Г. Вагнер, X. Taxa) ученых, а также и к другим современным публикациям, например.

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

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

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

Модель входного пуассоновского потока представляется функцией вида:

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

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

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

Процесс обслуживания . Основным параметром процесса обслуживания считается время обслуживания требования каналом j - t j (j =1,2,…, m ) . Величина τ j в каждом конкретном случае определяется рядом факторов: интенсивностью поступления заявок, квалификацией исполнителя, технологией работ, окружающей средой и т.д. Законы распределения случайной величины τ j могут быть самыми различными, но наибольшее распространение в практических приложениях получил экспоненциальный закон распределения. Функция распределения случайной величины τ j имеет вид:

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

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

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

,
	W S - среднее время пребывания требования в системе.

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

система с потерями или отказами;

система с ожиданием;

система с ограниченным временем ожидания (ВО);

система с ограниченной длиной очереди (ДО).

По числу каналов обслуживания системы делятся на одноканальные (m =1 ) и многоканальные (m >1 ). Структура СМО и характеристика ее объектов представлена на рисунке 1.21.

Одной из форм классификации СМО служит кодовая классификация Д. Кендалла. В соответствии с этой классификацией характеристику СМО записывают в виде трех, четырех или пяти символов. Например, a / b / c , где a – тип распределения входного потока требований, b – тип распределения времени обслуживания, c – число каналов обслуживания. Для пуассоновского и экспоненциального распределений принимают символ M , для любого произвольного распределения G . Например, запись М/М/2 означает, что входной поток требований пуассоновский, время обслуживания распределено по экспоненциальному закону, в системе имеются два канала. Четвертый символ (d) указывает допустимую длину очереди, пятый (e) – порядок отбора требований.

Рисунок 1.21 – Структура и характеристика объектов СМО

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

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

1. При установленных или проектных параметрах входящего потока:

а) вероятность поступления n требований в систему за период t (P n (T )) ;

б) вероятность наличия n требований в системе (P n ) .

2. При установленных или проектных параметрах обслуживания:

а) вероятность того, что все обслуживающие m каналов свободны (P 0 ) ;

б) вероятность того, что обслуживанием занято определенное число каналов (менеджеров, агентов) (P m ) ;

в) вероятность того, что r требований находится в очереди (P m + r ) .

3. При установленных или проектных параметрах входящего потока и системы обслуживания:

б) среднее число каналов m , занятых обслуживанием: E (m )= m k ;

в) среднее число простаивающих каналов: E (m 0 )=(m - m k ) ;

г) коэффициент использования (занятости) канала (K S ) ;

д) коэффициент простоя (отказа) канала (K 0 ) ;

е) относительная (Q ) и абсолютная (A ) пропускная способность СМО;

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

з) среднее число требований, ожидающих в очереди (L q ) ;

и) среднее время ожидания требования в очереди (W q ) ;

к) среднее время пребывания требования в системе (W S ) .

Рассмотрим приемы вычисления показателей первой группы на примере наиболее распространенной модели СМО (M / M / m ≥2 ) с ожиданием, содержащей m параллельных обслуживающих каналов. Здесь поступающие требования не теряются и оставляют систему лишь после обслуживания. Каналы выполняют однородные операции, и время обслуживания каждым каналом t распределено по экспоненциальному закону с параметром m , а входящий поток - пуассоновский с параметром λ ; дисциплина очереди не регламентирована, и отсутствует ограничение на число поступающих требований. Модель СМО представляется в виде системы уравнений для стационарного состояния.

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

1. Для условия, когда m =1, P n определяется по формуле математического ожидания дискретной случайной величины.

2. Для условия, когда 1≤ n ≤ m (вероятность, что все требования на обслуживании или очереди нет), P n рассчитывается по формуле:

Если ρ/ m <1 , то вероятность отсутствия требований в системе P 0 определяется по формуле для стационарного режима:

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

Коэффициенты использования (загрузки) каналов и простоя каналов соответственно определяются по формулам:

и
.

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

Среднее время ожидания в очереди составит:

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

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

Для общего случая L S определяется по формуле математического ожидания дискретной случайной величины:

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

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

Экономическая эффективность функционирования системы массового обслуживания составит:

Величина потерь определяется по следующим выражениям:

а) система с отказами:

б) система с ожиданием:

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

Пример 1.9. Требуется провести оценку эффективности централизации нескольких отделов или служб с однородными функциями. В качестве объекта рассматриваются две службы такси, которые приобрела компания «Автосервис». Заявки клиентов между службами распределяются поровну. Спрос на такси к диспетчеру поступает с частотой 10 вызовов в час. Среднее время обслуживания одного клиента составляет 11,5 минут. Вызовы такси распределены во времени по пуассоновскому закону, а продолжительность обслуживания одного клиента – по экспоненциальному закону. Каждая служба такси оснащена двумя автомобилями.

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

1) вариант с независимым обслуживанием системами типа (М/М/2 ) при λ=10 вызовов/час, τ=11,5 мин. и m = 2;

2) вариант с одной очередью типа (М/М/4 ) при λ=10*2=20 вызовов/час, τ=11,5 мин. и m = 4;

Для начала определим коэффициенты загруженности службы по первому и второму вариантам. При m = 2 имеем:

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

Вычислим W q (среднее время ожидания клиентом автомобиля-такси).

Для первого случая при m = 2 имеем ρ=1,917. Определим вероятность того, что в системе нет требований (P 0 ):

Используя значение P 0 определим W q :

ч.

Для второго случая при m = 4 имеем ρ=3,83 и определим P 0 :

При значении P 0 =0,0042, получим, что

ч.

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

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

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

Похожие статьи