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

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

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

Теория массового обслуживания представляет собой область прикладной математики, использующую методы теории случайных процессов и теории вероятностей для исследования различной природы сложных систем. Теория массового обслуживания непосредственно не связана с оптимизацией. Назначение ее состоит в том, чтобы на основе результатов наблюдений за «входом» в систему предсказать ее возможности и организовать наилучшее обслуживание для конкретной ситуации и понять, как последнее отразится на стоимости системы в целом. Для систем, относящихся к системам массового обслуживания, существует определенный класс задач, решение которых позволяет ответить на актуальные для сегодняшнего времени вопросы. С какой интенсивностью должно проходить обслуживание или должен выполняться процесс при заданной интенсивности и других параметрах входящего потока требований, чтобы минимизировать очередь или задержку в подготовке документа или другого вида информации? Каковы вероятность появления задержки или очереди и ее величина? Сколько времени требование находится в очереди и каким образом минимизировать его задержку? Какова вероятность потери требования (клиента)? Какова должна быть оптимальная загрузка обслуживающих каналов? При каких параметрах системы достигаются минимальные потери прибыли? К этому перечню можно добавить еще целый ряд задач.
Система массового обслуживания (СМО) включает следующие структурообразующие объекты: источник требований; входной поток требований (поступление заявок); очередь; обслуживающую систему как совокупность каналов обслуживания заявок; выходной поток (об-служенные заявки или удовлетворенные требования). Рассмотрим их модели.
Источник требований. По месту нахождения источника, формиру-ющего требования, СМО делятся на разомкнутые, когда источник на-ходится вне системы, и замкнутые, когда источник находится внутри системы.?
Входной поток требований. Подавляющее большинство теоретиче-ских разработок по исследованию систем массового обслуживания вы-полнено для условия, когда входной поток требований является пуассоновским (простейшим). Этот поток обладает рядом важных свойств. Он стационарен, ординарен и не имеет последствий.
Следующее важное для исследования свойство, которым обладает пуассоновский поток, заключается в том, что процедура разделения и объединения дает снова пуассоновские потоки.
В случае разделения пуассоновского потока на 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) ученых, а также и к другим современным публикациям, например.

Федеральное агентство по образованию Т. А. Радченко, А. В. Дылевский Методы анализа систем массового обслуживания Учебное пособие для вузов Воронеж 2007 2 Утверждено Научно-методическим советом факультета прикладной ма- тематики, информатики и механики 27 декабря 2006 г., протокол № 4 Учебное пособие подготовлено на кафедре технической кибернетики и автоматического регулирования факультета прикладной математики, ин- форматики и механики Воронежского государственного университета. Рекомендуется для студентов 4 курса д/о и 5 курса в/о. Для специальности: 010200 (010501) - Прикладная математика и ин- форматика 3 Содержание Введение. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1. Теоретическая часть 4 1. Теория массового обслуживания, ее математический аппарат и приложения. . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Случайные процессы. . . . . . . . . . . . . . . . . . . . . . . 5 3. Многомерные функции распределения, плотности вероятно- стей, вероятности случайного процесса. . . . . . . . . . . . . 6 4. Условные вероятности и плотности вероятностей. . . . . . . . 7 5. Классификация случайных процессов. . . . . . . . . . . . . . 8 6. Марковские случайные процессы. . . . . . . . . . . . . . . . 9 7. Цепи Маркова. . . . . . . . . . . . . . . . . . . . . . . . . . . 10 8. Уравнения Колмогорова–Чепмена. . . . . . . . . . . . . . . . 11 9. Классификация состояний марковской цепи. . . . . . . . . . 12 10. Циклические подклассы и матрица вероятности перехода для периодической цепи. . . . . . . . . . . . . . . . . . . . . 15 11. Стационарные и эргодические цепи Маркова. . . . . . . . . 16 12. Дискретные марковские процессы (цепи Маркова с непрерывным временем) . . . . . . . . . . . . . . . . . . . . 19 13. Уравнения Колмогорова. . . . . . . . . . . . . . . . . . . . . 20 14. Стационарное распределение вероятностей. . . . . . . . . . 24 15. Случайный поток событий. . . . . . . . . . . . . . . . . . . . 25 16. Классификация потоков событий. . . . . . . . . . . . . . . . 25 17. Пуассоновский поток событий. . . . . . . . . . . . . . . . . 26 18. Пуассоновский случайный процесс. . . . . . . . . . . . . . . 26 19. Системы массового обслуживания. . . . . . . . . . . . . . . 28 20. Одноканальная система массового обслуживания с отказами 29 21. Характеристики одноканальной системы массового обслу- живания с отказами. . . . . . . . . . . . . . . . . . . . . . . . 31 22. Многоканальная система массового обслуживания с отказами 32 23. Многоканальная система с отказами и полной взаимопомо- щью между каналами. . . . . . . . . . . . . . . . . . . . . . . 34 24. Многоканальная СМО с ожиданием (с очередью конечной длины) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 25. СМО с неограниченной очередью. . . . . . . . . . . . . . . . 38 26. Замкнутые системы массового обслуживания. . . . . . . . . 39 4 2. Лабораторные работы 41 1. Цепи Маркова. . . . . . . . . . . . . . . . . . . . . . . . . . . 41 2. Дискретные марковские процессы. . . . . . . . . . . . . . . . 44 3. Исследование СМО. . . . . . . . . . . . . . . . . . . . . . . . 47 3. Mathcad 49 1. Арифметические вычисления. . . . . . . . . . . . . . . . . . . 51 2. Использование формул в Mathcad . . . . . . . . . . . . . . . . 51 3. Работа с векторами и матрицами. . . . . . . . . . . . . . . . . 52 4. Построение графиков в среде Mathcad . . . . . . . . . . . . . 54 5. Решение обыкновенных дифференциальных уравнений. . . . 56 6. Чтение и запись данных. . . . . . . . . . . . . . . . . . . . . . 59 Приложение. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 Литература. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 Введение Системы массового обслуживания (СМО) в настоящее время широ- ко используются во многих прикладных областях. Данное пособие имеет цель - оказать помощь студентам в овладении теоретическими осно- вами и приобретении элементарных навыков в решении задач по теории массового обслуживания на персональном компьютере. Первая глава пособия содержит краткие сведения из теории случай- ных процессов и потоков событий, их применение к анализу типичных систем массового обслуживания с простейшим потоком заявок. Во второй главе содержатся задания для лабораторных работ и за- дачи для самостоятельного решения. В третьей главе представлены сведения о пакете Mathcad, необходи- мые для выполнения лабораторных работ по данному курсу. Глава 1. Теоретическая часть 1. Теория массового обслуживания, ее математический аппарат и приложения В науке, производстве, практической деятельности человека и даже в быту имеет место спрос на выполнение тех или иных операций (об- служивание). Заявки на обслуживание могут поступать в виде потока, и практически всегда существует ограничение на количество, скорость, качество обслуживающих единиц. Возникает задача синтеза систем (си- стем массового обслуживания), которые обеспечивали бы обслуживание 5 с учетом случайного характера потока заявок, времени обслуживания и других параметров. Для решения задач анализа и синтеза таких систем разработана теория массового обслуживания. Определение 1. Теория массового обслуживания - прикладная теоретико- вероятностная дисциплина, изучающая случайные процессы в системах обслуживания различного назначения с целью рационального построе- ния и анализа этих систем . Теория массового обслуживания возникла сравнительно недавно. Пер- вые работы по ТМО были выполнены в 20-х годах ХХ-го в. А. Эрлангом и были посвящены расчетам телефонных сетей. Проектирование различ- ных систем связи (в том числе компьютерных сетей, подвижных систем, АТС) и сейчас является основным приложением ТМО. Но современная область приложения ТМО гораздо шире, она включает в себя: производство (расчет количества оборудования и обслуживающе- го персонала, требуемой производительности при заданной рента- бельности и т.п.); экономику и бизнес (расчет числа торговых точек, распределение товаров, финансовых ресурсов с учетом потока клиентов и их по- требительской возможности и т.п.); сферу обслуживания (создание рентабельных и удобных для кли- ентов кафе, магазинов, ателье, автозаправочных станций, портов и т.п.) и многое другое. Процессы, протекающие в системах массового обслуживания, но- сят случайный характер, поэтому ТМО базируется на теории случайных процессов, элементы которой изложены ниже. 2. Случайные процессы Определение 2. Пусть для некоторого опыта задано вероятностное про- странство Ω, A, P , где Ω - пространство элементарных событий, A - алгебра его подмножеств, P - вероятностная мера на A. Случайным процессом ξ(t), заданным на данном вероятностном пространстве, на- зывается измеримая функция двух переменных ξ(t, ω), где ω ∈ Ω, а t - действительная переменная (t ∈ R), которая часто имеет смысл времени . 6 При фиксированном значении t = ti случайный процесс представля- ет собой измеримую функцию ξi = ξi (ω), т.е. случайную величину. При фиксированном элементарном событии ωi получаем некоторую детерминированную (неслучайную) функцию xi (t), называемую реали- зацией (траекторией) случайного процесса. Случайный процесс можно задавать или как множество реализаций с заданной на нем вероятностной мерой, или как последовательность (упо- рядоченную совокупность) случайных величин, соответствующих опре- деленным значениям t. В последнем случае его можно рассматривать как случайный вектор и задать с помощью многомерных законов распреде- ления. 3. Многомерные функции распределения, плотности вероятностей, вероятности случайного процесса Определение 3. Многомерной функцией распределения случайного про- цесса для фиксированных моментов времени t1 , t2 , . . . , tn называется функ- ция 2n переменных, определяемая следующим образом: F (x1 , x2 , . . . , xn , t1 , t2 , . . . , tn) = = P (ξ(t1) < x1 , ξ(t2) < x2 , . . . , ξ(tn) < xn). (1) Для непрерывнозначного процесса можно определить многомерную плотность вероятностей ∂ n F (x1 , . . . , xn , t1 , . . . , tn) f (x1 , x2 , . . . , xn , t1 , t2 , . . . , tn) = . (2) ∂ x1 . . . ∂xn Если случайный процесс дискретного типа (множество возможных значений дискретно), то можно определить многомерные вероятности P (x1 , x2 , . . . , xn , t1 , t2 , . . . , tn) = = P (ξ(t1) = x1 , ξ(t2) = x2 , . . . , ξ(tn) = xn). (3) Случайный процесс считается заданным, если заданы многомерные функции распределения (плотности вероятностей или многомерные ве- роятности) любой размерности. Замечание 1. Если t изменяется непрерывно, то для полного описания случайного процесса необходимо в многомерных законах распределения 7 (1)–(3) устремить n к бесконечности (n → ∞). Но этот предельный пе- реход представляет определенные математические трудности. Кроме то- го, работать с многомерными функциями (1)–(3) при конечном, но боль- шом значении n тоже не всегда удобно. Существуют классы процессов, для полного описания которых до- статочно знать двумерные законы распределения. К таким процессам относятся марковский и гауссовский процессы, которые наиболее часто используются в приложениях. 4. Условные вероятности и плотности вероятностей Для процесса дискретного типа можно определить условные веро- ятности (вероятность того, что в момент времени t2 значение процесса равно x2 , если в момент времени t1 оно равнялось x1): P (x1 , x2 , t1 , t2) P (x2 , t2 | x1 , t1) = . (4) P (x1 , t1) Для непрерывнозначного процесса условные плотности вероятностей имеют вид f (x1 , x2 , t1 , t2) f (x2 , t2 | x1 , t1) = . (5) f (x1 , t1) В n-мерном случае условные вероятности и плотности вероятностей определяютcя аналогично: P (x1 , . . . xn , t1 , . . . , tn) P (xn , tn | x1 , . . . xn−1 , t1 , . . . , tn−1) = , P (x1 , . . . , xn−1 , t1 , . . . , tn−1) f (x1 , . . . , xn , t1 , . . . , tn) f (xn , tn | x1 , . . . , xn−1 , t1 , . . . , tn−1) = . f (x1 , . . . , xn−1 , t1 , . . . , tn−1) Замечание 2. Условные вероятности (4) и плотности вероятностей (5) в теории случайных процессов называют переходными. Определение 4. Случайный процесс называется однородным, если услов- ные вероятности или условные плотности вероятностей зависят не от мо- ментов времени, а от разности моментов времени, т.е. P (x2 , t2 | x1 , t1) = P (x2 , x1 , t2 − t1), (6) f (x2 , t2 | x1 , t1) = f (x2 , x1 , t2 − t1). 8 5. Классификация случайных процессов Как отмечается в , строгой классификации случайных процессов нет, поэтому можно говорить лишь о выделении по тому или иному при- знаку типов процессов, которые не обязательно в своей совокупности исчерпывают всевозможные типы и не являются несовместимыми друг с другом. Случайные процессы можно классифицировать по: 1) характеру реализаций случайных процессов (характеру простран- ства состояний случайного процесса и параметра t); 2) виду закона распределения вероятностей; 3) характеру статистической связи между значениями случайного про- цесса в различные моменты времени. Классификация по характеру реализаций. 1. Дискретная последовательность (дискретный процесс с дискрет- ным временем) - это случайный процесс, у которого областью определения и областью возможных значений реализаций являют- ся дискретные множества. Примеры: процессы в цифровых систе- мах связи, компьютерных сетях, цифровой радиоаппаратуре и т.п. 2. Случайная последовательность, или временной ряд (непрерывно- значный процесс с дискретным временем) - это случайный про- цесс, область возможных значений реализаций которого - непре- рывное множество, а область определения - дискретное множе- ство. Примеры: метеорологические наблюдения, телеметрические данные состояния космонавтов и т.п. 3. Дискретный процесс (дискретный процесс с непрерывным време- нем) - это случайный процесс, множество возможных значений реализаций которого - дискретное множество, а область опреде- ления - непрерывное множество. Примеры: число абонентов те- лефонной станции, разговаривающих по телефону, количество ав- томобилей на автозаправочной стации и т.п. 4. Непрерывнозначный случайный процесс - это случайный процесс, у которого область возможных значений и область определения - непрерывные множества. Примеры: различные физические, хи- мические, биологические процессы, протекающие в природе, орга- низме человека. 9 Замечание 3. Случайные процессы с дискретным множеством возмож- ных значений (типы 1 и 3) называются цепями (последовательно перехо- дят от одного состояния к другому, образуя цепочку состояний). Если рассматривать классификацию случайных процессов по харак- теру статистической связи между значениями в отдельные моменты вре- мени, можно выделить наиболее простой и хорошо изученный тип - мар- ковский процесс. 6. Марковские случайные процессы Марковский случайный процесс - такой случайный процесс, эво- люция которого после любого фиксированного момента t (в будущем) и до момента t (в прошлом) является независимой при известном состо- янии в момент t (в настоящем) . Это основное свойство марковского процесса, которое можно математически записать по-разному. Определение 5. Случайный процесс ξ(t) называется марковским, если для любых моментов времени, связанных условием tk < tj < ti , спра- ведливо соотношение P (ξ(tk) < xk , ξ(ti) < xi | ξ(tj) = xj) = = P (ξ(tk) < xk | ξ(tj) = xj)P (ξ(ti) < xi | ξ(tj) = xj). (7) Для дискретного случайного процесса можно записать P (ξ(tk) = xk , ξ(ti) = xi | ξ(tj) = xj) = = P (ξ(tk) = xk | ξ(tj) = xj)P (ξ(ti) = xi | ξ(tj) = xj). (8) Можно дать эквивалентное определение марковского процесса в несколь- ко иной математической форме. Определение 6. Случайный процесс ξ(t) называется марковским, если P (ξ(tn) < xn | ξ(t1) = x1 , . . . , ξ(tn−1) = xn−1) = = P (ξ(tn) < xn | ξ(tn−1) = xn−1). (9) Для дискретного случайного процесса имеем P (ξ(tn) = xn | ξ(t1) = x1 , . . . , ξ(tn−1) = xn−1) = = P (ξ(tn) = xn | ξ(tn−1) = xn−1). (10) В обширном классе марковских случайных процессов можно выде- лить различные типы по характеру реализаций. 10 1. Дискретная последовательность (цепь Маркова). 2. Случайная (марковская) последовательность. 3. Дискретный случайный процесс (дискретный марковский процесс). 4. Непрерывнозначный случайный процесс (непрерывнозначный мар- ковский процесс). В теории массового обслуживания наиболее часто используются мар- ковские цепи и дискретные марковские процессы, последние иногда на- зывают марковскими цепями с непрерывным временем. 7. Цепи Маркова Определение 7. Цепь Маркова - это марковский случайный процесс с дискретными множествами возможных значений (состояний цепи) E1 , . . . , En и значений аргумента t0 , t1 , t2 , t3 , . . .. Если число возможных состояний n конечно, то цепь называется ко- нечной. Вместо значений аргумента можно указывать их номер. Разность меж- ду двумя соседними значениями аргумента tk+1 − tk называется шагом. Цепь Маркова задается множеством значений (E1 , . . . , En) и следу- ющими вероятностями. 1. Начальные вероятности Pj0 = P (ξ(0) = Ej), которые удовлетво- ряют условию нормировки Pj0 = 1. j 2. P (ξ(n + 1) = Ej | ξ(n) = Ei) - вероятность перехода из одного состояния в другое за один шаг. Если марковская цепь однород- на, то P (ξ(n + 1) = Ej | ξ(n) = Ei) = Pij . Условие нормировки Pij = 1. j 3. Вероятность перехода из одного состояния в другое за k шагов P (ξ(n+ k) = Ej | ξ(n) = Ei). Если марковская цепь однородна, то P (ξ(n + k) = Ej | ξ(n) = Ei) = Pij (k). Условие нормировки Pij (k) = 1. j 4. Вероятность состояния Ej в k-й момент времени: P (ξ(k) = Ej) = Pj (k). Условие нормировки Pj (k) = 1. j

Общие понятия, определения и классификация методов и моделей в системах массового обслуживания

Модели разомкнутых систем

1. Общие понятия, определения и классификация методов и моделей в системах массового обслуживания

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

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

Классификация СМО.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

P k (t)= e-
. (1)

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

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

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

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

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

F(t)=1 – e
, (2)

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

=1/t об (3)

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

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

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

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

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

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

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

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

• показатели, характеризующие систему в целом: число n занятых каналов обслуживания, число обслуженных (λ b ), ожидающих обслуживание или получивших отказ заявок (λ c ) в единицу времени и т.д.;
• вероятностные характеристики : вероятность того, что заявка будет обслужена (P обс) или получит отказ в обслуживании (P отк), что все приборы свободны (p 0) или определенное число их занято (p k ), вероятность наличия очереди и т.д.;
• экономические показатели : стоимость потерь, связанных с уходом не обслуженной по тем или иным причинам заявки из системы, экономический эффект, полученный в результате обслуживания заявки, и т.д.

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

Многоканальная система с отказами

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

Смешанные системы

1. Система с ограничением на длину очереди .
   Состоит из накопителя (очереди) и узла обслуживания. Заявка покидает очередь и уходит из системы, если в накопителе к моменту ее появления уже находятся m заявок (m – максимально возможноечисло мест в очереди). Если заявка поступила в систему и застала, хотя бы один канал свободным, она мгновенно начинает обслуживаться. Если в момент поступления заявки в систему все каналы заняты, то заявка не покидает систему, а занимает место в очереди. Заявка покидает систему не обслуженной, если к моменту её поступления в систему заняты все каналы обслуживания и все места в очереди.
   Для каждой системы определяется дисциплина очереди. Это система правил, определяющих порядок поступления заявок из очереди в узел обслуживания. Если все заявки и каналы обслуживания равнозначны, то чаще всего действует правило «кто раньше пришел, тот раньше обслуживается».
2. Система с ограничением на длительность пребывания заявки в очереди .
   Состоит из накопителя (очереди) и узла обслуживания. От предыдущей системы она отличается тем, что заявка, поступившая в накопитель (очередь), может ожидать начала обслуживания лишь ограниченное время Т ож (чаще всего это случайная величина). Если её время Т ож истекло, то заявка покидает очередь и уходит из системы не обслуженной.

Математическое описание СМО

СМО рассматриваются как некоторые физические системы с дискретными состояниями х 0 , х 1 , …, х n , функционирующие при непрерывном времени t . Число состояний n может быть конечным или счетным (n → ∞). Система может переходить из одного состояния х i (i= 1, 2, … , n) в другое х j (j= 0, 1, … ,n) в произвольный момент времени t . Чтобы показать правила таких переходов, используют схему, называемую графом состояний . Для типов перечисленных выше систем графы состояний образуют цепь, в которой каждое состояние (кроме крайних) связано прямой и обратной связью с двумя соседними состояниями. Это схема гибели и размножения.
Переходы из состояния в состояние происходят в случайные моменты времени. Удобно считать, что эти переходы происходят в результате действия каких-то потоков (потоков входных заявок, отказов в обслуживании заявок, потока восстановления приборов и т.д.). Если все потоки простейшие, то протекающий в системе случайный процесс с дискретным состоянием и непрерывным временем будет марковским.
Поток событий - это последовательность однотипных событий, протекающих в случайные моменты времени. Его можно рассматривать как последовательность случайных моментов времени t 1 , t 2 , … появления событий.
Простейшим называют поток, обладающий следующими свойствами:

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

В простейшем потоке интервалы времени Т 1 , Т 2 ,… между моментами t 1 , t 2 , … появления событий случайны, независимы между собой и имеют показательное распределение вероятностей f(t)=λe -λt , t≥0, λ=const, где λ - параметр показательного распределения, являющийся одновременно интенсивностью потока и представляющий собой среднее число событий, происходящих в единицу времени. Таким образом, .
Марковские случайные события описываются обыкновенными дифференциальными уравнениями . Переменными в них служат вероятности состояний р 0 (t), p 1 (t),…,p n (t) .
Для очень больших моментов времени функционирования систем (теоретически при t → ∞) в простейших системах (системы, все потоки в которых – простейшие, а граф – схема гибели и размножения) наблюдается установившийся, или стационарный режим работы. В этом режиме система будет изменять свое состояние, но вероятности этих состояний (финальные вероятности ) р к , к= 1, 2 ,…, n, не зависят от времени и могут рассматриваться как среднее относительное время пребывания системы в соответствующем состоянии.