Лекция 14. Основы марковских процессов. Уравнения Колмогорова

Определение марковского процесса. Пусть имеется система S, состояние которой изменяется во времени случайным, непредсказуе­мым образом и представляет собой случайный процесс. Этот процесс называется марковским, если для каждого момента времени t₀ веро­ятность любого состояния при t > t₀ (в будущем) зависит только от вероятности, состояния в момент t₀ (в настоящем) и не зависит от вероятностей состояний при t < t₀ (в прошлом).

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

Марковская цепь называется дискретной, если переход из одного состояния в другое происходит в строго фиксированные промежут­ки времени, отделенные друг от друга равными интервалами. Если же эти переходы возможны в любой момент времени t, то соответствую­щая марковская цепь называется непрерывной. Переход из одного состояния в другое может быть отображен графом состояний, в кото­ром вершины представляют собой возможные состояния системы, а ду­ги графа отражают переходы из одного состояния в другое. Если две вершины i и j соединяются дугой (i,j), то это означает, что воз­можен непосредственный переход из состояния i в состояние j. Мар­ковская цепь может, таким образом, быть представлена как случай­ное блуждание на графе состояний системы.

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

Одна из важнейших задач те­ории марковских процессов вообще и ТМО в частности заключается в нахождении вероятностей состоя­ний цепи. Эти вероятности для непрерывных марковских цепей оп­ределяются с помощью дифференци­альных уравнений Колмогорова.

Рис.1

Рассмотрим некоторую произвольную систему, граф состояний которой приведен на рис.1. Система имеет n состояний S₁,S₂,...,S_n. Процесс перехода из одного состояния в другое описывает­ся непрерывной цепью Маркова. Пусть P_i(t) - вероятность того, что в момент времени t система будет находиться в состоянии S_i (i=1,2,…,n). Поскольку система не может находиться одновременно в двух состояниях, то события, заключающиеся в нахождении системы в состояниях S₁,S₂,…,S_n, несовместны и образуют полную сис­тему событий. Отсюда следует

(51)

Это соотношение называется условием нормировки. Задача заключает­ся в определении вероятности любого состояния P_i(t) в любой мо­мент времени t.

Введем понятие вероятности перехода системы из состояния i, где она находилась в момент времени t, в состояние j за время Dt P_ij(t,Dt). Очевидно, что P_ij(t,Dt) представляет собой условную вероятность того, что в момент времени t + Dt система окажется в состоянии S_j при условии, что в момент времени t она находилась в состоянии S_i: p_ij(t,Dt)= p(S_j(t+Dt)/S_i(t)).

Предел отношения вероятности перехода p_ij(t,Dt) к длине интервала времени Dt назовем плотностью вероятности перехода

. (52)

Плотность вероятности перехода определим только для случаев i¹j.

Если l_ij(t)=const, то марковская цепь называется однородной. В противном случае, когда l_ij(t) являются функциями времени, цепь называется неоднородной. При расчетах вероятностей состояний марковской цепи предполагается, что все эти плотности вероятнос­тей переходов l_ij известны. Если у каждой дуги графа состояний системы проставить плотность вероятности перехода по данной дуге, то полученный граф назовем размеченным графом состояний (см.рис.1). Уравнения Колмогорова составляются в соответствии с разме­ченным графом состояний. Рассмотрим фрагмент размеченного графа состояний (рис.1), обведенный штрихпунктирной линией. Отбро­сим вначале дуги, изображенные пунктиром, и определим вероятность нахождения системы в состоянии S_i в момент времени t+Dt. С уче­том того, что вершина S_i связана только с вершинами S_k и S_j, ука­занное событие будет иметь место в двух случаях:

- система находилась в состоянии S_i в момент времени t и за время Dt из этого состояния не вышла;

- система находилась в состояния s_k в момент времени t и за время Dt перешла из S_k в S_i.

Если отрезок Dt достаточно мал, то вероятность перехода p_ij(t,Dt) может быть определена приближенно с помощью (52)

p_ij(t,Dt) » l_ij(t)Dt (53)

С учетом (53) и свойства марковости процесса вероятность первого случая (отсутствие перехода по дуге (S_i,S_j))

p_I = (1-l_ij(t)Dt)p_i(t).

Вероятность второго случая с учетом (53)

p_II » l_ki(t)p_k(t).

Тогда можно определить искомую вероятность как

p_i(t+Dt)= p_I + p_II = (1-l_ij(t)Dt)p_i(t) + l_ki(t)p_k(t)Dtp_k(t)

или

(54)

Переходя в (53) к пределу при Dt ® 0, получим

. (55)

Теперь добавим к вершине Si дуги, обозначенные на рис.1 пункти­ром. Тогда при вычислении p_i(t+Dt) необходимо учитывать возможный переход из S_i в S_j и S_r и переходы из S_k и S_l в S_i. В этом случае

P_I = [1-(l_ij(t)+l_ir)Dt]p₁(t),

P_II = l_k1(t)Dtp_k(t)+l_l1(t)Dtp₁(t).

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

. (56)

На основании (55) и (56) можно сформулировать правила сос­тавления уравнений Колмогорова по размеченному графу состояний непрерывной марковской цепи:

1. Система дифференциальных уравнений Колмогорова имеет форму Коши. Каждое уравнение составляется с помощью рассмотрения ве­роятности состояния, представленного соответствующей вершиной в размеченном графе. Число уравнений системы равно числу вершин графа.

2. Число слагаемых правой части каждого уравнения равно чис­лу дуг, инцидентных соответствующей вершине.

3. Дугам с положительной инциденцией соответствуют отрица­тельные слагаемые, а дугам с отрицательной инциденцией - положи­тельные.

4. Каждое слагаемое правой части равно произведению вероят­ности состояния, соответствующего началу рассматриваемой дуги, на плотность вероятности перехода по данной дуге.

Начальные условия для системы уравнений Колмогорова опреде­ляются начальным состоянием системы. Например, если начальное состояние было S₂ , то начальные условия имеют вид: p₁(0)=0; р₂(0)=1; р₃(0)=0;…;р_n(0)=0. Уравнения (55) и (56) были вы­ведены для общего случая неоднородной марковской цепи. Для одно­родной марковской цепи все l_ij(i,j=l,…,n) постоянны.

Рассмотрим одно важное свойство уравнений Колмогорова (55), которое может быть представлено в виде

, (57)

где - n-мерный вектор вероятностей состояний системы; р = {p₁(t),…,p_n(t)}; L - n´n-матрица плотностей перехода.

В соответствии с вышеописанными правилами составления урав­нений Колмогорова одна и та же плотность вероятности перехода l_ij будет входить в одно из уравнений со знаком "+", а в другое - со знаком "-", поскольку для двух смежных вершин дуга, соединяющая их, будет обладать положительной инциденцией по отношению к одной вершине и отрицательной по отношению к другой. Это приведет к то­му, что сумма всех элементов в каждом столбце матрицы будет равна нулю. Тогда любая строка матрицы L будет равна сумме остальных строк. Следовательно, матрица L является всегда вырожденной. Бо­лее строго это свойство доказывается в [7].

Рассмотрим систему с размеченным графом состояний, изобра­женным на рис.2. Система уравнений Колмогорова и матрица L для этого случая в соответствии с правилами 1-4 будут иметь вид:

dp₁/dt=-(l₁₂+l₁₃)p₁+l₄₁p_4,

dp₂/dt=l₁₂p₁-l₂₅p₂+l₃₂p_3,

dp₃/dt=l₁₃p₃-(l₃₂+l₃₄)p₃+l₅₃p_5, (58)

dp₄/dt=l₃₄p1-(l₄₁+l₄₅)p₄,

dp₅/dt=l₂₅p₂+l₄₅p₄-l₅₃p_5.

Исключение любого уравнения из этой системы нарушает указанное соотношение для строк матрицы L, следовательно, ранг матрицы L будет равен n-1. Для того чтобы система уравнений Колмогорова имела единственное решение при заданных начальных условиях, не­обходимо исключить любое из уравнений системы (58) и заме­нить его условием нормировки (51).

Итак, решение системы (57) без одного уравнения (безразлич­но какого) с условием (51) определяет в любой момент времени поведение вероятностей состояний марковской цепи при заданных начальных условиях.

Рис.2

Получить это решение можно с помощью любых численных методов (например, Рунге-Кутта, Эйлера-Коши и т.д.), реализуемых на ЭВМ. Только в самых простых случаях система уравнений Колмогорова мо­жет быть проинтегрирована в квадратурах. В большинстве практичес­ких случаев для расчета вероятностей состояний используются не решения систем уравнений Колмогорова в любой момент времени, а асимптотические оценки этих решений при t®¥.

Лекция 15. Предельные вероятности состояний. Простейший поток событий.

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

Определение 1. Если число состояний системы конечно и из каждого состояния можно перейти в любое другое за произвольное число шагов, то говорят, что такая система обладает эргодическим свойством.

Определение 2. Пусть марковский процесс характеризуется ве­роятностями перехода из состояния i в состояние j за время t

p_ij(t) (0£i£n; 0£j£n).

Процесс называется транзитивным, если существует такое t>0, что p_ij(t)>0 (0£i£n; 0£j£n). Из определений 1 и 2 следует, что процессы в марковских цепях с эргодическим свойством являются транзитивными.

Теорема Маркова. Для любого транзитивного марковского процесса предел существует и не зависит от начального состояния i.

Это означает, что при t®¥ в системе устанавливается неко­торый предельный стационарный режим, характеризующийся постоян­ной, не зависящей от времени, вероятностью каждого из состояний системы. При этом данная вероятность представляет собой среднее относительное время пребывания системы в данном состоянии. Это значит, что если время работы всей системы 100 ч, а вероятность состояния S1 равна p1=0,15, то система будет находиться в состоянии S1 в среднем 15 ч.

Пределы, к которым стремятся вероятности каждого из состоя­ний марковской цепи с эргодическим свойством при t®¥, называ­ются предельными вероятностями. При рассмотрении СМО мы будем иметь дело только с эргодическими марковскими цепями. Пусть V - некоторое подмножество множества состояний системы S , а V’ - его дополнение до S . Если множество V обладает эргодическим свойс­твом и ни из одного состояния множества V нельзя перейти ни в од­но из состояний множества V’, то множество называется замкнутым или эргодическим множеством. Эргодические системы состоят из од­ного единственного эргодического множества (S=V, V’=Æ) и называются поэтому неразложимыми. Если в системе S множество V'¹Æ или в этой системе можно выделить несколько эргодических множеств S = V₁ÈV₂È…ÈV_n, то такая система называется разложимой. Примеры таких систем приведены на рис.3.

На рис.3,а представлена сис­тема с двумя эргодическими множест­вами V₁=(S₂,S₃,S₄) и V₂(S₅,S₆). На рис.3, б эргодическое множество состоит лишь из одного состояния (S₄). Если эргодическое множест­во состоит лишь из одного состоя­ния, то это состояние называется поглощающим, так как попав в не­го однажды, процесс остается нав­сегда в поглощающем состоянии. Ха­рактерная особенность графа состо­яний неразложимой эргодической мар­ковской системы заключается в том, что каждой вершине этого графа ин­цидентны дуги как с положительной, так и с отрицательной инцидент­ностью (т.е. у каждой вершины име­ются дуги, направленные как к вер­шине, так и от нее, см., например, рис. 1 и 2).

а б

Рис. 3

Вычисление предельных вероят­ностей состояний для таких систем упрощается в связи с тем, что, поскольку все эти вероятности яв­ляются постоянными величинами, то их производные по времени рав­ны 0 (dp_i/dt=0 для всех i). Поэтому левые части системы уравнений Колмогорова (58) приравниваются нулю и она превращается в систе­му линейных алгебраических уравнений

. (59)

Нетривиальное решение системы (59) может быть получено только в случае вырожденности матрицы L. Выше было доказано, что матрица плотностей вероятностей L является вырожденной. Система (59) без одного из своих уравнений дополняется условием нормировки

(60)

Соотношения (59) и (60) позволяют определить предельные вероят­ности состояний. Поскольку часть слагаемых, соответствующая дугам с отрицательной инцидентностью, положительна, а другая часть, со­ответствующая дугам с положительной инцидентностью, отрицательна, то каждое уравнение системы (59) может быть составлено с учетом мнемонического правила: для каждого состояния сумма членов, соот­ветствующих входящим дугам, равна сумме членов, соответствующих выходящим дугам.

Пример. Для системы, изображенной на рис.2, из уравнений Колмогорова (58) следует

(l₁₂+l₁₃)p₁=l₄₁p₄ (l₄₁+l₄₅)p₄=l₃₄p₃

l₂₅p₁=l₁₂p₁+l₃₂p₃ l₅₃p₃=l₅₂p₂+l₄₅p₄

(l₃₂+l₃₄)p₄=l₁₃p₁+l₅₃p₅ (61)

Для решения (61) нужно исключить любое из первых пяти уравнений (например, пятое, как содержащее наибольшее число членов).

Предельные вероятности состояний используются в ТМО значи­тельно чаще, чем решения уравнений Колмогорова, причем, зная ре­шение системы уравнений Колмогорова, можно определить момент окончания переходного процесса изменения вероятностей состояний во времени. Это дает возможность рассчитать, промежуток времени начиная от включения системы в работу, по истечении которого ве­роятности состояний достигнут своих предельных значений и будут справедливы оценки, использующие эти значения. В заключение этого параграфа рассмотрим один частный, но практически очень важный класс марковских процессов, широко применяемых при исследовании СМО. Это - процессы "размножения и гибели". К ним относятся мар­ковские цепи, представимые размеченным графом, который состоит из вытянутой цепочки состояний, изображенной на рис.4.

Рис.4

Матрица плотностей вероятностей переходов такой системы яв­ляется якобиевой (тридиагональной):

Рассматривая начальное состояние S₀ , получим в соответствии с (59)

l₀₁p₀=l₁₀p₁ (62)

Для состояния S₁ имеем

l₀₁p₀+l₂₁p₂=l₁₀p₁+l₁₂p₁ (63)

Вычитая из (63) равенство (62), получим

l₂₁p₂=l₁₂p₁(64)

Продолжая этот процесс до n-гo состояния включительно, получим

l_n,n-1p_n=l_n-1,np_n-1

Из (62) теперь можно выразить p₁ через р₀:

p₁=p₀(l₀₁/l₁₀) (65)

Подставляя (64) в (65), получим

p₂=p₀(l₀₁l₁₂/l₁₀l₂₁)

Очевидно, что для произвольного k (1£k£n) будет справедливо вы­ражение

. (66)

В соответствии с (66) и размеченным графом состояний, представленным на рис.4, можно сформулировать правило, с по­мощью которого можно выразить предельные вероятности состояний процесса "размножения и гибели" через вероятность начального сос­тояния р₀. Это правило гласит: вероятность произвольного состоя­ния p_k (l£k£n) равна вероятности начального состояния р₀, умно­женной на дробь, числитель которой равен произведению плотностей вероятностей перехода для дуг, переводящих состояние системы сле­ва направо, а знаменатель - произведение плотностей вероятностей перехода справа налево от начального до k-гo состояний включи­тельно.

Вероятность р₀ находится из условия нормировки и выражений (66) следующим образом:

(67)

Выражения (66) и (67) полностью определяют предельные вероят­ности процесса "размножения и гибели".

Цепи Маркова с непрерывным временем являются математическими моделями СМО. Для анализа СМО необходимо также иметь математичес­кие модели входных потоков заявок на обслуживание. Эти математи­ческие модели представляют собой потоки события, являющиеся от­дельным классом случайных процессов. Потоком событий называется последовательность однородных событий, следующих одно за другим в случайные моменты времени. Этот поток количественно может быть охарактеризован числом событий x(t), имевших место в течение определенного промежутка времени (0,t). Тогда случайный поток со­бытий можно определить как случайный процесс x(t) (t³0), в кото­ром функция x(t) является неубывающей функцией времени, способной принимать лишь целые неотрицательные значения. Иными словами, график функции x(t) является ступенчатой кривой с постоянной вы­сотой ступеньки, равной единице, причем ширина ступеньки - слу­чайная величина. Примерами таких потоков могут служить: поток вызовов на АТС, поток запросов в вычислительный центр коллективного пользования и т.п. Моменты появления событий можно отобразить точками на временной оси, поэтому поток событий часто представляется и как последовательность таких точек. Поток событий называется регулярным, если события следуют одно за другим через одинаковые, строго фиксированные промежутки времени.

В ТМО такие потоки практи­чески, не используются, однако они представляют интерес как предельный случай. Значительно чаще имеют дело с потоками, в которых времена поступления со­бытий и, следовательно, проме­жутки времени между ними являются случайными (иррегулярными). При этом наиболее простые рас­четные соотношения получаются при использовании простейших потоков событий, которые широко применяются при исследовании CMО.

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

1. Поток событий называется стационарным, если вероятность p_k(l) того, что за отрезок времени t произойдет k событий, зави­сит только от его длины t и не зависит от его расположения на временной оси, т.е. p_k(t’,t’+t)=p_k(t). Из определения однородной марковской цепи следует, что стационар­ность - это однородность потока по времени.

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

3. Поток событий называется потоком без последействия, если вероятность попадания событий на некоторый участок временной оси не зависит от того, сколько событий попало на другие участки. Иными словами, условная вероятность наступления k событий за про­межуток времени (t’,t’+t), вычисленная при любом условии чередо­вания событий до момента t', равна безусловной вероятности p_k(t) того же события, т.е.

p[(t’,t’+t),k/(t",t"+t),m]=p_k(t),tÇt_k=Æ, t"<t’.

На практике редко встречаются потоки, удовлетворяющие всем трем допущениям одновременно. Например, поток вызовов в АТС в дневные часы более интенсивен, чем в ночные. Тем не менее, рассматривая работу АТС в периоды с 12 до 13 ч дня и с 2 до 3 ч ночи, поток вызовов на этих более коротких промежутках можно с высокой степенью точности считать стационарным. Этот пример говорит о том, что в большом числе случаев можно ввести определенные упрощения, вытекающие из принципов работы конкретных реальных систем и позволяющие проводить исследование реальных СМО путем замены их входных потоков простейшими. Это дает возможность существенно упростить математический аппарат исследования СМО.

Указанные свойства простейших потоков позволяют просто опре­делить их распределение вероятностей p_k(t), т.е. вероятность того, что за отрезок времени длиной t произойдет k событий. Прежде всего следует оговорить, что мы будем рассматривать только те по­токи, в которых за конечный промежуток времени t с вероятностью 1 будет происходить лишь конечное число событий, т.е.

(68)

Тогда простейший поток можно представить цепью Маркова, изобра­женной на рис.5,а, где состояние S₀ означает отсутствие собы­тий в интервале t, S₁ - появление одного события за время t, S₂ - появление двух событий за время t,…, S_k - появление k событий за время t. Применив правила составления уравнений Колмогорова для такого размеченного графа состояний, получим:

dp₀(t)/dt = - lp₀(t),

dp₁(t)/dt = - lp₁(t)+lp₀(t) (69)

…

dp_k(t)/dt = - lp_k(t)+lp_k-1

_…

с начальными условиями: р₀(0)=1, р₁(0)=0,…, р_k=0,…

Плотность вероятности перехода l, которая участвует в уравнениях (69), является в данном случае интенсивностью потока собы­тий. Под интенсивностью потока понимается среднее по ансамблю реализаций число событий в единицу времени. Вероятность перехода р_i,i+1(t,t+Dt) равна веро­ятности появления одного события в интервале от t до t+Dt, поскольку ординар­ность потока исключает появление большего числа событий в этом интервале. Очевидно, что эта вероятность равна среднему числу по­явлений одного события за время Dt. Тогда с учетом определения (52) можно сделать вывод, что плотность вероятности перехода для марковской цепи (56) равна интенсивности простейшего потока. В стационарном простейшем потоке l = const, тогда как в не­стационарном потоке интенсивность зависит от времени: l = l(t).

а б

Рис.5

Решить систему (69) можно различными методами. Одним из наиболее простых является метод производящих функций. Производя­щей функцией распределения вероятностей состояний p_k(t) называет­ся ряд

, (70)

где |z|£l.

С учетом (68) ряд (70) сходится абсолютно. Умножая на z_k все уравнения (69) и суммируя по k от 0 до ¥, получим:

откуда следует

dln Ф/dt = l(z-1) (71)

Интегрируя (71), получим

ln Ф(t,z) – ln Ф(0,z) = l(z-1)t

С учетом начальных условий системы (69) можно написать

Ф(0,z) = p₀(0) = 1, ln Ф(0,z) = 0.

Следовательно,

Подставив вместо Ф(t,z) выражение (70), получим окончательно

(72)

Распределение (72) является известным распределением Пуассона, поэтому простейшие потоки называются пуассоновскими.

Важнейшей характеристикой любого потока является закон рас­пределения интервала времени Т между двумя соседними событиями в потоке (см.рис.5,б). Определим этот закон для пуассоновских потоков. Вначале рассмотрим интегральный закон распределения F(t)=p(t>T), т.е. вероятность того, что случайная величина Т при­мет значение, меньшее чем t. Для этого необходимо определить ве­роятность того, что в интервал времени t, отсчитываемый от момента t₀ появления некоторого события, попадет еще хотя бы одно событие (см.рис.5,б). Эту вероятность можно определить, зная вероятность отсутствия событий в интервале t, равную вероятности p₀(t) состояния S₀ на графе рис.5, а. В соответствии с (72)

p₀(t)=e^-lt

откуда следует

F(t)=p(t>T)=1-e^-lt , t>0 . (73)

Дифференцируя (73) по времени, получим искомый закон распреде­ления

(74)

Закон распределения (74) называется показательным (экспоненци­альным). Определим первые два момента показательного распределе­ния:

- математическое ожидание

(75)

- дисперсия

(76)

Интегрируя (75) и (76) по частям, получим

. (77)

Из (77) следует, что для показательного распределения математи­ческое ожидание и среднеквадратичное отклонение равны друг другу. Кроме того из (77) следует, что в простейшем потоке среднее время между двумя соседними событиями равно обратной величине ин­тенсивности потока.

Определим теперь вероятность попадания одного события в простейшем потоке на элементарный участок временной оси (см.рис.5,б). Так же, как и в предыдущем случае, эта вероятность

P₁(Dt) = 1 – P₀(t) = 1 - e^-lDt .

Разлагая e^-lDt в ряд по степеням lDt и ограничиваясь только первой степенью (в силу малости Dt), получим

P₁(Dt) = lDt . (78)

Выражение в правой части (78) называется элементом вероятности появления события в простейшем потоке.

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

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

Лекция 16. Модели систем массового обслуживания при пуассоновских потоках заявок. Модели систем массового обслуживания с отказами

Рассмотрим сначала самую простую одноканальную СМО с отказа­ми. Поток заявок, приходящих на вход данной СМО, обслуживается одним прибором. Если прибор занят, то заявка получает отказ и по­кидает систему. В качестве примера можно привести местную теле­фонную станцию с одним каналом выхода в городскую сеть. Размечен­ный граф состояний такой системы изображен на рис. 6.

Рис.6

Здесь S₀ - состояние, при котором обслуживающий прибор свободен, S₁ - состояние, при котором он занят. Вправо (из состояния S₀ в состояние S₁) систему переводит поток заявок с интенсивностью l, а влево - поток обслуживания с интенсивностью m. Будем считать, что оба потока являются пуассоновскими. Тогда время обслуживания является случайной величиной, распределенной по показательному закону с математическим ожиданием Т_об = l/m. Необходимо определить абсолютную и относительную пропускные способности данной СМО.

Относительная пропускная способность q может быть оценена как вероятность того, что заявка, пришедшая в СМО, будет обслужена. Очевидно, что это будет вероятность р₀ состояния S₀. Абсолютная пропускная способность А может быть оценена как произ­ведение относительной пропускной способности q на среднее число всех заявок в единицу времени l

А = lq. (79)

Таким образом, чтобы определить все характеристики данной СМО. необходимо знать вероятности состояний р₁ и р₀. Воспользуемся для этого уравнениями Колмогорова. В соответствии с вышеизложенными правилами и свойством вырожденности матриц плотностей вероятнос­тей перехода достаточно написать уравнение для вероятности состояния р₁ и условие нормировки

(80)

(81)

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

очевидно, что в соответствии с (77) вероятность

Графики функций p₀(t) и p₁(t) представлены на рис.6, видно, что при t®¥ вероятности р₀ и p₁ асимптотически стремятся к постоянным значениям. Изменение во времени вероят­ностей состояний называется переходным процессом (аналогично переходным процес­сам в динамических систе­мах). Количественная оценка характеристик СМО, основан­ная на установившихся (пре­дельных) вероятностях состояний, справедлива только лишь для моментов времени t>t_n, где t_n - время переходного процесса, начиная с которого вероятности состояний будут отличаться от своих предельных значений на достаточно малую величину. Это время t_n можно легко оценить с помощью показателя экспоненты -(l+m).

Изложенное дает основание заключить, что установившиеся зна­чения относительной и абсолютной, пропускных способностей данной СМО равны соответственно

(82)

Вероятность отказа

(83)

Рис.7

Ранее отмечалось, что вероятности состояний могут быть определе­ны как средние времена нахождения системы в этих состояниях. Ес­ли - среднее время занятости канала (среднее время нахождения заявки в СМО), а - среднее время простоя канала, то вероят­ность равна

Так как

Таким образом, зная предельные вероятности состояний, можно определить все характеристики СМО.

Перейдем теперь к более сложной системе - многоканальной системе массового обслуживания с отказами, которая называется системой Эрланга. Размеченный граф состояний СМО Эрланга пред­ставлен на рис.8, где S₀ - состояние СМО, при котором все ка­налы свободны; S₁ - один канал занят, остальные свободны; S₂ - два канала заняты, остальные свободны; S_n - все n каналов заняты.

Рис. 8

На вход системы поступает поток заявок с интенсивностью l, кото­рый будем полагать пуассоновским. Очевидно, что этот поток пере­водит систему вправо, поскольку с приходом каждой заявки занима­ются свободные каналы. С другой стороны, на систему от каждого прибора действуют потоки обслуживания, которые также будем пред­полагать пуассоновскими с одинаковой интенсивностью m, так как все каналы одинаковы. Очевидно, что если работают одновременно два прибора, то интенсивность суммарного потока обслуживания бу­дет равна 2/m, а если работают все n каналов, то интенсивность суммарного потока обслуживаний будет равна nm. Поэтому интенсивности потоков, переводя­щих систему влево, возрастают с увеличением номера состояния.

Задача Эрланга заключается в нахождении вероятностей всех состояний данной СМО и вычислении по ним ее характеристик.

В соответствии с размеченным графом состояний система урав­нений Колмогорова будет иметь вид

p₀’(t) = -lp₀(t)+ mp₁(t),

p₁’(t) = -(l+m)p₁(t)+ lp₀(t)+2mp₂(t) (84)

…

p_k’(t) = -(l+km)p_k(t)+lp_k-1(t)+(k+1)mp_k+1(t) (k=l,…,n-l)

…

p_n’(t) = —nmp_n(t)+lp_n-1(t)

с начальными условиями: р₀(0)=1, p_k(0)=0 (k=1,…,n), кото­рые соответствуют случаю, когда все каналы свободны при t=0. При этом решение (80) должно удовлетворять условию

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

В соответствии с правилами определения предельных вероятнос­тей состояний процесса размножения и гибели с размеченным графом состояний, изображенным на рис.8, запи­шем выражения для предельных вероятностей состояний:

(85)

Введем безразмерный параметр r=l/m и назовем его приведенной интенсивностью потока заявок, равной среднему числу заявок, по­ступивших за среднее время обслуживания (Т_ОБ=1/m). Тогда форму­лы (85) можно представить в виде

(86)

Формулы (86) называются формулами Эрланга.

Формулы Эрланга можно выразить через табличные функции рас­пределения Пуассона

(87)

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

Определив вероятности состояний, перейдем к вычислению характе­ристик СМО Эрланга.

1) Вероятность отказа будет равна вероятности р_n состояния S_n, когда все каналы заняты:

(88)

2) Вероятность того, что поступившая заявка будет принята к обслуживанию, является оценкой относительной пропускной способ­ности q:

(89)

3) Абсолютная пропускная способность в соответствии с (75)

(90)

4) Среднее число занятых каналов может быть определено по формуле для расчета математического ожидания случайной величины k, принимающей целочисленные значения с вероятностями p_k:

(91)

Однако в данном случае можно обойтись более простой формулой. Среднее число А заявок, обслуженных в единицу времени, будет рав­но среднему числу занятых каналов k, умноженному на интенсивность потока обслуживания каждого канала m, т.е. А=km, откуда

(92)

Отсюда коэффициент загрузки системы будет равен

(93)

Коэффициент простоя k_n = l-k₃.

5) Определим коэффициент загрузки через вероятность занятос­ти канала - p_ЗК. Эту вероятность можно выразить через среднее время занятости канала и среднее время простоя

(94)

Среднее время занятости канала равно, очевидно, среднему времени обслуживания одной заявки = 1/m. Следовательно, среднее время простоя канала можно найти из выражения (94)

(95)

Формулы (88) – (95) позволяют рассчитывать характеристики СМО как с применением функций P(k,r) и R(n,r), так и без них.

6) Дисперсия числа занятых каналов будет равна

Лекция 17. Модель простейшей одноканальной системы массового обслуживания с очередями.

Рассмотрим вначале простейшую одноканальную СМО с очередью, число мест в которой ограничено числом m (рис. 9). В системе возможны такие состояния: S₀- прибор свободен, очереди нет; S₁ -прибор занят, очереди нет; S₂ - прибор занят, в очереди стоит од­на заявка; S₃ - прибор занят, в очереди стоят две заявки; … ; S_m+1 - прибор занят, в очереди стоят m заявок.

Рис. 9

Если заявка приходит в момент времени, когда система нахо­дится в состоянии S_m+1, то она получает отказ и покидает систему. Поскольку работает только один прибор, то интенсивность потока обслуживаний m одинакова для всех состояний. Используя правила вычислений вероятностей состояний для данного процесса размноже­ния и гибели, получим

p₁ = p₀l/m = rp₀, … , p_k = r^kp₀, … ,p_m+1 = r^m+1p₀

. (96)

В формуле (96) использован тот факт, что знаменатель является суммой членов геометрической прогрессии со знаменателем r. С по­мощью (96) можно рассчитать основные характеристики системы.

1. Вероятность отказа в соответствии с правилами работы сис­темы равна вероятности последнего состояния p_m+1:

.

2. Относительная пропускная способность

(97)

3. Абсолютная пропускная способность

4. Среднее число заявок, находящихся в очереди (математи­ческое ожидание количества заявок), определяется путем суммирова­ния всех возможных длин очередей от 1 до m с их вероятностями в качестве весовых коэффициентов:

(98)

Подставляя в (98) значения вероятностей из (96), получим

(99)

Для вычисления суммы в (99) воспользуемся методом дифференциро­вания рядов с учетом формулы суммы геометрической прогрессии со знаменателем r:

(100)

Следовательно, подставляя (100) и (96) в (99), получим

(101)

5. Среднее число заявок, находящихся в системе:

где W - случайная величина, принимающая значения 0 (канал свобо­ден) и 1 (канал занят). Вероятность занятости канала (с учетом (97))

(102)

Следовательно, M[W] = 0×p₀+l(l-p₀)=rq, откуда

6. Среднее время ожидания заявки в очереди можно определить, усредняя времена ожидания заявок в очереди по всем состояниям S₁ + S_m+1, с учетом вероятностей этих состояний. Поскольку среднее время обслуживания одной заявки равно l/m, то среднее время ожидания заявки в очереди

Подставляя сюда выражение для p₁ из (92) и принимая во внимание формулу (96), имеем:

(103)

Сравнивая (103) и (97), получим = /l. Таким образом, среднее время ожидания заявки в очереди равно среднему числу зая­вок в очереди, деленному на интенсивность потока заявок. Среднее время нахождения заявки в системе определяется аналогичным об­разом:

7. Среднее время простоя канала t_ПК, в соответствии с (91) равно:

где среднее время занятости = 1/m, а p_ЗК определяется из (102). Тогда

Рассмотрим теперь предельный случай, когда число мест в очереди не ограничено (m®¥). Этот случай имеет смысл только при r<1. Тогда геометрическая прогрессия в знаменателе (92) сходится. Если же r>0, то Sr_i=¥ и для любого конечного k

Это означает, что для любого k система рано или поздно пройдет состояние sК и никогда в него не вернется, двигаясь все время вправо по графу процесса "размножения и гибели", т.е. очередь бу­дет разрастаться до бесконечности. Иными словами, если l³m, то система при бесконечной длине очереди не справляется с потоком заявок. Поэтому, когда m=¥ мы будем рассматривать только слу­чай r<1. Тогда в системе наступит стабилизация очереди на ка­ком-то конечном уровне. Для r<1, переходя в (92) к пределу при m®¥, будем иметь

(104)

Поскольку все заявки рано или поздно будут обслужены, то относи­тельная пропускная способность будет равна 1. Абсолютная пропускная способность А=lq=l. Среднее числа заявок в очереди:

(105)

Среднее число заявок в системе

(106)

Среднее время ожидания в очереди и среднее время нахождения заявки в системе t_c равны соответственно

(107)

Лекция 18. Модель многоканальной системы массового обслуживания с очередями.

Перейдем к рассмотрению многоканальной СМ0 с очередью. Пусть число каналов обслуживания равно n, а число мест в очереди - m. Если заявка приходит тогда, когда все n каналов заняты, она ста­новится в очередь. Если же заняты и все m мест в очереди, то за­явка получает отказ и покидает систему.

В такой СМО возможны следующие состояния: S₀ - все каналы свободны, очереди нет; S₁ - один канал занят, очереди нет; … ; S_n - n каналов заняты, очереди нет; S_n+1 - n каналов заняты, в очереди стоит одна заявка; … ; S_n+m - n каналов заняты, в оче­реди стоят m заявок.

Размеченный граф состояний данной СМО представлен на рис. 10.

Рис.10

Интенсивность потоков обслуживания, переводящих систему по цепочке влево, возрастает с подключением новых каналов до тех пор, пока СМО не достигнет состояния S_n. После того как в рабо­ту включатся все n каналов СМО, интенсивности потоков обслужива­ния остаются неизменными и равными nm для состояний S_n + S_n+m.

Введем обозначение

æ = r/n = l/nm . (108)

Величину æ назовем приведенной интенсивностью потока заявок многоканальной СМО. Тогда в соответствии с правилом вычисления веро­ятностей состояний для процесса размножения и гибели получим:

p₁ = rp₀, p_n+1 = rⁿæp₀/n!

p₂ = r²p₀/2!, p_n+2 = rⁿæ²p₀/n!

…

p_n = rⁿp₀/n!, p_n+m = rⁿæ^mp₀/n!

(109)

Просуммируем геометрическую прогрессию со знаменателем æ в выражении для р₀. Получим

. (110)

Выражения (109) и (110) дают возможность по аналогии с одноканальной СМО определить все основные характеристики многоканальной СМО:

1. Вероятность отказа

p_ОТК = p_n+m = rⁿæ^mp₀/n!

2. Относительная пропускная способность

q = 1 - p_ОТК = 1 - rⁿæ^mp₀/n!

3. Абсолютная пропускная способность

А = lq = l[1 - rⁿæ^mp₀/n!]

4. Среднее число заявок в очереди

5. Среднее число занятых каналов . Если каждый канал об­служивает в среднем m заявок в единицу времени, а вся СМО обслу­живает А заявок за то же время, то среднее число занятых каналов

(111)

Отсюда можно определить вероятность занятости канала p_ЗК = /n.

6. Среднее число заявок, находящихся в системе,.

7. Среднее время ожидания заявки в очереди.

8. Среднее время ожидания заявки в системе.

Перейдем к предельному случаю при m®¥. Легко заметить, что этот переход возможен, как и в предыдущей СМО, только при æ < 1 (l < nm), так как в данном случае в выражении для р₀ суммиру­ется геометрическая прогрессия со знаменателем æ. Опуская проме­жуточные выкладки, которые рекомендуется проделать читателю, выпишем основные соотношения для предельного случая.

1. Предельные вероятности состояний

(112)

p₁ = p₀r¹/1! (i=1,…,n)

…

p_n+j = æ^jp₀rⁿ/n! (j=n+1,…,¥)

2. Вероятность отказа Р_ОТК = 0, q = 1, A = l.

3. Среднее число заявок в очереди

(113)

4. Среднее число занятых каналов z и среднее число заявок k, находящихся в системе:

(114)

Остальные характеристики находятся аналогичным образом.

В заключение рассмотрим СМО с ограниченным временем пребывания заявки в очереди. Будем считать, что число мест в очереди не ограничено (m=¥), а число каналов обслуживания равно n. Раз­меченный граф состояний такой системы представлен на рис.11, где состояния S₀ + S_n+r имеют тот же смысл, что и в предыдущем случае. Различие заключается в том, что заявки могут находиться в очереди ограниченное время, после чего они покидают систему, если за время ожидания их не успеют обслужить. Для того чтобы рассмот­реть такую СМО с "нетерпеливыми" заявками в рамках теории марковских процессов, будем считать, что на заявки, стоящие в очере­ди, действует пуассоновский "поток уходов" с интенсивностью v. Если среднее время ожидания заявки в очереди равно , то

Рис.11

Тогда интенсивности потоков, переводящих состояние системы влево, равны сумме интенсивности потока обслуживании nm и соответствую­щих интенсивностей потоков уходов rv = r/, где r - число зая­вок, находящихся в очереди. Кроме приведенной интенсивности пото­ка заявок æ = l/nm введем также приведенную интенсивность потока уходов многоканальной СМО b = v/nm.

Тогда в соответствии с правилами вычисления вероятностей состоя­ний процесса размножения и гибели получим:

(115)

Бесконечный ряд в выражении для р0 сходится при любых æ и b. В этом можно убедиться, применяя любой известный признак сходимости рядов. Это означает, что поток уходов стабилизирует очередь и не позволяет ей разрастись до бесконечности. Среднее число заявок, находящихся в очереди такой СМО, можно определить обычным обра­зом:

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

Определим вначале абсолютную пропускную способность. Если в очереди содержатся в среднем r заявок, то в единицу времени будет уходить vr заявок, а приходить - l заявок. Оставшиеся после ухо­дов заявки будут обслужены, следовательно.

А = l - v. (116)

Относительная пропускная способность

(117)

Среднее число занятых каналов определяется аналогично предыдущему случаю:

(118)

Из (118) можно найти r:

(119)

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

Однако сумму этого ряда определить достаточно сложно из-за необходимости суммирования бесконечного ряда для нахождения рn. Чтобы обойти это затруднение, сумму членов бесконечного ряда заменя­ют суммой (r-1) членов конечного ряда, отбрасывая все остальные члены, начиная с r-го. Легко показать, что погрешность вычисления суммы в результате такой замены

.

Заметим, что из (115) - (119) при v®0 (или b®0) в пределе получаем выражения для обычной многоканальной СМО с очередью ("нетерпеливые" заявки становятся "терпеливыми"). Вероятность от­каза в такой СМО с "нетерпеливыми" заявками не имеет смысла.

Все прочие характеристики СМО находятся способом, аналогичным ранее описанному.