Уравнения колмогорова предельные вероятности состояний. Предельные вероятности состояний. Найти валовой выпуск для сбалансированной многоотраслевой экономики в модели Леонтьева, если дана матрица прямых затрат А и вектор конечного потребления У

Пусть имеется физическая система S с дискретными состояниями:

S 1 ,S 2 ,...,S n ,

в которой протекает марковский случайный процесс с непрерывным временем (непрерывная цепь Маркова). Граф состояний показан на рис. 23.

Предположим, что все интенсивности потоков событий, переводя­щих систему из состояния в состояние, постоянны:

другими словами, все потоки событий – простейшие (стационарные. пуассоновские) потоки.

Записав систему дифференциальных уравнений Колмогорова для вероятностей состояний и проинтегрировав эти уравнения при заданных начальных условиях, мы получим вероятности состояний, как функции времени, т. е. n функций:

p 1 (t), p 2 (t),…,p n (t),

при любом t дающих в сумме единицу: .

Поставим теперь следующий вопрос: что будет происходить с сис­темой S при t®¥? Будут ли функции p 1 (t), p 2 (t),…,p n (t) стремиться к каким-то пределам? Эти пределы, если они существуют, называются предельными (или «финальными») вероятностями состояний.

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

На рис. 24 показан граф состояний, удовлетворяющий постав­ленному условию: из любого состояния система может рано или позд­но перейти в любое другое. Напротив, для системы, граф состояний которой показан на рис. 25, условие не выполнено. Очевидно, что если начальное состояние такой системы S 1 то, например, состояние S 6 при t®¥ может быть достигнуто, а если начальное состояние S 2 – не может.

Предположим, что поставленное условие выполнено, и предель­ные вероятности существуют:

(i = 1, 2,..., n). (6.1)

Предельные вероятности мы будем обозначать теми же буквами р 1 , р 2 , … р n , что и сами вероятности состояний, разумея подними на этот раз не переменные величины (функции времени), а постоянные числа.

Очевидно, предельные вероятности состоянии, так же как и допредельные, в сумме должны давать единицу:

Таким образом, при t®¥ в системе S устанавливается некоторый предельный стационарный режим: он состоит в том, что система случайным образом меняет свои состояния, но вероятность каждого из них уже не зависит от времени: каждое из состояний осу­ществляется с некоторой постоянной вероятностью. Каков смысл этой вероятности? Она представляет собой не что иное, как сред­нее относительное время пребывания си­стемы в данном состоянии. Например, если у системы S три возможных состояния: S 1 ,S 2 и S 3 , причем их предельные вероят­ности равны 0,2, 0,3 и 0,5, это означает, что после перехода к устано­вившемуся режиму система S в среднем две десятых времени будет находиться в состоянии S 1 три десятых – в состоянии S 2 и полови­ну времени – в состоянии S 3 . Возникает вопрос: как вычислить пре­дельные вероятности состояний р 1 , р 2 , … р n ?

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

Действительно, в предельном (установившемся) режиме все вероят­ности состояний постоянны, значит, их производные равны нулю.

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

(так называемым «нормировочным условием») эти уравнения дают возможность вычислить все предельные вероятности

р 1 , р 2 , … р n

Пример 1 . Физическая система S имеет возможные состояния: S l , S 2 , S 3 , S 4 , размеченный граф которых дан на рис. 26 (у каждой стрелки поставлено численное значение соответствующей интенсивности). Вычислить предельные ве­роятности состояний: р 1 , р 2 , р 3 , р 4 .

Решение . Пишем уравнения Колмогорова для вероятностей состояний:

(6.3)

Полагая левые части равными нулю, получим систему алгебраических уравнений для предельных вероятностей состояний:

(6.4)

Уравнения (6.4) – так называемые однородные уравнения (без свободного члена). Как известно из алгебры, эти уравнения определяют величины р 1 , р 2 , р 3 , р 4 только с точностью до постоянного множителя. К счастью, у нас есть нор­мировочное условие:

p 1 + p 2 + p 3 + p 4 = 1, (6.5)

которое, совместно с уравнениями (64), дает возможность найти все неизвест­ные вероятности.

Действительно, выразим из (6.4) все неизвестные вероятности через одну из них, например, через p 1 . Из первого уравнения:

p 3 = 5p 1

Подставляя во второе уравнение, получим:

р 2 = 2 p 1 + 2р 3 = 12 p 1 .

Четвертое уравнение дает:

p 4 = 1/2p 2 = 6 p 1 .

Подставляя все эти выражения вместо р 2 , р 3 , р 4 в нормировочное условие (6.5), получим

p 1 + 12p 1 + 5 p 1 + 6 p 1 = 1.

24 p 1 = 1, p 1 = 1/24, p 2 =12p 1 = 1/2.

p 3 = 5p 1 = 5/24. p 4 = 6 p 1 = 1/4.

Таким образом, предельные вероятности состояний получены, они равны;

p 1 = 1/24, p 2 = 1/2, p 3 = 5/24, p 4 = 1/4 (6.6)

Это значит, что в предельном, установившемся режиме система S будет проводить в состоянии S 1 в среднем одну двадцать четвертую часть времени, в состоянии S 2 – половину времени, в состоянии S 3 – пять двадцать четвертых и в состоянии S 4 – одну четверть времени.

Заметим, что решая эту задачу, мы совсем не пользовались одним из уравнений (6.4) – третьим. Нетрудно убедиться, что оно является следствием трех остальных: складывая все четыре уравнения, мы получим тождественный нуль. С равным успехом, решая систему, мы могли бы отбросить любое из четырех уравнений (6.4).

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

Пример 2 . Граф состоянии системы показан на рис. 27. Написать ал­гебраические уравнения для предельных вероятностей состояний.

Решение . Не записывая дифференциальных уравнений, прямо пишем соот­ветствующие правые части и приравниваем их нулю; чтобы не иметь дела с от­рицательными членами, сразу переносим их в другую часть, меняя знак:

(6.7)

Чтобы в дальнейшем сразу же писать такие уравнения, полезно запом­нить следующее мнемоническое правило: «что втекает, то и вытекает», то есть для каждого состояния сумма членов, соответствующих входящим стрелкам, рав­на сумме членов, соответствующих выходящим; каждый член равен интенсивнос­ти потока событий, переводящего систему по данной стрелке, умноженной на вероятность того состояния, из которого выходит стрелка.

В дальнейшем мы во всех случаях будем пользоваться именно этим кратчай­шим способом записи уравнений для предельных вероятностей.

Пример 3 . Написать алгебраические уравнения для предельных вероят­ностей состояний системы S , граф состояний которой дан на рис. 28. Решить эти уравнения.

Решение. Пишем алгебраические уравнения для предельных вероятно­стей состояний;

Нормировочное условие;

p 1 + p 2 + p 3 = 1 . (6.9)

Выразим с помощью первых двух уравнений (6.8) р 2 и р 3 через р 1:

Подставим их в нормировочное условие (6.9):

,

откуда .

; .

Что будет происходить с вероятностями состояний при .Будут лиP 1 (t), P 2 (t), … стремится к каким-то пределам? Если эти пределы существуют и не зависят от начального состояния системы, то они называются финальными вероятностями состояний. В теории случайных процессов доказывается, что если число n состояний системы конечно и из каждого из них можно (за конечное число шагов) перейти в любое другое, то финальные вероятности существуют (это условие достаточно, но не необходимо для существования финальных вероятностей).

Предположим, что это условие выполнено и финальные вероятности существуют:

Будем обозначать их теми же буквами P 1 , P 2 , …, что и сами вероятности состояний, но подразумевая под ними не функции времени, а постоянные числа. Очевидно, они тоже образуют в сумме единицу:

. (4.10)

Как понимать эти финальные вероятности? При
в системеS устанавливается предельный стационарный режим, в ходе которого система случайным образом меняет свои состояния, но их вероятности уже не зависят от времени. Финальную вероятность состояния S i можно понимать как среднее относительное время пребывания системы в этом состоянии.

Например, если система S имеет три состояния S 1 , S 2 , S 3 и их финальные вероятности равны 0,2; 0,3; 0,5, это значит, что в предельном стационарном режиме система в среднем две десятых времени проводит в состоянии S 1 , три десятых – в состоянии S 2 и половину времени – в состоянии S 3 .

Как же вычислить финальные вероятности? Если вероятности P 1 , P 2 , … постоянны, то их производные равны нулю. Значит, чтобы найти финальные вероятности, нужно все левые части в уравнениях Колмогорова положить равными нулю и решить полученную систему уже не дифференциальных, а линейных алгебраических уравнений. Даже можно сразу по графу состояний написать систему алгебраических уравнений. Если перенести отрицательный член каждого уравнения из правой части в левую, то получим сразу систему уравнений, где слева стоит финальная вероятность данного состояния P i , умноженная на суммарную интенсивность всех потоков, ведущих из данного состояния, а справа – сумма произведений интенсивностей всех потоков, входящих в i – е состояние, на вероятности тех состояний, из которых эти потоки исходят.

Пользуясь этим правилом, напишем линейные алгебраические уравнения для финальных вероятностей состояний системы, граф состояний дан на рис. 4.9:

(4.11)

Эту систему 4-х уравнений с 4-мя неизвестными P 0 , P 1 , P 2 , P 3 можно решить воспользовавшись так называемым нормировочным условием:

, (4.12)

при этом одно (любое) из уравнений можно отбросить (оно вытекает как следствие из остальных).

Зададимся численными значениями интенсивностей λ 1 =1, λ 2 =2, μ 1 =2, μ 2 =3 и решим систему (4.11). Отбросим четвертое уравнение, добавив вместо него нормировочное условие (4.12). Уравнения примут вид:

(4.13)

Решая их, получим т.е. в предельном, стационарном режиме системаS в среднем 40% времени будет проводить в состоянии S 0 (оба узла исправны), 20% - в состоянии S 1 (первый узел ремонтируется, второй работает), 27% - в состоянии S 2 (второй узел ремонтируется, первый работает) и 13% - в состоянии S 3 полной негодности (оба узла ремонтируются). Знание этих предельных вероятностей может помочь оценить среднюю эффективность работы системы и загрузку ремонтных органов. Предположим, что система S в состоянии S 0 приносит в единицу времени доход 8 (условных единиц), в состоянии S 1 – доход 3, в состоянии S 2 – доход 5, а в состоянии S 3 – вообще не приносит дохода. Тогда, в предельном стационарном режиме средний доход в единицу времени будет . Теперь оценим загрузку ремонтных органов (рабочих), занятых ремонтов узлов 1 и 2. Узел 1 ремонтируется долю времени, равную. Узел 2 ремонтируется долю времени
.

Здесь уже может возникнуть вопрос об оптимизации решения. Допустим, что мы можем уменьшить среднее время ремонта того или другого узла (а может быть и того, и другого), но это нам обойдется в какую-то сумму. И необходимо оценить, а окупит ли увеличение дохода, связанное с ускорением ремонта, повышенные расходы на ремонт? (для этого надо будет решить систему 4-х уравнений с 4-мя неизвестными).

Пусть имеется система S c дискретными состояниями, в которой протекает марковский процесс с непрерывным временем.

Что будет с системой S при t ® ¥ ? Будут ли функции p 1 (t), p 2 (t), ..., p n (t) стремиться к каким-то пределам? Эти пределы, если они существуют, называются предельными (или "финальными") вероятностями состояний.

Можно доказать следующее общее положение :

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

Предположим, что поставленное условие выполнено, и предельные вероятности существуют:

Очевидно, предельные вероятности состояний, также, как и допредельные, в сумме должны давать единицу:

Таким образом, при t®¥ в системе S устанавливается некоторый предельный стационарный режим : он состоит в том, что система случайным образом меняет свои состояния, но вероятность каждого из них уже не зависит от времени. Каков смысл вероятности? Она представляет собой среднее относительное время пребывания системы в данном состоянии .

Как вычислить предельные вероятности? В системе уравнений Колмогорова надо положить все производные равными нулю.

Пример 1 . Вычислить предельные вероятности для системы:

Пример 2 . Написать уравнения для предельных вероятностей.

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

9. Процесс "гибели и размножения".

Марковский поцесс называется "процессом гибели и размножения", если его граф состояний вытянут в цепочку, т.е. только l n,n+1 и. l n,n-1 не равны нулю, т.е. не равны нулю только плотности вероятностей перехода в соседнее состояние.

Пример 1 . Техническое устройство состоит из трех одинаковых узлов; каждый из них может выходить из строя (отказывать); отказавшее устройство немедленно начинает восстанавливаться. Состояние системы нумеруем по числу неисправных узлов.

В дальнейшем для процесса гибели и размножения будем обозначать l n,n+1 =l n , l n,n-1 =m n .

Определим общую схему решения для процессов гибели и размножения. Напишем алгебраические уравнения для вероятностей состояний

Для первого состояния S 1 имеем:

l 1 p 1 =m 2 p 2

Для второго состояния имеем:

l 2 p 2 +m 2 p 2 =l 1 p 1 +m 3 p 3

Но в силу (9.1) можно сократить справа и слева равные друг другу члены l 1 p 1 и m 2 p 2 , получим

l 3 p 3 =m 4 p 4

и вообще для всех k

l k p k =m k+1 p k+1 для k=1,2,..., n-1

Решение этой системы есть:

p 1 +p 2 +....+p n = 1

Пример 2 . Найти предельные вероятности состояний для процесса гибели и размножения с графом

Пример 3 . Прибор состоит из трех узлов; поток отказов - простейший, среднее время безотказной работы каждого узла равно Т в. Отказавший узел сразу же начинает ремонтироваться; среднее время ремонта (восстановления) узла равно t p ; закон распределения этого вемени показательный (поток восстановлений - простейший). Найти среднюю производительность прибора, если при трех работающих узлах она равна 100%, при двух - 50%, а при одном и менее - прибор вообще не работает.

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

Граф состояний системы с проставленными у стрелок интенсивностями будем называть размеченным (см. рис. 3.1). Рассматриваемая система S имеет четыре возможных состояния: S 0 ,S 1 , S 2 , S 3 .

Вероятностью i-го состояния называется вероятность p i (t ) того, что в момент t система будет находиться в состоянии S ,. Очевидно, что для любого момента t сумма вероятностей всех состояний равна единице:

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

(3.2.)

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

В системе (3.2) независимых уравнений на единицу меньше общего числа уравнений. Поэтому для решения системы необходимо добавить уравнение (3.1).

Особенность решения дифференциальных уравнений вообще состоит в том, что требуется задать так называемые начальные условия, т.е. в данном случае вероятности состояний системы в начальный момент t = 0. Так, например, систему уравнений (15.9) естественно решать при условии, что в начальный момент обе бригады свободны и система находилась в состоянии S 0 , т.е. при начальных условиях p 0 (0) = 1, p 1 (0) = 0, p 2 (0) = 0, p 3 (0) = 0.

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

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

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

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

(3.3)

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

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

Определение 1. Если число состояний системы конечно и из каждого состояния можно перейти в любое другое за произвольное число шагов, то говорят, что такая система обладает эргодическим свойством.

Определение 2. Пусть марковский процесс характеризуется ве­роятностями перехода из состоянияiв состояниеjза времяt

p ij (t) (0?i?n; 0?j?n).

Процесс называется транзитивным, если существует такое t>0, что p ij (t)>0 (0?i?n; 0?j?n). Из определений 1 и 2 следует, что процессы в марковских цепях с эргодическим свойством являются транзитивными.

Теорема Маркова . Для любого транзитивного марковского процесса пределсуществует и не зависит от начального состоянияi.

Это означает, что при t?? в системе устанавливается неко­торый предельный стационарный режим, характеризующийся постоян­ной, не зависящей от времени, вероятностью каждого из состояний системы. При этом данная вероятность представляет собой среднее относительное время пребывания системы в данном состоянии. Это значит, что если время работы всей системы 100 ч, а вероятность состояния S 1 равна p 1 =0,15, то система будет находиться в состоянии S 1 в среднем 15 ч.

Пределы, к которым стремятся вероятности каждого из состоя­ний марковской цепи с эргодическим свойством при t??, называ­ются предельными вероятностями. При рассмотрении СМО мы будем иметь дело только с эргодическими марковскими цепями. Пусть V - некоторое подмножество множества состояний системы S , а V’ - его дополнение до S . Если множество V обладает эргодическим свойс­твом и ни из одного состояния множества V нельзя перейти ни в од­но из состояний множества V’, то множество называется замкнутым или эргодическим множеством. Эргодические системы состоят из од­ного единственного эргодического множества (S=V, V’=?) и называются поэтому неразложимыми. Если в системе S множество V"?? или в этой системе можно выделить несколько эргодических множеств S = V 1 ?V 2 ?…?V n , то такая система называется разложимой. Примеры таких систем приведены на рис.1.3.

На рис.1.3,а представлена сис­тема с двумя эргодическими множест­вами V 1 =(S 2 ,S 3 ,S 4) иV 2 (S 5 ,S 6). На рис.1.3,б эргодическое множество состоит лишь из одного состояния (S 4). Если эргодическое множест­во состоит лишь из одного состоя­ния, то это состояние называется поглощающим, так как попав в не­го однажды, процесс остается нав­сегда в поглощающем состоянии. Ха­рактерная особенность графа состо­яний неразложимой эргодической мар­ковской системы заключается в том, что каждой вершине этого графа ин­цидентны дуги как с положительной, так и с отрицательной инцидент­ностью (т.е. у каждой вершины име­ются дуги, направленные как к вер­шине, так и от нее, см., например, рис. 1.1 и 1.2).

Вычисление предельных вероят­ностей состояний для таких систем упрощается в связи с тем, что, поскольку все эти вероятности яв­ляются постоянными величинами, то их производные по времени рав­ны 0 (dp i /dt=0 для всехi). Поэтому левые части системы уравнений Колмогорова (1.7) приравниваются нулю и она превращается в систе­му линейных алгебраических уравнений

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

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

Пример . Для системы, изображенной на рис.1.2, из уравнений Колмогорова (1.7) следует

• (? 12 +? 13)p 1 =? 41 p 4 (? 41 +? 45)p 4 =? 34 p 3
• ? 25 p 1 =? 12 p 1 +? 32 p 3 ? 53 p 3 =? 52 p 2 +? 45 p 4
• (? 3 2 +? 3 4)p 4 =? 13 p 1 +? 5 3 p 5 (1.10)

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

Предельные вероятности состояний используются в ТМО значи­тельно чаще, чем решения уравнений Колмогорова, причем, зная ре­шение системы уравнений Колмогорова, можно определить момент окончания переходного процесса изменения вероятностей состояний во времени. Это дает возможность рассчитать, промежуток времени начиная от включения системы в работу, по истечении которого ве­роятности состояний достигнут своих предельных значений и будут справедливы оценки, использующие эти значения. В заключение этого параграфа рассмотрим один частный, но практически очень важный класс марковских процессов, широко применяемых при исследовании СМО. Это - процессы "размножения и гибели". К ним относятся мар­ковские цепи, представимые размеченным графом, который состоит из вытянутой цепочки состояний, изображенной на рис.1.4.

Матрица плотностей вероятностей переходов такой системы яв­ляется якобиевой (тридиагональной):

Рассматривая начальное состояние S 0 , получим в соответствии с (1.8)

01 p 0 =? 10 p 1 (1.11)

Для состояния S 1 имеем

01 p 0 +? 21 p 2 =? 10 p 1 +? 12 p 1 (1.12)

Вычитая из (1.12) равенство (1.11), получим

21 p 2 = ? 12 p 1 (1.13)

Продолжая этот процесс до n-гoсостояния включительно, получим

N , n -1 p n =? n -1, n p n -1

Из (1.11) теперь можно выразить p 1 через р 0:

p 1 =p 0 (? 01 /? 10) (1.14)

Подставляя (1.14) в (1.13), получим

p 2 =p 0 (? 01 ? 12 /? 10 ? 21)

Очевидно, что для произвольного k (1?k?n) будет справедливо вы­ражение

В соответствии с (1.15) и размеченным графом состояний, представленным на рис.1.4, можно сформулировать правило, с по­мощью которого можно выразить предельные вероятности состояний процесса "размножения и гибели" через вероятность начального сос­тояния р 0 . Это правило гласит: вероятность произвольного состоя­ния p k (l?k?n) равна вероятности начального состояния р 0 , умно­женной на дробь, числитель которой равен произведению плотностей вероятностей перехода для дуг, переводящих состояние системы сле­ва направо, а знаменатель - произведение плотностей вероятностей перехода справа налево от начального до k-гo состояний включи­тельно.

Вероятность р 0 находится из условия нормировки и выражений (1.15) следующим образом:

Выражения (1.15) и (1.16) полностью определяют предельные вероят­ности процесса "размножения и гибели".