Моделирование систем лекция. Моделирование систем. Литература по теме Тема Модели на основе метода статистических испытаний
 Скачать 2.59 Mb.
|
|
Тема 4. Марковские процессы. Модели систем массового обслуживания Цели изучения темы: познакомиться с понятием марковского процесса; познакомиться с математическим аппаратом моделирования дискретно протекающих марковских процессов. Задачи изучения темы: изучить способ математического описания марковских процессов; научиться определять характеристики марковских процессов с дискретным временем и дискретным множеством состояний. Успешно изучив тему, Вы: получите представление о: сущности марковских процессов и их классификации; как формулируются задачи в терминах марковского процесса; способах построения математической модели и нахождения с ее помощью значений нужных показателей; будете знать: как описать протекающие процессы с помощью графа состояний и переходов; как найти вектор вероятностей состояния процесса на определенном шаге; как вычислить предельные вероятности процесса. Вопросы темы: 1. Понятие марковского процесса. 2. Классификация марковских процессов. 3. Граф состояний и переходов. 4. Дискретные цепи Маркова. 5. Уравнения Колмогорова. 6. Процессы гибели и размножения. 7. Оптимизация показателей многоканальной СМО с отказами. 8. Модель системы массового обслуживания с неограниченной очередью. Формула Хинчина – Полачека. 50 Вопрос 1. Понятие марковского процесса. Постановка многих задач анализа и, в особенности, проектирования систем связаны с необходимостью проведения оценивания количественных показателей протекающих в системе процессов. Часто поведение этих развивающихся во времени процессов в силу действия различных случайных факторов не удается исследовать во всех деталях. Следствием этого является невозможность в отличие от детерминированных систем однозначно предсказать поведение системы в какой-то момент в будущем. Такие системы и процессы, как это уже было определено ранее, носят название стохастических. Их анализ целесообразно проводить, рассматривая их как случайные процессы, ход и исход которых зависят от ряда случайных факторов, сопровождающих их развитие. Для нахождения числовых значений нужных параметров применяются как аналитические, так и имитационные модели. В настоящей и следующей теме будет рассмотрен подход на основе аналитических моделей. Построение аналитической модели в случае стохастических процессов означает необходимость построения некоторой вероятностной модели явления, в которой будут учтены обусловливающие его развитие случайные факторы. Для математического описания многих случайных процессов может быть применен аппарат, разработанный в теории вероятностей для так называемых марковских случайных процессов. Случайный процесс, протекающий в системе S, называется марковским (или процессом без последействия), если он обладает следующим свойством: для каждого момента времени t 0 вероятность любого состояния системы в будущем (при t>t 0 ) зависит только от ее состояния в настоящем (при t= t 0 ) и не зависит от того, когда и каким образом система пришла в это состояние (т.е. как развивался процесс в прошлом). Другими словами, в марковском случайном процессе будущее развитие зависит только от его настоящего состояния и не зависит от «предыстории» процесса. Вопрос 2. Классификация марковских процессов. Марковские случайные процессы делятся на классы. Основными классифицирующими признаками являются: множество состояний, в которых может находиться система; моменты времени, в которых происходит изменение состояния системы. 51 Случайный процесс называется процессом с дискретными состояниями, если возможные состояния системы S 1 , S 2 , S 3 ,... можно перечислить (перенумеровать) одно за другим, а сам процесс состоит в том, что время от времени система S скачком (мгновенно) переходит из одного состояния в другое. Кроме процессов с дискретными состояниями существуют случайные процессы с непрерывными состояниями: для этих процессов характерен постепенный, плавный переход из состояния в состояние. Например, процесс изменения напряжения в осветительной сети представляет собой случайный процесс с непрерывными состояниями. Если переходы системы из состояния в состояние возможны только в определенные моменты времени t 1 , t 2 , t 3 ,…, то марковский процесс относится к процессам с дискретным временем. В противном случае имеет место процесс с непрерывным временем. Вопрос 3. Граф состояний и переходов. Анализ случайных процессов с дискретными состояниями обычно проводится с помощью графа состояний и переходов (ГСП). Пусть имеется система S с n дискретными состояниями: S1, S2, S3,…, Sn. Каждое состояние изображается окружностью или прямоугольником (вершина), а возможные переходы из состояния в состояние («перескоки») – стрелками (дугами), соединяющими эти вершины (рис. 8а). Рис. 8. Пример неразмеченного (а) и размеченного (б) ГСП 52 Заметим, что стрелками можно отмечать только непосредственные переходы из состояния в состояние; если система может перейти из состояния S 1 в S 5 только через S 2 , то стрелками отмечаются только переходы S 1 –S 2 и S 2 –S 5 , но не S 1 –S 5 Удобно также пользоваться размеченным графом, который графически изображает не только возможные состояния системы и возможные переходы из состояния в состояние, но также и значения вероятностей перехода (рис. 8б), о которых речь будет идти ниже. Вопрос 4. Дискретные цепи Маркова. Пусть система S может находиться в состояниях: S1, S2, S3, …, Sn, и изменения состояния системы возможны только в моменты: t1, t2, t3, …, tn. Будем называть эти моменты шагами, или этапами процесса и рассматривать протекающий в системе S случайный процесс как функцию целочисленного аргумента m = 1, 2,..., k,..., обозначающего номер шага. Указанный случайный процесс состоит в том, что в последовательные моменты времени t 1 , t 2 ,..., t k ,... система S оказывается в тех или иных состояниях. Процесс, происходящий в системе, можно представить как последовательность (цепочку) событий, например: (0) (1) ( ) ( ) 1 2 , ,... ,..., i n i n S S S S , называемую марковской цепью, где для каждого шага вероятность перехода из любого состояния S i в любое S j не зависит от того, когда и как система пришла в состояние S i Марковскую цепь можно описать с помощью вероятностей состояний, в которых находится система на каком-то шаге. Пусть в любой момент времени (после любого шага) система может пребывать в одном из состояний: S1, S2, S3, …,.Sn, 53 т.е., в результате шага k осуществится одно из полной группы несовместных событий: ( ) ( ) ( ) ( ) 1 2 , ,.... ,..., k k k k i n S S S S . Обозначив вероятности этих событий для k -го шага через ( ) ( ) ( ) ( ) 1 1 2 2 ( ) ( ), ( ) ( ), ... ( ) ( ),... ( ) ( ) k k k k i i i n p k p S p k p S p k p S p k p S , легко видеть, что для каждого шага k 1 2 ( ) ( ) ... ( ) ... ( ) 1 i n p k p k p k p k , поскольку ( ), 1, i p k i n , представляют собой вероятности появления полной группы событий. Вероятности ( ), 1, i p k i n называются вероятностями состояния. Для любого шага (момента времени t 1 ,t 2 ,..., t k ,... или номера 1,2,...,k,...) существуют некоторые вероятности перехода системы из любого состояния в любое другое (некоторые из них равны нулю, если непосредственный переход за один шаг невозможен), а также вероятность задержки системы в данном состоянии. Эти вероятности называются переходными вероятностями марковской цепи. Если значения переходных вероятностей не зависят от номера шага, то марковская цепь называется однородной, или стационарной. В противном случае марковская цепь является неоднородной, или нестационарной. Если из состояния S i не исходит ни одной стрелки (переход из него ни в какое другое состояние невозможен, например, S 3 графа рис. 8), соответствующая вероятность задержки Р ii равна единице. Графу системы, содержащему n вершин, можно поставить в соответствие матрицу n×n, элементами которой являются вероятности переходов pij между вершинами графа, называемую матрицей вероятностей переходов: 11 12 1 1 21 22 2 2 1 2 1 2 ( ) j n j n ij i i ij in n n nj nn P P P P P P P P P P P P P P P P P P K K K K K K K K K K K K K K K K K K K . (9) 54 Элементы матрицы переходов, означающие вероятности переходов в системе за один шаг, удовлетворяют условиям: 0 1 ij p . (10) 1 1 n ij j p . (11) Условие (10) выражает ограничение, накладываемое на значение вероятности, а условие (11) означает, что система S обязательно либо переходит из какого-то состояния Si в другое состояние, либо остается в состоянии Si (иначе говоря, события S 1 (k), S 2 (k) ,…,S i (k) ,…,S n (k) образуют полную группу событий). Обычно на графе вероятности перехода системы из одного состояния в то же самое не отмечаются, так как каждая из них дополняет до единицы сумму переходных вероятностей, соответствующих всем стрелкам, исходящим из данного состояния. Например, для графа рис. 8б значения переходных вероятностей P ii будут равны: 11 12 13 1 ( ) P P P 22 23 24 25 1 ( ) P P P P 33 1 P 44 45 1 P P 55 53 1 P P . При рассмотрении конкретных систем удобно сначала построить граф состояний, затем определить вероятность переходов системы из одного состояния в то же самое (исходя из требования равенства единице суммы элементов строк матрицы), а потом составить матрицу переходов системы. 55 Имея размеченный ГСП (или, что равносильно, матрицу переходных вероятностей) и зная начальное состояние системы, можно найти вероятности состояний р 1 (k), р 2 (k),... р n (k) после любого (k-го) шага. Они находятся с помощью следующих рекуррентных соотношений: 1 ( ) ( 1) ( 1,..., ) n i j ji j p k p k P i n , (12) или в матричной форме (k) (k-1) p =p ×P , (13) где p (k) , p (k-1) – матрицы-строки вероятностей состояний после k-го и (k- 1)-го шагов соответственно; P– матрица переходных вероятностей. Предположим, что в начальный момент (перед первым шагом) система находится в каком-то определенном состоянии, например, S m Тогда для начального момента (0) будем иметь: р1(0) = 0, р2(0) = 0,..., рm(0) = 1,..., рn(0) = 0, т.е. вероятности всех состояний равны нулю, кроме вероятности начального состояния S m , равной единице. Найдем вероятности состояний после первого шага. Мы знаем, что перед первым шагом система заведомо находится в состоянии S m . Значит, за первый шаг она перейдет в состояния S 1 , S 2 ,..., S m ,..., S n с вероятностями Pm1, Pm2,..., Pmm,..., Pmn. находящимися в m-ой строке матрицы переходных вероятностей. Таким образом, вероятности состояний после первого шага будут: 1 1 2 2 (1) , (1) , ..., (1) , ..., (1) m m m mm n mn p P p P p P p P . (14) Найдем вероятности состояний после второго шага: (2) 1 2 ( (2), (2),..., (2),..., (2)) i n p p p p p . 56 Вычислим их по формуле полной вероятности с гипотезами: после первого шага система была в состоянии S 1 ; после первого шага система была в состоянии S 2 ; ……………………………………………………… после первого шага система была в состоянии S i ; ……………………………………………………… после первого шага система была в состоянии S n Вероятности гипотез известны (14), условные вероятности перехода в состояние S i – при каждой гипотезе тоже известны и записаны в матрице переходных вероятностей. По формуле полной вероятности получим: 1 1 11 2 21 1 2 1 12 2 22 2 1 1 2 2 1 1 2 2 (2) (1) (1) (1) (2) (1) (1) (1) (2) (1) (1) (1) (2) (1) (1) (1) n n n n i i i n ni n n n n nn p p P p P p P p p P p P p P p p P p P p P p p P p P p P K K (15) Или n i j ji j=1 p (2)= p (1)P , ( 1,..., ) i n . (16) Данное выражение может быть записано в векторно-матричной форме: (2) (1) p p P . (17) В формулах (15) – (16) суммирование распространяется формально на все состояния S 1 , S 2 ,..., S m ,..., S n ; фактически учитывать надо только те из них, для которых переходные вероятности Pij отличны от нуля, т.е. те состояния, из которых может совершиться переход в состояние S l (или задержка в нем). 57 Таким образом, вероятности состояний после второго шага известны. Очевидно, после третьего шага они определяются аналогично: 1 (3) (2) ( 1,..., ) n i j ji j p p P i n , (18) и вообще после k-то шага: 1 ( ) ( 1) ( 1,..., ) n i j ji j p k p k P i n , (19) или в матричной форме ( ) ( -1) k k p p P . (20) Таким образом, вероятности p i (k) состояний после k-го шага определяются рекуррентной формулой (20) через вероятности состояний после (к – 1)-го шага; последние, в свою очередь, – через вероятности состояний после (к – 2)-го шага, и т.д. Например, пусть требуется найти вероятность перехода системы из состояния S1 в состояние S2 за 3 шага для графа на рис. 9. Рис. 9. Пример ГСП 58 Из условия следует, что p 1 (0)=1,p 2 (0)=0,p 3 (0)=0. Находим вероятности состояния после первого шага: 1 (1) 0, 7 p 2 (1) 0,1 p 3 (1) 0, 2 p . Вероятности состояния после второго шага: 1 1 11 2 21 3 31 (2) (1) (1) (1) 0,7 0,7 0,1 0, 4 0, 2 0, 2 0,57 p p p p p p p 2 1 12 2 22 3 32 (2) (1) (1) (1) 0,7 0,1 0,1 0,0 0, 2 0,5 0,17 p p p p p p p 3 1 13 2 23 3 33 (2) (1) (1) (1) 0,7 0, 2 0,1 0,6 0, 2 0,3 0, 26 p p p p p p p . Вероятность состояния S2 после третьего шага P 2 (3) : 2 1 12 2 22 3 32 (3) (2) (2) (2) 0,57 0,1 0,17 0, 0 0, 26 0,5 0,187 p p p p p p p . Если обозначить через P (m) матрицу, элементами которой являются вероятности переходов из Si в Sj за m шагов p ij (m) , то справедлива формула: ( ) m m P P , (21) где |