Марковские случайные процессы

 

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

Случайный процесс протекающий в системе называется Марковским – если для любого момента времени  ,вероятностные характеристики процесса в будущем (t > ) зависят только от его состояния в данный момент времени  (в настоящем) и не зависят от того, когда и как система пришла в это состояние в прошлом. (Например, счетчик Гейгера, регистрирующий число космических частиц).

Марковские процессы принято делить на 3 вида:

1. Марковская цепь – процесс, состояния которого дискретны (т.е. их можно перенумеровать), и время, по которому он рассматривается, также дискретно (т.е. процесс может менять свои состояния только в определенные моменты времени). Такой процесс идет (изменяется) по шагам (иначе - по тактам).

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

3. Непрерывный марковский процесс – множество состояний и время -непрерывные.

На практике Марковские процессы в чистом виде встречаются не часто. Однако нередко приходится иметь место с процессами, для которых влиянием предыстории можно пренебречь. Кроме того, если все параметры из «прошлого»,от которых зависит «будущее» включить в состоянии системы в «настоящем», то ее также можно рассматривать как Марковскую. Однако это часто приводит к значительному росту числа учитываемых переменных и невозможности получить решение задачи.

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

Процесс называется процессом с дискретными состояниями, если все его возможные состояния , ,... можно заранее перечислить (перенумеровать). Переход системы из состояния в состояние переходит практически мгновенно –скачком.

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

Например: Техническое устройство S состоит из двух узлов, каждый из которых в случайный момент времени может выйти из строя (отказать). После этого мгновенно начинается ремонт узла (восстановление),который продолжается случайное время.

 Возможны следующие состояния системы:

- оба узла исправны;        

 - первый узел ремонтируется,второй исправен.

 – второй узел ремонтируется,первый исправен    

- оба узла ремонтируются.

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

 

        

    - состояния

 

                                                                           - переходы

 

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

Если все потоки событий, переводящие систему S из состояния в состояние – простейшие, то процесс, протекающий в такой системе будетМарковским. Это обуславливается тем, что простейший поток не обладает последействием, т.е. в нем «будущее» не зависит от «прошлого» и, кроме того, он обладает свойством ординарности – вероятность одновременного появления двух и более событий бесконечно мала, т.е невозможен переход из состояния в состояние, минуя несколько промежуточных состояний.

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

 

 

        

 

 

Используя размеченный граф состояний системы можно построить математическую модель данного процесса.

 

Рассмотрим переходы системы из некоторого состояния  в предыдущее или последующее  . Фрагмент графа состояний в этом случае будет выглядеть следующим образом:

 

             

             

 

                     

 

Пусть система в момент времени t находится в состоянии .

Обозначим (t)- вероятность i-ого состояния системы – вероятность того, что система в момент времени t находится в состоянии . Для любого момента времени t справедливо =1.

Определим вероятность того, что и в момент времени t+∆t система будет находиться в состоянии . Это может быть в следующих случаях:

1) Система находилась в состоянии  и за время ∆ t из него не вышла. Это означает, что за время ∆t не возникло события, переводящего систему в состояние  (поток с интенсивностью ) или события, переводящего её в состояние  (поток с интенсивностью  ). Определим вероятность этого при малых ∆t.

При экспоненциальном законе распределения времени между двумя соседними требованиями, соответствующему простейшему потоку событий вероятность того, что на интервале времени ∆t не возникнет ни одного требования в потоке с интенсивностью λ₁ будет равна

 ,

Разлагая функцию f(t) в ряд Тейлора (t>0) получим (для t=∆t)

f(∆t)=f(0)+ (0)* ∆t +  *∆ + *∆ +…=

= +(-l) *∆t+ (∆ + *(∆ +…» 1-l*∆t при ∆t®0

Аналогично для потока с интенсивностью λ₂получим .

Вероятность, что на интервале времени ∆t ( при ∆t®0) не возникнет ни одного требования будет равна

(∆t)/ = (∆t/ * (∆t/ = (1- *∆t)(1- *∆t) =

= 1 - - *∆t + 1 - ( + )*∆t + б.м.

 

Таким образом, вероятность того, что система за время ∆t не вышла из состояния , при малых ∆t будет равна 

P( / )=1 – ( + )* ∆t

 

2) Система находилась в состоянии S_i-1 и за время  перешла в состояние S_i. То есть в потоке с интенсивностью  возникло хотя бы одно событие. Вероятность этого равна для простейшего потока с интенсивностью λ будет

Для нашего случая вероятность такого перехода будет равна

 

3) Система находилась в состоянии и за время ∆tперешла в состояние . Вероятность этого будет

Тогда вероятность, что система в момент времени (t+∆t) будет в состоянии S_i равна

+

Вычтем из обеих частей P_i(t), разделим на ∆tи, перейдя к пределу, при ∆t→0, получим

 

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

 

Данные уравнения называются уравнениями Колмогорова-Чепмена для дискретного марковского процесса.

Задав начальные условия (например, P₀(t=0)=1,P_i(t=0)=0 i≠0) и решив их, получим выражения для вероятностей состояния системы как функций времени. Аналитические решения достаточно просто получить, если число уравнений ≤ 2,3. Если их больше, то обычно решают уравнения численно- на ЭВМ (например методом Рунге-Кутта).

 

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

Так как в стационарном режиме все , следовательно, все =0. Приравняв в системе уравнений левые части 0 и, дополнив их уравнением =1, получим систему линейных алгебраических уравнений, решив которую найдём значения финальных вероятностей.

Пример. Пусть в нашей системе интенсивности отказов и восстановления элементов следующие

Отказы   1эл:

           2эл:

Ремонт 1эл:

2эл:

 

P₀+P₁+P₂+P₃=1

0=-(1+2)P₀+2P₁+3 P₂

0=-(2+2)P₁+1P₀+3P₃

0=-(1+3)P₂+2P₀+2P₃

0=-(2+3)P₃+2P₁+1P₂

 

Решив данную систему, получим

P₀=6/15=0.4;  P₁=3/15=0.2; P₂=4/15=0.27; P₃=2/15≈0.13.

Т.е. в стационарном состоянии система в среднем

40% находится в состоянии S₀ (оба узла исправны),

20%- в состоянии S₁ (1-й эл-т ремонтируется, 2-й исправен),

27%- в состоянии S₂ (2-й эл-тремонтируется, 1исправен),

13%- в состоянии S₃ – оба эл-та в ремонте.

 

Знание финальных вероятностей позволяет  оценить среднюю эффективность работы системы и загрузку службы ремонта.

Пусть система в состоянии S₀приносит доход 8 усл.ед. в единицу времени; в состоянии S₁-доход 3 усл.ед.; в состоянии S₂- доход 5;в состоянии S₃-доход=0

Стоимость ремонта в единицу времени для эл-та 1- 1(S_1,S₃) усл.ед., эл-та 2- (S_2,S₃) 2 усл.ед. Тогда в стационарном режиме:

Доход системы в единицу времени будет:

W_дох=8P₀+3P₁+5P₂+0P₃=8·0.4+3·0.2+5·0.27+0·0.13=5.15 усл.ед.

Стоимость ремонта в ед. времени:

W_рем=0P₀+1P₁+2P₂+(1+2)P₃=0·0.4+1·0.2+2·0.27+3·0.13=1.39 усл.ед.

Прибыль в единицу времени

W= W_дох-W_рем=5.15-1.39= 3.76 усл.ед

Проведя определённые расходы можно изменить интенсивности λи μ и, соответственно, эффективность системы. Целесообразность таких расходов можно оценить, проведя пересчёт P_i. и показателей эффективности системы.