Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь FAQ Написать работу КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Лекция 14. Основы марковских процессов. Уравнения Колмогорова↑ ⇐ ПредыдущаяСтр 9 из 9 Содержание книги
Поиск на нашем сайте
Определение марковского процесса. Пусть имеется система S, состояние которой изменяется во времени случайным, непредсказуемым образом и представляет собой случайный процесс. Этот процесс называется марковским, если для каждого момента времени t0 вероятность любого состояния при t > t0 (в будущем) зависит только от вероятности, состояния в момент t0 (в настоящем) и не зависит от вероятностей состояний при t < t0 (в прошлом). Иными словами, свойство марковского процесса заключается в том, что на вероятности достижений будущих состояний "предыстория" процесса не оказывает никакого влияния. Если некоторая система меняет свое состояние скачкообразно, причем переходы из одного состояния в другое обладают марковским свойством, то случайный процесс в такой системе называется марковской цепью. Марковская цепь называется дискретной, если переход из одного состояния в другое происходит в строго фиксированные промежутки времени, отделенные друг от друга равными интервалами. Если же эти переходы возможны в любой момент времени t, то соответствующая марковская цепь называется непрерывной. Переход из одного состояния в другое может быть отображен графом состояний, в котором вершины представляют собой возможные состояния системы, а дуги графа отражают переходы из одного состояния в другое. Если две вершины i и j соединяются дугой (i,j), то это означает, что возможен непосредственный переход из состояния i в состояние j. Марковская цепь может, таким образом, быть представлена как случайное блуждание на графе состояний системы. Поскольку переход из одного состояния в другое для СМО возможен в любой момент времени, определяемый появлением заявки во входном потоке, то для изучения СМО применяются непрерывные марковские цепи. Одна из важнейших задач теории марковских процессов вообще и ТМО в частности заключается в нахождении вероятностей состояний цепи. Эти вероятности для непрерывных марковских цепей определяются с помощью дифференциальных уравнений Колмогорова.
Рис.1 Рассмотрим некоторую произвольную систему, граф состояний которой приведен на рис.1. Система имеет n состояний S1,S2,...,Sn. Процесс перехода из одного состояния в другое описывается непрерывной цепью Маркова. Пусть Pi(t) - вероятность того, что в момент времени t система будет находиться в состоянии Si (i=1,2,…,n). Поскольку система не может находиться одновременно в двух состояниях, то события, заключающиеся в нахождении системы в состояниях S1,S2,…,Sn, несовместны и образуют полную систему событий. Отсюда следует (47) Это соотношение называется условием нормировки. Задача заключается в определении вероятности любого состояния Pi(t) в любой момент времени t. Введем понятие вероятности перехода системы из состояния i, где она находилась в момент времени t, в состояние j за время Dt Pij(t,Dt). Очевидно, что Pij(t,Dt) представляет собой условную вероятность того, что в момент времени t + Dt система окажется в состоянии Sj при условии, что в момент времени t она находилась в состоянии Si: pij(t,Dt)= p(Sj(t+Dt)/Si(t)). Предел отношения вероятности перехода pij(t,Dt) к длине интервала времени Dt назовем плотностью вероятности перехода . (48) Плотность вероятности перехода определим только для случаев i¹j. Если lij(t)=const, то марковская цепь называется однородной. В противном случае, когда lij(t) являются функциями времени, цепь называется неоднородной. При расчетах вероятностей состояний марковской цепи предполагается, что все эти плотности вероятностей переходов lij известны. Если у каждой дуги графа состояний системы проставить плотность вероятности перехода по данной дуге, то полученный граф назовем размеченным графом состояний (см.рис.1). Уравнения Колмогорова составляются в соответствии с размеченным графом состояний. Рассмотрим фрагмент размеченного графа состояний (рис.1), обведенный штрихпунктирной линией. Отбросим вначале дуги, изображенные пунктиром, и определим вероятность нахождения системы в состоянии Si в момент времени t+Dt. С учетом того, что вершина Si связана только с вершинами Sk и Sj, указанное событие будет иметь место в двух случаях: - система находилась в состоянии Si в момент времени t и за время Dt из этого состояния не вышла; - система находилась в состояния sk в момент времени t и за время Dt перешла из Sk в Si. Если отрезок Dt достаточно мал, то вероятность перехода pij(t,Dt) может быть определена приближенно с помощью (48) pij(t,Dt)» lij(t)Dt (49) С учетом (49) и свойства марковости процесса вероятность первого случая (отсутствие перехода по дуге (Si,Sj)) pI = (1-lij(t)Dt)pi(t). Вероятность второго случая с учетом (49) pII» lki(t)pk(t). Тогда можно определить искомую вероятность как pi(t+Dt)= pI + pII = (1-lij(t)Dt)pi(t) + lki(t)pk(t)Dtpk(t) или (50) Переходя в (49) к пределу при Dt ® 0, получим . (51)
Теперь добавим к вершине Si дуги, обозначенные на рис.1 пунктиром. Тогда при вычислении pi(t+Dt) необходимо учитывать возможный переход из Si в Sj и Sr и переходы из Sk и Sl в Si. В этом случае PI = [1-(lij(t)+lir)Dt]p1(t), PII = lk1(t)Dtpk(t)+ll1(t)Dtp1(t). Повторяя вышеописанные рассуждения, получим . (52)
На основании (51) и (52) можно сформулировать правила составления уравнений Колмогорова по размеченному графу состояний непрерывной марковской цепи: 1. Система дифференциальных уравнений Колмогорова имеет форму Коши. Каждое уравнение составляется с помощью рассмотрения вероятности состояния, представленного соответствующей вершиной в размеченном графе. Число уравнений системы равно числу вершин графа. 2. Число слагаемых правой части каждого уравнения равно числу дуг, инцидентных соответствующей вершине. 3. Дугам с положительной инциденцией соответствуют отрицательные слагаемые, а дугам с отрицательной инциденцией - положительные. 4. Каждое слагаемое правой части равно произведению вероятности состояния, соответствующего началу рассматриваемой дуги, на плотность вероятности перехода по данной дуге. Начальные условия для системы уравнений Колмогорова определяются начальным состоянием системы. Например, если начальное состояние было S2, то начальные условия имеют вид: p1(0)=0; р2(0)=1; р3(0)=0;…;рn(0)=0. Уравнения (51) и (52) были выведены для общего случая неоднородной марковской цепи. Для однородной марковской цепи все lij(i,j=l,…,n) постоянны. Рассмотрим одно важное свойство уравнений Колмогорова (51), которое может быть представлено в виде , (53)
где - n-мерный вектор вероятностей состояний системы; р = {p1(t),…,pn(t)}; L - n´n-матрица плотностей перехода. В соответствии с вышеописанными правилами составления уравнений Колмогорова одна и та же плотность вероятности перехода lij будет входить в одно из уравнений со знаком "+", а в другое - со знаком "-", поскольку для двух смежных вершин дуга, соединяющая их, будет обладать положительной инциденцией по отношению к одной вершине и отрицательной по отношению к другой. Это приведет к тому, что сумма всех элементов в каждом столбце матрицы будет равна нулю. Тогда любая строка матрицы L будет равна сумме остальных строк. Следовательно, матрица L является всегда вырожденной. Более строго это свойство доказывается в [7]. Рассмотрим систему с размеченным графом состояний, изображенным на рис.2. Система уравнений Колмогорова и матрица L для этого случая в соответствии с правилами 1-4 будут иметь вид: dp1/dt=-(l12+l13)p1+l41p4, dp2/dt=l12p1-l25p2+l32p3, dp3/dt=l13p3-(l32+l34)p3+l53p5, (54) dp4/dt=l34p1-(l41+l45)p4, dp5/dt=l25p2+l45p4-l53p5. Исключение любого уравнения из этой системы нарушает указанное соотношение для строк матрицы L, следовательно, ранг матрицы L будет равен n-1. Для того чтобы система уравнений Колмогорова имела единственное решение при заданных начальных условиях, необходимо исключить любое из уравнений системы (54) и заменить его условием нормировки (47). Итак, решение системы (53) без одного уравнения (безразлично какого) с условием (47) определяет в любой момент времени поведение вероятностей состояний марковской цепи при заданных начальных условиях.
Рис.2
Получить это решение можно с помощью любых численных методов (например, Рунге-Кутта, Эйлера-Коши и т.д.), реализуемых на ЭВМ. Только в самых простых случаях система уравнений Колмогорова может быть проинтегрирована в квадратурах. В большинстве практических случаев для расчета вероятностей состояний используются не решения систем уравнений Колмогорова в любой момент времени, а асимптотические оценки этих решений при t®¥.
Лекция 15. Предельные вероятности состояний. Простейший поток событий.
Асимптотические оценки в соответствии с известной теоремой А.А.Маркова могут быть получены для марковских цепей, обладающих эргодическим свойством. Определение 1. Если число состояний системы конечно и из каждого состояния можно перейти в любое другое за произвольное число шагов, то говорят, что такая система обладает эргодическим свойством. Определение 2. Пусть марковский процесс характеризуется вероятностями перехода из состояния i в состояние j за время t pij(t) (0£i£n; 0£j£n). Процесс называется транзитивным, если существует такое t>0, что pij(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 = V1ÈV2È…ÈVn, то такая система называется разложимой. Примеры таких систем приведены на рис.3. На рис.3,а представлена система с двумя эргодическими множествами V1=(S2,S3,S4) и V2(S5,S6). На рис.3, б эргодическое множество состоит лишь из одного состояния (S4). Если эргодическое множество состоит лишь из одного состояния, то это состояние называется поглощающим, так как попав в него однажды, процесс остается навсегда в поглощающем состоянии. Характерная особенность графа состояний неразложимой эргодической марковской системы заключается в том, что каждой вершине этого графа инцидентны дуги как с положительной, так и с отрицательной инцидентностью (т.е. у каждой вершины имеются дуги, направленные как к вершине, так и от нее, см., например, рис. 1 и 2).
а б Рис. 3
Вычисление предельных вероятностей состояний для таких систем упрощается в связи с тем, что, поскольку все эти вероятности являются постоянными величинами, то их производные по времени равны 0 (dpi/dt=0 для всех i). Поэтому левые части системы уравнений Колмогорова (54) приравниваются нулю и она превращается в систему линейных алгебраических уравнений . (55) Нетривиальное решение системы (55) может быть получено только в случае вырожденности матрицы L. Выше было доказано, что матрица плотностей вероятностей L является вырожденной. Система (55) без одного из своих уравнений дополняется условием нормировки (56)
Соотношения (55) и (56) позволяют определить предельные вероятности состояний. Поскольку часть слагаемых, соответствующая дугам с отрицательной инцидентностью, положительна, а другая часть, соответствующая дугам с положительной инцидентностью, отрицательна, то каждое уравнение системы (55) может быть составлено с учетом мнемонического правила: для каждого состояния сумма членов, соответствующих входящим дугам, равна сумме членов, соответствующих выходящим дугам. Пример. Для системы, изображенной на рис.2, из уравнений Колмогорова (54) следует (l12+l13)p1=l41p4 (l41+l45)p4=l34p3 l25p1=l12p1+l32p3 l53p3=l52p2+l45p4 (l32+l34)p4=l13p1+l53p5 (57) Для решения (57) нужно исключить любое из первых пяти уравнений (например, пятое, как содержащее наибольшее число членов). Предельные вероятности состояний используются в ТМО значительно чаще, чем решения уравнений Колмогорова, причем, зная решение системы уравнений Колмогорова, можно определить момент окончания переходного процесса изменения вероятностей состояний во времени. Это дает возможность рассчитать, промежуток времени начиная от включения системы в работу, по истечении которого вероятности состояний достигнут своих предельных значений и будут справедливы оценки, использующие эти значения. В заключение этого параграфа рассмотрим один частный, но практически очень важный класс марковских процессов, широко применяемых при исследовании СМО. Это - процессы "размножения и гибели". К ним относятся марковские цепи, представимые размеченным графом, который состоит из вытянутой цепочки состояний, изображенной на рис.4.
Рис.4
Матрица плотностей вероятностей переходов такой системы является якобиевой (тридиагональной):
Рассматривая начальное состояние S0, получим в соответствии с (55) l01p0=l10p1 (58) Для состояния S1 имеем l01p0+l21p2=l10p1+l12p1 (59) Вычитая из (59) равенство (58), получим l21p2 = l12p1(60) Продолжая этот процесс до n-гo состояния включительно, получим ln,n-1pn=ln-1,npn-1 Из (58) теперь можно выразить p1 через р0: p1=p0(l01/l10) (61) Подставляя (60) в (61), получим p2=p0(l01l12/l10l21) Очевидно, что для произвольного k (1£k£n) будет справедливо выражение . (62)
В соответствии с (62) и размеченным графом состояний, представленным на рис.4, можно сформулировать правило, с помощью которого можно выразить предельные вероятности состояний процесса "размножения и гибели" через вероятность начального состояния р0. Это правило гласит: вероятность произвольного состояния pk (l£k£n) равна вероятности начального состояния р0, умноженной на дробь, числитель которой равен произведению плотностей вероятностей перехода для дуг, переводящих состояние системы слева направо, а знаменатель - произведение плотностей вероятностей перехода справа налево от начального до k-гo состояний включительно. Вероятность р0 находится из условия нормировки и выражений (62) следующим образом: (63)
Выражения (62) и (63) полностью определяют предельные вероятности процесса "размножения и гибели". Цепи Маркова с непрерывным временем являются математическими моделями СМО. Для анализа СМО необходимо также иметь математические модели входных потоков заявок на обслуживание. Эти математические модели представляют собой потоки события, являющиеся отдельным классом случайных процессов. Потоком событий называется последовательность однородных событий, следующих одно за другим в случайные моменты времени. Этот поток количественно может быть охарактеризован числом событий x(t), имевших место в течение определенного промежутка времени (0,t). Тогда случайный поток событий можно определить как случайный процесс x(t) (t³0), в котором функция x(t) является неубывающей функцией времени, способной принимать лишь целые неотрицательные значения. Иными словами, график функции x(t) является ступенчатой кривой с постоянной высотой ступеньки, равной единице, причем ширина ступеньки - случайная величина. Примерами таких потоков могут служить: поток вызовов на АТС, поток запросов в вычислительный центр коллективного пользования и т.п. Моменты появления событий можно отобразить точками на временной оси, поэтому поток событий часто представляется и как последовательность таких точек. Поток событий называется регулярным, если события следуют одно за другим через одинаковые, строго фиксированные промежутки времени. В ТМО такие потоки практически, не используются, однако они представляют интерес как предельный случай. Значительно чаще имеют дело с потоками, в которых времена поступления событий и, следовательно, промежутки времени между ними являются случайными (иррегулярными). При этом наиболее простые расчетные соотношения получаются при использовании простейших потоков событий, которые широко применяются при исследовании CMО. Простейшими называются потоки, обладающие следующими тремя свойствами: стационарностью, ординарностью и отсутствием последействия. Рассмотрим эти свойства подробнее. 1. Поток событий называется стационарным, если вероятность pk(l) того, что за отрезок времени t произойдет k событий, зависит только от его длины t и не зависит от его расположения на временной оси, т.е. pk(t’,t’+t)=pk(t). Из определения однородной марковской цепи следует, что стационарность - это однородность потока по времени. 2. Поток называется ординарным, если вероятность попадания на любой элементарный участок временной оси двух или более событий является бесконечно малой величиной, т.е.
3. Поток событий называется потоком без последействия, если вероятность попадания событий на некоторый участок временной оси не зависит от того, сколько событий попало на другие участки. Иными словами, условная вероятность наступления k событий за промежуток времени (t’,t’+t), вычисленная при любом условии чередования событий до момента t', равна безусловной вероятности pk(t) того же события, т.е. p[(t’,t’+t),k/(t",t"+t),m]=pk(t),tÇtk=Æ, t"<t’. На практике редко встречаются потоки, удовлетворяющие всем трем допущениям одновременно. Например, поток вызовов в АТС в дневные часы более интенсивен, чем в ночные. Тем не менее, рассматривая работу АТС в периоды с 12 до 13 ч дня и с 2 до 3 ч ночи, поток вызовов на этих более коротких промежутках можно с высокой степенью точности считать стационарным. Этот пример говорит о том, что в большом числе случаев можно ввести определенные упрощения, вытекающие из принципов работы конкретных реальных систем и позволяющие проводить исследование реальных СМО путем замены их входных потоков простейшими. Это дает возможность существенно упростить математический аппарат исследования СМО. Указанные свойства простейших потоков позволяют просто определить их распределение вероятностей pk(t), т.е. вероятность того, что за отрезок времени длиной t произойдет k событий. Прежде всего следует оговорить, что мы будем рассматривать только те потоки, в которых за конечный промежуток времени t с вероятностью 1 будет происходить лишь конечное число событий, т.е. (64) Тогда простейший поток можно представить цепью Маркова, изображенной на рис.5,а, где состояние S0 означает отсутствие событий в интервале t, S1 - появление одного события за время t, S2 - появление двух событий за время t,…, Sk - появление k событий за время t. Применив правила составления уравнений Колмогорова для такого размеченного графа состояний, получим: dp0(t)/dt = - lp0(t), dp1(t)/dt = - lp1(t)+lp0(t) (65) … dpk(t)/dt = - lpk(t)+lpk-1 … с начальными условиями: р0(0)=1, р1(0)=0,…, рk=0,… Плотность вероятности перехода l, которая участвует в уравнениях (65), является в данном случае интенсивностью потока событий. Под интенсивностью потока понимается среднее по ансамблю реализаций число событий в единицу времени. Вероятность перехода рi,i+1(t,t+Dt) равна вероятности появления одного события в интервале от t до t+Dt, поскольку ординарность потока исключает появление большего числа событий в этом интервале. Очевидно, что эта вероятность равна среднему числу появлений одного события за время Dt. Тогда с учетом определения (48) можно сделать вывод, что плотность вероятности перехода для марковской цепи (52) равна интенсивности простейшего потока. В стационарном простейшем потоке l = const, тогда как в нестационарном потоке интенсивность зависит от времени: l = l(t).
а б Рис.5
Решить систему (65) можно различными методами. Одним из наиболее простых является метод производящих функций. Производящей функцией распределения вероятностей состояний pk(t) называется ряд , (66) где |z|£l. С учетом (64) ряд (66) сходится абсолютно. Умножая на zk все уравнения (65) и суммируя по k от 0 до ¥, получим: откуда следует dln Ф/dt = l(z-1) (67) Интегрируя (67), получим ln Ф(t,z) – ln Ф(0,z) = l(z-1)t С учетом начальных условий системы (65) можно написать Ф(0,z) = p0(0) = 1, ln Ф(0,z) = 0. Следовательно, Подставив вместо Ф(t,z) выражение (66), получим окончательно (68)
Распределение (68) является известным распределением Пуассона, поэтому простейшие потоки называются пуассоновскими. Важнейшей характеристикой любого потока является закон распределения интервала времени Т между двумя соседними событиями в потоке (см.рис.5,б). Определим этот закон для пуассоновских потоков. Вначале рассмотрим интегральный закон распределения F(t)=p(t>T), т.е. вероятность того, что случайная величина Т примет значение, меньшее чем t. Для этого необходимо определить вероятность того, что в интервал времени t, отсчитываемый от момента t0 появления некоторого события, попадет еще хотя бы одно событие (см.рис.5,б). Эту вероятность можно определить, зная вероятность отсутствия событий в интервале t, равную вероятности p0(t) состояния S0 на графе рис.5, а. В соответствии с (68) p0(t)=e-lt откуда следует F(t)=p(t>T)=1-e-lt, t>0. (69) Дифференцируя (69) по времени, получим искомый закон распределения (70) Закон распределения (70) называется показательным (экспоненциальным). Определим первые два момента показательного распределения: - математическое ожидание (71) - дисперсия (72) Интегрируя (71) и (72) по частям, получим
. (73)
Из (73) следует, что для показательного распределения математическое ожидание и среднеквадратичное отклонение равны друг другу. Кроме того из (73) следует, что в простейшем потоке среднее время между двумя соседними событиями равно обратной величине интенсивности потока. Определим теперь вероятность попадания одного события в простейшем потоке на элементарный участок временной оси (см.рис.5,б). Так же, как и в предыдущем случае, эта вероятность P1(Dt) = 1 – P0(t) = 1 - e-lDt. Разлагая e-lDt в ряд по степеням lDt и ограничиваясь только первой степенью (в силу малости Dt), получим P1(Dt) = lDt. (74) Выражение в правой части (74) называется элементом вероятности появления события в простейшем потоке. Марковские цепи являются математическими моделями некоторых реальных систем, а потоки событий являются моделями внешних воздействий на эти системы. В дальнейшем будем считать, что переход системы из одного состояния i в другое j в соответствии с размеченным графом состояний происходит под действием потока событий с интенсивностью lij, равной соответствующей плотности вероятности перехода. Эта интенсивность определяется как среднее число переходов из состояния i в состояние j за единицу времени. Если все потоки событий являются пуассоновскими, то процесс в системе будет марковским.
Лекция 16. Модели систем массового обслуживания при пуассоновских потоках заявок. Модели систем массового обслуживания с отказами Рассмотрим сначала самую простую одноканальную СМО с отказами. Поток заявок, приходящих на вход данной СМО, обслуживается одним прибором. Если прибор занят, то заявка получает отказ и покидает систему. В качестве примера можно привести местную телефонную станцию с одним каналом выхода в городскую сеть. Размеченный граф состояний такой системы изображен на рис. 6.
Рис.6
Здесь S0 - состояние, при котором обслуживающий прибор свободен, S1 - состояние, при котором он занят. Вправо (из состояния S0 в состояние S1) систему переводит поток заявок с интенсивностью l, а влево - поток обслуживания с интенсивностью m. Будем считать, что оба потока являются пуассоновскими. Тогда время обслуживания является случайной величиной, распределенной по показательному закону с математическим ожиданием Тоб = l/m. Необходимо определить абсолютную и относительную пропускные способности данной СМО. Относительная пропускная способность q может быть оценена как вероятность того, что заявка, пришедшая в СМО, будет обслужена. Очевидно, что это будет вероятность р0 состояния S0. Абсолютная пропускная способность А может быть оценена как произведение относительной пропускной способности q на среднее число всех заявок в единицу времени l А = lq. (75) Таким образом, чтобы определить все характеристики данной СМО. необходимо знать вероятности состояний р1 и р0. Воспользуемся для этого уравнениями Колмогорова. В соответствии с вышеизложенными правилами и свойством вырожденности матриц плотностей вероятностей перехода достаточно написать уравнение для вероятности состояния р1 и условие нормировки (76) (77) Начальные условия уравнения (76) означают, что в момент запуска СМО обслуживающий прибор свободен. Подставляя (77) в (76) и решая полученное уравнение при данных начальных условиях, будем иметь: очевидно, что в соответствии с (77) вероятность Графики функций p0(t) и p1(t) представлены на рис.6, видно, что при t®¥ вероятности р0 и p1 асимптотически стремятся к постоянным значениям. Изменение во времени вероятностей состояний называется переходным процессом (аналогично переходным процессам в динамических системах). Количественная оценка характеристик СМО, основанная на установившихся (предельных) вероятностях состояний, справедлива только лишь для моментов времени t>tn, где tn - время переходного процесса, начиная с которого вероятности состояний будут отличаться от своих предельных значений на достаточно малую величину. Это время tn можно легко оценить с помощью показателя экспоненты -(l+m). Изложенное дает основание заключить, что установившиеся значения относительной и абсолютной, пропускных способностей данной СМО равны соответственно (78)
Вероятность отказа (79)
Рис.7
Ранее отмечалось, что вероятности состояний могут быть определены как средние времена нахождения системы в этих состояниях. Если - среднее время занятости канала (среднее время нахождения заявки в СМО), а - среднее время простоя канала, то вероятность равна Так как Таким образом, зная предельные вероятности состояний, можно определить все характеристики СМО. Перейдем теперь к более сложной системе - многоканальной системе массового обслуживания с отказами, которая называется системой Эрланга. Размеченный граф состояний СМО Эрланга представлен на рис.8, где S0 - состояние СМО, при котором все каналы свободны; S1 - один канал занят, остальные свободны; S2 - два канала заняты, остальные свободны; Sn - все n каналов заняты.
Рис. 8
На вход системы поступает поток заявок с интенсивностью l, который будем полагать пуассоновским. Очевидно, что этот поток переводит систему вправо, поскольку с приходом каждой заявки занимаются свободные каналы. С другой стороны, на систему от каждого прибора действуют потоки обслуживания, которые также будем предполагать пуассоновскими с одинаковой интенсивностью m, так как все каналы одинаковы. Очевидно, что если работают одновременно два прибора, то интенсивность суммарного потока обслуживания будет равна 2/m, а если работают все n каналов, то интенсивность суммарного потока обслуживаний будет равна nm. Поэтому интенсивности потоков, переводящих систему влево, возрастают с увеличением номера состояния. Задача Эрланга заключается в нахождении вероятностей всех состояний данной СМО и вычислении по ним ее характеристик. В соответствии с размеченным графом состояний система уравнений Колмогорова будет иметь вид p0’(t) = -lp0(t)+ mp1(t), p1’(t) = -(l+m)p1(t)+ lp0(t)+2mp2(t) (80) … pk’(t) = -(l+km)pk(t)+lpk-1(t)+(k+1)mpk+1(t) (k=l,…,n-l) … pn’(t) = —nmpn(t)+lpn-1(t) с начальными условиями: р0(0)=1, pk(0)=0 (k=1,…,n), которые соответствуют случаю, когда все каналы свободны при t=0. При этом решение (80) должно удовлетворять условию Уравнения (80) называются уравнениями Эрланга. В общем случае интегрирование системы уравнений Эрланга выполняется с помощью численных методов, реализуемых на ЭВМ, так как аналитическое решение является слишком сложным. Поэтому в дальнейшем ограничимся определением вероятностей состояний для установившегося режима. В соответствии с правилами определения предельных вероятностей состояний процесса размножения и гибели с размеченным графом состояний, изображенным на рис.8, запишем выражения для предельных вероятностей состояний: (81) Введем безразмерный параметр r=l/m и назовем его приведенной интенсивностью потока заявок, равной среднему числу заявок, поступивших за среднее время обслуживания (ТОБ=1/m). Тогда формулы (81) можно представить в виде (82) Формулы (82) называются формулами Эрланга. Формулы Эрланга можно выразить через табличные функции распределения Пуассона (83)
аналогичные дифференциальному и интегральному законам распределения. Так же, как и для нормального распределения, таблицы этих функций имеются в литературе. С учетом (83) формулы Эрланга (82) перепишутся в виде Определив вероятности состояний, перейдем к вычислению характеристик СМО Эрланга. 1) Вероятность отказа будет равна вероятности рn состояния Sn, когда все каналы заняты: (84)
2) Вероятность того, что поступившая заявка будет принята к обслуживанию, является оценкой относительной пропускной способности q: (85)
3) Абсолютная пропускная способность в соответствии с (75) (86) 4) Среднее число занятых каналов может быть определено по формуле для расчета математического ожидания случайной величины k, принимающей целочисленные значения с вероятностями pk: (87)
Однако в данном случае можно обойтись более простой формулой. Среднее число А заявок, обслуженных в единицу времени, будет равно среднему числу занятых каналов k, умноженному на интенсивность потока обслуживания каждого канала m, т.е. А=km, откуда (88)
Отсюда коэффициент загрузки системы будет равен (89)
Коэффициент простоя kn = l-k3. 5) Определим коэффициент загрузки через вероятность занятости канала - pЗК. Эту вероятность можно выразить через среднее время занятости канала и среднее время простоя (90)
Среднее время занятости канала равно, очевидно, среднему времени обслуживания одной заявки |
||
| Поделиться: |
Познавательные статьи:
Последнее изменение этой страницы: 2016-08-26; просмотров: 941; Нарушение авторского права страницы; Мы поможем в написании вашей работы!
infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.138.67.56 (0.011 с.)