Моделирование систем массового обслуживания

курсовая работа

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

Рассмотрим математическое описание марковского случайного процесса с дискретными состояниями системы So, Sl, S2(см. рис. 6.2.1) и непрерывным временем. Полагаем, что все переходы системы массового обслуживания из состояния Si в состояние Sj происходят под воздействием простейших потоков событий с интенсивностями лij, а обратный переход под воздействием другого потока лij,. Введем обозначение pi как вероятность того, что в момент времени t система находится в состоянии Si. Для любого момента времени t справедливо записать нормировочное условие--сумма вероятностей всех состояний равна 1:

2

Уpi(t)=p0(t)+ p1(t)+ p2(t)=1

i=0

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

а) система в момент t с вероятностью p1(t) находилась в состоянии S1 и за малое приращение времени Дt так и не перешла в другое соседнее состояние -- ни в S0, ни b S2. Вывести систему из состояния S1 можно суммарным простейшим потоком c интенсивностью (л1012), поскольку суперпозиция простейших потоков также является простейшим потоком. На этом основании вероятность выхода из состояния S1 за малый промежуток времени Д t приближенно равна (л1012)* Д t. Тогда вероятность невыхода из этого состояния равна [1 -(л1012)* Д t].B соответствии с этим вероятность того, что система останется в состоянии Si на основании теоремы умножения вероятностей, равна:

p1(t) [1 -(л1012)* Д t];

б) система находилась в соседнем состоянии So и за малое время Д t перешла в состояние So Переход системы происходит под воздействием потока л01 с вероятностью, приближенно равной л01Д t

Вероятность того, что система будет находиться в состоянии S1, в этом варианте равна po(t) л 01 Д t;

в) система находилась в состоянии S2 и за время Д t перешла в состояние S1 под воздействием потока интенсивностью л 21 с вероятностью, приближенно равной л21Д t. Вероятность того, что система будет находиться в состоянии S1, равна p2(t) л21Д t.

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

p2(t+Дt)= p1(t) [1 -(л1012)* Д t]+ po(t) л 01 Д t+ p2(t) л21Д t ,

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

p2(t+Дt)- p1(t)/ Д t= po(t) л 01+ p2(t) л21- p1(t) (л1012) .

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

dp2/dt= p0 л 01 +p2 л21 -p11012) ,

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

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

dp0 /dt= p1 л 10 ,

dp1 /dt= p0 л 01 +p2 л21 -p11012) ,

dp2 /dt= p1 л 12 +p2 л21 .

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

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

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

Уpi(t)=1

i=1

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

Для состояния So> p0 л 01 = p1 л 10

Для состояния S1> p11012) = p0 л 01 +p2 л21

Для состояния S2> p2 л21 = p1 л 12

p0 +p1 +p2 =1

dp 4(t) /dt= л34 p3(t) - л43 p4(t) ,

p1(t)+ p2(t)+ p3(t)+ p4(t)=1 .

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

p1(0)=1, p2(0)= p3(0)= p4(0)=0 .

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

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

pi(t), p2(t),…., pn(t) .

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

lim pi(t) = pi (i=1,2,…,n) ; t>?

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

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

Делись добром ;)