математическое моделирование. Т 1 МАТ. Моделирование. Литература по теме 197 Вопрос Узловые операторы. 201 Вопрос Текст программной модели смо. 202 Вопрос Сборка и запуск исполнительного модуля модели. 205
 Скачать 1.51 Mb.
|
|
&12P1(t) + KlPl(t) + ^nP3(t) at Аналогично, рассматривая вершины графа S и S , получим уравнения = —&21P1 (t) + &12P2 (t) + &32P3 (t) at dP3(t) _ —■ . (^31 +^32)P3(t) at К этим уравнениям необходимо добавить нормировочное условие, которое в данном случае имеет вид P1(t) + P2(t) + P3(t) = 1 Решение этой системы уравнений в зависимости от времени можно найти либо аналитически, либо численно с учетом начальных условий. На основе рассмотренного примера можно сформулировать общее правило составления уравнений Колмогорова: В левой части каждого уравнения стоит производная вероятности какого-то (j-го) состояния. В правой части - сумма произведений вероятностей всех состояний, из которых идут стрелки в данное состояние, на интенсивности соответствующих потоков, минус суммарная интенсивность всех потоков, выводящих систему из данного (j-го) состояния, умноженная на вероятность данного (j-го) состояния. Это правило составления дифференциальных уравнений для вероятностей состояний является универсальным и применимо к любому марковскому процессу с непрерывным временем; с его помощью можно без проведения специального рассмотрения условий задачи, записывать дифференциальные уравнения для вероятностей состояний непосредственно по размеченному графу состояний. Весьма важным является вопрос о том, что будет происходить с системой при t ^да, а именно, будут ли функции p(t), p2(t), ... , pn(t) стремиться к каким-то пределам. Эти пределы, если они существуют, называются предельными (или финальными) вероятностями состояний. В самой системе S устанавливается некоторый предельный стационарный режим: система хоть и меняет случайным образом свои состояния, но вероятность каждого из них не зависит от времени и каждое из состояний осуществляется с некоторой постоянной вероятностью, которая представляет собой среднее относительное время пребывания системы в данном состоянии. Например, если у системы три возможных состояния: ^, S2 и S3, причем их предельные вероятности равны 0,2; 0,3 и 0,5, то это означает, что после перехода к установившемуся режиму система в среднем 20% времени будет находиться в состоянии S, 30% — в состоянии S2 и 50% — в состоянии S3. Доказано, что если число состояний системы S конечно и из каждого состояния можно перейти (за то или иное число шагов) в любое другое, то предельные вероятности состояний существуют и не зависят от начального состояния системы. В этом случае в процессе моделирования системы можно ограничиваться для нахождения ее параметров одной достаточно длинной реализацией процесса. Вычислить все предельные вероятности можно, перейдя от системы дифференциальных уравнений к системе линейных алгебраических уравнений, дополнив ее нормировочным условием. Найдем финальные вероятности pj системы уравнений для ГСП на рис 11. Полагая dpi/dt = 0 (j=1,2, 3) получаем три алгебраических уравнения, которые являются однородными. Поэтому одно из них можно отбросить. Отбросим, например, второе уравнение и вместо него запишем нормировочное условие. В результате система уравнений для финальных вероятностей примет вид: А2 P1 +A1P2 +A1P3 = 0 P1 + P2 + P3 = 1 31 +А2) P3 = 0 Из последнего уравнения следует, что Р3 = 0 Решая оставшиеся уравнения, получим Р2 Р1= 2/3, 1/3 Т.е., вектор состояния системы в стационарном режиме равен J - (f,3,o) Как мы увидели, имея размеченный ГСП системы, можно сразу написать алгебраические уравнения для предельных вероятностей состояний. Таким образом, если две непрерывные цепи Маркова имеют одинаковые графы состояний и различаются только значениями интенсивностей Aif, отсутствует необходимость находить предельные вероятности состояний для каждого из графов в отдельности, достаточно составить и решить уравнения для одного из них, а затем подставить вместо Aif соответствующие значения. Для многих часто встречающихся на практике форм графов линейные уравнения без особых затруднений решаются в алгебраическом виде. Рассмотрим практический пример. Пусть имеется система, состоящая из двух серверов, которая обрабатывает поток поступающих к ней запросов (рис. 12, а).  Рис. 12. Система с двумя серверами Средний интервал между поступлениями запросов Гя , производительность серверов неодинакова: среднее время обработки запроса первым сервером составляет Тх, второго - Т2, Т < Т2. Если в момент поступления в систему очередной заявки: первый сервер свободен, то заявка берется на обработку первым сервером; первый сервер занят обслуживанием, а второй сервер свободен, то заявка берется на обработку вторым сервером; оба сервера заняты обслуживанием, то заявка теряется. В предположении экспоненциального характера распределения Тя, Т, Т2 требуется найти вероятность отказа в обслуживании запроса Ротк . В силу экспоненциального характера распределения временных параметров процесс можно считать марковским. Поэтому решение задачи начинаем с построения ГСП процесса. Исследуемый процесс может находиться в следующих состояниях: - оба сервера свободны, - первый сервер занят, второй свободен, - первый сервер свободен, второй занят, - оба сервера заняты. Если обозначить Л = 1/ Тя - интенсивность потока запросов к системе; / = 1/ Т - интенсивность обработки запросов первым сервером; /2 = 1/ Т2 - интенсивность обработки запросов вторым сервером. то размеченный ГСП будет иметь вид, показанный на рис. 12, б. Соответствующие уравнения Колмогорова для установившегося режима: -Лр00 + /Р10 + /2Р01 = 0 Лр00 - (X + /1)Рю + /Р11 = 0 -(Я + /2) Р01 + /1Р1 = 0 Лр10 +Лр01 - / +/2)Р11 = 0 Вероятность отказа в обработке запроса есть не что иное как вероятность Р занятости обслуживанием обоих серверов. Оставив из имеющихся уравнений три и дополнив их условием нормировки: Р + р + р + р = 0 р 00 + 1 10 + 1 01 + 1 11 0 решаем далее полученную систему линейных алгебраических уравнений (например, методом подстановки). Вопрос 3. Процессы гибели и размножения. Важной разновидностью непрерывных марковских цепей является процесс гибели и размножения. Происхождение термин берет в биологии, где такая схема описывает процессы изменения численности популяции, распространения эпидемий и т.п. Марковская непрерывная цепь называется процессом гибели и размножения, если ее ГСП имеет вид, представленный на рис. 13.  Рис. 13' Процесс гибели и размножения Граф на рисунке имеет вид цепочки, крайние звенья которой связаны переходами только с одним соседним звеном, а каждое внутреннее связано прямой и обратной связью с каждым из соседних. Величины \2, ,■■■ \_Хп (интенсивности переходов системы из состояния в состояние слева направо) можно трактовать как интенсивности рождения, величины Xlx, , ■■■ \п_х (интенсивности переходов системы из состояния в состояние справа налево) - как интенсивности гибели. Запишем алгебраические уравнения для вероятностей состояний в установившемся режиме. Для каждого состояния поток, втекающий в данное состояние, должен равняться потоку, вытекающему из данного состояния. Для состояния S : Л2Л _ Для состояния S : ^2 + _ Л2Л + 4^3 С учетом равенства для состояния S1 равные друг другу члены справа и слева можно сократить, поэтому получаем: ^23p2 _ A32p3 Аналогично, для S3: KP3 = ^43P4 Вообще для состояния k, k = 2,..n, имеем: \-1,kPk-1 = \ ,k-1Pk Таким образом, предельные вероятности состояний P , P , ... , P процесса размножения и гибели можно найти из уравнений: Л2Л = ^2 = ^3 KP3 = ^43P4 \-1,kPk-1 = \ ,k-1Pk \-1,nPn-1 = \,n-1Pn которые нужно дополнить нормировочным условием: n Ilp. = 1 i=1 Последовательно выразим из каждого уравнения переменные через P . Из первого уравнения выразим P : P2 P1 Л21 Из второго уравнения с учетом выражения для P выразим P : P3 =-Т3 Pi =22 P1 Вообще, для k , k = 2, ... n, имеем: p - К-из K-f,k-1 \f "k,k-1 Kk-1,k-f "21 Подставив полученные выражения для p , p2 , ... , p в нормировочное условие и вынося p, получаем: 1 \ -I-Af-I- "23"^ | Кk-1, k"k-2,k-1 ••• ".2 ^ | Kn-1,n ••• "12 "21 К32К21 Kk,k-Л-1,k-f ••• "21 "n,n-1 ••• "21 Остальные вероятности легко выражаются через р. Как показано в ряде работ, для существования стационарного режима необходимо и достаточно необходимо и достаточно, чтобы Р1 > 0. Рассмотрим простой практический пример. Пусть небольшой компьютерный класс состоит из трех одинаковых компьютеров, каждый из которых может выходить из строя с интенсивностью "=1 компьютер/сутки. Отказавший компьютер немедленно начинает восстанавливаться, на восстановление уходят в среднем также одни сутки, ju=1 сутки -1. Требуется найти вероятности числа неисправных компьютеров. Определим возможные состояния системы: S0 - все три компьютера исправны; S - один компьютер восстанавливается, два исправны; S - два компьютера восстанавливаются, один исправен; S - все три компьютера восстанавливаются. Размеченный ГСП системы показан на рис. 14.  Рис. 14. Процесс поломок и восстановлений компьютерного класса Из графа видно, что процесс, протекающий в системе, представляет собой процесс гибели и размножения. Значения интенсивностей переходов для состояния с номером k определяются так: интенсивность перехода в состояние с большим номером равна Я-(3-k), поскольку интенсивность поломок кратна числу исправных компьютеров (3 - к); интенсивность перехода в состояние с меньшим номером равна j (к -1) , поскольку интенсивность восстановления кратна числу неисправных компьютеров (к -1). Используя выражения для вероятностей состояний процесса гибели и размножения, получаем: F(0, 02, ... , вп) = P(Ti <01, 7*2 <^2, ... , 7 <вп) , 21 tk = k \ k , k = 1,2,...,6 28 fT ' 29 у2 _ У1 (f к - fk) 29 Лнабл / , rT ' 29 Pk =^p0,k = 1,2- n 84 л — — — — — — 84 — 84 Проверка графа модели. 196 Вопросы для самопроверки: 197 Литература по теме: 197 Вопрос 2. Узловые операторы. 201 Вопрос 3. Текст программной модели СМО. 202 Вопрос 4. Сборка и запуск исполнительного модуля модели. 205 File \cnv-> Projects -> Win32 Application. 206 • Build Execute ModelPro.exe. 207 Вопрос 5. Результаты моделирования. 208 Вопросы для самопроверки: 211 3.Какую функцию выполняет предложение #include ? 211 term? 211 Литература по теме: 211 Вопрос 2. Использование узла parent. 215 Вопрос 3. Использование узлов pay, rent, down. 216 Вопрос 4. Многослойная модель бизнес-процесса. 219 Выводы: 225 Вопросы для самопроверки: 226 Литература по теме: 226 Вопрос 2. Определение нестандартных выходных параметров. 230 Вопрос 3. Отладка модели. 233 Вопрос 4. Построение гистограмм. 235 Вопросы для самопроверки: 240 Литература по теме: 240 Вопрос 2. Отсеивающий эксперимент 246 F"=! F 249 Вопрос 33. Аналитическое описание функции отклика. 250 ■ n(n - l)(n - 2)...(n - i -1) 251 1-2 • ....i 251 , 4 • 3 • 2 251 4 1-2 • 3 251 b + bx + bx +... + bx = bx + bx + bx +... + bx =V bx 251 Вопрос 4. Поиск оптимальных значений. 253 Выводы: 254 Вопросы для самопроверки: 255 Приложение 255 Узловые операторы системы Pilgrim 255 1 1 8 8 _ 2 3_3 p _ 2 ^ 8 _ 8 1 3 1 p3 _ _ _ 3 3 8 8 Выводы: В ряде практически важных случаев протекающие в системах процессы могут быть описаны как марковские процессы с дискретным множеством состояний и непрерывным временем. Это позволяет применить для их математического описания аппарат дифференциальных уравнений Колмогорова, с помощью которых можно получить числовые характеристики процессов. Особый интерес во многих прикладных задачах представляет стационарный режим, в который по истечении некоторого времени входит марковский процесс. Если такой режим существует, то предельные вероятности находятся путем решения системы алгебраических линейных уравнений, получаемых из уравнений Колмогорова дополненных нормировочным условием. Важным частным случаем марковских процессов с непрерывным временем являются процессы гибели и размножения. Их обобщенное решение, получаемое на основе уравнений Колмогорова, позволяет решать целый класс практических задач и строить модели многих систем, в частности, систем массового обслуживания, которые будут рассматриваться в следующей теме. Вопросы для самопроверки: Дайте определение марковского процесса с непрерывным временем и дискретными состояниями? Как описывается марковского процесса с непрерывным временем и дискретными состояниями? Что такое интенсивность перехода? Что такое установившийся режим? Каким правилом можно пользоваться для записей уравнений Колмогорова? Что такое предельные вероятности марковского процесса? При каких условиях существуют предельные вероятности состояний марковского процесса? Каков физический смысл предельных вероятностей? Как найти предельные вероятности системы, имеющей стационарный режим? Что называется процессами гибели и размножения? Поясните на ГСП. Запишите выражения для предельных вероятностей процесса гибели и размножения. Приведите практические примеры процессов, описываемых как марковские процессы с непрерывным временем и дискретными состояниями. Литература по теме: Емельянов А.А., Власова Е.А., Дума Р.В., Емельянова Н.З. Компьютерная имитация экономических процессов: Учебник / Под ред. А.А. Емельянова. - М.: Маркет ДС, 2010. - 464 с. Саати Т.Л. Элементы теории массового обслуживания и её приложения. - М.: Радио и связь, 1965. - 512 с. Климов Г.П. Теория массового обслуживания. - М.: Издательство МГУ, 2011. - 312 с. |