33.Графы состояний смо. Марковская цепь. Случайные процессы. Уравнения Колмогорова

Рассмотрим математическое описание марковского процесса с дискретными состояниями и непрерывным временем на примере процесса, граф которого изображен на рис. 1. Будем полагать, что все переходы системы из состояния Si в Sj происходят под воздействием простейших потоков событий с интенсивностями состояний λij (i, j = 0, 1, 2, 3).

Переход системы из состояния S0 в состояние S1 будет происходить под воздействием потока отказов первого узла, а обратный переход из состояния S1 в S0 – под воздействием потока и событий, связанных с окончанием ремонтов первого узла и т.п. Граф состояний системы с проставленными у стрелок интенсивностями будем называть размеченным. Рассматриваемая система S имеет четыре возможных состояния: S0, S1, S2, S3 . Назовем вероятностью i-го состояния вероятность pi(t) того, что в момент t система будет находиться в состоянии Si. Очевидно, что для любого момента t сумма вероятностей всех состояний равна единице:

₃

Σ pi (t) = 1. (22)

^{i = 0}

Рассмотрим систему в момент t и, задав малый интервал времени Δt, найдем вероятность p0 (t + Δt) того, что система в момент t + Δt будет находиться в состоянии S0 . Это достигается разными способами.

1. Система в момент t с вероятностью p0 (t), находясь в состоянии S₀, за время Δt не вышла из него. Вывести систему из этого состояния можно суммарным простейшим потоком с интенсивностью (λ₀₁ + λ₀₂), т.е. в соответствии с (21) с вероятностью, приближенно равной (λ01 + λ02) Δt. Вероятность же того, что система не выйдет из состояния S0, равна по теореме умножения вероятностей

p0 (t) [1 – ( λ01 + λ02) Δt] .

2. Система в момент t с вероятностями p1 (t) (или p2 (t)) находилась в состоянии S1 или S2 , и за время Δt перешла в состояние S0 . Потоком интенсивностью λ10 (или λ20 , как следует из рис. 1) система перейдет в состояние S₀ с вероятностью, приближенно равной λ10 Δt (или λ20 Δt). Вероятность того, что система будет находиться в состоянии S0 по этому способу, равна p1(t) λ10 Δt (или p2(t) λ20 Δt).

Применяя теорему сложения вероятностей, получим p0 (t + Δt) = p1(t) λ10 Δt + p2(t) λ20 Δt + p0 (t) [ 1 – (λ01 + λ02) Δt ] , откуда p0 (t + Δt)/ Δt = p1(t) λ10 + p2(t) λ20 – p0 (t) (λ01 + λ02).

Переходя к пределу в левой части последнего равенства получим: p0′ (t) = λ10 p1(t) + λ20 p2(t) – (λ01 + λ02) p0 (t).

Получено дифференциальное уравнение первого порядка, т.е. уравнение, содержащее как саму неизвестную функцию, так и ее производную первого порядка.

Рассуждая аналогично для других состояний системы S, получим систему дифференциальных уравнений, которая носит название системы

дифференциальных уравнений Колмогорова для вероятностей состояний:

p0′ (t) = λ10 p1(t) + λ20 p2(t) – (λ01 + λ02) p0 (t)

p1′ (t) = λ01 p0(t) + λ31 p3(t) – (λ10 + λ13) p1 (t)

p2′ (t) = λ02 p0(t) + λ32 p3(t) – (λ20 + λ23) p2 (t)

p3′ (t) = λ13 p1(t) + λ23 p2(t) – (λ31 + λ32) p3 (t).

Сформулируем правило составления уравнений Колмогорова. В левой части каждого из них стоит производная вероятностей i-го состояния.

В правой части – сумма произведений вероятностей всех состояний (из которых идут дуги в данное состояние) на интенсивности соответствующих потоков событий минус суммарная интенсивность всех потоков, выводящих систему из данного состояния, умноженная на вероятность данного состояния.

В системе (23) независимых уравнений на единицу меньше общего числа уравнений, поэтому для решения системы для каждого фиксированного t необходимо добавить еще уравнение (22). Особенность решения дифференциальных уравнений состоит в том, что необходимо задать начальные условия уравнений, т.е. в данном случае вероятности состояний системы в начальный момент времени t = 0 .

Например, систему уравнений (23) естественно решать при условии, что в начальный момент времени t = 0 оба узла исправны и система находится в состоянии S0, т.е. при начальном условии p0 (0) = 1, p1 (0) = p2(0)= p3 (0) = 0

Уравнения Колмогорова дают возможность найти все вероятности состояний как функции времени. Особый интерес представляют вероятности системы pi (t) в предельном стационарном решении, т.е. при t → ∞ , которые называются предельными (или финальными) вероятностями состояний.

В теории случайных процессов доказывается, что если число состояний системы конечно и из каждого из них можно (за конечное число шагов) перейти в любое другое состояние, то предельные вероятности существуют.

Предельная вероятность состояния Si имеет вполне определенный смысл: она показывает среднее относительное время пребывания системы в этом состоянии. Например, если предельная вероятность состояния S0 , т.е. р0= 0,5, то это означает, что в среднем половину времени система находится в состоянии S0 .

Так как предельные вероятности постоянны, то, заменяя в уравнениях Колмогорова их производные нулевыми значениями, получим систему линейных алгебраических уравнений, описывающих стационарный режим.

Для системы S с графом состояний, изображенном на рис. 1, такая система уравнений имеет вид:

( λ01 + λ02) p0 (t) = λ10 p1(t) + λ20 p2(t)

(λ10 + λ13) p1 (t) = λ01 p0(t) + λ31 p3(t)

(λ20 + λ23) p2 (t) = λ02 p0(t) + λ32 p3(t)

(λ31 + λ32) p3 (t) = λ13 p1(t) + λ23 p2(t)

Система (24) может быть получена непосредственно по размеченному графу состояний, если руководствоваться правилом, согласно которому в левой части уравнений стоит предельная вероятность данного состояния pi, умноженная на суммарную интенсивность всех потоков, входящих в i-е состояние, на вероятности тех состояний, из которых эти потоки исходят.

Пример. Найти предельные вероятности для системы, граф состояний которой изображен на рис. 1 при λ01 = 1, λ02 = 2, λ10 = 2, λ13 = 2, λ20 = 3, λ23 =1, λ31 = 3, λ32 = 2.

Система алгебраических уравнений для этого случая согласно (24)

имеет вид:

3 p0 = 2 p1 + 3 p2

4 p1 = p0 + 3 p2

4 p2 = 2 p0 + 2 p3

p0 + p1 + p2 + p3 = 1

Решив линейную систему уравнений, получим p0 = 0,4; p1 = 0,2;

p2 = 0,27; p3 = 0,13; т.е. в предельном стационарном режиме система S в среднем 40% времени будет находиться в состоянии S0 (оба узла исправны), 13% времени в состоянии S1 (первый узел ремонтируется, второй работает), 27% – в состоянии S2 (второй узел ремонтируется, первый работает) и 13% – в состоянии S3 (оба узла ремонтируются). Определим чистый доход от эксплуатации в стационарном режиме рассмотренной системы S в условиях, что в единицу времени исправная работа узла один и узла два приносит доход соответственно 10 и 6 денежных единиц, а их ремонт требует соответственно затрат 11 и 2 денежных единиц.

Оценим экономическую эффективность имеющейся возможности уменьшения вдвое среднего времени ремонта каждого из двух узлов, если при этом придется вдвое увеличить затраты на ремонт каждого узла (в единицу времени).

Для решения этой задачи с учетом полученных значений p0, p1, p2, p3 определим долю времени исправной работы первого узла, т.е. p0 + p3 = 0,4 + 0,27 = 0,67 и долю времени исправной работы второго узла p0 + p1 = 0,4 + 0,2 = 0,6.

В то же время первый узел находится в ремонте в среднем долю времени, равную p1 + p3 = 0,2 + 0,13 = 0,33, а второй узел p2 + p3 = 0,27 + 0,13 = 0,40. Поэтому средний чистый доход в единицу времени от эксплуатации системы равен Д = 0,67·10 + 0,6·6 – 0,33·4 – 0,4·2 = 8,18 денежных единиц. Уменьшение вдвое среднего времени ремонта каждого узла будет означать увеличение вдвое интенсивностей потока «окончания ремонтов» каждого узла, т.е. теперь λ10 = 4, λ20 = 6, λ31 = 6, λ32 = 4.

Система уравнений, описывающая стационарный режим системы S, будет иметь вид:

3 p0 = 4 p1 + 6 p2

4 p1 = p0 + 6 p2

7 p2 = 2 p0 + 4 p3

p0 + p1 + p2 + p3 = 1

Решив систему, получим p0 = 0,6, p1 = 0,15, p2 = 0,2, p3 = 0,05 . Учитывая, что p0 + p2 = 0,6 + 0,2 = 0,8; p0 + p1 = 0,6 + 0,15 = 0,75; p1 + p3 = 0,15 + 0,05 = 0,2; p2 + p3 = 0,2 + 0,05 = 0,25, а затраты на ремонт первого и второго узла составляют соответственно 8 и 4 денежных единиц, вычислим чистый средний доход в единицу времени: Д1 = 0,8·10 + 0,75·6 – 0,2·8 – 0,25·4 = 9,99 денежных единиц. Так как Д1 > Д (примерно на 20%), то экономическая целесообразность ускорения ремонта узлов очевидна.

Процессы "рождения-гибели" среди однородных Марковских процессов

В теории массового обслуживания широкое распространение имеет специальный класс случайных процессов – так называемый процесс размножения и гибели. Название этого процесса связано с рядом задач, которые описывают динамику биологических популяций. Граф состояний процесса размножения и гибели имеет вид, представленный на рис. 3.

Рис. 3. Граф состояний процесса размножения и гибели

Рассмотрим упорядоченное множество состояний системы S0, S1, S2,.., Sk. Переходы могут осуществляться из любого состояния только в состояние с соседним номером, т.е. из состояния S_k возможны только переходы в состояние S_{k – 1} или S_{k + 1 .} Будем полагать, что все потоки событий простейшие, с соответствующими интенсивностями λ_{k, k +1} или λ_{k + 1, k} . По графу состояний на рис. 3 сформируем систему уравнений для предельных вероятностей состояний. В соответствии с правилами составления таких уравнений для состояния S0 получим

λ01 p0 = λ10 p1 (26)

Для состояния S1 соответствующее уравнение имеет вид:

(λ12 + λ10) p1 = λ01 p0 + λ21 p2 .

Это уравнение с учетом преобразуется к виду:

λ12 p1 = λ21 p2 .

Аналогично, записывая уравнения для предельных вероятностей

других состояний, получим следующую систему уравнений:

λ 01 p0 = λ10 p1

λ12 p1 = λ21 p2 (28)

……………..

λ_{k – 1, k} p_{k – 1} = λ_{k, k + 1} p_k

……………..

λ_{n – 1, n} p_{n – 1} = λ_{n, n + 1} p_n

к которой добавляется условие:

p0 + p1 + p2 +…+ pn = 1 . (28.1)

Решая систему (28) – (28.1), получим:

p0 = (1 + λ01/ λ10 + λ12/ λ10 + (λn – 1,n … λ12 λ01)/ (λn,n – 1 … λ21 λ10), (29)

p1 = λ01/ λ10 p0, p2 = λ12 λ01/ λ21 λ10 p0 ,…, pn= λn – 1,n … λ12 λ01/ λn,n – 1 … λ21 λ10 p0 (30)

Заметим, что в (30) для p1, p2, p3,…, pn коэффициенты при p0 есть слагаемые, стоящие после единицы в формуле (29). Числители этих коэффициентов есть произведение всех интенсивностей, стоящих у дуг графа, ведущих справа налево до состояния Sk Пример. Процесс гибели и размножения представлен графом состояния

на рис. 4. Найти предельные вероятности состояний.

Рис. 4. Граф состояний примера

Используя (29), найдем p0 :

p0 =( 1 +1/4+ 2 · 1/3 · 4)

Используя (30), получим

p1 = 1/4 · 0,706 = 0,176; p2 =(2 · 1/3 · 4) 0,176 = 0,118,

т.е. в установившемся режиме в среднем 70,6% времени система будет

находиться в состоянии S0, 17,6% – в состоянии S1 и 11,8% – в состоянии S2.