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

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

Различают замкнутые и разомкнутые сети.

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

Для разомкнутой сети имеются источники требований и стоки требований.

Замкнутая сеть СМО соединяется следующим образом:

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

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

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

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

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

В матричной форме это выражение имеет вид:λ= λT

Интенсивности потоков заявок в СМО зависят от λ0, следовательно, можно определить: ,

где λ0 - интенсивность источника заявок (интенсивность потока, поступающего на вход сети).

Допустим, сеть замкнута, и в ней циркулирует конечное число заявок. Тогда

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

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

Сравнивая с λ= λT, получаем:

где Pj - вероятность нахождения заявки в j-й СМО.

Относительная частота прохождения требования через систему j за достаточно большой интервал времени t : где nj - число случаев, когда заявка оказалась в системе j; N- общее число заявок, прошедших через сеть. <=Тогда

При достаточно большом интервале времени

Таким образом, требования, поступающие из источника, αj раз проходят через систему с номером j, прежде чем вернуться в источник.

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

Цели планирования экспериментов с моделями систем.

Теория исходит из абстрактной схемы сложной системы, называемой «чер­ным ящиком» (рисунок 8.1). Считается, что исследователь может наблюдать вхо­ды и выходы «черного ящика» (имитационной модели) и по результатам на­блюдений определять зависимость между входами и выходами. Эксперимент на имитационной модели будем рассматривать состоящим из наблюдений, а каждое наблюдение - из прогонов модели. Входные переменные х 1 , х 2 , ..., х т называются факторами. Выходная пере­менная у называется наблюдаемой переменной (реакцией, откликом). Факторное пространство - это множество факторов, значения которых ис­следователь может контролировать в ходе подготовки и проведения модель­ного эксперимента.

Каждый фактор имеет уровни. Уровни - это значения, которые устанавли­ваются для каждого фактора при определении условий прогона модели в на­блюдении. Целью эксперимента является нахождение функции у, при этом предпола­гается, что значение отклика складывается из двух составляющих: y = f(x l ,x 2 , ..., х m ,) + е(х 1 х 2 , ..., х т), где f(x l ,x 2 , ..., х т) - функция отклика (неслучайная функция факторов); е(х 1 х 2 , ..., х т ) - ошибка эксперимента (случайная величина); х 1 х 2 , ..., х т - определенное сочетание уровней факторов из факторного пространства. Очевидно, что у является случайной переменной, так как зависит от случай­ной величины е(х 1 х 2 , ..., х т). Дисперсия D [у], которая характеризует точность измерений, равна дисперсии ошибки опыта: D [у] = D [е]. Дисперсионный анализ - это статистический метод анализа результатов на­блюдений, зависящих от различных, одновременно действующих факторов, выбор наиболее важных факторов и оценка их влияния. В условиях эксперимента факторы могут варьировать, благодаря чему можно иссле­довать влияние фактора на наблюдаемую переменную. Если влияние неко­торого фактора на наблюдаемую переменную изменяется при изменении уровня некоторого другого фактора, говорят, что между факторами существует взаимодействие. (ПФЭ). Общее число различных сочетаний уровней в ПФЭ для т S = где к i - число уровней i -го фактора. Если число уровней для всех факторов одинаково, то S = k m . Каждому соче­танию уровней факторов соответствует одно наблюдение. Недостаток ПФЭ - большие затраты на подготовку и проведение, так как с увеличением числа факторов и их уровней число наблюдений в эксперименте растет. Например, если имеется шесть факторов с двумя уровнями каждый, то даже при одном прогоне модели в каждом наблюдении нужно S = 2 6 = 64 на­блюдения. Очевидно, что каждый прогон удваивает это число, следовательно, увеличивает затраты машинного времени. Такого рода задачи и явились одной из причин возникновения теории пла­нирования экспериментов. Планирование экспериментов - один из разделов математической статистики, изучающий рациональную организацию измерений, подверженных случай­ным ошибкам. Планом эксперимента называется совокупность значений факторов, при ко­торых находятся значения оценок функции отклика, удовлетворяющих не­которому критерию оптимальности, например, точности. Различают стратегическое планирование эксперимента и тактическое пла­нирование эксперимента.

23. Стратегическое планирование имитационного эксперимента .

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

При стратегическом планировании эксперимента должны быть решены две основные задачи.

1.Идентификация факторов.

2.Выбор уровней факторов.

Под идентификацией факторов понимается их ранжирование по степени вли­яния на значение наблюдаемой переменной.

По итогам идентификации целесообразно разделить все факторы на две груп­пы - первичные и вторичные.

Первичные - это факторы, исследование которых необходимо провести.

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

Выбор уровней факторов производится с учетом двух противоречивых требо­ваний:

Уровни фактора должны перекрывать весь возможный диапазон его измене­ния;

Общее количество уровней по всем факторам не должно приводить к боль­шому количеству наблюдений.

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

Эксперимент, в котором реализуются все возможные сочетания уровней фак­торов, называется полным факторным экспериментом (ПФЭ).

Общее число различных сочетаний уровней в ПФЭ для т факторов можно вычислить по формуле:

S = k 1 · k 2 · k 3 · ... k i · ... · k m ,

где к i - число уровней i -го фактора.

Если число уровней для всех факторов одинаково, то S = k^ m . Каждому соче­танию уровней факторов соответствует одно наблюдение.

Недостаток ПФЭ - большие затраты на подготовку и проведение, так как с увеличением числа факторов и их уровней число наблюдений в эксперименте растет.

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

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

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

Если число факторов невелико (обычно меньше пяти), то ЧФЭ нецелесооб­разен вследствие смешивания эффектов, не позволяющего различить главные эффекты и важные взаимодействия.

В качестве примера рассмотрим план дробного факторного эксперимента (ДФЭ) - одного из видов ЧФЭ, с полным числом возможных сочетаний 2 5 . В ДФЭ каждый фактор имеет два уровня - нижний и верхний, поэтому общее число наблюдений S = 2 т.

3. Замкнутые СМО

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

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

Пусть n - число каналов обслуживания, s - число потенциальных заявок, n

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

Р 0 = .

Финальные вероятности состояний системы:

P k = при k

Через эти вероятности выражается среднее число занятых каналов

P 1 +2P 2 +…+n(P n +P n+ 1 +…+P s) или

P 1 +2P 2 +…+(n-1)P n- 1 +n(1-P 0 -P 1 -…-P n-1).

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

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

Пример 1. На вход трехканальной СМО с отказами поступает поток заявок с интенсивностью =4 заявки в минуту, время обслуживания заявки одним каналом t обсл =1/μ =0,5 мин. Выгодно ли с точки зрения пропускной способности СМО заставить все три канала обслуживать заявки сразу, причем среднее время обслуживания уменьшается втрое? Как это скажется на среднем времени пребывания заявки в СМО?

Решение. Находим вероятность простоя трехканальной СМО по формуле

ρ = /μ =4/2=2, n=3,

Р 0 = = = 0,158.

Вероятность отказа определяем по формуле:

Р отк =Р n ==

P отк = 0,21.

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

Р обсл =1-Р отк 1-0,21=0,79.

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

А= Р обсл 3,16.

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

1,58, доля каналов, занятых обслуживанием,

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

Объединяя все три канала в один, получаем одноканальную систему с параметрами μ=6, ρ=2/3. Для одноканальной системы вероятность простоя:

Р 0 = = =0,6,

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

Р отк =ρ Р 0 = =0,4,

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

Р обсл =1-Р отк =0,6,

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

А= Р обсл =2,4.

t СМО =Р обсл = =0,1 мин.

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

Пример 2. На вход трехканальной СМО с неограниченной очередью поступает поток заявок с интенсивностью =4 заявки в час, среднее время обслуживания одной заявки t=1/μ=0,5 ч. Найти показатели эффективности работы системы.

Для рассматриваемой системы n=3, =4, μ=1/0,5=2, ρ= /μ=2, ρ/n=2/3<1. Определяем вероятность простоя по формуле:

Р=.

P 0 = =1/9.

Среднее число заявок в очереди находим по формуле:

L=.

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

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

Т=t+ 0,22+0,5=0,72.

Пример 3. В парикмахерской работают 3 мастера, а в зале ожидания расположены 3 стула. Поток клиентов имеет интенсивность =12 клиентов в час. Среднее время обслуживания t обсл =20 мин. Определить относительную и абсолютную пропускную способность системы, среднее число занятых кресел, среднюю длину очереди, среднее время, которое клиент проводит в парикмахерской.

Для данной задачи n=3, m=3, =12, μ=3, ρ=4, ρ/n=4/3. Вероятность простоя определяем по формуле:

Р 0 =.

P 0 = 0,012.

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

Р отк =Р n+m = .

P отк =P n + m 0,307.

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

P обсл =1-P отк 1-0,307=0,693.

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

А= Р обсл 12 .

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

.

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

L=

L= 1,56.

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

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

Среднее время пребывания заявки в СМО:

Т=М/ 0,36 ч.

Пример 4. Рабочий обслуживает 4 станка. Каждый станок отказывает с интенсивностью =0,5 отказа в час, среднее время ремонта t рем =1/μ=0,8 ч. Определить пропускную способность системы.

Эта задача рассматривает замкнутую СМО, μ=1,25, ρ=0,5/1,25=0,4. Вероятность простоя рабочего определяем по формуле:

Р 0 =.

P 0 = .

Вероятность занятости рабочего Р зан =1-Р 0 . А=(1-P 0)μ=0,85μ станков в час.

Решение задачи

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

Найдите среднюю долю свободного времени для каждого рабочего и среднее время работы станка.

Найдите те же характеристики для системы, в которой:

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

б) два рабочих всегда обслуживают станок вместе, причем с двойной интенсивностью;

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

Возможны следующие состояния системы S:

S 0 – все станки исправны;

S 1 – 1 станок ремонтируется, остальные исправны;

S 2 – 2 станок ремонтируется, остальные исправны;

S 3 – 3 станок ремонтируется, остальные исправны;

S 4 – 4 станок ремонтируется, остальные исправны;

S 5 – (1, 2) станки ремонтируются, остальные исправны;

S 6 – (1, 3) станки ремонтируются, остальные исправны;

S 7 – (1, 4) станки ремонтируются, остальные исправны;

S 8 – (2, 3) станки ремонтируются, остальные исправны;

S 9 – (2, 4) станки ремонтируются, остальные исправны;

S 10 – (3, 4) станки ремонтируются, остальные исправны;

S 11 – (1, 2, 3) станки ремонтируются, 4 станок исправен;

S 12 – (1, 2, 4) станки ремонтируются, 3 станок исправен;

S 13 – (1, 3, 4) станки ремонтируются, 2 станок исправен;

S 14 – (2, 3, 4) станки ремонтируются, 1 станок исправен;

S 15 – все станки ремонтируются.

Граф состояний системы…

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

Если рабочий занят, он налаживает μ-станков в единицу времени, пропускная способность системы:

Средняя доля свободного времени для каждого рабочего ≈ 0,09.

Среднее время работы станка ≈ 3,64.

а) За каждым рабочим закреплены два станка.

Вероятность простоя рабочего определяется по формуле:

Вероятность занятости рабочего:

Если рабочий занят, он налаживает μ-станков в единицу времени, пропускная способность системы:

Средняя доля свободного времени для каждого рабочего ≈ 0,62.

Среднее время работы станка ≈ 1,52.

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

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

Сравнение 5 ответов:

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

Заключение

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

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

1. Количество заявок в системе (которая рассматривается как СМО) должно быть достаточно велико (массово).

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

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

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

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

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

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

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

Список литературы

1) http://www.5ballov.ru.

2) http://www.studentport.ru.

3) http://vse5ki.ru.

4) http://revolution..

5) Фомин Г.П. Математические методы и модели в коммерческой деятельности. М: Финансы и статистика, 2001.

6) Гмурман В.Е. Теория вероятностей и математическая статистика. М: Высшая школа, 2001.

Остальных состояний системы. В результате получим систему уравнений: Решение этой системы будет иметь вид: (4) ,…, (5) 4. Основные понятия и классификация систем массового обслуживания Заявкой (или требованием) называется спрос на удовлетворение какой-либо потребности (далее потребности предполагаются однотипными). Выполнение...

2-3 Поиск литературы 7 1 7 2-4 Разработка модели разветвленной СМО 6 1 6 3 Поиск литературы завершен 3-6 Изучение литературы по теории массового обслуживания 10 1 10 4 Модель разработана 4-5 Разработка алгоритма программы 10 1 10 5 Алгоритм программы разработан 5-7 Выбор среды программиро-вания и создание программы 30 1 ...

Очередь длины k, остается в ней с вероятностью Pk и не присоединяется к очереди с вероятностью gk=1 - Pk,". именно так обычно ведут себя люди в очередях. В системах массового обслуживания, являющихся математическими моделями производственных процессов, возможная длина очереди ограничена постоянной величиной (емкость бункера, например). Очевидно, это частный случай общей постановки. Некоторые...

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

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

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

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

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

Схема возможных состояний такой системы показана на рис. 1.13.

Рис. 1.13.

Система может иметь следующие состояния:

s 0 - все электроустановки исправны и электромонтер не занят их обслуживанием;

Sj - электромонтер обслуживает одну электроустановку, остальные электроустановки работают;

s 2 - две электроустановки неисправны, одна ремонтируется, вторая находится в очереди;

s k - к электроустановок неисправны, одна ремонтируется, к - 1 стоят в очереди;

s n - п электроустановок неисправны, одна ремонтируется, п - 1 ожидают ремонта.

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

При переходе системы из состояния s 0 в состояние Sj интенсивность потока неисправностей равна пХ (поток неисправностей всех работающих электроустановок).

При переходе системы из состояния Sj в состояние s 2 интенсивность потока неисправностей уже определяется п - 1 работающими электроустановками (одно изделие находится в ремонте) и т. д.

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

Такие СМО исследовал К. Пальм, который вывел и получил удобные и простые уравнения для определения вероятностей состояния системы:

Пример 1.15. Дежурный электромонтер на птицефабрике обслуживает 3 объекта. На каждом из объектов в сутки возникает по две неисправности. Процесс устранения неисправности занимает у электромонтера 1 ч. Необходимо рассчитать вероятности состояний, вероятность занятости электромонтера, абсолютную пропускную способность системы.

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

§1. Марковские цепи с конечным числом состояний и дискретным временем.

Пусть некоторая система S может находиться в одном из состояний конечного (или счетного) множества возможных состояний S 1, S 2,…, S n, а переход из одного состояния в другое возможен только в определенные дискретные моменты времени t 1, t 2, t 3, …, называемые шагами .

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

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

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

Рис. 1

Вершины графа S 1, S 2, S 3 обозначают возможные состояния системы. Стрелка, направленная из вершины S i в вершину S j обозначает переход S i → S j; число, стоящее рядом со стрелкой, обозначает величину вероятности этого перехода. Стрелка, замыкающаяся на i -той вершине графа, обозначает, что система остается в состоянии S i с вероятностью, стоящей у стрелки.

Графу системы, содержащему n вершин, можно поставить в соответствие матрицу n ´n , элементами которой являются вероятности переходов p ij между вершинами графа. Например, граф на рис.1 описывается матрицей P :

https://pandia.ru/text/78/171/images/image003_65.gif" width="95" height="33 src="> (1.1)

Условие (1.1) - обычное свойство вероятностей, а условие (1.2) (сумма элементов любой стрелки равна 1) означает, что система S обязательно либо переходит их какого-то состояния S i в другое состояние, либо остается в состоянии S i.

Элементы матрицы дают вероятности переходов в системе за один шаг. Переход S i → S j за два шага можно рассматривать как происходящий на первом шаге из S i в некоторое промежуточное состояние S k и на втором шаге из S k в S i. Таким образом, для элементов матрицы вероятностей переходов из S i в S j за два шага получим:

(1.3)

В общем случае перехода S i → S j за m шагов для элементов https://pandia.ru/text/78/171/images/image008_47.gif" width="164 height=58" height="58">, 1 ≤ l ≤ m

Полагая в (1.4) l = 1 и l = m - 1 получим два эквивалентных выражения для https://pandia.ru/text/78/171/images/image009_45.gif" width="162" height="65 src="> (1.5)

. (1.6)

Пример 1. Для графа на рис.1 найти вероятность перехода системы из состояния S 1 в состояние S 2 за 3 шага.

Решение. Вероятность перехода S 1 → S 2 за 1 шаг равна . Найдем вначале , используя формулу (1.5), в которой полагаем m = 2.

https://pandia.ru/text/78/171/images/image014_31.gif" width="142" height="54 src=">.

Как видно из этой формулы, в дополнение к необходимо вычислить также https://pandia.ru/text/78/171/images/image016_30.gif" width="38" height="30">:

https://pandia.ru/text/78/171/images/image018_27.gif" width="576" height="58 src=">

Таким образом

https://pandia.ru/text/78/171/images/image020_25.gif" width="156" height="123 src=">.

Если обозначить через P (m) матрицу, элементами которой являются - вероятности переходов из S i в S j за m шагов, то справедлива формула

P (m) = P m, (1.7)

где матрица P m получается умножением матрицы P саму на себя m раз.

Исходное состояние системы характеризуется вектором состояния системы (называемым также стохастическим вектором ).

= (q 1, q 2,…,q n),

где q j-вероятность того, что исходным состоянием системы является S j состояние. Аналогично (1.1) и (1.2) справедливы соотношения

0 ≤ q i ≤1; https://pandia.ru/text/78/171/images/image025_19.gif" width="218 height=35" height="35">

вектор состояния системы после m шагов, где - вероятность того, что после m шагов система находится в S i состоянии. Тогда справедлива формула

(1.8)

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

Решение. Исходное состояние системы характеризуется вектором =(0,7; 0; 0,3). После первого шага (m = 1) система перейдет в состояние

После второго шага система окажется в состоянии

Ответ: Состояние системы S после двух шагов характеризуется вектором (0,519; 0,17; 0,311).

При решении задач в примерах 1, 2 предполагалось, что вероятности переходов P ij остаются постоянными. Такие марковские цепи называются стационарными. В противном случае марковская цепь называется нестационарной.

§2. Марковские цепи с конечным числом состояний и непрерывным временем.

Если система S может переходить в другое состояние случайным образом в произвольный момент времени, то говорят о случайном процессе с непрерывным временем. В отсутствии последействия такой процесс называется непрерывной марковской цепью. При этом вероятности переходов S i → S j для любых i и j в любой момент времени равны нулю (в силу непрерывности времени). По этой причине вместо вероятности перехода P ij вводится величина λij - плотность вероятности перехода из состояния S i в состояние S j, определяемая как предел

; (i ≠ j ). (2.1)

Если величины λ ij не зависят от t , то марковский процесс называется однородным. Если за время Δt система может изменить свое состояние не более чем один раз, то говорят, что случайный процесс является ординарным. Величину λ ij называют интенсивностью перехода системы из S i в S j. На графе состояний системы численные значения λ ij ставят рядом со стрелками, показывающими переходы в вершины графа (рис. 2).

https://pandia.ru/text/78/171/images/image036_12.gif" width="101 height=62" height="62"> (2.2)

Распределение вероятностей состояний системы, которое можно характеризовать вектором https://pandia.ru/text/78/171/images/image038_11.gif" width="21 height=27" height="27"> являются константами.

Состояния S i и S j называются сообщающимися, если возможны переходы S i ↔ S j (на рис. 2 сообщающимися являются состояния S 1 и S 2, а S 1, S 3 и S 2, S 3 такими не являются).

Состояние S i называется существенным, если всякое S j, достижимое из S i, является сообщающимся с S i. Состояние S i называется несущественным, если оно не является существенным (на рис. 2 существенными являются состояния S 1 и S 2).

Если существуют предельные вероятности состояний системы

(2.3)

не зависящие от начального состояния системы, то говорят, что при t → ∞ в системе устанавливается стационарный режим.

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

Теорема 1. Если S i – несущественное состояние, то

(2.4)

т. е. при t → ∞ система выходит из любого несущественного состояния (для системы на рис. 2 т. к. S 3 – несущественное состояние).

Теорема 2. Чтобы система с конечным числом состояний имела единственное предельное распределение вероятностей состояний, необходимо и достаточно, чтобы все ее существенные состояния сообщались между собой (система на рис.2 удовлетворяет этому условию, т. к. существенные состояния S 1 и S 2 сообщаются между собой).

Если случайный процесс, происходящий в системе с дискретными состояниями является непрерывной марковской цепью, то для вероятностей p 1(t ), p 2(t ),…, p n(t ) можно составить систему линейных дифференциальных уравнений, называемых уравнениями Колмогорова. При составлении уравнений удобно пользоваться графом состояний системы. Рассмотрим получение уравнений Колмогорова на конкретном примере.

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

Решение. Рассмотрим вначале вершину графа S 1. Вероятность p 1(t + Δt ) того, что система в момент времени (t + Δt ) будет находиться в состоянии S 1 достигается двумя способами:

а) система в момент времени t с вероятностью p 1(t ) находилась в состоянии S 1 и за малое время Δt не перешла в состояние S 2. Из состояния S 1 система может быть выведена потоком интенсивностью λ 12; вероятность выхода системы из состояния S 1 за время Δt при этом равна (с точностью до величин более высокого порядка малости по Δt ) λ 12 Δt , а вероятность невыхода из состояния S 1 будет равна (1 - λ 12 Δt ). При этом вероятность того, что система останется в состоянии S 1, согласно теореме об умножении вероятностей будет равна p 1(t ) (1 - λ 12 Δt ).

б) система в момент времени t находилась в состоянии S 2 и за время Δt под воздействием потока λ 21 перешла в состояние S 1 с вероятностью λ 21 Δt S 1 равна p 2(t )∙λ 21Δt .

в) система в момент времени t находилась в состоянии S 3 и за время Δt под воздействием потока λ 31 перешла в состояние S 1 с вероятностью λ 31 Δt . Вероятность того, что система будет находиться в состоянии S 1 равна p 3(t )∙λ 31Δt .

По теореме сложения вероятностей получим:

p 1(t + Δt ) = p 1(t ) (1 - λ12 Δt ) + p 2(t ) (1 - λ21 Δt ) + p 3(t ) (1 – λ31 Δt );https://pandia.ru/text/78/171/images/image043_10.gif" width="20" height="16 src=">

https://pandia.ru/text/78/171/images/image045_11.gif" width="269" height="46 src="> (2.5)

Аналогично, рассматривая вершины графа S 2 и S 3 , получим уравнения

, (2.6)

https://pandia.ru/text/78/171/images/image048_10.gif" width="217" height="84 src=">

Из последнего уравнения следует, что p 3 = 0. Решая оставшиеся уравнения, получим p 1= 2/3, p 2 = 1/3.

Ответ: вектор состояния системы в стационарном режиме равен

С учетом рассмотренного примера сформулируем общее правило составления уравнений Колмогорова:

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

§3. Процессы рождения и гибели.

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

https://pandia.ru/text/78/171/images/image052_9.gif" width="61" height="12"> λ0 λ1 λ2 λg-2 λ g-1

https://pandia.ru/text/78/171/images/image054_9.gif" width="32" height="12">.gif" width="61" height="12">μ0 μ1 μ2 μg-2 μg-1

Здесь величины λ 0, λ 1,…, λ g-1 - интенсивности переходов системы из состояния в состояние слева направо, можно интерпретировать как интенсивности рождения (возникновения заявок) в системе. Аналогично, величины μ 0, μ 1,…, μ g-1 - интенсивности переходов системы из состояния в состояние справа налево, можно интерпретировать как интенсивности гибели (выполнения заявок) в системе.

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

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

для состояния S 0:

p 0∙λ 0Δt = p 1∙μ 0Δt ;λ 0 p 0 = μ 0 p 1;

для состояния S 1:

р 1·(λ 1 + μ 0)Δt = p 0∙λ 0Δt + p 2∙μ 1·Δt ;(λ 1 + μ 0) p 1 = λ 0 p 0 + μ 1p 2.

Последнее уравнение с учётом предыдущего можно привести к виду λ 1 p 1 = μ 1p 2 . Аналогично можно получить уравнения для остальных состояний системы. В результате получится система уравнений:

https://pandia.ru/text/78/171/images/image059_9.gif" width="12" height="23 src=">.gif" width="94" height="54 src="> (3.3)

§4. Основные понятия и классификация систем массового обслуживания. Простейший поток заявок.

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

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

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

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

1)отсутствие последействия , т. е. заявки поступают независимо друг от друга;

2)стационарность, т. е. вероятность поступления данного числа заявок на любом временнóм отрезке [t 1, t 2] зависит лишь от величины этого отрезка и не зависит от значения t 1, что позволяет говорить о среднем числе заявок за единицу времени, l, называемом интенсивностью потока заявок ;

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

Для простейшего потока вероятность p i(t ) поступления в СМО ровно i заявок за время t вычисляется по формуле

(4.1)

т. е. вероятности распределены по закону Пуассона с параметром lt . По этой причине простейший поток называется также пуассоновским потоком .

Функция распределения F (t ) случайного интервала времени T между двумя последовательными заявками по определению равна F (t ) = P (T < t ). Но P (T <t )=1 - P (T ≥ t ), где P (T ≥ t ) – вероятность того, что следующая после последней заявки поступит в СМО по истечении времени t , т. е. за время t в СМО не поступит ни одна заявка. Но вероятность этого события находится из (4.1) при i = 0. Таким образом,

P (T https://pandia.ru/text/78/171/images/image067_9.gif" width="177" height="28 src="> (t > 0),

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

https://pandia.ru/text/78/171/images/image069_9.gif" width="91" height="39 src=">.gif" width="364" height="48 src=">;

б) при решении этого пункта целесообразно использовать противоположную вероятность:

https://pandia.ru/text/78/171/images/image073_8.gif" width="167" height="30 src=">.gif" width="243" height="31 src=">.gif" width="72 height=31" height="31">

https://pandia.ru/text/78/171/images/image079_7.gif" width="320" height="31 src=">

Обозначим через А, В, С события, фигурирующие в пунктах (а), (б), (в) соответственно и учитывая, что блоки работают независимо друг от друга, найдём:

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

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

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

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

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

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

СМО описываются некоторыми параметрами, которые характеризуют эффективность работы системы.

n – число каналов в СМО ;

λ – интенсивность поступления в СМО заявок ;

μ – интенсивность обслуживания заявок ;

ρ = λ /μ – коэффициент загрузки СМО;

m – число мест в очереди ;

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

Q ≡ p обс - вероятность обслуживания поступившей в СМО заявки (относительная пропускная способность СМО); при этом

Q = p обс = 1 - р отк; (4.5)

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

А = λ∙Q ; (4.6)

L смо - среднее число заявок , находящихся в СМО;

https://pandia.ru/text/78/171/images/image083_7.gif" width="22" height="27 src="> определяется как математическое ожидание случайного числа занятых обслуживанием n каналов:

https://pandia.ru/text/78/171/images/image085_7.gif" width="95" height="27 src="> - коэффициент занятости каналов ;

t ож - среднее время ожидания (обслуживания) заявки в очереди,

v = 1/t ож - интенсивность потока ухода заявок из очереди.

L оч - среднее число заявок в очереди (если очередь есть); определяется как математическое ожидание случайной величины m – числа заявок, состоящих в очереди

https://pandia.ru/text/78/171/images/image087_6.gif" width="87" height="31 src="> - среднее время пребывания заявки в СМО;

https://pandia.ru/text/78/171/images/image089_7.gif" width="229" height="48 src="> (4.9)

Здесь λ и μ – интенсивность потока заявок и выполнения заявок соответственно. Состояние системы S 0 обозначает, что канал свободен, а S 1 - что канал занят обслуживанием заявки.

Система дифференциальных уравнений Колмогорова для такой СМО имеет вид (см. пример 3)

https://pandia.ru/text/78/171/images/image093_7.gif" width="168" height="50 src="> , (5.1)

https://pandia.ru/text/78/171/images/image095_7.gif" width="197" height="51 src=">; .

Таким образом, обслуживается лишь 62,5% звонков, что нельзя считать удовлетворительным. Абсолютная пропускная способность СМО

А = λQ = λp обс = 1,2∙0,625(мин)-1 = 0,75(мин)-1,

т. е. в среднем обслуживается 0,75 звонка в минуту.

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

Пусть СМО содержит n каналов, интенсивность входящего потока заявок равна λ , а интенсивность обслуживания заявки каждым каналом равна μ . Размеченный граф состояний системы изображён на рис. 5.

https://pandia.ru/text/78/171/images/image099_6.gif" width="106" height="29"> означает, что обслуживанием заявок заняты k каналов. Переход из одного состояния в другое соседнее правое происходит скачкообразно под воздействием входящего потока заявок интенсивностью λ независимо от числа работающих каналов (верхние стрелки). Для перехода системы из одного состояния в соседнее левое неважно, какой именно канал освободится. Величина kμ характеризует интенсивность обслуживания заявок при работе в СМО k каналов (нижние стрелки).

Сравнивая графы на рис. 3 и на рис. 5 легко увидеть, что многоканальная СМО с отказами является частным случаем системы рождения и гибели, если в последней принять g = n и

https://pandia.ru/text/78/171/images/image101_6.gif" width="234" height="51 src="> (6.2)

https://pandia.ru/text/78/171/images/image103_6.gif" width="84 height=29" height="29"> (6.3)

Формулы (6.2) и (6.3) называются формулами Эрланга – основателя теории массового обслуживания.

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

https://pandia.ru/text/78/171/images/image105_6.gif" width="215" height="44"> (6.5)

Абсолютную пропускную способность найдём из (4.6) и (6.5):

https://pandia.ru/text/78/171/images/image107_6.gif" width="24" height="24 src="> можно найти по формуле:

https://pandia.ru/text/78/171/images/image108_6.gif" width="158" height="46 src="> (6.7)

Пример 7. Найти оптимальное число телефонных номеров на предприятии, если заявки на переговоры поступают с интенсивностью 1,2 заявки в минуту, а средняя продолжительность разговора по телефону составляет https://pandia.ru/text/78/171/images/image059_9.gif" width="12" height="23"> Оптимальное число каналов n неизвестно. Используя формулы (6.2) – (6.7) найдём характеристики СМО при различных значениях n и заполним таблицу 1.

Таблица 1

р отк
р обс
А [мин-1]

Оптимальным числом телефонных номеров можно считать n = 6, когда выполняется 97,6% заявок. При этом за каждую минуту обслуживается в среднем 1,171 заявки. Для решения 2-го и 3-го пунктов задачи воспользуемся формулой (4.1). Имеем:

а) https://pandia.ru/text/78/171/images/image112_6.gif" width="513" height="61">

§7. Одноканальная СМО с ограниченной длиной очереди.

В СМО с ограниченной очередью число мест m в очереди ограничено. Следовательно, заявка, поступившая в момент времени, когда все места в очереди заняты, отклоняется и покидает СМО. Граф такой СМО представлен на рис.6.

λ λ λ λ λ λ

μ μ μ μ μ μ

Рис.6

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

S 0 - канал обслуживания свободен,

S 1 – канал обслуживания занят, но очереди нет,

S 2 – канал обслуживания занят, в очереди одна заявка,

S k+1 – канал обслуживания занят, в очереди k заявок,

S m+1 – канал обслуживания занят, все m мест в очереди заняты.

Для получения необходимых формул можно воспользоваться тем обстоятельством, что СМО на рис.6 является частным случаем системы рождения и гибели (рис.3), если в последней принять g = m + 1 и

λ i = λ , μ i = μ , (). (7.1)

Выражения для финальных вероятностей состояний рассматриваемой СМО можно найти из (3.2) и (3.3) с учётом (7.1). В результате получим:

p k = ρk ∙p 0, (7.3)

При ρ = 1 формулы (7.2), (7.3) принимают вид

https://pandia.ru/text/78/171/images/image123_6.gif" width="88" height="25 src="> (7.4)

При m = 0 (очереди нет) формулы (7.2), (7.3) переходят в формулы (5.1) и (5.2) для одноканальной СМО с отказами.

Поступившая в СМО заявка получает отказ в обслуживании, если СМО находится в состоянии Sm +1, т. е. вероятность отказа в обслуживании заявки равна

p отк = р m +1 = ρm +1p 0. (7.5)

Относительная пропускная способность СМО равна

Q = p обс = 1 – р отк = ρm +1p 0, (7.6)

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

https://pandia.ru/text/78/171/images/image124_6.gif" width="251" height="49 src="> (7.8)

При ρ = 1 формула (7.8) принимает вид

https://pandia.ru/text/78/171/images/image126_6.gif" width="265" height="53 src="> (7.10)

При ρ = 1, из (7.10) получим:

https://pandia.ru/text/78/171/images/image128_6.gif" width="223" height="47 src=">

р отк = ρ m+1 ∙ p 0 ≈ (1,5)6 ∙ 0,031 ≈ 0,354,

т. е. 35,4% покупателей получают отказ в обслуживании, что недопустимо много. Среднее число людей, стоящих в очереди, находим по формуле (7.8)

https://pandia.ru/text/78/171/images/image130_6.gif" width="212" height="45 src=">

т. е. не очень большое. Увеличение очереди до m = 10 даёт

p 0 ≈ 0,0039, p отк ≈ 0,0336,

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

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

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

λ λ λ λ λ

μ μ μ μ μ

Все характеристики такой СМО можно получить из формул предыдущего раздела, полагая в них m → ∞. При этом необходимо различать два существенно разных случая: а) ρ ≥ 1; б) ρ < 1. В первом случае, как это видно из формул (7.2), (7.3), p 0 = 0 и pk = 0 (при всех конечных значениях k ). Это означает, что при t → ∞ очередь неограниченно возрастает, т. е. этот случай практического интереса не представляет.

Рассмотрим случай, когда ρ < 1. Формулы (7.2) и (7.3) при этом запишутся в виде

р 0 = 1 - ρ , (8.1)

р k = ρk ∙ (1 – ρ ), k = 1, 2,… (8.2)

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

Q = p обс =

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

А = λ ∙ Q = λ . (8.4)

Среднее число заявок в очереди получим из формулы(7.8) при m → ∞

https://pandia.ru/text/78/171/images/image140_6.gif" width="105" height="29 src=">, (8.6)

а среднее число заявок, находящихся в СМО, равно

https://pandia.ru/text/78/171/images/image142_6.gif" width="187" height="48 src="> покупателя,

а среднее число покупателей, находящихся в СМО (т. е. у кассы), равно

https://pandia.ru/text/78/171/images/image144_6.gif" width="208" height="47 src=">

что вполне приемлемо.

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

Пусть на вход СМО, имеющей n каналов обслуживания, поступает пуассоновский поток заявок с интенсивностью λ . Интенсивность обслуживания заявки каждым каналом равна μ , а максимальное число мест в очереди равно m . Граф такой системы представлен на рис.8.

Очереди нет Очередь есть

λ λ λ λ λ λ

μ 2μ nμ nμ nμ nμ

S 0 - все каналы свободны, очереди нет;

S l - заняты l каналов https://pandia.ru/text/78/171/images/image147_6.gif" width="65" height="26">.

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

S 0 → S 0; Sg → Sn +m ; Sk → Sl , ; Sk → Sn +i , https://pandia.ru/text/78/171/images/image150_7.gif" width="377" height="56">. (9.1)

Выражения для финальных вероятностей легко найти из формул (3.2) и (3.3) с учётом (8.6). В результате получим:

https://pandia.ru/text/78/171/images/image152_6.gif" width="80" height="47 src=">, ; ,. (9.3)

Образование очереди происходит, когда в момент поступления в СМО очередной заявки все n каналов заняты, т. е. когда в системе будет находиться либо n , либо n + 1,…, либо (n + m – 1)заявок. Так как эти события несовместимы, то вероятность образования очереди р оч равна сумме соответствующих вероятностей p n, p n+1,…, p n+m-1:

https://pandia.ru/text/78/171/images/image156_3.gif" width="166" height="48 src=">. (9.5)

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

https://pandia.ru/text/78/171/images/image158_6.gif" width="231" height="43 src="> (9.7)

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

https://pandia.ru/text/78/171/images/image160_6.gif" width="192" height="51"> (9.9)

Среднее число заявок, находящихся в СМО, равно

L смо = L оч + L обс. (9.10)

Среднее время пребывания заявки в СМО и в очереди определяется формулами (4.9) и (4.10).

При ρ = n в формулах (9.2), (9.4), (9.8) возникает неопределённость типа 0/0. В этом случае, раскрывая неопределённость можно получить:

https://pandia.ru/text/78/171/images/image162_5.gif" width="149" height="44 src=">; , (9.12)

https://pandia.ru/text/78/171/images/image165_5.gif" width="195" height="49 src=">, (9.14)

https://pandia.ru/text/78/171/images/image167_5.gif" width="305" height="53 src=">

т. е. грузчики работают практически без отдыха.

По формуле (9.5) находим вероятность отказа в обслуживании прибывшей на склад машины:

Т. е. вероятность отказа не столь велика. Относительная пропускная способность равна

Q = p обс = 1 – р отк ≈ 1 – 0,145 = 0,855.

Среднее число машин в очереди находим по формуле (9.14).

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

Примером замкнутой СМО может служить, например, следующая система. Рабочий-наладчик обслуживает m станков. Каждый станок может в любой момент выйти из строя и потребовать обслуживания со стороны наладчика. Интенсивность потока неисправностей каждого станка равна  . Вышедший из строя станок останавливается. Если в этот момент рабочий свободен, он берется за наладку станка; на это он тратит среднее время t обсл =1/ , где  – интенсивность потока обслуживаний (наладок).

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

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

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

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

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

Построим аналитическую модель такой системы.

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

Рис. 2.17. ДИП для одноканальной замкнутой СМО

Определим вероятности состояний.

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

Найдем характеристики эффективности замкнутой СМО.

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

Р зан = 1-Р 0 =1-р .

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

А = (1-р ) μ .

Так как каждая заявка, в конце концов, будет обслуже­на, то относительная пропускная способность q = 1.

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

L c = 1Р 1 + 2Р 2 +…+ mР m ,

но проще будет найти ее через абсолютную пропускную способность А.

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

(m - L c) = (1-р ) μ ,

L c =

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

Среднее число заявок в системе L c складывается из числа заявок в очереди L оч и среднего числа заявок, находящихся под обслуживанием в канале :

L c = L оч + .

В канале может находиться 0 заявок с вероятностью р или 1 с вероятностью 1- р , следовательно,

L оч = .

Теперь перейдем к случаю с несколькими каналами обслуживания. Будем кодировать состояния общим числом выданных источниками и еще не обслуженных заявок. Так как источник не может выдать новую заявку до окончания обслуживания предыдущей, то интенсивностьобщего потока заявок зависит от того, сколько заявок связано с процессом обслуживания (непосредственно обслуживается или стоит в очереди). Количество источников –m , число каналов –n (n < m ). Диаграмма интенсивностей переходов для данной системы изображена на рис. 2.18.

Рис. 2.18. ДИП для многоканальной замкнутой СМО

Требуется найти вероятности состояний данной системы и ее характеристики.

, i =1, 2,…,n .

При i > n возникает ситуация, когда n заявок обслуживаются, а i - n ожидают обслуживания.

Подставляя в выражения для P n + i и P m полученное выше значение P n , получаем

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

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

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

Пример. Рабочий обслуживает группу из трех станков. Каждый станок останавливается в среднем 2 раза в час Процесс наладки занимает у рабочего, в среднем, 10 минут Определить характеристики замкнутой СМО: вероятность занятости рабочего; его абсолютную пропускную способность А ; среднее коли­чество неисправных станков L c . Все потоки полагаем простейшими.

Решение. Имеем п = 3, λ = 2, μ == 6,
.

Определяем по формулам для одноканальной замкнутой СМО

Вероятность занятости рабочего:

Р зан =1-Р 0 =1-р =0,654.

Абсолютная пропускная способность (среднее число неисправностей, которое рабочий ликвидирует в час):

Среднее число неисправных станков:

L c =