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

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

2

 p_i(t) = p₀(t) + p₁(t) + p₂(t) = 1.

i=0

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

а) система в момент t с вероятностью p_i(t) находилась в состоянии S_i и за малое приращение времени t так и не перешла в другое соседнее состояние — ни в S₀, ни в S₂. Вывести систему из состояния S₁ можно суммарным простейшим потоком с интенсивностью (₁₀ + ₁₂) , поскольку суперпозиция простейших потоков также является простейшим потоком. На этом основании вероятность выхода из состояния S₁ за малый промежуток времени t приближенно равна (₁₀ + ₁₂)t. Тогда вероятность невыхода из этого состояния равна [1 — (₁₀ + ₁₂)  t]. В соответствии с этим вероятность того, что система останется в состоянии S₁ на основании теоремы умножения вероятностей, равна:

p₁(t)[l – (₁₀ + ₁₂)t];

б) система находилась в соседнем состоянии S₀ И за малое время t перешла в состояние S₁. Переход системы происходит под воздействием потока ₀₁ c вероятностью, приближенно равной ₀₁ t.

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

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

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

p₁(t + t) = p₁(t)[1 – (₁₀ + ₁₂ ) t] + p₀(t) ₀₁t + p₂(t)₂₁t,

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

p₁(t + t) – p₁(t) ₌ p₀(t)₀₁ + p₂(t)₂₁ – p₁(t)(₁₀ + ₁₂).

t

Переходя к пределу при А/ -^ О, приближенные равенства перейдут в точные, и тогда получим производную первого порядка

dp_{1 =} p₀₀₁ + p₂₂₁ – p₁(₁₀ + ₁₂),

d_t

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

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

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

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

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

2

 p_i(t)=1

i=1

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

Выходящие Входящие

Для состояния S₀ p₀ – ₀₁ = p₁₁₀

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

Для состояния S₂ p₂₂₁ = p₁₁₂

p₀ + p₁ + p₂ = 1

Пример 1. Составим систему уравнений Колмогорова в общем виде для случая, когда граф состояний имеет вид (рис. 6.2.2):

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

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

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

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

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

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

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

Lim p_i(t) = p_i (i = 1,2, …, n)

t

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

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

Пример 2. Запишем систему алгебраических уравнений для вычисления предельных вероятностей состояний системы, изображенной на рис. 6.2.2.

Для этого допустим, что

= 0 (i = 1; 2; 3; 4),

тогда из записанной ранее в примере 1 системы уравнений Колмогорова получаем:

 21p23 - 12p1 =0,

12p1 + 23p^3 - (21 + 23)p2 =0,

23p2 + 43p4 -(32 +34)p3 =0,

34p3 - 43p4=0;

И, Кроме того, мы должны учесть нормировочное условие:

p₁+p₂+p₃+p₄=1

Любое из уравнений записанной системы можно исключить, использовав вместо него нормировочное условие.