Моделирование систем массового обслуживания (стр. 4 из 13)

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

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

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

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

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

Глава II. Уравнения описывающие системы массового обслуживания

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

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