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

Рис. 3. Размеченный граф состояний системы

На этом рисунке   - интенсивности потока отказов;   - интенсивности потока восстановлений.

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

Пусть система находится в состоянии S 0 . В состояние S 1 ее переводит поток отказов первого станка. Его интенсивность равна:

где   - среднее время безотказной работы первого станка.

Из состояния S 1 в S 0 систему переводит поток «окончаний ремонтов» первого станка. Его интенсивность равна:

где   - среднее время ремонта первого станка.

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

Пусть рассматриваемая система S имеет  -возможных состояний  . Вероятность  -го состояния   - это вероятность того, что в момент времени  , система будет находиться в состоянии  . Очевидно, что для любого момента времени сумма всех вероятностей состояний равна единице:

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

Что будет происходить с вероятностями состояний при  ? Будут ли   стремиться к каким-либо пределам? Если эти пределы существуют и не зависят от начального состояния системы, то они называются финальными вероятностями состояний .

где   - конечное число состояний системы.

Финальные вероятности состояний – это уже не переменные величины (функции времени), а постоянные числа. Очевидно, что:

Финальная вероятность состояния   – это по–существу среднее относительное время пребывания системы в этом состоянии.

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

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

Пользуясь этим правилом, напишем систему уравнений для нашего примера :

.

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

Продолжение примера . Пусть значения интенсивностей потоков равны:  .

Четвертое уравнение отбрасываем, добавляя вместо него нормировочное условие:

.

.

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

Пусть система S в состоянии S 0 (полностью исправна) приносит в единицу времени доход 8 условных единиц, в состоянии S 1 – доход 3 условные единицы, в состоянии S 2 – доход 5 условных единиц, в состоянии S3 – не приносит дохода. Тогда в предельном, стационарном режиме средний доход в единицу времени будет равен:   условных единиц.

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

 

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

 

Рассмотрим математическое описание марковского случайного процесса с дискретными состояниями системы 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 , ни bS2 . Вывести систему из состояния S1 можно суммарным простейшим потоком c интенсивностью (λ10 +λ12 ), поскольку суперпозиция простейших потоков также является простейшим потоком. На этом основании вероятность выхода из состояния S1 за малый промежуток времени Δtприближенно равна (λ10 +λ12 )* Δt. Тогда вероятность невыхода из этого состояния равна [1 -(λ10 +λ12 )* Δt].Bсоответствии с этим вероятность того, что система останется в состоянии Siна основании теоремы умножения вероятностей, равна:

p1 (t) [1 -(λ10 +λ12 )* Δ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 -(λ10 +λ12 )* Δt]+ po (t)λ01 Δt+p2 (t) λ21 Δt ,

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

p2 (t+Δt)-p1 (t)/ Δt= po (t)λ01 + p2 (t) λ21 - p1 (t) (λ10 +λ12 ) .

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

dp2 /dt= p0 λ01 +p2 λ21 -p1 (λ10 +λ12 ) ,

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

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

dp0 /dt= p1 λ10 ,

dp1 /dt= p0 λ01 +p2 λ21 -p1 (λ10 +λ12 ) ,

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 →p1 (λ10 +λ12 ) = p0 λ01 +p2 λ21

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

p0 +p1 +p2 =1

dp4 (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-> ∞ зависимость от времени пропадает. Тогда система дифференциальных уравнений превращается в систему Обычных линейных алгебраических уравнений, которая совместно с нормировочным условием позволяет вычислить все предельные вероятности состояний.

 

Список используемых источников

 

1. Фомин Г.П. Математические методы и модели в коммерческой деятельности. М: Финансы и статистика, 2001.
2. Гмурман В.Е. Теория вероятностей и математическая статистика. М: Высшая школа, 2001.
3. Советов Б.А., Яковлев С.А. Моделирование систем. М: Высшая школа, 1985.
4. Лифшиц А.Л. Статистическое моделирование СМО. М., 1978.
5. Вентцель Е.С. Исследование операций. М: Наука, 1980.
6. Вентцель Е.С., Овчаров Л.А. Теория вероятностей и её инженерные приложения. М: Наука, 1988.