Шпаргалка по "Математическому моделированию"

СМО с потерями.

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

FIFO.

LIFO.

SIRO (Service In Random Order).

Очереди с приоритетами.

Кендалл ввел нотацию для описания СМО: A/B/s/m/k.

s – число обслуживающих  приборов (число каналов обслуживания).

m – количество мест  ожидания (максимальная длина очереди).

k – число источников.

A – входной поток.

B – поток обслуживаний.

С помощью А и В  задается закон распределения вероятностей для этих потоков.

Варианты A, B:

D – детерминированный  (регулярный) поток.

M – показательное  распределение.

Er – распределение  Эрланга порядка r.

Hr – гиперпоказательное (гиперэрлонговское) распределение  порядка r.

G – распределение общего вида (все остальное).

18. СМО  M /M/ 1/n с блокировкой источника. Граф состояний. Уравнения Колмогорова. Решение системы  и анализ результатов.

Размеченный граф состояний  одноканальной СМО представлен  на рисунке 3.

 

Рисунок 3 – Граф состояний  одноканальной СМО

 

Здесь и – интенсивность потока заявок и выполнения заявок соответственно. Состояние системы S_o обозначает, что канал свободен, а S₁ – что канал занят обслуживанием заявки.

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

где p_o(t) и p₁(t) – вероятности нахождения СМО в состояниях So и S1 соответственно. Уравнения для финальных вероятностей p_o и p₁ получим, приравнивая нулю производные в первых двух уравнениях системы. В результате получим:

          (14)

           (15)

Вероятность p₀ по своему смыслу есть вероятность обслуживания заявки p_обс, т. к. канал является свободным, а вероятность р₁ по своему смыслу является вероятностью отказа в обслуживании поступающей в СМО заявки р_отк, т. к. канал занят обслуживанием предыдущей заявки.

 

19. Диаграммы  интенсивностей  переходов (ДИП). Закон  сохранения потоков вероятностей.

Разность между  суммой интенсивностей, с которой  система попадает в состояние k и суммой интенсивностей, с которой система покидает это состояние должна равняться интенсивности изменения потока в это состояние (производной по времени).

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

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

Полагая, что интенсивности  λ_-1 =λ_-2 = λ_-3 =…0; μ₀ = μ_-1 = μ_-2 = μ_-3 =…=0, второе уравнение выписывать отдельно далее не потребуется. Итак, стационарный режим в цепи Маркова будет описываться системой разностных уравнений и условием нормировки для вероятностей

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

.

Интенсивность потока вероятностей в состояние k равна интенсивности потока из этого состояния.

Решать уравнение баланса можно, сначала определив при k =0 значение

.

Затем, построив систему  уравнений для k =1, можно получить .

Далее получаем

Из условия нормировки: .

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

.

Для большинства реальных систем массового обслуживания это  неравенство выполняется.

 

20. Формула Литтла.

Эта формула связывает  между собой среднее время  пребывания заявок в системе (Wc) и  среднюю длину

очереди (Lc) в этой системе.

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

ограничена и предполагается наличие при работе системы наличие  стационарного режима (λ/μ>1).

Если система работает длительное время, то λ=μ.

X(t) – количество заявок  пришедших в систему к моменту  времени t.

Y(t) – количество заявок ушедших  из системы к моменту времени  t.

Нарисуем график:

Рис. 2.11. К выводу формулы  Литтла.

Обе функции случайны, меняются скачком на 1 при приходе  или окончании обслуживания очередной заявки соответственно.. Число заявок, находящихся в СМО в момент t равно: Z(t) = X(t) – Y(t).

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

Интеграл  представляет собой площадь заштрихованной фигуры, состоящей из прямоугольников высотой 1 и длиной, равной времени пребывания в системе соответствующей заявки t₁,    t₂    …t_i…    .

Следовательно, мы можем  заменить этот интеграл суммой площадей и записать:

Умножим и разделим это выражение  на

Но  это количество заявок, поступивших в систему за время Т, а представляет собой суммарное время пребывания всех этих заявок в системе. Следовательно, отношение является средним временем пребывания заявки в СМО, т.е W_c. Окончательно:

Аналогично  выводится соотношение

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

W_оч - среднее время пребывания заявки в очереди.

Эти формулы носят  название формул Литтла и позволяют  при анализе систем по значению L находить W и наоборот.

 

21. Исследование  СМО   M/M/1/m с помощью ДИП.

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

 

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

 

Первые  три – это классические представители из огромного количества типов СМО. Для них и некоторых других получены законченные аналитические выражения для вероятностно – временных характеристик (ВВХ) [1]. Поэтому целью проведении имитационного моделирования этих СМО является сравнение полученных результатов при аналитическом и имитационном моделировании. Ниже приведены результаты моделирования для СМО типа M/M/1/N – экспоненциальный входной поток и экспоненциальное время обслуживания, M/D/1/N – экспоненциальный входной поток и постоянное время обслуживания, D/M/1/N – постоянный поток и экспоненциальное время обслуживания.

 

Моделирование проводилось при буферах размером N=5 и N=10. 

Моделирование проводилось при буферах размером N=5 и N=10.

 

 

22. Исследование  СМО   M/M/n  (задача Эрланга) с помощью ДИП.
23. Исследование  СМО   M/M/n/m с помощью ДИП.
24. Исследование  СМО   M/M/1/∞ с помощью ДИП.

 

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

Последняя сумма – сумма геометрической прогрессии

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

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

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

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

Под обслуживанием может  находится 0 заявок с вероятностью p, а 1 заявка с вероятностью 1-p.

25. Исследование  СМО   M/M/n/∞ с помощью ДИП.

 

 

26. Замкнутые СМО с  одним  обслуживающим  прибором  и количеством  источников  равным m. Анализ результатов.

 

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

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

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

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

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

 

27. Замкнутые СМО с  несколькими  каналами  обслуживания. Анализ результатов.

 

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

 

Рассмотрим СМО, для которых  интенсивность l входящего потока заявок зависит от состояния системы, причем источник требований является внутренним и генерирует ограниченный поток заявок. Например, обслуживается машинный парк, состоящий из N машин, бригадой из R механиков (N>R), причем каждая машина может обслуживаться только одним механиком. Интенсивность l зависит от того, сколько машин в данный момент находится в эксплуатации (N-k) и сколько машин обслуживается или стоит в очереди, ожидая обслуживания (k). Входящий поток требований исходит из ограниченного числа эксплуатируемых машин (N-k), которые в случайные моменты времени выходят из строя и требуют обслуживания. Общий входящий поток имеет интенсивность (N - k)l. Требование, поступившее в систему в момент, когда свободен хотя бы один канал, немедленно идет на обслуживание. Если требование застает все каналы занятыми обслуживанием других требований, то оно не покидает систему, а становится в очередь и ждет, пока один из каналов не станет свободным. Таким образом, в замкнутой СМО входящий поток требований формируется из выходящего.

Состояние Sk системы характеризуется  общим числом требований, находящихся на обслуживании и в очереди, равным k, k=0, 1,..., N. При этом число объектов, находящихся в эксплуатации, равно N-k. Если l интенсивность потока требований в расчете на одну машину, то:

 

 при 0<=k<=N,

  при k>N;

  при 0<=k<R,

 при R<=k<=N,

  при k>N.

 

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