Введение в аналитическое моделирование
Моделирование операций по схеме Марковских случайных процессов

Говорят, что в системе  протекает случайный процесс, если состояние этой системы меняется с течением времени случайным образом.

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

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

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

 

Пример:

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

 – обе подсистемы функционируют;

 – первая подсистема восстанавливается, вторая подсистема функционирует;

 – вторая подсистема восстанавливается, первая подсистема функционирует;

 – обе подсистемы восстанавливаются.

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

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

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

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

Марковский процесс с дискретными состояниями и непрерывным временем. Уравнения Колмогорова для вероятностей состояний.

Марковский процесс с дискретными состояниями и непрерывным временем ещё называют непрерывной цепью Маркова.

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

Определим для любого момента времени  вероятности состояний:

и рассмотрим элементарный промежуток времени , примыкающий справа к моменту времени .

Назовем плотностью вероятности перехода  – предел отношения вероятности  – перехода системы за время  из состояния  в состояние  к длине промежутка

.

Если все плотности вероятностей перехода  не зависят от , то непрерывную цепь Маркова называют однородной; если эти плотности представляют функции времени, то процесс называется неоднородным.

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

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

 

Пример:

Система  имеет четыре возможных состояния .

Найдем вероятность .

Это событие может произойти двумя способами:

1. В момент времени система была в состоянии , а за время  ничего не изменилось: .
2. В момент времени  система была в состоянии , а за время  перешла в состояние : .

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

.

или

.

Таким образом, выведено дифференциальное уравнение, которому должна удовлетворять функция .

Рассуждая аналогично, получим систему дифференциальных уравнений Колмогорова:

Заметим, что всегда справедливо: .

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

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

Пусть . Можно доказать общее положение:

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

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

Циклический процесс

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

Алгебраические уравнения для предельных вероятностей состояний имеют следующий вид:

Решая эти уравнения, получим:

После элементарных преобразований  получим

,

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

 

Пример:

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

 

 

 – система функционирует;

 – система неисправна, ведется поиск неисправности;

 – неисправность локализована, ведется восстановление;

 – восстановление закончено, ведется инициализация.

 – среднее время безотказной работы;

 – среднее время локализации неисправности;

 – среднее время восстановления система;

 – среднее время подготовки к функционированию.

 

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

 

 

Решение:

Вариант А:

Вариант В:

Таким образом, варианту В следует отдать предпочтение, так как по этой схеме система функционирует дольше.

Процесс «гибели и размножения»

Марковская непрерывная цепь называется процессом «гибели и размножения», если её граф состояний имеет следующий вид:

 

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

Рассмотрим случайный процесс «гибели и размножения». Для него справедлива следующая система алгебраических уравнений:

 

и нормированное уравнение .

Решая эту систему, получим:

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

Из нормировочного условия получим:

 

 

Пример:

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

 – все подсистемы исправны;

 – одна подсистема восстанавливается, две подсистемы исправны;

 – две подсистемы восстанавливаются, одна подсистема исправна;

 – все подсистемы восстанавливаются.

Найти среднюю производительность системы, если при трех работающих системах она равна , а при двух – .

Решение:

Средняя производительность системы в установившемся режиме:

 

.

Рассмотрим простейший процесс «чистого размножения», который определяется как процесс, для которого . Кроме того, для ещё большего упрощения, предположим, что .

Для этого процесса система уравнений Колмогорова имеет вид:

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

Отсюда для  получим решение .

При

.

Решение этого дифференциального уравнения будет .

Далее по индукции в качестве решения уравнения

находим

.

Это распределение носит название «распределение Пуассона».

Марковский процесс с дискретными состояниями и дискретным временем. Однородные цепи Маркова.

Вычислительная система обслуживает  поток задач двух типов. Каждая из задач монополизирует вычислительную систему. Решение задач 1-го типа требует двух часов непрерывной работы, а 2-го типа одного часа непрерывной работы. Вероятность появления требования на выполнение задач

1-го типа – , а 2-го типа –.

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

Из постановки задачи следует, что система может принимать конечное число состояний:

E₀, E₁,…E_k,…E_m.

Переход из состояния E_i в состояние E_j происходит в дискретные моменты времени:

t=0, 1, 2,…n, n+1,…

Если  – вероятность состояния E_k в момент времени n, то состояние системы в момент времени n можно описать вектором состояний:

.

Пусть для любой пары состояний (E_i,E_j) можно поставить () вероятность перехода из состояния E_i в состояние E_j:

которая равна вероятности того, что если система в момент времени n находилась в состоянии E_i, то в момент времени n+1 она будет находиться в состоянии E_j:

.

Тогда состояние системы в момент времени n+1 можно описать вектором:

,

где  – матрица переходов:

.

Методом математической индукции можно показать:

.

и если P_t не зависит от времени:

.

такие цепи Маркова называют однородными.

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

E₀ – отсутствие работы (простой ВС),

E₁ – первый час работы ВС над задачей 1-го типа,

E₂ – второй час работы ВС над задачей 1-го типа,

E₃ – работа ВС над задачей 2-го типа.

Рассмотрим две возможные гипотезы:

а) наивысший приоритет имеет задача типа 1;

б) наивысший приоритет имеет задача типа 2.

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

 

 

Таким образом, в условиях первой гипотезы имеем:

 

 

После возведения матрицы A во вторую и третью степень имеем:

 

После возведения матрицы A в степень n имеем:

 

 

Неограниченно увеличивая n, получим:

 

 

Следовательно:

То есть в установившемся режиме 3/4 всего времени ВС обслуживает поток задач. Оставшуюся 1/4 времени ВС находится в состоянии E₀.

Аналогично рассмотрим гипотезу 2. В этом случае наивысший приоритет имеет задача II типа, следовательно, суммарная матрица переходов имеет вид:

 

 

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

После возведения матрицы B в степени 2 и 3:

 

Можно заменить:

Неограниченно увеличивая n, получим:

.

Следовательно:

Таким образом, можно сделать вывод, что первая гипотеза более благоприятна для работы ВС, так как время простоя ВС, соответствующее первой гипотезе 1/4 всего времени, тогда как при второй гипотезе оно равно 2/7 всего времени .

Матрицы переходов, n-я степень которых стремятся к предельной матрице с постоянными строками, называются эргодическими.

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

Редуцируемые.

Начав с состояния, находящемся в A, когда нельзя оказаться в сегменте, находящемся в B.

 

Периодические.

 

Система находится между состояниями, находящимися в C и состояниями, находящимися в D.

 

Переходные.

Система из состояний 0 и 1 переходит в состояния 2 или 3 и оттуда не может возвратиться в состояния 0 и 1.

 

Рассмотрим уравнение: .

Если существует предел при , то вектор стационарного распределения вероятностей задается равенством:

 

.

 

В случае нашего примера для первого случая:

 

Пример 2:

 

 

 

 

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

                           (1)

В этом случае естественно ввести в рассмотрение производящую функцию:

.

Произведя преобразование (1), получим:

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

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

Рассмотрим применение этого метода, на примере, диаграмма переходов которого показана на рисунке.

 

 

 

Прежде всего, образуем матрицу:

.

Вычислим обратную матрицу :

1.            элементы  заменим их алгебраическими дополнениями;

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

3.            вычисляют определитель:

;

4.           

Теперь с помощью обратного z-преобразования можно вычислить .

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

 

В нашем примере:

Проведя аналогичные вычисления, получим:

Совпадение всех строк матрицы A отражает факт независимости решения для установившегося режима от начального состояния.

Выполняя обратное z-преобразование с помощью таблицы, получаем

,

 – интенсивность входного потока в интервале
(0, t).

 

Из последних уравнений следует:

.

Увеличим интервал наблюдения до бесконечности и обозначим:

.

тогда получим результат: , называемый формулой Литтла, который устанавливает связь между математическим ожиданием числа требований в системе G/G/m и математическим ожиданием времени, проведённым каждым требованием в этой системе.

Аналогично рассуждая, можно получить:

где:

 – среднее число требований;

 – среднее число требований в обслуживающем приборе;

 – среднее время ожидания в очереди;

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

Очевидно, что всегда имеют место следующие равенства:

.

СМО типа G/G/1

Пусть  – число требований в системе, тогда

.

Но  по определению, следовательно, учитывая , получим

,

что позволяет сделать следующие выводы:

1.      .

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

2.      .

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

 

СМО типа M/M/1

Введем следующие обозначения:

 – средняя норма прибытия, интенсивность входного потока

 – средняя норма обслуживания, интенсивность потока обслуживания

 – вероятность того, что в системе в момент времени  находится ровно  требований

 

Вычислим  – вероятность того, что в системе момент времени  находится ровно  требований.

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

Так как простейший поток обладает свойством ординарности (за интервал времени  не может произойти более одного прибытия), то справедливо:

 – вероятность того, что за время  не произошло прибытий;

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

Рассмотрим случаи реализации события с вероятностью :

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

б) В момент времени  в системе находилось  требований, а за время  нет новых прибытий, и произошло обслуживание:

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

Вероятность  равна сумме вероятностей рассмотренных случаев:

 

                (1)    

Эта формула справедлива для , а для  имеем:

а)  В момент времени  нет требований, а за время  нет новых прибытий:

б) В момент времени  в системе 1 требование, а за время  нет новых прибытий и окончаний обслуживания:

              

            

                                   (2)

Уравнения (1) и (2) называют дифференциальными уравнениями Колмогорова для СМО типа .

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

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

Доказательство:

Для  и  это справедливо, так как  и . Предположим, что справедливо  и , тогда

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

.

Тогда .

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

 

 

Вычислим среднее число требований N, находящихся в системе:

Так как всегда имеет место

 - среднее число требований в обсл. пр.

 

Задача 1. Вычислительная система обслуживает поток задач, запросы, на выполнение которых поступают в случайные моменты времени (в среднем 9 требований в час). На решение одной задачи тратиться в среднем 5 минут.

Определить математическое ожидание

¾     времени реакции системы на запрос – T,

¾     времени ожидания в очереди – W,

¾     числа требований в системе – N,

¾     числа требований в очереди – Q,

¾     числа требований в обслуживающем приборе – V,

если в качестве модели системы выбрать модель M/M/1

 

 

Задача 2. Проектируется система обработки информации описываемая системой M/M/1.

Цена потерь в результате пребывания задачи в системе составляет a руб.

Расходы, которые необходимы для создания и эксплуатации обслуживающих мощностей составляют  bm ^руб./_час=L₁.

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

l – число поступающих требований в час.

T=(m–l)^-1 – время пребывания требования в системе.

L₂=alT=aN – потери в результате пребывания требования в системе.

L₁=bm – потери для создания и эксплуатации обслуживающих мощностей.

L= L₁+L₂ – общие расходы.

 

Одноканальная СМО с отказами (M/M/1/0)

На вход поступает пуассоновский поток с интенсивностью l. Заявка, заставшая канал занятым получает отказ и покидает систему. Обслуживание подчинено показательному закону с параметром m. Единственный канал может находиться в одном из двух состояний: S₀ – канал свободен, S₁ – канал занят.

Пользуясь общим решением для схемы «гибели и размножения» получим:

 

Очевидно, требование получит отказ, когда канал занят (доля необслуженных заявок)

.

Доля обслуженных заявок – относительная пропускная способность:

.

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

.

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

.

Пример. Система обработки информации представима в виде M/M/1/0.

Интенсивность потока требований l=9 ^тр/_час.

Средняя продолжительность обработки t_обр=5 мин.

Определить T, W, X, N, Q, V, q, A, P_отк.

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

 

 

 

 

 

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

.

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

.

Таким образом, »57% заявок будет обслужено в установившемся режиме.

Вероятность отказа P_отк=1-q=0,429.

Значит около 49% требований получит отказ.

Абсолютная (фактическая) пропускная способность обслуживающего прибора (канала):

,

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

.

Одноканальная СМО с ограниченным ожиданием (M/M/1/k).

В этой модели количество мест в очереди равно k, что и накладывает ограничение на время ожидания каждого требования, т. е. (W<k/m). Время ожидания не превышает k обсл.

Будем нумеровать состояния СМО по числу требований, находящихся в системе.

S₀ – канал свободен.

S₁ – канал занят, очереди нет.

…

S_k+1 – канал занят, в очереди k заявок.

 

 

 

 

 

 

 

 

 

Пользуясь общим решением схемы «гибели и размножения» и введя обозначение r=l/m, получим:

,

.

Выражение для p₀ справедливо для r<1, при:

Заявка получает отказ, когда все k мест в очереди заняты:

.

Оставшаяся доля заявок будет обслужена, поэтому относительная пропускная способность:

.

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

Выводы выражения для среднего времени ожидания пребывания в очереди (W). Любая заявка с вероятностью p₀ не будет ждать обслуживания (время ожидания=0), с вероятностью p₁ будет ждать одного обслуживания (время ожидания=), с вероятностью p₂ будет ждать одного обслуживания (время ожидания=) и т. д.

Время обслуживания X равно 1/m, если заявка обслуживается и X=0, если она получила отказ.

.

 

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

l=9

m=12

Определить математическое ожидание

¾     времени реакции системы на запрос – T,

¾     времени ожидания в очереди – W,

¾     числа требований в системе – N,

¾     числа требований в очереди – Q,

¾     числа требований в обслуживающем приборе – V,

¾     относительную пропускную способность – q,

если в качестве модели системы выбрать модель M/M/1/3.

 

,

,

 

Пример 2.  В условиях примера 1 рассмотреть модель M/M/1/5 и сравнить характеристики для k₁=¥, k₂=3, k₃=1, k₄=0.

 

 

 

Одноканальные замкнутые СМО (M/M/1/k/l).

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

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

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

Пусть m – число каналов обслуживания, l – число источников заявок, k – число мест в очереди (k³l-1), m - интенсивность обслуживания.

S₀ – канал свободен.

S₁ – канал занят, очереди нет.

S_l – канал занят, в очереди l-1 требований.

Из состояния S₀ в состояние S₁ систему переводит поток ll, из S₁ в S₂ уже  (l -1)l, т. к. один источник заявок не функционирует и ожидает обслуживания. Из S₂ в S₃ в имеем поток (l -2)l и т. д.

k³l-1

 

 

 

 

 

 

 

 

 

Пользуясь общим решением для схемы гибели и размножения, напишем:

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

P_зан=(1–p₀) – вероятность, что канал занят. Занятый канал обслуживает в среднем m требований в единицу времени, следовательно, абсолютная пропускная способность:

.

В СМО в среднем работает (l-N) источников заявок, каждый из которых поток интенсивность которого =l.

Общий поток требований (l-N)l будет обслужен и, следовательно, равен абсолютной пропускной способности:

.

Откуда среднее число требований, находящихся в СМО:

.

Значение N можно вычислить непосредственно:

.

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

.

 

 

 

 

 

 

 

 

 

 

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

.

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

Если k<l-1

 

 

 

 

 

 

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

 

Определить эксплуатационные характеристики системы.

 

Решение.

 

 

Вероятность занятости системы коллективного доступа:

.

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

.

Среднее число запросов в системе:

.

Среднее число требований в обслуживающем устройстве:

.

Среднее число требований в ожидающем устройстве:

.

в виде следующего графа:

Тогда  – вероятность того, что в системе нет требований, можно вычислить как следующим образом:

где

,

но

,

так как

Вычислим среднее число требований в очереди:

,

где .

Обозначим  через .

Но  – производная .

Тогда  и

.

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

(В G/G/m )

Таким образом, для системы M/M/m получено:

;

 

Для системы M/M/1 справедливо:

Для системы M/M/ имеем:

.

что справедливо и для системы M/G/.

 

Задача № 1:

Вычислительная система обслуживает поток задач, запросы, на выполнение которых поступают в случайные моменты времени (в среднем 72 требования за 8 часов). На решение одной задачи тратится в среднем 5 минут.

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

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

если в качестве модели системы выбрать модель M/M/2.

 

Решение:

;

В таблице для сравнения приведены эксплуатационные характеристики одноканальной СМО ().

 

Задача № 2:

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

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

 

Решение:

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

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

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

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

Подсчитаем 100 раз подряд число требований, которые появляются в течение часа.

 – число требований, поступивших за час наблюдения,

 – наблюдаемая частота появления ровно  требований,

 – теоретическая частота появления  требований за 1 час.

.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

(кривая с ромбиками соответствует , а с квадратиками – )

Найдем среднее число прибытий за час:

Для оценки близости измеренного закона к закону Пуассона можно применить критерий Пирсона:

 

.

 

Число степеней свободы = 9.

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

Теперь проведем анализ закона обслуживания. Продолжительность обслуживания случайна:  минуты. Разобьем этот отрезок на 12 интервалов, и исследуем продолжительность 100 различных обслуживаний.

 

 

 

(кривая с ромбиками соответствует , а с квадратиками – )

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

 – теоретическое число требований, время обслуживания которых меньше чем  минуты.

.

Среднее значение времени обслуживания можно вычислить

Для оценки близости измеренного закона и показательного можно воспользоваться критерием Пирсона:

.

Число степеней свободы = 11.

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

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

 – интенсивность входного потока.

 – интенсивность потока обслуживания.

 – время пребывания требования в системе.

 – время пребывания  требований в системе.

 – потери из-за времени реакции системы.

 – время обслуживания каждого требования.

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

 – ресурс времени  вычислительных устройств.

 – простой системы обработки информации.

 – потери из-за простоя системы.

Следовательно, суммарные потери равны:

В качестве целевой функции выберем

.

 

 

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

Многоканальная СМО с отказами (M/M/m/0)

Обозначения:

S₀ – все каналы свободны.

S₁ – занят один канал, остальные свободны.

---

S_i – занято i каналов.

---

S_m – заняты все каналы.

 

 

 

 

 

Пользуясь общим решением для схемы «гибели и размножения» получим формулы Эрланга:

 

Зная все выражения можно найти характеристики эффективности СМО:

.

т. к. заявка получает отказ, если все каналы заняты.

Вероятность того, что заявка будет принята к обслуживанию (Она же относительная пропускная способность).

.

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

.

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

A – среднее число заявок, обслуживаемых в единицу времени.

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

 

Тогда число занятых каналов (число заявок в системе).

.

Однако N можно выразить и непосредственно:

N=0 p₀+1p₁+…+mp_m

 

 

 

.

 

Пример 1. Систему обработки информации можно представить в виде модели M/M/2/0. Интенсивность требований l=9 ^тр/_час. Номинальная пропускная способность m=12 ^тр/_час.

Найти эксплуатационные характеристики системы.

 

Решение. Приведенная интенсивность потока требований .

.

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

P_отк=p₂=(0,75)²/2!p₀=0,28p₀=0,138.

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

q=1– p₂=0,862;  A=lq=7,754.

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

V=N=r  q=0,647.

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

T=X=q/m=0,018 час=4,3 мин.

 

Многоканальная СМО с ограниченным ожиданием M/M/m/k

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

S₀ – все каналы свободны.

S₁ – занят один канал, остальные свободны.

---

S_m+1 – заняты все m каналов, одна заявка в очереди.

---

S_m+k – заняты все m каналов, k заявок в очереди.

 

 

 

 

 

 

 

Выражения для предельных вероятностей состояний будут выглядеть:

 

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

P_отк=p_m+k          q=1-P_отк      A=l  q.

Каждый занятый канал обслуживает в среднем m заявок в единицу времени; вся СМО за это время обслуживает A заявок.

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

V= A/m =r  q.

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

 

Пример. Сравнить эксплуатационные характеристики для моделей систем обработки информации M/M/2/k (kÎ{0,3,¥})

l=9 ^тр/_час  =12 ^тр/_час

Решение:

r=0,75    y=0,375,

А=lq=8,939    V=0,75q=0,745,

,

T=(0,745+0,104)/9=0,0943 час=5,65 мин.

W=0,104/9=0,0115 час=0,69 мин.

Х=0,745/9=0,083 час=4,96 мин.

 

Замкнутая многоканальная СМО (M/M/m/k/l)

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

Предполагается, что имеется конечное число источников требований (l). Интенсивность каждого генератора требований – l.

Система содержит m обслуживающих приборов, каждый из которых характеризуется параметром m. Наконец в системе имеется конечное число мест для ожидания, такое, что m+k ³ l.

Это приводит к следующему множеству параметров процесса гибели и размножения:

 

 

 

 

 

 

 

Обозначая ^l/_m=r, получим:

 

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

Так как каждый занятый канал обслуживает в среднем  m требований, то абсолютная пропускная способность:

.

В СМО в среднем работает (l-N) источников, каждый из тех порождает поток l:

.

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

Q=l-V(¹/_r+1);   W=^Q/_A.

Q=N–V.

 

Пример. Сравнить системы коллективного пользования с одним и двумя каналами обслуживания l=3, l=2, m=6.

Решение.

r=¹/_3.

V=0,419+2(0,14+0,023)=0,744 – Среднее число занятых каналов;

A=Vm=0,744·6=4,465 – Абсолютная пропускная способность;

N=l-V/r=3-0,744/(1/3)=0,767 – Среднее число тр. Вес.? (всего?);

Q=N-V=0,023 – Среднее число тр. в очереди;

X=1/m=0,167; T=N/A=0,172; W=0,005.

 

 

В случае m+k<l граф такой системы будет выглядеть следующим образом: