Смо с отказами определения и формулы.
Краткая теория
В качестве показателей эффективности СМО с отказами будем рассматривать:
Абсолютную пропускную способность СМО, т.е. среднее число заявок, обслуживаемых в единицу времени;
Относительную пропускную способность, т.е. среднюю долю пришедших заявок, обслуживаемых системой;
Вероятность отказа, т.е. того, что заявка покинет СМО необслуженной;
Среднее число занятых каналов.
Рассмотрим классическую задачу Эрланга.
Имеется каналов, на которые поступает поток заявок с интенсивностью . Поток обслуживаний имеет интенсивность . Найти предельные вероятности состояний системы и показатели ее эффективности.
Система (СМО) имеет следующие состояния (нумеруем их по числу заявок, находящихся в системе): , где – состояние системы, когда в ней находится заявок, то есть занято каналов.
Граф состояний СМО соответствует процессу гибели и размножения и показан на рисунке.
Поток заявок последовательно переводит систему из любого левого состояния в соседнее правое с одной и той же интенсивностью . Интенсивность же потока обслуживаний, переводящих систему из любого правого состояния в соседнее левое состояние, постоянно меняется в зависимости от состояния. Действительно, если СМО находится в состоянии (два канала заняты), то она может перейти в состояние (один канал занят), когда закончит обслуживание либо первый, либо второй канал, то есть суммарная интенсивность их потоков обслуживаний будет . Аналогично, суммарный поток обслуживаний, переводящий СМО из состояния (три канала заняты) в будет иметь интенсивность , то есть может освободиться любой из трех каналов и так далее.
Для схемы гибели и размножения получим для предельной вероятности состояния:
где члены разложения будут представлять собой коэффициенты при в выражениях для предельных вероятностей . Величина
называется приведенной интенсивностью потока заявок или интенсивностью нагрузки канала. Она выражает среднее число заявок, приходящее за среднее время обслуживания одной заявки. Теперь:
Последние формулы для предельных вероятностей получили названия формул Эрланга в честь основателя теории массового обслуживания.
Вероятность отказа СМО есть предельная вероятность того, что все каналов системы будут заняты, то есть:
Относительная пропускная способность – вероятность того, что заявка будет обслужена:
Абсолютная пропускная способность:
Среднее число занятых каналов есть математическое ожидание числа занятых каналов:
где – предельные вероятности состояний
Однако среднее число занятых каналов можно найти проще, если учесть, что абсолютная пропускная способность системы есть не что иное, как интенсивность потока обслуженных системой заявок (в единицу времени). Так как каждый занятый канал обслуживает в среднем заявок (в единицу времени), то среднее число занятых каналов:
Пример решения задачи
Условие задачи
Контроль готовой продукции фирмы осуществляют три контролера. Если изделие поступает на контроль, когда все контролеры заняты проверкой готовых изделий, то оно остается непроверенным. Среднее число изделий, выпускаемых фирмой, составляет 20 изд./ч. Среднее время на проверку одного изделия - 7 мин.
Определить показатели эффективности отдела технического контроля. Сколько контролеров необходимо поставить, чтобы вероятность обслуживания составила не менее 97%?
Оказались на этой странице, пытаясь решить задачу на экзамене или зачете? Если так и не смогли сдать экзамен - в следующий раз договоритесь заранее на сайте об Онлайн помощи по методам оптимальных решений .
Решение задачи
Контроль представляет собой открытую многоканальную систему массового обслуживания с отказом в обслуживании.
За единицу измерения времени выберем час. Будем считать, что контроль работает в установившемся режиме. По условию задачи
–число каналов обслуживания
Изделий в час –интенсивность потока заявок
Изделий в час –интенсивность потока обслуживания
Вычислим –относительные интенсивности переходов из состояние в состояние:
Вычислим :
Вероятность отказа:
Вероятность обслуживания
Абсолютная пропускная способность системы:
–среднее число заявок, обслуживаемых системой в единицу времени.
Среднее число каналов, занятых обслуживанием заявки:
Вычислим, сколько контролеров нужно поставить, чтобы вероятность обслуживания составила не менее 97%:
Таким образом, чтобы вероятность обслуживания составляла не менее 97%, необходимо иметь 6 контролеров.
Средняя стоимость решения контрольной работы 700 - 1200 рублей (но не менее 300 руб. за весь заказ). На цену сильно влияет срочность решения (от суток до нескольких часов). Стоимость онлайн-помощи на экзамене/зачете - от 1000 руб. за решение билета.
Заявку можно оставить прямо в чате, предварительно скинув условие задач и сообщив необходимые вам сроки решения. Время ответа - несколько минут.
Примеры близких по теме задач
СМО с неограниченной очередью
Приведены необходимые теоретические сведения и образец решения задачи по теме "Многоканальная система массового обслуживания с неограниченной очередью", подробно рассмотрены показатели многоканальной системы массового обслуживания (СМО) с ожиданием обслуживания - среднее число каналов, занятых обслуживанием заявки, длина очереди, вероятность образования очереди, вероятность свободного состояния системы, среднее время ожидания в очереди.
Задача оптимального распределения ресурсов
Кратко изложены основные принципы динамического программирования (динамического планирования), рассмотрены уравнения Беллмана. Подробно решена задача оптимального распределения ресурсов между предприятиями.
Метод множителей Лагранжа
На странице рассмотрено нахождение условного экстремума методом множителей Лагранжа. Показано построение функции Лагранжа на примере решения задачи нелинейного программирования. Решенную задачу предваряет краткая теория.
Вектор конечного потребления и вектор валового выпуска
На примере решения задачи рассмотрена межотраслевая модель Леонтьева. Показано вычисление матрицы коэффициентов прямых материальных затрат, матрицы «затраты-выпуск», матрицы коэффициентов косвенных затрат, векторов конечного потребления и валового выпуска.
Рассмотрим одноканальную систему
массового обслуживания (СМО) с ожиданием.
Пусть входящий поток заявок на обслуживание -
простейший поток с интенсивностью l
.
Интенсивность потока обслуживания равна m . Длительность обслуживания - случайная величина, подчиненная показательному закону распределения. Поток обслуживаний является простейшим пуассоновским потоком событий. Заявка, поступившая в момент, когда канал занят, становится в очередь и ожидает обслуживания. Предположим, что СМО не может вместить более N заявок, т.е. заявки, не попавшие в ожидание, покидают СМО. Состояния СМО имеют следующую интерпретацию:
Канал свободен;
Канал занят, очереди нет;
Канал занят, одна заявка в очереди;
..............................
Канал занят, n-1 заявка в очереди;
Канал занят, N-1 заявка в очереди.
Стационарный процесс в данной системе будет описываться следующей системой алгебраических уравнений:
, n=0,
...................................
-( , 0 ................................... , n=N, n - номер состояния. Система уравнений имеет следующее
решение:: , Если , n=1, 2, ..., N, Выполнение условия стационарности r
< 1 не обязательно, поскольку
число допускаемых в СМО заявок контролируется
путем введения ограничения на длину очереди.
Определим характеристики одноканальной СМО с
ожиданием и ограниченной длиной очереди, равной
(N-1): 2) относительная пропускная способность
СМО: 3) абсолютная пропускная способность
СМО: 4) среднее число находящихся в СМО
заявок: ; 5) среднее время пребывания заявки в СМО: ; 6) средняя продолжительность пребывания
клиента (заявки) в очереди: ; 7) среднее число заявок в очереди (длина
очереди): ; Задача 1
. Специализированный пост
диагностики представляет собой одноканальную
СМО. Число стоянок для автомобилей, ожидающих
проведения диагностики, ограниченно и равно 3.
Если все стоянки заняты, то очередной автомобиль,
прибывший на диагностику, в очередь на
обслуживание не становится. Поток автомобилей,
прибывающих на диагностику, распределен по
закону Пуассона и имеет интенсивность l
= 0.85 (автомобиля в час). Время
диагностики автомобиля распределено по
показательному закону и в среднем составляет 1.05
час. Требуется определить вероятностные
характеристики поста диагностики, работающего в
стационарном режиме. > lambda:=0.85;
2) Зададим среднее время обслуживания и
выразим интенсивность потока обслуживания
автомобилей: > t:=1.05:mu:=1/t;
3) Найдем приведенную интенсивность
потока автомобилей как отношение интенсивностей
l
и m
, т.е.. > rho:=lambda/mu;
4) Вычислим финальные вероятности
системы: > N:=4:P:=(1-rho)/(1-rho^(N+1));P:=rho*P;P:=rho^2*P;P:=rho^3*P;P:=rho^4*P;
5) Вероятность отказа в обслуживании
автомобиля:: > P:=P;
Отсюда следует, что пост диагностики не
обслуживает автомобили в среднем в 15.8% случаев. > q:=1-P;
7) Абсолютная пропускная способность
поста диагностики (автомобиля в час): > A:=lambda*q;
8) Среднее число автомобилей в СМО: > L[s]:=rho*(1-(N+1)*rho^N+N*rho^(N+1))/((1-rho)*(1-rho^(N+1)));
9) Среднее время пребывания автомобиля в
СМО: > W[s]:=L[s]/(lambda*(1-P[N]));
10) Средняя продолжительность пребывания
заявки в очереди на обслуживание: > W["q"]:=W[s]-1/mu;
11) Среднее число заявок в очереди (длина
очереди): > L["q"]:=lambda*(1-P[N])*W["q"];
Для статистического моделирования
работы поста диагностики составим следующую
процедуру: > p:=proc(k) global
t_och1,t_och2,t_och3,sm_t_obs,post,otk,obsl:local t1,t_okon,t,rn_post,och,per: Принятые обозначения: Повторите опыт 50 раз в цикле, найдите
оценки характеристик СМО, сравните их с
теоретическими значениями. Задача 2
: При решении задач управления, в том числе и управления войсками, часто возникает ряд однотипных задач: Все эти задачи однотипны в том смысле, что в них присутствует массовый спрос на обслуживание. В удовлетворении этого спроса участвует определенная совокупность элементов, образующая систему массового обслуживания (СМО) (рис. 2.9). Элементами СМО являются: Входящий поток
- это совокупность заявок на обслуживание. Часто заявка отождествляется с ее носителем. Например, поток
неисправной радиоаппаратуры, поступающий в мастерскую объединения, представляет собой поток
заявок - требований на обслуживание в данной СМО. Как правило, на практике имеют дело с так называемыми рекуррентными потоками, - потоками, обладающими свойствами: Первые два свойства мы определили ранее. Что касается ограниченного последействия, то оно заключается в том, что интервалы между поступающими заявками являются независимыми случайными величинами. Рекуррентных потоков много. Каждый закон распределения интервалов порождает свой рекуррентный поток
. Рекуррентные потоки иначе называют потоками Пальма. Поток
с полным отсутствием последействия, как уже отмечалось, называется стационарным пуассоновским. У него случайные интервалы между заявками имеют экспоненциальное распределение: здесь - интенсивность потока. Название потока - пуассоновский - происходит от того, что для этого потока вероятность
появления заявок за интервал
определяется законом Пуассона: Поток
такого типа, как отмечалось ранее, называют также простейшим. Именно такой поток
предполагают проектировщики при разработке СМО. Вызвано это тремя причинами. Во-первых
, поток
этого типа в теории массового обслуживания аналогичен нормальному закону распределения в теории вероятностей в том смысле, что к простейшему потоку приводит предельный переход для потока, являющегося суммой потоков с произвольными характеристиками при бесконечном увеличении слагаемых и уменьшении их интенсивности. То есть сумма произвольных независимых (без преобладания) потоков с интенсивностями является простейшим потоком с интенсивностью Во-вторых
, если обслуживающие каналы (приборы) рассчитаны на простейший поток
заявок, то обслуживание других типов потоков (с той же интенсивностью) будет обеспечено с не меньшей эффективностью. В-третьих
, именно такой поток
определяет марковский процесс в системе и, следовательно, простоту аналитического анализа системы. При других потоках анализ
функционирования СМО сложен. Часто встречаются системы, у которых поток
входных заявок зависит от количества заявок, находящихся в обслуживании. Такие СМО называют замкнутыми
(иначе - разомкнутыми
). Например, работа мастерской связи объединения может быть представлена моделью замкнутой СМО. Пусть эта мастерская предназначена для обслуживания радиостанций, которых в объединении . Каждая из них имеет интенсивность отказов
. Входной
поток
отказавшей аппаратуры будет иметь интенсивность : где - количество радиостанций, уже находящихся в мастерской на ремонте. Заявки могут иметь разные права
на начало обслуживания. В этом случае говорят, что заявки неоднородные
. Преимущества одних потоков заявок перед другими задаются шкалой приоритетов. Важной характеристикой входного потока является коэффициент вариации
: где - математическое ожидание длины интервала; Среднеквадратическое отклонение случайной величины (длины интервала) . Для простейшего потока Для большинства реальных потоков . При поток
регулярный, детерминированный. Коэффициент вариации
- характеристика, отражающая степень неравномерности поступления заявок. Каналы (приборы) обслуживания
. В СМО могут быть один или несколько обслуживающих приборов (каналов). Согласно с этим СМО называют одноканальными или многоканальными. Многоканальные
СМО могут состоять из однотипных или разнотипных приборов. Обслуживающими приборами могут быть: Основная характеристика канала - время обслуживания. Как правило, время обслуживания - величина случайная. Обычно практики полагают, что время обслуживания имеет экспоненциальный закон распределения: где - интенсивность обслуживания, ; Математическое ожидание времени обслуживания. То есть процесс обслуживания - марковский, а это, как теперь нам известно, дает существенные удобства в аналитическом математическом моделировании. Кроме экспоненциального встречаются -распределение Эрланга, гиперэкспоненциальное, треугольное и некоторые другие. Это нас не должно смущать, так как показано, что значение
критериев эффективности СМО мало зависят от вида закона распределения вероятностей времени обслуживания. При исследовании СМО выпадает из рассмотрения сущность обслуживания, качество обслуживания
. Каналы могут быть абсолютно надежными
, то есть не выходить из строя. Вернее, так может быть принято при исследовании. Каналы могут обладать конечной надежностью
. В этом случае модель СМО значительно сложнее. Очередь заявок
. В силу случайного характера потоков заявок и обслуживания пришедшая заявка может застать канал (каналы) занятым обслуживанием предыдущей заявки. В этом случае она либо покинет СМО не обслуженной, либо останется в системе, ожидая начало своего обслуживания. В соответствии с этим различают: СМО с ожиданием
характеризуются наличием очередей. Очередь
может иметь ограниченную или неограниченную емкость: . Исследователя обычно интересуют такие статистические характеристики, связанные с пребыванием заявок в очереди: Нередко встречаются СМО, в которых заявки имеют ограниченное время пребывания в очереди
независимо от ее емкости. Такие СМО также относят к СМО смешанного типа. Выходящий поток
- это поток
обслуженных заявок, покидающих СМО. Встречаются случаи, когда заявки проходят через несколько СМО: транзитная связь
, производственный конвейер и т. п. В этом случае выходящий поток
является входящим для следующей СМО. Совокупность последовательно связанных между собой СМО называют многофазными СМО
или сетями СМО
. Входящий поток
первой СМО, пройдя через последующие СМО, искажается и это затрудняет моделирование
. Однако следует иметь в виду, что при простейшем входном потоке и экспоненциальном обслуживании (то есть в марковских системах) выходной поток тоже простейший
. Если время обслуживания имеет не экспоненциальное распределение, то выходящий поток
не только не простейший, но и не рекуррентный. Заметим, что интервалы между заявками выходящего потока, это не то же самое, что интервалы обслуживания. Ведь может оказаться, что после окончания очередного обслуживания СМО какое-то время простаивает из-за отсутствия заявок. В этом случае
1) вероятность отказа в обслуживании заявки:
Решение
:
1) Интенсивность прибытия автомобилей на
обслуживание:
6) Относительная пропускная способность поста
диагностики:
t_och1:=0:t_och2:=0:t_och3:=0:post:=0:otk:=0:obsl:=0:t_okon:=0:sm_t_obs:=0:och:=0:rn_post:=rand(1..1200):
for t from 1 by 1 to k do
t1:=rn_post():
if och=1 then t_och1:=t_och1+1 fi:
if och=2 then t_och2:=t_och2+1 fi:
if och=3 then t_och3:=t_och3+1 fi:
if t1>=1 and t1<=17 and t_okon=0 and och>=0 and och<=3 then per:=1 fi:
if t1>=1 and t1<=17 and t_okon>0 and och>=0 and och<3 then per:=2 fi:
if t1>=1 and t1<=17 and t_okon>0 and och=3 then per:=3 fi:
if t1>17 and t_okon>0 then per:=4 fi:
if t1>17 and t_okon=0 and och>0 then per:=5 fi:
if per=1 then t_okon:=stats():
sm_t_obs:=sm_t_obs+t_okon:obsl:=obsl+1:post:=post+1 fi:
if per=2 then t_okon:=t_okon-1:obsl:=obsl+1:och:=och+1:post:=post+1 fi:
if per=3 then t_okon:=t_okon-1:otk:=otk+1:post:=post+1 fi:
if per=4 then t_okon:=t_okon-1 fi:
if per=5 then t_okon:=stats(): sm_t_obs:=sm_t_obs+t_okon:och:=och-1 fi
od end:
t_och1,t_och2,t_och3 - количество минут, когда в очереди 1, 2
и 3 машины соответственно;
sm_t_obs - затрачено всего минут на обслуживание;
post - прибыло машин на обслуживание; otk - количество
отказов в обслуживании; obsl - обслужено машин;
t_obsl - продолжительность обслуживания машины,
инициализируется как случайная величина,
распределенная по закону Пуассона с
математическим ожиданием 65 минут (1 час 5 минут);
t1 - случайная величина, с одинаковой вероятностью
принимающая целые значения из интервала от 1 до
12000. Если t1>=0 и t1<=17, то считаем, что на пункт
диагностики поступила заявка (интенсивность 0.85
заявки в час = 17/12000 заявки в минуту);
t - параметр цикла (количество минут).
Проведем опыт продолжительностью в 5000 минут:
> p(5000);print("Поступило на
обслуживание автомобилей
",post);print("Обслужено ",obsl);
print("Отказано в обслуживании ",otk);
print("Затрачено на обслуживание
",sm_t_obs,"мин."); print(t_och1," мин. 1 машина в
очереди");print(t_och2,"мин. 2 машины в очереди");
print(t_och3," мин. 3 машины в очереди");
1) Модифицируйте процедуру для вычисления
числовых характеристик СМО. Задайте
продолжительность опыта в 1000 минут и повторите
опыт, например, 5 раз. Затем вычислите средние
значения каждой характеристики СМО. Сравните
опытные данные с вероятностными
характеристиками СМО.
2) Смоделируйте работу СМО для случая, когда
автомобиль обслуживается ровно 1 час 5 минут, а
все остальные параметры остаются прежними.
Сравните полученные данные с результатами
предыдущего пункта.
3) Так как интенсивность поступления заявок равна
0.85 машины в час, то в среднем промежуток времени
между поступлениями заявок составляет 1/0.85=100/85
часа, или около 71 минуты. Задайте интервал между
поступлениями заявок с помощью функции stats() и проведите ряд испытаний работы СМО.
Сравните средние значения характеристик,
полученных опытным путем, с вероятностными
характеристиками.
4) Задайте интенсивность обслуживания в 70 минут, а
число стоянок для машин равной 4, и проведите
испытания работы поста диагностики. Повторите
опыт для случая, когда интенсивность
обслуживания составляет 60 минут, а число стоянок
2. Как изменятся характеристики поста
диагностики?
5) Смоделируйте работу поста диагностики при
условии, что число стоянок не ограниченно.