Уравнения Колмогорова

Рассмотрим математическое описание марковского случайного процесса с дискретными состояниями системы S_o, S_l, S₂(см. рис. 6.2.1) и непрерывным временем. Полагаем, что все переходы системы массового обслуживания из состояния S_i в состояние Sj происходят под воздействием простейших потоков событий с интенсивностями λ_ij, а обратный переход под воздействием другого потока λ_ij,. Введем обозначение p_i как вероятность того, что в момент времени t система находится в состоянии S_i. Для любого момента времени t справедливо записать нормировочное условие—сумма вероятностей всех состояний равна 1:

 ₂

Σp_i(t)=p₀(t)+ p₁(t)+ p₂(t)=1

 ⁱ⁼⁰

Проведем анализ системы в момент времени t, задав малое приращение времени Δt, и найдем вероятность р₁ (t+ Δt) того, что система в момент времени (t+ Δt) будет находиться в состоянии S₁ которое достигается разными вариантами:

а) система в момент t с вероятностью p₁(t) находилась в состоянии S₁ и за малое приращение времени Δt так и не перешла в другое соседнее состояние — ни в S₀, ни b S₂. Вывести систему из состояния S₁ можно суммарным простейшим потоком c интенсивностью (λ₁₀ +λ₁₂), поскольку суперпозиция простейших потоков также является простейшим потоком. На этом основании вероятность выхода из состояния S₁ за малый промежуток времени Δ t приближенно равна (λ₁₀ +λ₁₂)* Δ t. Тогда вероятность невыхода из этого состояния равна [1 -(λ₁₀ +λ₁₂)* Δ t].B соответствии с этим вероятность того, что система останется в состоянии Si на основании теоремы умножения вероятностей, равна:

p₁(t) [1 -(λ₁₀ +λ₁₂)* Δ t];

б) система находилась в соседнем состоянии S_o и за малое время Δ t перешла в состояние S_o Переход системы происходит под воздействием потока λ₀₁ с вероятностью, приближенно равной λ₀₁Δ t

Вероятность того, что система будет находиться в состоянии S₁, в этом варианте равна p_o(t) λ ₀₁ Δ t;

в) система находилась в состоянии S₂ и за время Δ t перешла в состояние S₁ под воздействием потока интенсивностью λ ₂₁ с вероятностью, приближенно равной λ₂₁Δ t. Вероятность того, что система будет находиться в состоянии S₁, равна p₂(t) λ₂₁Δ t.

Применяя теорему сложения вероятностей для этих вариантов, получим выражение:

p₂(t+Δt)= p₁(t) [1 -(λ₁₀ +λ₁₂)* Δ t]+ p_o(t) λ ₀₁ Δ t+ p₂(t) λ₂₁Δ t ,

которое можно записать иначе:

p₂(t+Δt)- p₁(t)/ Δ t= p_o(t) λ ₀₁+ p₂(t) λ₂₁- p₁(t) (λ₁₀ +λ₁₂) .

Переходя к пределу при Δt -> 0, приближенные равенства перейдут в точные, и тогда получим производную первого порядка

dp₂/dt= p₀ λ ₀₁ +p₂ λ₂₁ -p₁ (λ₁₀ +λ₁₂) ,

что является дифференциальным уравнением.

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

dp₀ /dt= p₁ λ ₁₀ ,

dp₁ /dt= p₀ λ ₀₁ +p₂ λ₂₁ -p₁ (λ₁₀ +λ₁₂) ,

dp₂ /dt= p₁ λ ₁₂ +p₂ λ_{21 .}

Для составления уравнений Колмогорова существуют общие правила.

Уравнения Колмогорова позволяют вычислить все вероятности состояний СМО S_i в функции времени p_i(t). В теории случайных процессов показано, что если число состояний системы конечно, а из каждого из них можно перейти в любое другое состояние, то существуют предельные (финальные) вероятности состояний, которые показывают на среднюю относительную величину времени пребывания системы, в этом состоянии. Если предельная вероятность состояния S₀ – равна p₀ ⁼ 0,2, то, следовательно, в среднем 20% времени, или 1/5 рабочего времени, система находится в состоянии S_o. Например, при отсутствии заявок на обслуживание к = 0, р₀ = 0,2,; следовательно, в среднем 2 ч в день система находится в состоянии S_o и простаивает, если продолжительность рабочего дня составляет 10 ч.

Поскольку предельные вероятности системы постоянны, то заменив в уравнениях Колмогорова соответствующие производные нулевыми значениями, получим систему линейных алгебраических уравнений, описывающих стационарный режим СМО. Такую систему уравнений составляют по размеченному графу состояний СМО по следующим правилам: слева от знака равенства в уравнении стоит предельная вероятность р_i рассматриваемого состояния Si умноженная на суммарную интенсивность всех потоков, выводящих (выходящие стрелки) изданного состояния S_i систему, а справа от знака равенства — сумма произведений интенсивности всех потоков, входящих (входящие стрелки) в состояние Si систему, на вероятность тех состояний, из которых эти потоки исходят. Для решения подобной системы необходимо добавить еще одно уравнение, определяющее нормировочное условие, поскольку сумма вероятностей всех состояний СМО равна 1: _n

Σp_i(t)=1

 ⁱ⁼¹

Например, для СМО, имеющей размеченный граф из трех состояний S_o, S₁, S₂ рис. 6.2.1, система уравнений Колмогорова, составленная на основе изложенного правила, имеет следующий вид:

Для состояния S_o→ p₀ λ ₀₁ = p₁ λ ₁₀

Для состояния S₁→ p₁ (λ₁₀ +λ₁₂) = p₀ λ ₀₁ +p₂ λ₂₁

Для состояния S₂→ p₂ λ₂₁ = p₁ λ ₁₂

p₀ +p₁ +p₂ =1

dp ₄(t) /dt= λ₃₄ p₃(t) - λ₄₃ p₄(t) ,

p₁(t)+ p₂(t)+ p₃(t)+ p₄(t)=1 .

К этим уравнениям надо добавить еще начальные условия. Например, если при t = 0 система S находится в состоянии S_1, то начальные условия можно записать так:

p₁(0)=1, p₂(0)= p₃(0)= p₄(0)=0 .

Переходы между состояниями СМО происходит под воздействием поступления заявок и их обслуживания. Вероятность перехода в случае, если поток событий простейший, определяется вероятностью появления события в течение времени Δ t, т.е. величиной элемента вероятности перехода λ_ij Δ t, где λ_ij — интенсивность потока событий, переводящих систему из состояния i в состояние i (по соответствующей стрелке на графе состояний).

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

p_i(t), p₂(t),…., p_n(t) .

Во многих случаях на практике оказывается, что вероятности состояний как функции времени ведут себя таким образом, что существует

lim p_i(t) = p_i (i=1,2,…,n) ; t→∞

независимо от вида начальных условий. В этом случае говорят, что существуют предельные вероятности состояний системы при t->∞ и в системе устанавливается некоторый предельный стационарный режим. При этом система случайным образом меняет свои, состояния, но каждое из этих состояний осуществляется с некоторой постоянной вероятностью, определяемой средним временем пребывания системы в каждом из состояний.

Вычислить предельные вероятности состояния р_i можно, если в системе положить все производные равными 0, поскольку в уравнениях Колмогорова при t-> ∞ зависимость от времени пропадает. Тогда система дифференциальных уравнений превращается в систему Обычных линейных алгебраических уравнений, которая совместно с нормировочным условием позволяет вычислить все предельные вероятности состояний.