Моделирование систем лекция. Моделирование систем. Литература по теме Тема Модели на основе метода статистических испытаний
 Скачать 2.59 Mb.
|
|
матрица P m получается умножением матрицы P саму на себя m раз. Пусть исходное состояние системы задается вектором P (0) : (0) 1 1 ( , ,..., ) n p p p p , где pi, i=1,…,nесть вероятность того, что в начальный момент система находится в состоянии Si. 59 Тогда для нахождения вектора вероятностей состояния системы после m шагов можно воспользоваться формулой: ( ) (0) ( ) m m p p P . (22) Воспользуемся приведенными формулами для нахождения вектора состояния системы, изображенной на рис. 9, после двух шагов, для случая, когда исходное состояние системы задается вектором p (0) =(0,7;0;0,3). С помощью формулы (20) находим сначала состояние системы после первого шага p (1) : (1) (0) 0,7 0,1 0, 2 p =p ×P=(0,7;0;0,3) 0, 4 0 0, 6 0, 2 0,5 0,3 (0, 7 0, 7 0, 0 0, 4 0,3 0, 2; 0, 7 0,1 0, 0 0, 0 0,3 0,5; 0, 7 0, 2 0, 0 0, 6 0,3 0,3) (0,55; 0, 22; 0, 23) , и состояние системы после втрого шага p (2) : (2) (1) 0,7 0,1 0, 2 p =p ×P=(0,55;0,22;0,23) 0, 4 0 0, 6 (0,519; 0,17; 0,311) 0, 2 0,5 0,3 . Тот же результат получается с помощью формулы (22). Вычислив предварительно величину элементов матрицы (2) 0,7 0,1 0, 2 0,7 0,1 0, 2 0,57 0,17 0, 26 P = 0, 4 0 0, 6 × 0, 4 0 0, 6 0, 4 0,34 0, 26 0, 2 0,5 0,3 0, 2 0,5 0,3 0, 4 0,17 0, 43 , находим: (2) (0) (2) 0,57 0,17 0, 26 p =p ×P =(0,7;0,0;0,3) 0, 4 0,34 0, 26 (0,519; 0,17; 0,311) 0, 4 0,17 0, 43 . 60 Вопрос 5. Уравнения Колмогорова. Рассмотрим пример. Пусть имеем систему S, включающую один компьютер, который может находиться в одном из пяти возможных состояний: S 1 – исправен, работает. S 2 – неисправен, ожидает осмотра. S 3 – осматривается. S 4 – ремонтируется. S 5 – списан. ГСП системы показан на рис. 10: Рис. 10. Граф состояний и переходов процесса поломок и восстановлений В примере на рис. 10 выход из строя (отказ) компьютера и окончание его ремонта (восстановление) могут произойти в заранее неизвестный момент. Для описания таких процессов может быть применена схема марковского случайного процесса с дискретными состояниями и непрерывным временем. Процессы такого типа известны как непрерывные цепи Маркова. Непрерывной цепью Маркова (марковским процессом) называется процесс, для которого при 1 2 1 0 n t t t выполняется: 1 1 1 1 1 1 { ( ) | ( ) ,..., ( ) } { ( ) | ( ) } n n n n n n n n P S t S S t S S t S P S t S S t S . Здесь рассматривается ряд дискретных состояний: S 1 , S 2 , S 3 ,..., S n , однако переход системы S из состояния в состояние может происходить в произвольный момент времени. 61 Обозначим через p i (t) вероятность того, что в момент t система S будет находиться в состоянии S i (i= 1,..., n). Очевидно, для любого момента t сумма вероятностей состояний равна единице: 1 ( ) 1 n i i p t . (23) Так как события, состоящие в том, что в момент t система находится в состояниях S 1 , S 2 ,,..., S n, несовместны. Необходимо определить для любого t вероятности состояний: 1 1 ( ) ( ( ), ( ),..., ( ) ) n p t p t p t p t (24) Для того чтобы найти эти вероятности, необходимо знать характеристики процесса. Поскольку вероятность перехода системы из состояния в состояние точно в момент t будет равна нулю (так же как вероятность любого отдельного значения непрерывной случайной величины), то в качестве характеристик процесса рассматриваются плотности вероятностей, или интенсивности перехода λ ij из состояния S i в состояние S j Пусть система S в момент t находится в состоянии S r . Рассмотрим элементарный промежуток времени Δt, примыкающий к моменту t. Назовем плотностью вероятности переходаλ ij из состояния i в состояние j предел отношения вероятности перехода системы за время Δt из состояния S i в состояние S j к длине промежутка Δt: 0 0 ( ) ( ) ( ) lim lim ij ij ij ij t t p t t p t p t t t , (25) где Pij(Δt) – вероятность того, что система, находившаяся в момент t в состоянии S i за время Δt перейдет из него в состояние S j (плотность вероятностей перехода определяется только для j≠i). Из (25) следует, что при малом Δt вероятность перехода (с точностью до бесконечно малых высших порядков) равна: Pij(Δt)=λij Δt. 62 Если все плотности вероятностей перехода λ ij не зависят от t (от того, в какой момент начинается элементарный участок Δt). { ( ) | ( ) }, 1, , 1, i P S t t S S t j i n j n , то марковский процесс называется однородным, в противном случае -неоднородным. Предположим, что известны плотности вероятностей перехода λ ij для всех пар состояний S i , S j . ГСП системы с проставленными у стрелок плотностями вероятностей перехода называется размеченным графом состояний (рис. 11), на основании которого можно определить вероятности состояний р i (t) как функции времени (24). Рис. 11. Пример размеченного графа состояний и переходов Если протекающий в системе случайный процесс является марковским процессом с непрерывным временем, то для вероятностей p 1 (t) , p 2 (t) ,…p n (t) можно составить систему линейных дифференциальных уравнений, называемых уравнениями Колмогорова. Покажем, как получаются эти уравнения на примере ГСП рис. 11. Рассмотрим вначале вершину графа S 1 . Вероятность p 1 (t + Δt) того, что система в момент времени (t + Δt) окажется в состоянии, S 1 определяется на основе рассмотрения трех возможностей попасть в это состояние: 1. Система в момент времени t с вероятностью p 1 (t) находилась в состоянии S 1 и за малое время Δt не перешла в состояние S 2 . Из состояния S 1 система может быть выведена потоком интенсивностью 12 Вероятность выхода системы из состояния S 1 за время Δt с точностью до величин более высокого порядка малости по Δt равна 12 t , а вероятность сохранения состояния S 1 будет равна 12 1 t При этом вероятность того, что система останется в состоянии S 1 , согласно теореме об умножении вероятностей будет равна p 1 (t) (1- 12 Δt). 63 2. Система в момент времени t находилась в состоянии S 2 и за время Δt под воздействием потока 21 перешла в состояние S 1 с вероятностью 21 t . Вероятность того, что система будет находиться в состоянии S 1 , равна p 2 (t) 21 Δt. 3. Система в момент времени t находилась в состоянии S 3 и за время Δt под воздействием потока 31 перешла в состояние S 1 с вероятностью 31 t . Вероятность того, что система будет находиться в состоянии S 1 , равна p 3 (t) 31 Δt. По теореме сложения вероятностей получим: 1 1 12 2 21 3 31 ( ) ( )(1 ) ( ) ( ) p t t p t t p t t p t t 1 1 1 12 2 21 3 31 ( ) ( ) ( ) ( ) ( ) p t t p t p t t p t t p t t 1 1 1 12 2 21 3 31 ( ) ( ) ( ) ( ) ( ) p t t p t p t p t p t t t и, переходя к пределу Δt → 0, 1 12 1 21 2 31 3 ( ) ( ) ( ) ( ) dp t p t p t p t dt . Аналогично, рассматривая вершины графа S 2 и S 3 , получим уравнения: 2 21 1 12 2 32 3 ( ) ( ) ( ) ( ) dp t p t p t p t dt 3 31 32 3 ( ) ( ) ( ) dp t p t dt . К этим уравнениям необходимо добавить нормировочное условие, которое в данном случае имеет вид 1 2 3 ( ) ( ) ( ) 1 p t p t p t . Решение этой системы уравнений в зависимости от времени можно найти либо аналитически, либо численно с учетом начальных условий. 64 На основе рассмотренного примера можно сформулировать общее правило составления уравнений Колмогорова: В левой части каждого уравнения стоит производная вероятности какого-то (j-го) состояния. В правой части - сумма произведений вероятностей всех состояний, из которых идут стрелки в данное состояние, на интенсивности соответствующих потоков, минус суммарная интенсивность всех потоков, выводящих систему из данного (j-го) состояния, умноженная на вероятность данного (j-го) состояния. Это правило составления дифференциальных уравнений для вероятностей состояний является универсальным и применимо к любому марковскому процессу с непрерывным временем; с его помощью можно без проведения специального рассмотрения условий задачи, записывать дифференциальные уравнения для вероятностей состояний непосредственно по размеченному графу состояний. Весьма важным является вопрос о том, что будет происходить с системой при t ∞, а именно, будут ли функции р(t), р 2 (t),..., р n (t) стремиться к каким-то пределам. Эти пределы, если они существуют, называются предельными (или финальными) вероятностями состояний. В самой системе S устанавливается некоторый предельный стационарный режим: система хоть и меняет случайным образом свои состояния, но вероятность каждого из них не зависит от времени и каждое из состояний осуществляется с некоторой постоянной вероятностью, которая представляет собой среднее относительное время пребывания системы в данном состоянии. Например, если у системы три возможных состояния:S 1, S 2 и S 3 , причем их предельные вероятности равны0,2; 0,3 и 0,5, то это означает, что после перехода к установившемуся режиму система в среднем 20% времени будет находиться в состоянии S 1 , 30% – в состоянииS 2 и50% – всостоянии S 3 Доказано, что если число состояний системы S конечно и из каждого состояния можно перейти за то или иное число шагов в любое другое, то предельные вероятности состояний существуют и не зависят от начального состояния системы. В этом случае в процессе моделирования системы можно ограничиваться для нахождения ее параметров одной достаточно длинной реализацией процесса. Вычислить все предельные вероятности можно, перейдя от системы дифференциальных уравнений к системе линейных алгебраических уравнений, дополнив ее нормировочным условием. 65 Найдем финальные вероятности pj системы уравненийдля ГСПна рис.11. Полагая dpi/dt = 0 (j=1,2, 3) получаем три алгебраических уравнения, которые являютсяоднородными. Поэтому одно из них можно отбросить. Отбросим,например, второе уравнение и вместо него запишем нормировочное условие. В результате система уравнений для финальных вероятностей примет вид: 12 1 21 2 31 3 1 2 3 31 32 3 0 1 ( ) 0 p p p p p p p . Из последнего уравнения следует, что p3 = 0. Решая оставшиеся уравнения, получим p1= 2/3 p2 = 1/3. Т.е., вектор состояния системы в стационарном режиме равен 2 1 ( , , 0) 3 3 p . Как мы увидели, имея размеченный ГСП системы, можно сразу написать алгебраические уравнения для предельных вероятностей состояний. Таким образом, если две непрерывные цепи Маркова имеют одинаковые графы состояний и различаются только значениями интенсивностей λ ij , отсутствует необходимость находить предельные вероятности состояний для каждого из графов в отдельности, достаточно составить и решить уравнения для одного из них, а затем подставить вместо λ ij соответствующие значения. Для многих часто встречающихся на практике форм графов линейные уравнения без особых затруднений решаются в алгебраическом виде. 66 Вопрос 6. Процессы гибели и размножени. Важной разновидностью непрерывных марковских цепей является процесс гибели и размножения. Происхождение термин берет в биологии, где такая схема описывает процессы изменения численности популяции, распространения эпидемий и т.п. Марковская непрерывная цепь называется процессом гибели и размножения, если ее ГСП имеет вид, представленный на рис. 12. Рис. 12. Процесс гибели и размножения Граф на рисунке имеет вид цепочки, крайние звенья которой связаны переходами только с одним соседним звеном, а каждое внутреннее связано прямой и обратной связью с каждым из соседних. Величины 12 , 23 ,… n-1,n (интенсивности переходов системы из состояния в состояние слева направо) можно трактовать как интенсивности рождения, величины 21 , 32 ,… n,n-1 (интенсивности переходов системы из состояния в состояние справа налево) - как интенсивности гибели. Запишем алгебраические уравнения для вероятностей состояний в установившемся режиме. Для каждого состояния поток, втекающий в данное состояние, должен равняться потоку, вытекающему из данного состояния. Для состояния S 1 : 12 1 21 2 p p . Для состояния S 2 : 23 2 21 2 12 1 32 3 p p p p . С учетом равенства для состояния S 1 равные друг другу члены справа и слева можно сократить, поэтому получаем: 23 2 32 3 p p . 67 Аналогично, для S 3 : 34 3 43 4 p p . Вообще для состояния k, k = 2,..n, имеем: 1, 1 , 1 k k k k k k p p . Таким образом, предельные вероятности состояний p 1, p 2,…, p n процесса размножения и гибели можно найти из уравнений: 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 . Последовательно выразим из каждого уравнения переменные через p 1 Из первого уравнения выразим p 2 : 12 2 1 21 p p . 68 Из второго уравнения с учетом выражения для p 2 выразим p 3 : 23 23 12 3 2 1 32 32 21 p p p . Вообще, для k = 2,…,n, имеем: 1, 3 2, 1 12 1 , 1 1, 2 21 k k k k k k k k k p p . Подставив полученные выражения для p 1 , p 2 ,…, p n в нормировочное условие и вынося p 1 , получаем: 1 1, 2, 1 12 1, 12 23 12 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 . Остальные вероятности легко выражаются через P 1 Как показано в ряде работ, для существования стационарного режима необходимо и достаточно необходимо и достаточно, чтобы P 1 >0. Рассмотрим простой практический пример. Пусть небольшой компьютерный класс состоит из трех одинаковых компьютеров,каждый из которых может выходить из строя с интенсивностью =1 компьютер/сутки. Отказавший компьютер немедленно начинает восстанавливаться, на восстановление уходят в среднем также одни сутки, =1 сутки -1. Требуется найти вероятности числа неисправных компьютеров. Определим возможные состояния системы: три компьютера исправны; один компьютер восстанавливается, два исправны; два компьютера восстанавливаются, один исправен; все три компьютера восстанавливаются. Размеченный ГСП системы показан на рис. 13. Рис. 13. Процесс поломок и восстановлений компьютерного класса 69 Из графа видно, что процесс, протекающий в системе, представляет собой процесс гибели и размножения. Значения интенсивностей переходов для состояния с номером k определяются так: интенсивность перехода в состояние с большим номером равна λ ×(3-k), поскольку интенсивность поломок кратна числу исправных компьютеров (3-k); интенсивность перехода в состояние с меньшим номером равна μ (k-1), поскольку интенсивность восстановления кратна числу неисправных компьютеров (k-1). Используя выражения для вероятностей состояний процесса гибели и размножения, получаем: 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 . Вопрос 7. Оптимизация показателей многоканальной СМО с отказами. В многоканальной СМО имеется n каналов обслуживания, которые функционируют независимо друг от друга. Очередь отсутствует, т.е., заявки, заставшие все каналы занятыми обслуживанием, получают отказ, и уходят из системы. Входной поток заявок и поток обслуживания заявок являются пуассоновскими. Интенсивность поступления заявок равна λ, интенсивность обслуживания μ. СМО может находиться в следующих состояниях: S 0 :в СМО 0 заявок (все каналы свободны). S 1 : в СМО 1 заявка (один канал занят, остальные свободны). S k : в СМО n заявок (k каналов заняты, остальные свободны). S n : в СМО n заявок (все каналы заняты). 70 Рис. 14. ГСП многоканальной СМО с отказами Если система находится в состоянии S 1 , то поток, переводящий систему в состояние S 0 , будет иметь интенсивность μ. Если система находится в состоянии S 2 , то поток, переводящий систему в состояние S 1 , будет иметь интенсивность 2μ. (два канала порождают поток с интенсивностью в два раза большей). Если система находится в состоянии S k , то поток, переводящий систему в состояние S k-1 , будет иметь интенсивность kμ. (k каналов порождают поток с интенсивностью в k раз большей). Процесс, показанный на рис. 14, представляет собой частный случай процесса гибели и размножения. Уравнения Колмогорова для вероятностей состояний системы P 0 , P 1 ,..., P n будут иметь следующий вид: 0 0 1 1 1 ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( 1) ( ) ( ) k k k k n n dp t p t p t dt dp t p t k p t k p t dt dp t p dt 1 ( ) ( ) n t np t . (26) Предельные вероятности имеют вид 2 1 0 0 1 (1 ) 1! 2! ! ! n k N k P n k 0 , 1,..., ! k k P P k n k , (27) где 71 Соотношения (27) называются формулами Эрланга. С их помощью можно найти предельные вероятности в зависимости от значений параметров λ и μ. Характеристики стационарного режима таковы. Вероятность отказа. Заявка получает отказ, если все каналы заняты. Вероятность этого равна: 0 ! n отк n P P P n (28) Относительная пропускная способность есть вероятностьтого, что заявка будет принята к обслуживаниюи может быть найдена как дополнение P отк до 1: 1 отк q P (29) Абсолютная пропускная способность находится как: (1 ) n A q P (30) Среднее число заявок в системе (среднее число занятых каналов) можно вычислить через вероятности P 0 , P 1 ,,…, P k ,…, P n , по формуле 0 1 0 1 s n n P P n P , (31) как математическое ожидание дискретной случайной величины. Однако, проще выразить среднее число занятых каналов через абсолютную пропускную способность А, которая уже известна. Действительно, А есть среднее число заявок, обслуживаемых в единицу времени; один занятый канал обслуживает в среднем μ заявок в единицу времени; среднее число занятых каналов получается делением А на μ (1 ) n s P A n , 72 или, переходя к обозначению (1 ) s n n P . Вопрос 8. Модель системы массового обслуживания с неограниченной очередью. Формула Хинчина – Полачека. В системах с ожиданием заявки, заставшие обслуживающий прибор в момент прихода занятым, в отличие от систем с отказами не покидают систему, а остаются ждать в очереди вместе с другими ждущими заявками (рис. 7). Для описания таких систем используются показатели, характеризующие длину очереди и время ожидания заявками обслуживания. В частности, если временной интервал между появлением заявок распределен по экспоненциальному закону (пуассоновский поток), то среднее время ожидания заявки в очереди w t можно найти по формуле Хинчина – Полачека: 2 (1 ) 2(1 ) s s w t c t , (32) где t s – среднее время обслуживания заявки, σ s – среднеквадратическое (стандартное) отклонение времени обслуживания в приборе; p– коэффициент использования прибора s a t t , a t – средний интервал времени между поступлением заявок; c s – коэффициент вариации времени обслуживания s s t 73 Число заявок, ожидающих обслуживания (среднюю длина очереди), можно найти, умножив w t на величину λ: 2 (1 ) 2(1 ) s s w w t c n t , (33) что, с учетом равенства w t , дает 2 2 (1 ) 2(1 ) s w c n (34) Формула Хинчина – Полачека используется для оценивания длин очередей при проектировании информационных систем. Она применяется в случае экспоненциального распределения времени поступления при любом распределении времени обслуживания и любой дисциплине управления, лишь бы выбор очередного сообщения для обслуживания не зависел от времени обслуживания. При проектировании систем встречаются такие ситуации возникновения очередей, когда дисциплина обслуживания выбирается в зависимости от времени обслуживания. Например, в некоторых случаях для первоочередного обслуживания могут выбираться более короткие сообщения с тем, чтобы получить меньшее среднее время обслуживания (среднее время пребывания в заявки системе). При управлении линией связи (каналом Интернет) можно присвоить входным сообщениям более высокий приоритет, чем выходным, поскольку первые короче. В таких случаях уже необходимо использовать не уравнение Хинчина – Поллачека или производные от него, а более сложные уравнения или использовать метод имитационного моделирования, рассматриваемы далее. Особый интерес для практических применений представляют два случая. 74 1. Время обслуживания постоянно. При регулярном характере потока рассеяние отсутствует, поэтому среднеквадратическое отклонение σ s =0, и формулы (32), (33) преобразуются в выражения: 2 2 2 (1 ) 2(1 ) 2(1 ) s w c n , (35) и 2(1 ) s w t t (36) 2. Время обслуживания имеет экспоненциальное распределение. В случае экспоненциального распределения, как известно, среднеквадратическое отклонение σ s =1, поэтому (32), (33) принимают вид: 2 2 2 (1 ) 2(1 ) (1 ) s w c n , (37) и (1 ) s w t t (38) Большинство значений времени обслуживания в информационных системах лежит где-то между этими двумя значениями. Времена обслуживания, равные постоянной величине, встречаются редко. Даже время доступа к твердому диску непостоянно из-за различного положения массивов с данными на поверхности. Одним из примеров, иллюстрирующих случай постоянного времени обслуживания может служить занятие линии связи для передачи сообщений фиксированной длины. 75 С другой стороны, разброс времени обслуживания обычно не так велик, как в случае произвольного или экспоненциального распределения, т.е., s редко достигает значений t s . Этот случай иногда считают наихудшим и потому пользуются формулами, относящимися к экспоненциальному распределению времени обслуживания. Такой расчет может дать несколько завышенные размеры очередей и времен ожидания в них, но эта ошибка, по крайней мере, не опасна. Экспоненциальное распределение времен обслуживания не наихудший случай, с которым приходится иметь дело в действительности. Однако, если времена обслуживания, полученные при расчете очередей, оказываются распределенными хуже, чем времена с экспоненциальным распределением, то его можно рассматривать как предостережение разработчику. Если стандартное отклонение больше среднего значения, то обычно возникает необходимость в коррекции расчетов. Покажем, каким образом можно использовать формулу (33) для улучшения характеристик СМО. Пусть имеются шесть типов сообщений, требующих для своего обслуживания соответственно 15, 20, 25, 30, 35, 40 и 300 временных единиц. Число сообщений каждого типа одинаково. Стандартное отклонение указанных времен несколько выше их среднего. Значение последнего времени обслуживания намного больше других. Это приведет к тому, что сообщения будут находиться в очереди значительно дольше, чем, если бы времена обслуживания были одного порядка. В таком случае при проектировании целесообразно принять меры для уменьшения длины очереди. Например, если указанные значения связаны с длинами приходящих сообщений, то, возможно, очень длинные сообщения стоит разделить на части. Получим количественную оценку системных показателей для первоначального варианта организации информационного обмена и для двух вариантов, в которых длины сообщений передаваемых сообщений выровнены. Вычислим величины, входящие в формулу для средней длины очереди. Будем считать, что средняя продолжительность для всей группы сообщений составляет 600 временных единиц. Тогда коэффициент загрузки: 15 20 25 30 35 40 300 0, 775 600 , математическое ожидание времени обслуживания 15 20 25 30 35 40 300 66, 43 7 s t , 76 среднеквадратическое отклонение времени обслуживания 2 2 2 2 2 2 2 2 2 2 [ ] [ ] (15 20 25 30 35 40 300 ) / 7 66, 43 9155,1 95, 68 s s s M T M T , коэффициент вариации времени обслуживания 95, 68 1, 44 66, 43 s c . Подставляя в (33) получаем средний размер очереди в первоначальном варианте: 2 2 0, 775 (1 1, 44 ) 4,10 2(1 0, 775) w n . Вычислим теперь этот показатель для случая, когда последнее сообщение разбивается на два Выводы: 1. Многие задачи анализа и проектирования можно решить с использованием моделей систем массового обслуживания. Это дает возможность применять модели теории с тем же названием, многие из моделей которой получены на основе теории марковских процессов. 2. Основными показателями моделей систем с отказами являются относительная и абсолютная пропускная способность, а также вероятность отказа в обслуживании. Эти показатели для стационарного режима могут быть найдены на основе математических выражений. 3. Важными показателями для системы с ожиданием являются показатели, характеризующие нахождение заявок в очереди. Анализ таких систем может производиться в случае пуассоновского входящего потока на основе формулы Хинчина – Полачека. 4. Модели СМО можно применять для решения разнообразных практических задач. В частности, на примерах данной темы показано, как с помощью модели многоканальной СМО отказами можно решить задачу оптимизации числа каналов по критерию величины прибыли, а с помощью модели СМО с очередью определить требования к размерам заявок для уменьшения размера очереди и связанного с ней размера буферного накопителя. 77 5. Решение многих задач, связанных с анализом процессов и создания систем, основано на рассмотрении протекающих процессов как стохастических. Для оценивания показателей этих процессов и систем применяются аналитические модели. 6. Важным классом случайных процессов является марковский процесс. Марковские процессы протекают в отсутствие предыстории, что значительно упрощает их математическое описание. 7. Для описания процесса с дискретным временем и дискретными состояниями используются граф переходов и состояний, а также связанная с ним матрица переходных вероятностей. На основе этих элементов можно найти вероятности нахождения процесса в каждом из своих состояний после любого шага, для чего применяются рекуррентные или матричные выражения, которые получены на основе формулы полной вероятности. 8. В случае регулярных цепей Маркова процесс обладает предельными вероятностями нахождения в каждом из своих состояний. Эти вероятности не зависят от номера шага и могут быть найдены путем решения системы линейных уравнений, получаемой из выражения для предельных вероятностей и нормировочного условия. 9. В ряде практически важных случаев, протекающих в системах, процессы могут быть описаны как марковские процессы с дискретным множеством состояний и непрерывным временем. Это позволяет применить для их математического описания аппарат дифференциальных уравнений Колмогорова, с помощью которых можно получить числовые характеристики процессов. 10. Особый интерес во многих прикладных задачах представляет стационарный режим, в который по истечении некоторого времени входит марковский процесс. Если такой режим существует, то предельные вероятности находятся путем решения системы алгебраических линейных уравнений, получаемых из уравнений Колмогорова дополненных нормировочным условием. 11. Важным частным случаем марковских процессов с непрерывным временем являются процессы гибели и размножения. Их обобщенное решение, получаемое на основе уравнений Колмогорова, позволяет решать целый класс практических задач и строить модели многих систем, в частности, систем массового обслуживания, которые будут рассматриваться в следующей теме. 78 Вопросы для самопроверки: 1. Приведите примеры СМО с отказами. 2. Дайте краткое описание модели СМО с отказами. 3. Как получаются выражения для характеристик СМО с отказами? 4. Что такое относительная пропускная способность СМО с отказами? 5. Что такое абсолютная пропускная способность? 6. Как рассчитывается вероятность 0 p одноканальной СМО? 7. Как рассчитывается вероятность 1 p одноканальной СМО? 8. Чему равна вероятность отказа обслуживания заявки в многоканальной СМО с отказами? 9. Как подсчитывается среднее число заявок в многоканальной системе с отказами? 10. Как можно определить структуру (число каналов) многоканальной СМО по критерию максимума получаемой прибыли? 11. Какими показателями характеризуется функционирование одноканальной СМО с неограниченной очередью? 12. Что такое дисциплина обслуживания? Назовите примеры наиболее известных дисциплин. 13. Что позволяет определить формула Хинчина – Полачека? Для каких случаев справедлива формула? 14. Какие распределения времени обслуживания в одноканальной СМО с неограниченной очередью представляют наибольший интерес для практики? Опишите эти случаи. 15. Какие основные факторы влияют на значения показателей одноканальной СМО с неограниченной очередью? 16. Каким образом можно улучшить характеристики функционирования одноканальной СМО с неограниченной очередью? 17. Что такое стохастическая система? 18. Какой процесс называется марковским? 19. Как классифицируются марковские процессы? 20. Дайте определение марковского процесса с непрерывным временем и дискретными состояниями. 21. Что такое однородный марковский процесс? 22. Что такое граф состояний и переходов (ГСП) Марковской цепи? Какие бывают ГСП? 23. Что понимается под матрицей переходных вероятностей? 24. Как можно найти вероятность нахождения процесса в определенном состоянии после определенного числа шагов? 25. Что такое нестационарная марковская цепь? 26. Что такое предельные вероятности марковского процесса? 27. Каков физический смысл предельных вероятностей? 79 28. Как описывается марковского процесса с непрерывным временем и дискретными состояниями? 29. Что такое интенсивность перехода? 30. Что такое установившийся режим? 31. Каким правилом можно пользоваться для записей уравнений Колмогорова? 32. При каких условиях существуют предельные вероятности состояний марковского процесса? 33. Как найти предельные вероятности системы, имеющей стационарный режим? 34. Что называется процессами гибели и размножения? Поясните на ГСП. 35. Запишите выражения для предельных вероятностей процесса гибели и размножения. 36. Приведите практические примеры процессов, описываемых как марковские процессы с непрерывным временем и дискретными состояниями. Литература по теме: 1. Математическое моделирование системных объектов: учебное пособие / Фоменков С.А., Камаев В.А., Орлова Ю.А.; ВолгГТУ, Волгоград, 2014. – 340с. 2. Компьютерное моделирование. Курс лекций. Типовые математические модели (лекция 3) https://www.intuit.ru/studies/courses/643/499/lecture/11353 3. Теория случайных процессов. Часть 2. Марковские процессы. Учебно-методическое пособие для студентов ФПМК. ТГУ, Томск 2014. |