Математическое моделирование
Методическое пособие - Компьютеры, программирование
Другие методички по предмету Компьютеры, программирование
?ности состояний по приведенному на рис. 3 графу состояний, считая все потоки простейшими. В случайный момент времени t система может находиться в одном из состояний zi с вероятностью pi (t). Придадим t малое приращение и найдем, например, p2 (t + ) - вероятность того, что в момент t + t система будет в состоянии z2. Это может произойти, во-первых, если система в момент t была в состоянии z2 и за время не вышла из него; во-вторых, если в момент t система была в состоянии z1 или z5 и за время перешла в состояние z2.
В первом случае надо вероятность р2(t) умножить на вероятность того, что за время система не перейдет в состояние z1, z3 или z4. Суммарный поток событий, выводящий систему из состояния z2, имеет интенсивность. Значит, вероятность того, что за время система выйдет из состояния z2, равна. Отсюда вероятность первого варианта
Найдем вероятность перехода в состояние z2. Если в момент t система находилась в состоянии z1 с вероятностью p1 (t), то вероятность перехода в состояние z1 за время равна
Аналогично для состояния z5
Складывая вероятности и , получим
,
Раскроем квадратные скобки, перенесем p2 (t) в левую часть и разделим обечасти на :
.
Если устремить к нулю, то слева получим производную функции :
Аналогичные уравнения можно вывести для всех остальных состояний. Получается система дифференциальных уравнений:
(8)
Эта система линейных дифференциальных уравнений дает возможность найти вероятности состояний, если задать начальные условия. В левой части каждого уравнения стоит производная вероятности i-го состояния, а в правой - сумма произведений вероятностей всех состояний, из которых ведут стрелки в данное состояние, на интенсивности соответствующих потоков событий, минус суммарная интенсивность всех потоков, выводящих систему из данного состояния, умноженная на вероятность i-гo состояния.
Представим уравнения Колмогорова в общем виде:
(9)
Здесь учтено, что для состояний, не имеющих непосредственных переходов, можно считать
Предельные вероятности состояний. В теории случайных процессов доказывается, что если число п состояний системы конечно и из каждого состояния можно перейти в любое другое за конечное число шагов, то существуют предельные (финальные) вероятности состояний:
(10)
Сумма вероятностей всех возможных состояний равна единице. При в системе S устанавливается стационарный режим, в ходе которого система случайным образом меняет свои состояния, но их вероятностные характеристики уже не зависят от времени. Предельную вероятность состояния zi можно трактовать как среднее относительное время пребывания системы в этом состоянии.
Для вычисления предельных вероятностей нужно все левые части в уравнениях Колмогорова (9) положить равными нулю и решить полученную систему линейных алгебраических уравнений:
(11)
В связи с тем, что эти уравнения однородные, т. е. не имеют свободного члена и, значит, позволяют определить неизвестные только с точностью до произвольного множителя, следует воспользоваться нормировочным условием
(12)
и с его помощью решить систему уравнений.
Модель размножения и гибели. Разновидностью марковской модели с дискретным числом состояний и непрерывным временем является модель размножения и гибели. Она характерна тем, что ее граф состояний имеет вид цепи (рис. 4). Особенность этого графа состоит в том, что каждое из средних состояний z1, ..., zn-1 связано прямой и обратной стрелками с каждым из соседних состояний - zj правым и левым, а крайние состояния z0 и zn - только с одним соседним состоянием.
Рис. 4. Граф состояний модели размножения и гибели
В этой модели формулы для определения вероятностей состояний, полученные в результате решения уравнений Колмогорова, имеют вид:
(13)
(14)
Эти формулы часто, используют при решении задач теории массового обслуживания.
Контрольные вопросы
- Простейший поток и его свойства.
- Основная характеристика экспоненциального распределения.
- Пуассоновский поток.
- Поток Эрланга и его основные свойства.
- Какой процесс называется Марковским, описание Марковской модели?
- Для чего используется уравнение Колмогорова?
- Граф состояний модели размножения и гибели и основные формулы.
Литература
1.Альянах И.Н. Моделирование вычислительных систем, Л.: Машиностроение, 1988 г. - 223 стр.
2.Вентцель Е.С. Исследование операций: задачи, принципы, методология. М.: Наука, 1980 г. - 208 стр.
3.Зобов Б.И., Сурков А.В. Основы моделирования вычислительных систем. М.: МЛТИ, 1982 г. -32 стр.
4.Масков А.И. моделирование вычислительных систем. Пермь: ПГУ, 1982 г. - 95 стр.
Лекция 10. ХАРАКТЕРИСТИКИ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ (2 часа)
План
1. Характеристики вычислительных систем как систем массового обслуживания
. Характеристики вычислительных систем как сложных систем массового обслуживания
. Методы приближённой оценки характеристик вычислительных систем
. Характеристики вычислительных систем как систем массового обслуживания
Описание системы. Предположим, что моделью ВС является одноканальная СМО ?/p>