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

Из множества  разновидностей случайных процессов  наибольшее распространение в коммерческой деятельности получили такие процессы, для которых в любой момент времени характеристики процесса в  будущем зависят только от его  состояния в настоящий момент и не зависят от предыстории —  от прошлого. Например, возможность  получения с завода «Кристалл» ликероводочной продукции зависит от наличия  ее на складе готовой продукции, т.е. его состояния в данный момент, и не зависит от того, когда и  как получали и увозили в прошлом  эту продукцию другие покупатели.

Такие случайные  процессы называются процессами без  последствия, или марковскими, в  которых при фиксированном настоящем  будущее состояние СМО не зависит  от прошлого. Случайный процесс, протекающий  в системе, называется марковским случайным  процессом, или «процессом без последствия», если он обладает следующим свойством: для каждого момента времени  t₀ вероятность любого состояния t > t₀ системы S_i, - в будущем (t >t_Q) зависит только от ее состояния в настоящем (при t = t₀) и не зависит от того, когда и каким образом система пришла в это состояние, т.е. оттого, как развивался процесс в прошлом.

Марковские  случайные процессы делятся на два  класса: процессы с дискретными и  непрерывными состояниями. Процесс  с дискретными состояниями возникает  в сиcтемах, обладающих только некоторыми фиксированными состояниями, между которыми возможны скачкообразные переходы в некоторые, заранее не известные моменты времени. Рассмотрим пример процесса с дискретными состояниями. В офисе фирмы имеются два телефона. Возможны следующие состояния у этой системы обслуживания: S_o—телефоны свободны; S_l — один из телефонов занят; S₂— оба телефона заняты.

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

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

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

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

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

 

 

 

 

 

2 УРАВНЕНИЯ ОПИСЫВАЮЩИЕ СИСТЕМЫ  МАССОВОГО ОБСЛУЖИВАНИЯ

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

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

 

 

 

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

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

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

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

 

 

 

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

 

 

 

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

 

 

 

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

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

 

 

 

 

 

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

Уравнения Колмогорова позволяют вычислить  все вероятности состояний СМО  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:

 

 

 

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

 

Для состояния 

Для состояния 

Для состояния 

 

 

 

 

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

 

 

 

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

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

 

 

 

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

 

 

 

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

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

 

2. Процессы «рождения – гибели»

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

 

S1

S2

λ₀ λ₁  λ₂ λ₃ λ_n-1

S0

S3

kjlSn

μ₀ μ₁ μ₃ μ₄ μ_n-1

Рис.

 

2.1 Размеченный  граф процесса «рождения - гибели»

 

Этот  граф воспроизводит известную биологическую  интерпретацию: величина λ_k отображает интенсивность рождения нового представителя некоторой популяции, например, кроликов, причем текущий объем популяции равен k; величина μ является интенсивностью гибели (продажи) одного представителя этой популяции, если текущий объем популяции равен k. В частности, популяция может быть неограниченной (число n состояний марковского процесса является бесконечным, но счетным), интенсивность λ может быть равна нулю (популяция без возможности возрождения), например, при прекращении воспроизводства кроликов.

Для Марковского  процесса «рождения - гибели», описанного стохастическим графом, приведенным  на рис. 2.1, найдем финальное распределение. Пользуясь правилами составления  уравнений для конечнего числа  n предельных вероятностей состояния системы S₁, S₂, S₃,… S_k,…, S_n, составим соответствующие уравнения для каждого состояния:

для состояния  S₀-λ₀p₀=μ₀p₁;

для состояния  S₁-(λ₁+μ₀)p₁= λ₀p₀+μ₁p₂, которое с учетом предыдущего уравнения для состояния S₀ можно преобразовать к виду λ₁р₁= μ₁p₂.

Аналогично  можно составить уравнения для  остальных состояний системы  S₂, S₃,…, S_k,…, S_n. В результате получим следующую систему уравнений: