Министерство образования Республики Беларусь БЕЛОРУССКАЯ ГОСУДАРСТВЕННАЯ ПОЛИТЕХНИЧЕСКАЯ АКАДЕМИЯ Кафедра «Высшая математика № 2» А.Д.Корзников В.В.Павлов ЭЛЕМЕНТЫ ТЕОРИИ МАРКОВСКИХ ПРОЦЕССОВ И СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ Методическое пособие для студентов инженерно-экономических специальностей втузов М и н с к 2 0 0 1 Министерство образования Республики Беларусь БЕЛОРУССКАЯ ГОСУДАРСТВЕННАЯ ПОЛИТА АКАДЕМИЯ Кафедра «Высшая математика № 2» А.Д.Корзников В.8.Павлов ЭЛЕМЕНТЫ ТЕОРИИ МАРКОВСКИХ ПРОЦЕССОВ И СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ Методическое пособие для студентов инженерно-экономических специальностей втузов Минск 2001 у д е 519.217 514?. 872 Корзников А.Д. Элементы теории марковских процессов и систем массового обслуживания; Метод, пособие для студ. инженерно-экономических спец. втузов / А.Д.Корз- ников, В.В.Павлов. - Мн : БГПА, 2001. - 40 с. В пособии описаны случайные марковские процессы, протекаю- щие в вероятностных системах, - системах массового обслуживания (СМО). Помимо теоретического материала в пособии приведены примеры по основным типам СМО. Данное пособие написано в полном соответствии с программой курса «Высшая математика» для студентов инженерно-экономиче- ских специальностей втузов. Рецензент В.В.Веременюк © Корзников А.Д., Павлов В В., 2001 1. МАРКОВСКИЕ ПРОЦЕССЫ В практической деятельности очень часто приходится сталки- ваться с анализом работы своеобразных вероятностных систем, назы- ваемых системами массового обслуживания (СМО). Примерами та- ких систем могут служить телефонные станции, обслуживание на АЗС, обработка приходящих на железнодорожную станцию составов, ремонт неисправного оборудования и т.д. Теория массового обслужи- вания изучает зависимость между характером потока заявок (требо- ваний) , поступающих в случайные моменты времени на вход систе- мы, и производительностью обслуживающих устройств, а также опи- сывает количественные характеристики, позволяющие оценить эф- фективность функционирования системы. В СМО происходит случайный процесс, что обусловлено слу- чайным характером потока заявок и временем их обслуживания. Ис- следование работы СМО существенно облегчается, если случайный процесс, протекающий в СМО, является марковским. Это позволяет е помощью обыкновенных дифференциальных уравнений (в предель- ном случае - линейных алгебраических уравнений) найти основные количественные характеристики СМО. Поэтому вначале рассмотрим основные понятия марковских процессов. Пусть состояние некоторой системы S (АТС, АЗС, ремонтная мастерская и т.д.) изменяется в процессе ее функционирования. Если состояния системы изменяются во времени заранее непредсказуемым образом, то в системе S протекает случайный процесс. Случайный процесс, протекающий в системе 5, называется мар- ковским, если для каждого момента времени t0 вероятность пребыва- ния системы в любом из состояний в будущем (() > to) зависит только от того, в каком состоянии система находилась в настоящем (t = t0\ и не зависит от того, когда и каким образом система пришла в это со- стояние (т.е. не зависит от того, как развивался процесс в прошлом). Случайный процесс называется процессом с дискретными со- стояниями, если множество возможных состояний системы {S!t S2, ..., конечно либо они могут быть перечислены одно за другим: SJt S2, ... , S„. Сам процесс состоит в том, что система S время от времени скачком переходит из одного состояния в другое. Граф состояний системы геометрически изображает возможные состояния системы, а II стрелки указывают возможные переходы системы из состояния в со- стояние (рис. 1). Если система S переходит из состояния в состояние в фиксиро- ванные моменты времени th t2, ... , то случайный процесс, протекаю- щий в системе S, называется процессом с дискретным временем; если же система 5 переходит из состояния в состояние в случайный мо- мент времени t, то - процессом с непрерывным временем. Рассмотрим процесс с дискретным временем. Обозначим через S{t^ состояние системы в момент времени t k , е {//, t2, ... }, S(tk) е е {Sj, S2,... ,5„}, а черезр{j (к) - условную вероятность перехода сис- темы S из состояния Si, в котором она находилась в момент времени tk-i, в состояние Sj в момент времени Г*: Такие вероятности будем называть переходными вероятностями. Если Pi j(k) не зависят от того, когда и как система пришла в со- стояние Si, то говорят, что в системе протекает марковский процесс. Марковский процесс называется однородным, если вероятности перехода из состояния в состояние pi j(k) не зависят от времени, когда осуществляется переход, т.е. от к, а лишь от состояний 5, и Sj, в про- тивном случае процесс называется неоднородным. Рассмотрим однородный марковский процесс. Обозначим через Pii вероятность перехода системы из состояния S, в состояние Sj за S Рис. 1 PiJ(k) = P{S(4i) = Sj\S(tk_l)=Si). (1) II один переход (шаг); через р,, - вероятность задержки системы S в со- стоянии St. Полная вероятностная картина переходов будет задаваться матрицей Р- >11 Р\2 '"Pin Р2\Ргг-Ргп Р„ 1 Рп2-Рпп) (2) которая называется матрицей переходных вероятностей, или мат- рицей вероятностей переходов. Элементы данной матрицы удовлетворяют условиям: I) 0 = F(0)P • P = K(0 )P2, F(3) = V(2)P = V{0)P2 • P = V(0)P} и Продолжая таким образом, получим V(m) = V(Q)P"'. (5) Пример 2. В начальный момент времени система (см. пример. 1) находится в состоянии Sh Определить вероятности состояний систе- мы после двух шагов. Решение. Вектор вероятностей состояний системы S в начальный момент времени V(0) = (1; 0; 0; 0). Найдем вектор V(2) вероятностей состояний системы после двух шагов по формуле (5): F(2) = F(Q) Р2. Следовательно, Г(2) = (1;0;0;р) ^0,5 0,4 0 0,1 = (0,5; 0,4; 0,1; 0} 0,5 0 0 0 0 0 0,4 0.1 0 0 0,1 0 0,6 0,3 0,7 0,3 0 0,1 0,6 0,7 0 1 '0,5 0 0 о 0) 0,3 0,3 1 0,4 0,1 0 о 0,1 0,6 0,7 0 0 0,3 0,3 1 =(0,25; 0,24; 0,36; 0,15). Марковский процесс называется регулярным, если система мо- жет перейти из любого состояния 5, в любое другое состояние Sj за конечное число шагов. Это означает, что существует т е N такое, что все элементы матрицы Р т строго положительны. Рассмотрим марковский процесс с дискретными состояниями и непрерывным временем. Обозначим через V,{t) вероятность того, что в момент времени t система будет находиться в состоянии S„ /=1,2,..., п . В любой момент времени t справедливо соотношение II 1=1 Обозначим через Pjj{Ai) вероятность перехода системы из со- стояния Sj в состояние Sj за время At. Плотностью вероятности перехода Л,у будем называть величину, VK) равную Л-(ДО Ay = lim — — - . (6) 1 д(->о д/ Из (6) следует, что при достаточно малом At Ру (At) = Ay • At + 0 (At) я Ay • At. Если плотности вероятностей не зависят от времени (Л,у = const), то марковский процесс с непрерывным временем называется одно- родным, в противном случае - неоднородным. Рассмотрим однородный марковский процесс с непрерывным временем. Вероятности состояний системы S Vj(t), V2(f),..., V„(0 мож- но найти, решая систему обыкновенных дифференциальных уравнений (уравнений Колмогорова), которая может быть получена из следую- щих соображений. Найдем одну из вероятностей состояний системы, например, V/(r). Придадим / малое приращение 4t и найдем вероятность V;(/ + Al) того, что в момент времени (t + At} система будет находиться в состоя- нии S]. Это событие может произойти следующими п способами: система находилась в состоянии S, и осталась в этом состоянии; система находилась в состоянии S2 и за время At перешла в со- стояние S f , система находилась в состоянии S3 и за время At перешла в со- стояние Si и т.д. Воспользовавшись формулой полной вероятности, получим V,(t + At) = V,(t)Pn(At) + V2(t)P21(At) + ... + Vn(t)Pni(At) . II Так как сумма элементов любой строки матрицы вероятностей переходов равна единице, то Р„(Л() = 1 - Pl2(At) -... - P,„(At). Отсюда V,(t + At) = Vl(t)(l-Pn(At)-...-Pln(At)) + V2(t) P21(At) +... + Vn(t)PnI(At) = = Ы) - V,(t)(Pn(At) +...+ P,n(At)) + V2(t)P2l(At) +...+ V„(t)P„i(At). Учитывая, что Рц(М) ~ Д,у - At, получим V,(t + At) - V,(t) = - F/fJ +... + . Я ^ Л + v2(t)[x21 +... + f / ? ; At. Разделим обе части на At и, устремив At к нулю, перейдем к пре- делу: Левая часть есть не что иное, как производная функции Vj(t) , то есть Таким образом, получено дифференциальное уравнение, которо- му должна удовлетворять функция V,{t). Аналогичные дифференци- альные уравнения могут быть выведены и для остальных вероятно- стей состояний: V2(t), V3(t),..., V„(t). Получим систему II Решение этой системы дифференциальных уравнений даст нам искомые вероятности состояний как функции времени. Начальные условия берутся в зависимости от того, в каком состоянии находилась система в начальный момент времени. Например, если система в на- чальный момент времени (t = 0) находилась в состоянии Sj, то на- чальными условиями будут: при t = О К/0) = 1, К,(0) = 0, если / * j. Если рассмотреть граф состояний системы и систему дифферен- циальных уравнений Колмогорова, то можно легко описать правило построения последней. В левой части каждого уравнения стоит производная вероятно- сти состояния системы, а правая часть содержит столько членов, сколько стрелок связано с данным состоянием в графе состояний сис- темы. Если стрелка направлена из состояния, то Соответствующий член имеет знак "минус", а если в состояние - знак "плюс". Каждый член равен произведению плотности вероятности перехода, соответ- ствующей данной стрелке, умноженной на вероятность того состоя- ния, из которого исходит стрелка. Пример 3. Размеченный граф состояний системы S имеет вид, приведенный на рис. 3. Составить уравнения Колмогорова, если в на- чальный момент времени система находится в состоянии Sh Решение. Уравнения Колмогорова имеют вид II dV - ^ - V . ' V v dV2 dt dV И Т - Ч : j - W V * Начальные условия: при с = 0 ^ = 1 , ^ = ^ = ^ = 0. Интегри- рование этой системы уравнений даст нам вероятности состояний ..., Vn(t) системы S. Можно было бы все уравнения системы не составлять; так как V, + V2 + V3 \.У4 = 1, то можно составить систему уравнений, к примеру, для Vh V2, V3 и найти V4 = 1 - {V, -f V2 + V3), Рассмотрим однородный марковский процесс с известной мат- рицей вероятностей переходов Р (см. формулу (2)). Если марковский процесс является регулярным, то при т +со, независимо от началь- ного состояния, система будет функционировать в установившемся режиме, то есть вероятности сбстояний системы в этом режиме не за- висят от начального состояния. Такие вероятности V = (У},У2,...,У„) называются предельными или финальными и могут быть найдены из следующих соображений. Пусть Етп единичная пхп матрица. Тогда У(т) = У(т)Е = У(т-])Р или У(т)Е-У(т-1)Р = 0. Переходя к пределу при т —• оо и учитывая, что lim У(т )= lim У ( т - l) = V. т-*оо 4 ' да--*» 4 ' ф получаем Уф • Е - Уф •/>= 0 или УФ-(Е-Р) = 0. (7) II Таким образом, для определения финальных вероятностей Уф = (F1,...,Fn) необходимо решить систему линейных однородных уравнений (7) с учетом того, что Vt + V2 + ... + V„ = ]. Пусть в системе S с дискретными состояниями Sh S2, ..., S„ про- текает однородный марковский случайный процесс с непрерывным временем. Составив систему уравнений Колмогорова и проинтегри- ровав их при заданных начальных условиях, мы получим вероятности состояний системы S: Vi(t), V2(t), ..., Vn(t) как функции от t. Если су- ществуют пределы этих функций при t ~> <», то они называются пре- дельными или финальными вероятностями состояний: = = (8) Справедливо следующее условие: если число состояний системы S конечно и из любого состояния можно перейти за конечное число шагов в любое другое состояние, то предельные вероятности состоя- ний существуют и не зависят от начального состояния системы. На рис. 4 показан граф состояний, удовлетворяющий вышесказанному условию, а на рис. 5 - не удовлетворяющий. Рис.4 Рис.5 При t -» оо в системе S устанавливается предельный стационар- ный режим, причем вероятности состояний системы Vh V2 , ... , V„ предстайляют собой среднее относительное время пребывания систе- мы в данном состоянии. Так как производная от постоянных предель- ных вероятностей равна нулю, то для того, чтобы их найти, нужно все левые части уравнений Колмогорова положить равными нулю и ре- II шить систему линейных алгебраических уравнений совместно с до- полнительным условием + У2 + ••• + К - 1- 2. ПРОЦЕСС «ГИБЕЛИ И РАЗМНОЖЕНИЯ» Найдем предельные вероятности состояний системы на примере процесса "гибели и размножения". Марковский непрерывный процесс называется процессом "гибели и размножения", если граф состояний имеет вид, показанный на рис. 6. •^23 S2 Я.21 ^32 •^п-2,п-1 sn- ^п-1, п S„ ^п-1, п-2 V п-1 Рис.6 Так как режим в данной системе является установившимся, то по правилу составления уравнений Колмогорова получаем систему ал- гебраических уравнений Ч г - Ч у Я V ГЛ V, п-1,и п - 1 и,и-1 й У.+К+...+Г =1 . 1 2 л (9) Выразим вероятности V2,..., V„ через Vt. Из первого уравнения системы (9) имеем (1С) Из второго уравнения получаем II 32 32 21 И так далее: Л . • Л . . -...-Л , 'Л. I / п - \ . п И - 2 . И - 1 2 3 1 2 т / г - = Х - , . л , , - - Л 2 - я '• 1 1 2 1 п , п - 1 п - 1 , л - 2 3 2 2 1 Выразим V] из последнего уравнения системы (9), подставив в него V2, Vh ..., Г„: 1 + Д 1 2 + Я 2 3 - Д , 2 ^ / " - ' . » - - а 2 3 - ; 1 1 2 1 V ^ l Яп,п-\-'Лц'Л2\ (13) Тогда остальные вероятности V2,..., F„ состояний системы нахо- дятся из формул (10)-(12) при подстановке в них У/. 3. ПРОСТЕЙШИЙ ПОТОК СОБЫТИЙ В большинстве случаев при рассмотрении процессов, проте- кающих в системе с дискретными состояниями и непрерывным вре- менем, удобно представлять, что переходы системы из состояния в состояние происходят под действием потоков событий (требований), например, потока машин, подъезжающих на АЗС. Поток требований называется регулярным, если требования сле- дуют одно за другим через строго определенные промежутки време- ни. На практике такой поток редок, но представляет интерес как пре- дельный случай. Чаще приходится встречаться с потоками требова- ний, когда промежутки времени между ними являются случайными величинами. Рассмотрим потоки требований, которые обладают сле- дующими свойствами: стационарностью, ординарностью и отсут- ствием последействия. 1. Поток требований называется стационарным, если вероят- ность появления того или иного числа требований на участок времени II длиной At зависит только от его длины, но не от места его располо- жения на оси времени Ot (рис. 1). Вероятностные характеристики стационарного потока требова- ний не изменяются во времени. Интенсивность (или плотность) пото- ка требований - среднее число требований, поступающих в единицу времени, - для стационарного потока является постоянной. 2. Поток требований называется Ординарным, если вероятность появления двух или более требований за достаточно малый промежу- ток времени At пренебрежимо мала по сравнению с вероятностью по- явления одного требования. Это означает, что требования в потоке приходят поодиночке. 3. Поток требований называется потоком без последействия, ес- ли для любых непересекающихся участков времени число требова- ний, попадающих на один из них, не зависит от того, сколько требо- ваний попало на другой. Отсутствие последействия означает, что тре- бования появляются в последовательные моменты времени независи- мо друг от друга. Поток требований, обладающий всеми тремя свойствами, назы- вается простейшим или пуассоновским потоком. Вероятность поступ- ления к требований в течение промежутка времени t для такого пото- ка определяется формулой Пуассона: Для выяснения смысла параметра Я вычислим математическое ожидание числа требований, поступивших с СМО в течение проме- жутка времени (0, t): t О Рис.7 II M(t)= I kPk(t)= ЬкЩ-е-ь =e-*'At £ = £ Ц^ • i = 1 * = 1 ' * = I л = 0 Так как „ = 0 И 2! п! то получаем M(t) = Л t. При t = } M(t) - Л, то есть параметр Л равен среднему числу требований, поступающих в СМО в единицу времени. Но тогда среднее время между поступлениями требований равно МЛ. Для пуаесоновского потока с параметром Л промежутки времени между поступлениями требований распределены по экспоненциаль- ному закону с функцией распределения F(t) = I - еХ'. Действительно, F(t) - Р(Т< t). Но вероятность Р(Т < t) того, что промежуток време- ни между поступлениями требований меньше t, равна вероятности то- го, что за этот промежуток поступило хотя бы одно требование, т.е. = е - д ' И + е д ' ) = 1 - < Г / 1 ' . — Л' / * * /L1 Отметим еще одно важное свойство, которым обладают пуассо- новские потоки.Объединение нескольких пуассоновских потоков да- ет снова пуассоновский поток, а вероятностное разделение пуаесо- новского потока на несколько дает независимые пуассоновские пото- ки. Если поток требований формируется п независимыми источника- ми интенсивности Л/, / = 1, 2,..., я, потоки соизмеримы и оказывают на сумму равномерно малое влияние, то объединение этих потоков в один дает пуассоновский поток интенсивности Л = Л; + Л2 + ... + Л„ . II 4. КЛАССИФИКАЦИЯ СМО При исследовании СМО предполагаем, что потоки требований, переводящие систему из одного состояния в другое, являются про- стейшими. Это обусловлено следующим: 1) простейшие потоки часто встречаются на практике; 2) для простейшего потока сравнительно просто получить фор- мулы для вычисления характеристик работы различных СМО; 3) если потоки требований не являются простейшими, то при анализе такой СМО могут быть получены приближенные, достаточно удовлетворительные результаты, если этот поток заменить простей- шим с такой же интенсивностью. В СМО выделяют следующие основные компоненты: входящий поток требований, дисциплина очереди, узел обслуживания, выходя- щий поток требований. Будем считать, что все потоки требований, переводящие СМО из состояния в состояние, являются простейшими. Входящий поток представляет процесс поступления в систему требований, нуждающихся в обслуживании. Если требования посту- пают в систему по одному (например, прибытие автомобилей на АЗС, поступление заказов в ателье и т.д.), то такие СМО называются сис- темами с единичным поступлением требований. Если же требования поступают в систему группами (посетители ЗАГСа, прибытие вагонов на станцию под погрузку и разгрузку и т.д.), то такие СМО называют системами с групповым поступлением требований. СМО, у которых требование, поступившее в тот момент, когда все узлы обслуживания заняты, получает отказ и покидает систему, называются системами с отказами (потерями). СМО, у которых требование, поступившее в тот момент, когда все узлы обслуживания заняты, становится в очередь и ожидает, пока не. освободится один из узлов, называются системами с ожиданием (очередью). Системы с ожиданием (очередью) делятся на системы с неограниченным ожиданием и системы с ограниченным ожиданием. В системах с неограниченным ожиданием требование, посту- пившее в тот момент, когда все узлы обслуживания заняты, становит- ся в очередь и ждет обслуживания. В таких системах поступившее требование всегда будет обслужено. II В системах с ограниченным ожиданием на пребывание требова- ния (заявки) в очереди могут накладываться ограничения: длина оче- реди - число одновременно находящихся в очереди требований; ог- раниченное время пребывания каждого требования в системе. Процесс выбора требований из очереди на обслуживание харак- теризуется дисциплиной очереди. Чаще всего на практике встречаете* дисциплина: первым поступил - первым обслужен. В этом случае об- служивание в СМО с ожиданием является упорядоченным, требова- ния обслуживаются в порядке поступления. Кроме того, в некоторых СМО применяются приоритетные дисциплины очереди - приори- тетные СМО. В таких СМО некоторые требования обслуживаются в первую очередь на оснований каких-то признаков. После выбора из очереди требования поступают в узел обслужй вания, который характеризуется продолжительностью й порядков выполнений процедуры обслуживания. Узел обслуживания может со стоять из одного обслуживающего устройства (канала), в этом случае система называется одноканальной СМО, или из нескольких - многд канальной СМО. Время обслуживания является одной Из самых важных характе ристик обслуживающего устройства. Как правило, это случайная вв личина, зависящая в каждом конкретном случае от ряда причин. Там например, время обслуживания автомобиля, поступившего на стаи- .цию технического обслуживания для ремонта, будет зависеть от ди- агностики, серьезности неисправности, наличия запасных частей it т.д. Поэтому случайная величина - время обслуживания, Тобсл., может быть полностью охарактеризовано функцией распределения т = Р(Тобс.,. гп+2 2 /0>-»'гя+« т , О» п п\ п п\ п п\ п+2 1! 2f п\ (рпЛ рп+г рп к +-С1—+...+— а-а п2 • п\ пт п\ -1 (21) В круглых скобках в выражении для У0 стоит геометрическая прогрессия со знаменателем р/п. Суммируя ее, мы получаем выраже- ние для Vq. Fn = 1! 2t ni и! Р) -Pi п) п -1 - 1 (22) Вероятность того, что поступившее требование получает отказ, равна р -* - ' п+т .п+т •У,п птп\ (23) II Тогда относительная пропускная способность как дополнение вероятности отказа до единицы равна п+т l - £ — V 0 . (24) п п\ Абсолютная пропускная способность равна n+m A = X-q = X(\-£— -V0). (25) п •«! Найдем к - среднее число занятых обслуживанием каналов. Для данной СМО оно уже не будет совпадать со средним числом требова- ний, находящихся в системе, к можно найти как математическое ожидание дискретной случайной величины: — и т k = lk-Vk + Zn-V„+J. (26) к=\ j=I Так как каждый канал обслуживает в среднем /л заявок в единицу времени, а вся СМО обслуживает в среднем А заявок в единицу вре- мени, то среднее число занятых обслуживанием каналов можно найти следующим образом: ; _ п+т к=А/М = р { ( 2 7 ) п -т Легко получить среднее число простаивающих устройств: "пр. - п - к . (28) Тогда можно определить коэффициент простоя обслуживающих каналов и коэффициент занятости II k к Л = \ - к пр. n зан. n пр. (29) Среднее число требований в очереди обозначим го ж , и вычис- лим как математическое ожидание дискретной случайной величины: Гож. = 1 - Vn+i + 2 • V„+2 + ... + т • Vn+m. Учитывая формулы (21), получаем: и V п _ Р п+1 и и! т-1 (30) вид Введем обозначение р/ и = а. Тогда сумма в формуле (30) имеет = 1 + 2а +• За? + ...+т- сГ'1. Если нэйти сумму геометрической прогрессии а + + сГ со знаменателем а и продифференцировать затем обе части, мы "получим, что , „ 2 m-i 1-ат(т + 1-та) , .1Ч Гож = 1 + 2а + За2 + ... + т - с Г , = — — * г (31) ( 1 - а ) Среднее число требований, находящихся в системе, равно г = г + к. ож. (32) Найдем среднее время }ож. ожидания требования в очереди. По- ступающее в систему требование будет ожидать в очереди только то- гда, когда будут заняты все обслуживающие устройства, при этом в очереди могут быть 0, 1, 2,..., т - 1 требований. Если в очереди 0 требований, то поступающее требование будет ждать в среднем время, равное 1 / п/и, т.к. поток обслуженных требо- 27 ваний п каналами имеет интенсивность пц. Если в очереди 1 требова- ние, то поступающее требование ожидает время 2 / пц (по 1 / пц на каждое впереди стоящее требование) и т.д. Если в очереди к требова- ний (к < т), то поступившее требование ожидает в среднем время (к+ ])/ пц. Тогда : 1 f , 2 t / т „ р" -Г 2 р Ър2 тртА Л пц пц пц птц ^ п п п ) Можно заметить, что это выражение отличается от формулы (30) только множителем \ I рц= 1/Л .Тогда получаем, что *аж. = Г J ' . <33) Обозначим через Тсист. случайную величину - время нахождения требования в системе, и через <9 - случайную величину, равную вре- мени обслуживания. Причем 0 = Тобс , если требование обслуживает- ся, и <9= 0 в противном случае: Тсист. = Тож. + ® По теореме сложения математических ожиданий получаем М(Гсист.) = М(Гож.) + М(0) . Отсюда среднее время ~tcucm нахождения требования в системе, с учетом того, что M(@f = q, Г обе. = q/ц, равно tcucm. = tax. + Ц/Ц- (34) Пример 5. Автозаправочная станция (АЗС) имеет две колонки (и = 2). Поток-машин, прибывающих на заправку, имеет интенсив- ность Я = 2 (машины в минуту). Среднее время обслуживания (за- правки) одной машины to6c. = 2 мин. Площадка у АЗС может вме- II стить не более трех машин ( т = 3). Машина, прибывшая в момент, когда все три места в очереди заняты, покидает АЗС (получает отказ). Найти вероятность отказа, абсолютную и относительную пропускные способности, среднее число- машин в очереди, среднее время ожида- ния и пребывания машины на АЗС. Решение. Имеем: и = 2, т = 3, Я = 2, р = 1 /t06c. = 0,5, р = 4, а = = рМ = 2. По формулам (21 )-(22) находим Кй = г = — = 0,008. 0 , 4 42 4 2 - 2 125 1 + -+—•+- 1 2 2 1 - 2 Вероятность отказа ^ , = ^ = ^ = 6 4 ^ = 0,512. Относительная пропускная способность q = 1 - Ротк. = 0,488. Таким образом, более половины машин, прибывших на АЗС, не Moiyr быть обслужены. Абсолютная пррпускная способность А = q • Я = 0,976 машин в минуту, т А 0.976 . Среднее число занятых колонок к = — = - — - = 1,952, т.е. обе р 0,5 колонки почти все время заняты. Среднее число машин в очереди 4 3 1 - 4 2 3 + 3 2 4 1 6 17 = 2,18. оае' 2-2-125 (1 -2 ) 3 125 _ - т ож, 2,18 Среднее время ожидания в очереди: /о ж . = —— = —— = 1,U9 ми-л JL нуты. II Среднее время пребывания машины на АЗС (включая время об- служивания) tcucm. = \ож. + q • tc6e. = 1,09 +0,976 = 2,07 минуты. Выше была рассмотрена СМО, когда длина очереди ограничена некоторым числом т. Посмотрим, что будет происходить, если длина очереди не ограничена, а может быть сколь угодно большой. Рассфтрим многоканальную СМО с неограниченной очередью. Граф состояний системы имеет вид, изображенный на рис. 11. So к к к Ц 2(Л пц к Sn Sn+i пц Рис. 11 к к к пц пц пц Вероятности состояний системы найдем предельным переходом (при т оо) из формул (21)-(22). Пусть р/п < 1 (иначе при р/п > 1 очередь будет бесконечно возрастать), тогда сумма соответствующей геометрической прогрессии сходится. Отсюда получаем 1! 2! п\ и+1 ,и+2 V, п+1 *о = f j р — Л ; vn+i о ; п-п\ п -и! п -п\ „2 „п п+1 1 Р Р Р Р 1! 2! и! nl(n - р) (35) Так как каждое поступающее в систему требование будет об- служено в любом случае, то Ротк = 0, q = 1, Л = Я • q = Я. Среднее число занятых обслуживанием устройств найдем из (27): А Л . я , . = — = — = р. р р (36) 30 Среднее число требований в очереди получим из формулы (30) при т —> со; - /1И+' 1 l - - V 0 . (37) пп\ ( \-Е Среднее время ожидания требования в очереди и среднее число требований, находящихся в системе, будем находить по формулам (32)-(33) соответственно. Пример 6. Автозаправочная станция с двумя колонками in = 2) обслуживает поток машин с интенсивностью Л = 0,8 машин в минуту. Среднее время обслуживания одной машины (обе. = — = 2 мин. Р В данном районе нет другой АЗС, так что очередь машин перед АЗС может расти практически неограниченно. Найти характеристики СМО. Решение. Имеем: п = 2, Я = 0,8, р = = 0,5, р = 1,6,а = — = 0,8. tобе. п Поскольку а <1, очередь не растет безгранично и имеет смысл говорить о предельном стационарном режиме работы СМО. По фор- мулам (35) находим вероятности состояний: V п = 4 09 Т 1 1 + 1,6 + 1,28 + - ^ - «0,111; 2 0,4 У{=1,6У0* 0,178; У2 =1,28К0» 0,142; Уз <М14; У4 =^~Уо*0,091 2-2! 2 - 2 ! и т.д. Среднее число занятых каналов найдем, разделив абсолютную пропускную способность СМО А = Я = 0,8 на интенсивность обслу- живания р = 0,5: 0,5 3,1 Вероятность отсутствия очереди у АЗС будет Vq + V, + V2 ^0,431, Среднее число машин в очереди 1,63 0,111 п „ , гож. — г «0,71. 2 -2 0,422 Среднее число машин на АЗС г = i t+ голс. «0,71 + 1,6 = 2,31. Среднее время ожидания в очереди /«ж. = » 0,89 мин. Д Среднее время пребывания машины на АЗС tcucn = /в*.+ « 0,89 +2 =2,89 мин. Замечание. Для нахождения характеристик работы одноканаль- ных СМО с ограниченной очередью и неограниченной очередью нужно в вышеприведенных расчетных формулах для многоканальной СМО положить п = 1. 7. ЗАМКНУТЫЕ СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ В вышерассмотренных СМО заявки на обслуживание приходили извне и интенсивность потока заявок не зависела от состояния самой системы. СМО, в которых интенсивность общего потока заявок зависит от того, сколько заявок связано с процессом обслуживания, т.е. от со* стояния самой системы, называется замкнутой. Элементами замкну* той СМО являются как обслуживающие каналы, так и источники зая- II вок. Для замкнутой СМО характерно ограниченное число источников заявок. Рассмотрим задачу обслуживания рабочим п станков. Интенсив- ность потока неисправностей каждого станка равна Я. Интенсивность общего потока заявок зависит от того, сколько имеется неисправных станков, т.к. при выходе из строя станок перестает быть источником заявок. Таким образом, интенсивность потока станков, требующих обслуживания, зависит от состояния самой системы, следовательно, это замкнутая СМО. На наладку станка рабочий тратит в среднем 1 to6c. = —, где м ~ интенсивность потока отремонтированных станков. И Число станков п - ограничено. Наша система имеет следующие состояния: 50 - все станки исправны (рабочий свободен); 51 - один станок неисправен (рабочий занят его наладкой); 52 - два станка неисправны, один налаживается, другой находит- ся в очереди; Sn - все п станков неисправны, один налаживается, (я - 1) Стан- ков находятся в очереди. Граф состояний имеет вид, показанный на рис. 12. Очереди нет Ц Ц Ц Ц Рис. 12 Как видим, процесс, протекающий в данной СМО, является ча- стным случаем процесса "гибели и размножения". Введя обозначение Я — = р , из формул (10)-( 13) получаем М II yt=l3Lr0=!*fr0=npr0; Я 2 1 Я 1 0 Ц Vn __ Л01Л Л ^ ф - l l . A - r Kq ^ „ . ц . . ^ . (38) /1л,л-1"-/("21/11<> Ц vn = Я10 Я21Л0 , Вероятность того, что рабочий будет свободен (соответствует вероятности состояния So), равна У0. Поэтому вероятность того, что рабочий занят наладкой станка, равна: Рхт. = 1 - у* (39) Если рабочий обслуживает /л станков в единицу времени, то аб- солютная пропускная способность системы (среднее число станков, обслуженных рабочим в единицу времени) равна A = f3m,-fi = {\-V0)-p. (40) Поскольку каждая заявка (станок) будет обслужена, то относи- тельная пропускная способность q- 1. Среднее число станков, связанных с процессом обслуживания (математическое ожидание числа неисправных станков), будет равно ш = 1 • V, + 2- V2 + ... + n- Vn, (41) Общее число Останков, связанных с обслуживанием, равно W = = R + U, где R - число станков в очереди; U - число станков, которые обслуживаются (ремонтируются), U = {0, 1}. Тогда среднее значение U (ее математическое ожидание) равно II и = 0- Уо+Л • Узан. = 1-У0. Вычитая эту величину из ы , получим среднее число станков г , находящихся в очереди в ожидании обслуживания: Важной характеристикой данной СМО является производитель- ность группы станков, обслуживаемых рабочим. Средняя относительная потеря производительности за счет неис- правностей равна 1 = йг • I, где иг - среднее число неисправных стан- ков, а / - производительность исправного станка в единицу времени. Пример 7. Рабочий обслуживает три станка. Каждый станок ос- танавливается в среднем 2 раза в час. Процесс наладки занимает у ра- бочего в среднем 10 минут. Определить характеристики замкнутой СМО: вероятность занятости рабочего; абсолютную пропускную спо- собность, среднюю относительную потерю производительности стан- ков за счет неисправностей. Решение. По условию имеем: п = 3, Л = 2, р = -—-777 > tofic. 1/6 Л 1 /£> = — = - . По формулам (38) находим: г = ы - и. (42) Р 3 1 1 1 + 3- + 3 - 2 ' 3 3 К, = 3 - ^ 0 «0,346. 1 0,346. 2 + 3-2-1 • - г З3 2 Вероятность занятости рабочего Рзт = \ - У0~ 0,654 II Абсолютная пропускная способность рабочего (среднее число не- исправностей, которое он ликвидирует за час) равна А = 0,654 • 6 = 3,94. Среднее число неисправных станков находим по формуле (41): ш = 1 • 0,346 + 2 • 0,231 +3 - 0,077 * 1,04. Средняя относительная потеря производительности станков за счет неисправностей ьт/п = 0,347. Таким образом, за счет неисправно- стей станков теряется около 35% их общей производительности. Рассмотрим теперь более общую замкнутую СМО. Предполо- жим, что имеется п устройств, которые могут потребовать обслужи- вания, и т обслуживающих каналов ( т <п). Перечислим возможные состояния системы. 50 - все устройства работают, обслуживающие каналы сво- бодны; 51 - одно устройство вышло из строя, один канал >занят обслу- \ живанием; Sm-rn устройств вышло из строя, все каналы заняты обслужи- ванием; Sm+} — (т +1) устройство вышло из строя, т из них налажива- ются, одно ждет в очереди; Sn - все п устройств вышли из строя, т из них налаживаются, (п - т) ждут в очереди. Если обозначить, как обычно, через X - интенсивность, с кото- рой одно устройство выходит из строя, а через р - интенсивность по- тока обслуживании одним каналом, и учитывая, что процессы, проте- кающие в СМО, являются марковскими, можно построить граф со- стояний СМО. Он имеет вид, изображенный на рис. 13. Очереди нет (n-m+T)%~Xn-m)/l (n-m-1 )Х >m+l т ц т ц т ц т ц Рис. 13 II Как обычно, интенсивности потоков событий, переводящих сис- тему из состояния в состояние, проставлены у стрелок. Воспользо- вавшись правилом составления уравнений Колмогорова в установив- шемся режиме (формулы (9)-(13)), находим предельные вероятности: V -ИЛу V, = 1-2 я (я -1Хя-2 ) (Л 1-2-3 го> Vm = п{п - Щи - 2)...(и - т +1) (Л Ущ+l ~ т+2 1-2-3. ..т l-2...w?n и(и-1).. .(и-/и-1) l - Z - m m 2 \т ч/и+1 л и. У0, О' т+2 Уо> У„ = ф-1)...1 1 • 2...mm" Л , п Л п(п-\) (Л 1 + + 1 1 р 1 - 2 \р +...+ я(я-3)..1(«-/и + 1) l-2-..m Т + п(п-1)...(п-т) I 1 1-2 . . .mm Л Р) и(и-1)...1 1-2 ...mm" ' л Г (43) Обозначая, как всегда, — = р , приведем формулы к виду II vn = n и(и-1) 2 и (и-1) . . . (и -т + 1) 1 + - p + 1! 2! -p'+...+• ml p m + . n(n-\)...{n-m) , я(я-1)...1 H • p +...H p m\m m\-rnn~m _n(n-l)...(n-m + l) ' m — P ' 0 ' m! я(я-1) . . . (я- /и) „+1 m\m Pm+,V0; K„ = p V0. m\-mn (44) Через эти вероятности выражается среднее число z занятых ра- бочих: 2 = 0 • V0 + 1 • V, + 2 • V2 + ... + т {Vm + Vm+1 + ... + Vn) = = V, + 2 • V2 + ... + (m -1) Vm., + m(]-V0-V,-... - Vm.,). (45) Через z выражается, в свою очередь, среднее число станков, об- служиваемых бригадой в единицу времени (абсолютная пропускная способность): А = z -р, а также среднее число неисправных станков (46) z • р z w=n =п Л (36) Р 38 Отсюда же находится и средняя потеря производительности группы станков в единицу времени за счет неисправностей: нужно умножить среднее число неисправных станков ъ/ на производитель- ность / одного станка в единицу времени. Пример 8. Два рабочих обслуживают группу из шести станков. Остановки каждого (работающего) станка случаются, в среднем, че- рез каждые полчаса. Процесс наладки занимает у рабочего в среднем 10 минут. Определить характеристики замкнутой СМО: среднее чис- ло занятых рабочих; абсолютную пропускную способность; среднее количество неисправных станков. 1 А 1 Решение. Имеем: п = 6, т = 2, Я = 2, р = =— = 6 , р = — = ^. (обе. Р J По формулам (44) у + - I + 1 ( 6 - 5 - 4 I | 6 - 5 - 4 - 3 1 | 6 - 5 - 4 - 3 1 | + 1 3 + 1 • 2 З2 + 1 • 2• 2 З3 + 1 -2-2 " з 3 + 1 -2 -2 2 • З4 + . 6-5 4 -3 -2 J_ 6 -5 -4 -3 -2 • 1 1 1-2-2 3 З5 1 -2 -2 4 З6 у. = - . - . 0 ,153 » 0,306. 1 1 3 ч-< J =—-— « 0,153; 6,549 Вероятность того, что два рабочих заняты обслуживанием, равна (1 • Vo-V,). z = 1 • F; + 2 (1 - Vo - V,) = 1 • 0 , 1 5 3 2 • 0 ,5411 ,235 . . По формуле (46) находим абсолютную пропускную способность А = 1,235 • 6 = 7,41. По формуле (47) находим среднее число неисправных станков = 2,295. II С о д е р ж а н и е 1. МАРКОВСКИЕ ПРОЦЕССЫ . 3 2. ПРОЦЕСС «ГИБЕЛИ И РАЗМНОЖЕНИЯ» 13 3. ПРОСТЕЙШИЙ ПОТОК СОБЫТИЙ.. 14 4. КЛАССИФИКАЦИЯ СМО 17 5. СМО С ОТКАЗАМИ 20 6. СМО С ОЖИДАНИЕМ 24 7. ЗАМКНУТЫЕ СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ... 32 Учебное издание КОРЗНИКОВ Александр Дмитриевич ПАВЛОВ Валерий Валентинович ЭЛЕМЕНТЫ ТЕОРИИ МАРКОВСКИХ ПРОЦЕССОВ И СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ Методическое пособие для студентов инженерно-экономических специальностей втузов Редактор Т.Н.Мику лик _ Компьютерная верстка Н.А.Школьниковой Подписано в печать 15.03.2001. Формат 60x84 1/16. Бумага типографская №2. Печать офсетная. Гарнитура книжно-журнальная. Усл.печ. л. 2,3. Уч.-изд. л. 1,8. Тираж 200. Заказ 406. Издатель и полиграфическое исполнение: Белорусская государственная политехническая академия. Лицензия ЛВ №155 от 30.01.98. 220027, Минск, проспект ФСкорины, 65.