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

76 00 1 10 2 01 00 1
10 2 11 2
01 1 11 10 01 1
2 11 0
(
)
0
(
)
0
(
)
0
P
P
P
P
P
P
P
P
P
P
P




 

 



 








 






Вероятность отказа в обработке запроса есть не что иное как вероятность
11
P занятости обслуживанием обоих серверов. Оставив из имеющихся уравнений три и дополнив их условием нормировки:
00 10 01 11 0
P
P
P
P




решаем далее полученную систему линейных алгебраических уравнений (например, методом подстановки).
Вопрос 3. Процессы гибели и размножения.
Важной разновидностью непрерывных марковских цепей является процесс гибели и размножения. Происхождение термин берет в биологии, где такая схема описывает процессы изменения численности популяции, распространения эпидемий и т.п.
Марковская непрерывная цепь называется процессом гибели и размножения, если ее ГСП имеет вид, представленный на рис. 13.
Рис. 13. Процесс гибели и размножения
Граф на рисунке имеет вид цепочки, крайние звенья которой связаны переходами только с одним соседним звеном, а каждое внутреннее связано прямой и обратной связью с каждым из соседних.
Величины
12 23 1,
,
, ...
n
n
 


(интенсивности переходов системы из состояния в состояние слева направо) можно трактовать как интенсивности рождения, величины
21 32
,
1
,
, ...
n n
 


(интенсивности переходов системы из состояния в состояние справа налево) - как интенсивности гибели.
Запишем алгебраические уравнения для вероятностей состояний в установившемся режиме. Для каждого состояния поток, втекающий в данное состояние, должен равняться потоку, вытекающему из данного состояния.

77
Для состояния
1
S :
12 1
21 2
p
p



Для состояния
2
S :
23 2
21 2
12 1
32 3
p
p
p
p







С учетом равенства для состояния S
1
равные друг другу члены справа и слева можно сократить, поэтому получаем:
23 2
32 3
p
p



Аналогично, для
3
S :
34 3
43 4
p
p



Вообще для состояния k, k = 2,..n, имеем:
1,
1
,
1
k
k
k
k k
k
p
p






Таким образом, предельные вероятности состояний
1
p ,
2
p , ... ,
n
p процесса размножения и гибели можно найти из уравнений:
12 1
21 2
p
p



23 2
32 3
p
p



34 3
43 4
p
p



1,
1
,
1
k
k
k
k k
k
p
p






1,
1
,
1
n
n
n
n n
n
p
p






которые нужно дополнить нормировочным условием:
1 1
n
i
i
p



Последовательно выразим из каждого уравнения переменные через
1
p .

78
Из первого уравнения выразим
2
p :
12 2
1 21
p
p



Из второго уравнения с учетом выражения для
2
p выразим
3
p :
23 23 12 3
2 1
32 32 21
p
p
p

 

 


Вообще, для k , k = 2, ... n, имеем:
1, 3 2,
1 12 1
,
1 1,
2 21
k
k
k
k
k
k k
k
k
p
p










 

Подставив полученные выражения для
1
p ,
2
p
, ... ,
n
p
в нормировочное условие и вынося
1
p , получаем:
1 1,
2,
1 12 1,
12 12 23 12 21 32 21
,
1 1,
2 21
,
1 21 1
1
k
k
k
k
n
n
k k
k
k
n n
p






 

 
















 
 
Остальные вероятности легко выражаются через
1
p .
Как показано в ряде работ, для существования стационарного режима необходимо и достаточно необходимо и достаточно, чтобы
1 0
p

Рассмотрим простой практический пример. Пусть небольшой компьютерный класс состоит из трех одинаковых компьютеров,каждый из которых может выходить из строя с интенсивностью

=1 компьютер/сутки. Отказавший компьютер немедленно начинает восстанавливаться, на восстановление уходят в среднем также одни сутки,

=1 сутки -1. Требуется найти вероятности числа неисправных компьютеров.
Определим возможные состояния системы:
0
S - все три компьютера исправны;
1
S - один компьютер восстанавливается, два исправны;
2
S - два компьютера восстанавливаются, один исправен;
3
S - все три компьютера восстанавливаются.
Размеченный ГСП системы показан на рис. 14.

79
Рис. 14. Процесс поломок и восстановлений компьютерного класса
Из графа видно, что процесс, протекающий в системе, представляет собой процесс гибели и размножения. Значения интенсивностей переходов для состояния с номером k определяются так: интенсивность перехода в состояние с большим номером равна
(3
)
k

 
, поскольку интенсивность поломок кратна числу исправных компьютеров
(3
)
k

; интенсивность перехода в состояние с меньшим номером равна
(
1)
k



, поскольку интенсивность восстановления кратна числу неисправных компьютеров
(
1)
k

Используя выражения для вероятностей состояний процесса гибели и размножения, получаем:
0 1
1 3
3 2 3 2 1 8
1 1
2 1 3 2 1
p



 
 


 
1 3 1 3
1 8 8
p
  
2 2 3 3
2 8 8
p
  
3 1 3 1
3 8 8
p
  
Выводы:
1. В ряде практически важных случаев протекающие в системах процессы могут быть описаны как марковские процессы с дискретным множеством состояний и непрерывным временем. Это позволяет применить для их математического описания аппарат дифференциальных уравнений Колмогорова, с помощью которых можно получить числовые характеристики процессов.
2. Особый интерес во многих прикладных задачах представляет стационарный режим, в который по истечении некоторого времени входит марковский процесс. Если такой режим существует, то предельные вероятности находятся путем решения системы

80 алгебраических линейных уравнений, получаемых из уравнений
Колмогорова дополненных нормировочным условием.
3. Важным частным случаем марковских процессов с непрерывным временем являются процессы гибели и размножения. Их обобщенное решение, получаемое на основе уравнений Колмогорова, позволяет решать целый класс практических задач и строить модели многих систем, в частности, систем массового обслуживания, которые будут рассматриваться в следующей теме.
Вопросы для самопроверки:
1. Дайте определение марковского процесса с непрерывным временем и дискретными состояниями?
2. Как описывается марковского процесса с непрерывным временем и дискретными состояниями?
3. Что такое интенсивность перехода?
4. Что такое установившийся режим?
5. Каким правилом можно пользоваться для записей уравнений
Колмогорова?
6. Что такое предельные вероятности марковского процесса?
7. При каких условиях существуют предельные вероятности состояний марковского процесса?
8. Каков физический смысл предельных вероятностей?
9. Как найти предельные вероятности системы, имеющей стационарный режим?
10. Что называется процессами гибели и размножения? Поясните на ГСП.
11. Запишите выражения для предельных вероятностей процесса гибели и размножения.
12. Приведите практические примеры процессов, описываемых как марковские процессы с непрерывным временем и дискретными состояниями.
Литература по теме:
1. Емельянов А.А., Власова Е.А., Дума Р.В., Емельянова Н.З.
Компьютерная имитация экономических процессов: Учебник / Под ред.
А.А.

Емельянова. – М.: Маркет ДС, 2010. – 464 с.
2. Саати Т.Л. Элементы теории массового обслуживания и еѐ приложения. – М.: Радио и связь, 1965. – 512 с.
3. Климов Г.П. Теория массового обслуживания. – М.:
Издательство МГУ, 2011. – 312 с.

81
Практические задания:
Задание 1.
Используя уравнения Колмогорова для системы из двух серверов
(рис 7.Рис.), проведите расчет вероятности отказа
отк
P
для следующих значений параметров:
П
Т =5 1
Т =5 2
Т =8
Ответ: 0,248
Задание 2.
Составьте систему алгебраических уравнений для нахождения предельных вероятностей для ГСП рис 5.
Задание 3.
Размеченный ГСП системы имеет вид:
Составьте систему алгебраических уравнений для нахождения предельных вероятностей.
Задание 4.
Подсистема хранения информации в корпоративной информационной системе состоит из двух дублирующих друг друга твердых дисков, имеющих одинаковые характеристики. Подсистема работоспособна, если работоспособен хотя бы один диск. Считая среднее время наработки диска на отказ
отк
T
равным 100 дням, среднее время восстановления одного диска
восст
T
равным 5 дням, законы распределения этих величин экспоненциальными, определите вероятность нахождения дисковой подсистемы в рабочем состоянии.
Ответ: 0,978.

82
Тесты для самопроверки:
1. Случайный процесс называется процессом с непрерывным временем, если … а) состояния процесса образуют непрерывное множество б) число возможных состояний процесса бесконечно в) процесс может перейти из состояния в состояние в любой момент
2. Процесс гибели и размножения описывается графом состояний и переходов … а) б) в)
3. В уравнениях Колмогорова для предельных вероятностей
i
P марковского процесса с дискретным множеством состояний и непрерывным временем … а) в левой части уравнения стоит сумма произведений вероятностей всех состояний, из которых идут стрелки в i-ое состояние, на интенсивности соответствующих потоков б) в левой части уравнения стоит сумма интенсивностей всех потоков, выводящих систему из данного состояния, умноженная на вероятность данного состояния, взятая со знаком минус в) в правой части уравнения стоит 0 г) в правой части уравнения стоит 1

83

84
Входящий поток
Выходящий поток
Очередь
Обслуживающий прибор
Рис. 15. Элементы СМО
Поток заявок (другие названия: запросы, вызовы, требования и т.д.), исходящий из источника заявок, поступает на вход СМО в случайные моменты времени для обслуживания. Этот входной поток может представлять собой вызовы от абонентов, передаваемые сообщения и т.д. Обслуживание поступившей заявки продолжается некоторое случайное время, после чего канал освобождается и готов к принятию следующей заявки. Случайный характер потока заявок приводит к тому, что в какие-то промежутки времени на входе СМО скапливается излишне большое число заявок (они либо образуют очередь, либо покидают СМО не обслуженными); в другие же периоды
СМО будет работать с недогрузкой или простаивать.
Для СМО в рамках теории массового обслуживания разработаны математические модели, которые широко применяются для количественного оценивания системных показателей. Многие модели основаны на уже рассмотренном ранее аппарате марковских процессов.
Проиллюстрируем применение теории на нескольких моделях СМО.
Вопрос 2. Моделирование одноканальной СМО с отказами.
Примером одноканальной СМО с отказами, которая является
простейшей из моделей, может служить телефонное справочное бюро.
В случае незанятой линии происходит соединение с оператором, и абонент получает ответ на заданный вопрос, в противном случае соединение не устанавливается и звонок необходимо повторить. Считая интервалы между звонками и продолжительность разговора случайными величинами, распределенными по экспоненциальному закону, процесс в такой системе можно рассматривать как марковский. Обозначив через

интенсивность входящего потока,

- интенсивность обслуживания, можно построить размеченный ГСП (рис. 16Рис.) .
Рис. 16. ГСП одноканальной СМО с отказами
Вероятности состояний системы
0
p (вероятность того, что в системе находится 0 заявок) и
1
p (вероятность того, что в системе