Основы построения аналитических моделей дискретных процессов и систем

Дисциплина “Математическое и Имитационное Моделирование ” Введение. Дисциплина состоит из двух разделов: 1. Математическое моделирование, содержащее: - теоретические основы построения математических (аналитических) моделей (АМ), - методику построения АМ и - решение конкретных задач расчёта характеристик дискретных систем по аналитическим моделям; 2. Имитационное моделирование, содержащее: - Принципы имитационного компьютерного моделирования дискретных систем (ИМ), - методику и средства построения имитационных моделей систем, (Средства ИМ - Язык и система имитационного моделирования – GPSS) - решение конкретных задач оценки численных значений характеристик процессов и систем по имитационным моделям. . Перечень тем раздела Аналитическое Моделирование - АМ: Лекция 1 ТЕМА 1. Теоретические основы построения аналитических моделей дискретных процессов и систем ТЕМА 2. МЕТОДИКА ПОСТРОЕНИЯ аналитических моделей дискретных процессов и систем ТЕМА 3. Классификация СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ как объектов моделирования ТЕМА 4.: Построение аналитических моделей типовых схем дИСКРЕТНЫХ пРОЦЕССОВ как процессов в системах массового обслуживания (смо) 4.1. Построение моделей расчёта характеристик одноканальных систем 4.2. Построение моделей расчёта характеристик многоканальных систем массового обслуживания Лекция 2 ТЕМА 5.: ПОСТРОЕИЕ АНАЛИТИЧЕСКИХ МОДЕЛЕЙ ЗАМКНУТЫХ СИСТЕМ ТЕМА 6.: УНИВЕРСАЛЬНАЯ МЕТОДИКА ПОСТРОЕНИЯ АМ СМО С ОГРАНИЧЕННОЙ ОЧЕРЕДЬЮ Лекция 1. ТЕМА 1. Теоретические основы построения аналитических моделей дискретных процессов и систем Общепринятая классификация моделирования систем приведена на рисунке: Итак, из этой схемы имеем многообразие понятий системы. Мы будем рассматривать класс систем, которые характеризуются: 1) дискретным множеством состояний и 2)непрерывным временем функционирования. Переход системы из одного состояния в другое называется событием. Событие происходить мгновенно, но в случайные моменты времени. Последовательность событий во времени называется потоком событий. К этому классу систем относятся так называемые СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ (СМО), охватывающие большое разнообразие процессов и систем человеческой деятельности (см. литературу по СМО). 1. Понятие о марковском процессе как теоретической основе моделирования систем с дискретными состояниями и непрерывным временем Марковский случайный процесс. Рассматриваемые здесь положения являются основой раздела исследования систем, который называется исследованием операций. Для нас это важно, так как практические задачи исследования многих классов систем, в том числе экономических систем и процессов, хорошо согласуются с теоретическими предпосылками теории марковских процессов. В стохастических задачах исследования опе­раций часто затруднительно даже построение матема­тической модели, уже не говоря об оптимизации. В большинстве случаев не удается построить простую математическую модель, по­зволяющую в аналитическом виде найти инте­ресующие нас величины (характеристики исследуемого процесса, показатели его эффективности) в зависимости от условий выполнения процесса и элементов ре­шения. Однако в некоторых особых случаях такую математическую модель удается построить. Например, ког­да исследуемая операция (процесс) представляет собой (точно или приближенно) так называемый марковский случайный процесс. Оп­ределение этого понятия прежде всего связано с более общим понятием «случайный про­цесс». Пусть некоторая физическая система характеризуется некоторым множеством состояний, а процесс функционирования системы во времени представляется изменением состояний (переход системы из одного состояния в другое). При этом моменты времени перехода за­ранее неизвестны, случайны. Тогда мы будем говорить, что в системе протекает случайный процесс. Большинству процессов, протекающих в реальных системах, свойственны, в той или иной мере, черты случайности, неопределенности. Пусть, например, автомобиль, движущийся по шоссе. Его перемещение в пространстве и во времени неизбежно сопровождается случайными отклонениями от заданного курса, которые прихо­дится корректировать. Поездка из дома на работу, обслуживание покупателя в магазине, ремонт оборудования в мастерской, телефонные звонки в офис, поиск информации в сети — всё это примеры операций, характеризующихся наличием случайных процессов. Пусть физическая система — учебный класс персональных компьютеров, состоящий из ряда ПК, которые время от времени выходят из строя, заменяются или восстанавливаются. Процесс, протекающий в этой системе, безусловно, случаен. А станция техобслуживания? В ней время от времени могут образовываться и рассасываться оче­реди на выполнение определённых операций, возникать задержки в очереди из-за занятости технического персонала, боксов ремонта и прочее. Вообще труднее привести пример «неслучайного» процесса, чем случайного. Наиболее вероятны неслучайные процессы могут быть связаны с работой автоматизированных или автоматических устройств типа робот. Но практически многие процессы в природе и в деятельности человека, мало влияющие на интересующие нас параметры, можно рассматривать как детерминирован­ные, неслучайные. Необходимость учета случайностей возникает тогда, когда они прямо касаются нашей за­интересованности, то есть воздействуют на адекватность принимаемых решений или точность оценок искомых характеристик системы. Например, составляя расписание са­молетов, можно пренебречь случайными колебаниями самолета вокруг центра массы, а проектируя автопи­лот — безусловно, нельзя пренебрегать этими колебаниями. Большинство процессов, кото­рые мы изучаем в физике, технике, экономике, по существу яв­ляются случайными, но только некоторые из них мы изучаем как случайные — когда нам это «практически важно». Одним из базовых понятий теории массового обслуживания является понятие марковского процесса. Случайный процесс называется марковским, если для любого мо­мента времени t0 вероятностные характеристики про­цесса в будущем зависят только от его состояния в данный момент t0 и не зависят от того, когда и как система пришла в это состояние. Пусть в настоящий момент t0 система находится в определенном со­стоянии S0. Мы наблюдаем процесс со стороны и в момент t0 знаем состояние системы S0 и всю пред­ысторию процесса, то есть всё, что было при t < t0. Нас, ес­тественно, интересует будущее (t > t0). Можем ли мы его предугадать (предсказать)? В точности — нет, наш процесс случайный, значит — непредсказуемый. Но какие-то вероятностные характеристики процесса в бу­дущем мы найти можем. Например, вероятность того, что через некоторое время dt система окажется в со­стоянии Si или сохранит состояние S0, и т. п. Следует иметь в виду, что для марковского случайного процесса та­кое «вероятностное предсказание» оказывается гораз­до проще, чем для немарковского. Если процесс — мар­ковский, то предсказывать можно, только учитывая на­стоящее состояние системы S0 и забыв о его «предысто­рии» (поведении системы при t < t0). Само состояние S0, разумеется, зависит от прошлого, но как только оно достигнуто, о прошлом можно забыть, то есть можно сказать, что в марковском процессе «будущее зависит от прошлого только через настоящее». Пример марковского процесса: система — счет­чик Гейгера, на который время от времени попадают космические частицы; состояние системы в момент t характеризуется показанием счетчика — числом частиц, пришедших до данного момента. Пусть в момент t0 счетчик показывает S0. Вероятность того, что в момент t > t0 счетчик покажет то или другое число частиц, разумеется, зависит от S0, но не за­висит от того, в какие именно моменты приходили ча­стицы до момента t0. На практике часто встречаются процессы, которые если не в точности марковские, то могут быть в каком-то приближении рассмотрены как марковские. При­мер, система S — группа самолетов, участвующих в воздушном бою. Состояние системы характеризуется числом самолетов «красных» — х и «синих» — y, сохра­нившихся (не сбитых) к какому-то моменту. В момент t0 нам известны численности самолетов обеих сторон — x0 и у0. Нас ин­тересует вероятность того, что в какой-то момент t0 + dt численный перевес будет на стороне «красных». От чего зависит эта вероятность? В пер­вую очередь от того, в каком состоянии находится си­стема в данный момент t0, а не от того, когда и в ка­кой последовательности погибали самолеты, сбитые до момента t0. Теперь выскажем парадоксальное утверждение, которое является основополагающим в теории исследования операций: в сущности, любой процесс можно рассматривать как марковский, если все пара­метры из «прошлого», от которых зависит «будущее», включить в «настоящее». Например, пусть известно, что некоторое техническое устройство в какой-то момент t0 работает исправно и нас интересует вероят­ность того, что оно проработает еще время t. Если за настоящее состояние устройства принять состояние «устройство исправно», то процесс безусловно будет не марковским, пото­му что вероятность того, что оно не откажет за время t, зависит в общем случае от того, сколько времени оно уже проработало и когда был послед­ний ремонт. Если оба эти параметра (общее время работы и время после последнего ремонта) включить в настоящее состояние данного устройства, то процесс уже можно будет считать марковским. Однако такое «обогащение настоящего за счет предыстории» далеко не всегда бывает полезно, так как (если число парамет­ров прошлого велико) оно зачастую приводит к «про­клятию многомерности». Поэтому в дальнейшем, говоря о марковском процессе, мы будем подразумевать его простым, «бесхитрост­ным», с небольшим числом параметров, определяющих «настоящее». На практике марковские процессы в чистом виде обычно не встречаются, но нередко приходится иметь дело с процессами, для которых влиянием «преды­стории» можно пренебречь. При изучении таких про­цессов можно с успехом применять марковские модели. При исследовании экономических процессов как случайных процессов, рассматриваемых в рамках дисциплины «Математическое и имитационное моделирование», большое значение имеют так называемые марковские случайные процессы с дискретными состояниями и с непрерывным временем. Процесс называется процессом с дискретными состояниями, если его возможные состояния S1, S2, S3,... можно заранее перечислить (перенумеровать, если даже их количество неограничено), и переход системы из одного состояния в некоторое другое состояние происходит «скачком», практи­чески мгновенно. Процессом с непрерывным временем называется процесс, в котором моменты воз­можных переходов из одного состояния в другое не фик­сированы заранее, а случайны. Далее будем рассматривать только процес­сы с дискретными состояниями и непрерывным вре­менем. При анализе случайных процессов с дискретными состояниями S1, S2, ..., Sn удобно пользоваться графическим представлением переходов системы из одного состояния в другое, которое называется графом состояний. Со­стояниям системы соответствуют вершины графа, а возможные перехо­ды из состояния в состояние обозначаются направленными ребрами графа (стрел­ками), соединяющими состояния. Например, система S состоит из двух подсистем, каждая из которых в случайный момент времени может выйти из строя (отказать), пос­ле чего мгновенно начинается ремонт подсистемы, про­должающийся некоторое заранее неизвестное, случайное время. Возможные состояния системы обозначим следующим образом: S0 — обе подсистемы исправны, S1 — первая подсистема ремонтируется, вторая исправна, S2 — вторая подсистема ремонтируется, первая исправна, S3— обе подсистемы ремонтируются. Переходы системы из одного состояния в другое про­исходят в случайные моменты времени (например, время работы подсистемы до отказа, называемое временем наработки на отказ, и время ремонта данной подсистемы) и отображаются на графе состояний соответствующими направленными ребрами графа (Рисунок 1). Факт выхода из строя первой подсистемы при работающей второй отображается ребром перехода из S0 в S1, выход второй подсистемы после выхода первой –– ребром перехода из S1 в S3 , факт окончания ремонт отображается соответствующим ребром перехода в обратном направлении (например, из S1 в S0 — при окончании ремонта первой подсистемы и при работающей второй). Рисунок 1 — Граф состояний СМО (на примере технического устройства) Возникает вопрос, почему нет стрелок, ведущих непосредственно из S0 в S3 и обратно? Раз­ве не может быть, что обе подсистемы откажут одновремен­но, например, вследствие короткого замыкания? Так внимание: здесь и далее будем предполагать, что подсистемы выходят из строя независимо друг от друга, и ве­роятностью того, что обе (а в общем случае – несколько) подсистемы могут выйти из строя строго одновременно, пренебрегаем (ниже будет дано более точно обоснова­ние этого допущения). Почему так важно понятие марковского процесса? Потому что если процесс, протекающий в системе с дискрет­ными состояниями и непрерывным временем, является марковским, то для его описания можно построить до­вольно простую математическую модель. Потоки событий. Простейший поток событий. Событием в системе называется переход системы из одного состояния в другое. Потоком событий называется последователь­ность однородных событий, следующих одно за другим в какие-то случайные моменты времени. Например, поток вызовов на телефонной станции, поток отказов (сбоев) ЭВМ, поток покупателей в магазин, поток автомобилей к заправочной станции и т. д. Говоря о «потоке событий», нужно иметь в виду, что здесь термин «событие» имеет значение, несколько отличное от того, к которому мы привыкли в теории вероятностей. Там «событием» (или «случайным со­бытием») называется какой-то исход опыта, обладаю­щий той или другой вероятностью. События, образую­щие поток, сами по себе вероятностями не обладают, вероятностями обладают другие, производные от них события, например: «на интервале времени dt выпадет ровно два события», или «на интервал време­ни dt выпадет хотя бы одно событие», или «промежу­ток времени между двумя соседними событиями бу­дет не меньше t1». Важнейшей характеристикой потока событий является его интенсивность, далее обозначаемая греческой буквой . Интенсивностью называется среднее число событий, появляющихся за единицу времени. Интенсивность по­тока может быть как постоянной (= const), так и переменной, зависящей от времени t (= f(t)). Например, по­ток автомашин, движущихся по улице, днем интенсив­нее, чем ночью, в часы пик — интенсивнее, чем в дру­гие часы. Поток событий называется регулярным, если события следуют одно за другим через определенные, равные промежутки времени. На практике чаще встре­чаются потоки не регулярные, со случайными интер­валами. Поток событий называется стационарным, ес­ли его вероятностные характеристики не зависят от времени. В частности, интенсивность стационарного потока должна быть постоянной. Это отнюдь не зна­чит, что фактическое число событий, появляющихся за определенный интервал времени, (например, за 5 мин) постоянное, — нет, поток неизбежно (если только он не регулярный) имеет какие-то слу­чайные сгущения и разрежения. Важно, что для стационарного потока эти сгущения и разрежения не носят законо­мерного характера: на один участок длины dt может попасть больше, а на другой участок такой же длины — меньше событий, но среднее число событий, появляющихся за единицу времени, постоянно и от времени не зависит. Как правило, отклонения от стационарности могут быть объяснены какими-то физическими причинами. Например, совершенно естественно, интенсивность по­тока вызовов, поступающих на АТС ночью, меньше, чем днем. На практике часто встречаются потоки событий, которые (по крайней мере на ограниченном участке времени) могут считаться стационарными. Например, поток пассажиров на транспорте между 13 и 14 часами практически стационарен, тот же поток в те­чение суток уже не стационарен, его интенсивность утром и вечером существенно выше. Поток событий называется потоком без пос­ледействия, если для любых двух непересекаю­щихся участков времени t1 и t2 число событий, попадающих на один из них, не зависит от того, сколько событий попало на другой. По сути это означает, что события, образующие поток, появляются в те или другие моменты времени независимо друг от друга, вызванные каждое своими собственными причинами. Например, поток пассажиров, входящих в метро, практически не имеет последействия. А вот поток покупателей, отходяших от привавков с купленными торварами, уже имеет последействие, потому что интервал времени между от­дельными покупателями не может быть меньше, чем минимальное время t2 обслуживания каждого из них). Так же обстоит дело и с потоком поездов, подходящих к станции (между ними всегда существует какой-то минимальный интервал t0, выбираемый из соображе­ний безопасности). Впрочем, если минимальный ин­тервал между событиями много меньше среднего ин­тервала между ними tс =1/, иногда наличием после­действия можно пренебречь. Поток событий называется ординарным, если события в нем появляются поодиночке, а не группа­ми — по нескольку сразу. Например, поток клиентов, направляющихся в парикмахерскую или к зубному врачу, обычно ординарен, чего нельзя сказать о потоке клиентов, направляющихся в загс для регистрации бра­ка. Поток поездов, подходящих к станции, ординарен, а поток вагонов — неординарен. Если поток событий ординарен, то предполагается, что вероятностью попадания на малый уча­сток времени dt двух или более событий можно пре­небречь, так как она несоизмеримо меньше, чем вероятность попадания одного события. Поток событий называется простейшим (или стационарным пуассоновским), если он обладает всеми тремя свойствами: свойством стационарности, свойством без последействия и свойством ординарности. Название «простейший» обусловлено тем, что процессы, связанные с простейшими потоками, име­ют наиболее простое математическое описание. Примечание: следует иметь ввиду, что регулярный поток не является «простейшим», так как обладает последействием: моменты появления событий в таком потоке связаны жесткой, функциональной зависи­мостью. Без специальных усилий по поддержанию его регулярности такой поток обычно не создается. Простейший поток играет среди других потоков особую роль, в чем-то подобную роли нормального за­кона среди других законов распределения. При этом математически доказано, что при суммировании достаточно большого числа независимых, стацио­нарных и ординарных пото­ков (сравнимых между собой по интенсивности) получает­ся поток, близкий к простей­шему. Важно: для простейшего потока с интенсивностью ин­тервал Т между соседними событиями имеет так назы­ваемое показательное распределение с плотностью распределения f(t) = e -(t), (t >= 0). Величина в этой формуле называет­ся параметром показательного закона. Для слу­чайной величины t, имеющей показательное распре­деление, математическое ожидание тt есть величина, обратная параметру, а среднеквадратическое откло­нение Dt равно математическому ожиданию, то есть mt = Dt = 1/. ТЕМА 2. МЕТОДИКА ПОСТРОЕНИЯ аналитических моделей дискретных процессов и систем 2.1. Уравнения Колмогорова — математическая основа расчета марковского процесса. Принципы построения по графу состояний системы уравнений Колмогорова, примеры решения системы уравнений. Рассматривая марковские процессы с дискретными состояниями и непрерывным временем, удобно представлять, что все переходы системы из состояния Si в состояние Sj происходят под действием каких-то потоков событий (поток вызовов, поток отка­зов, поток восстановлений и т. д.). Если все потоки со­бытий, переводящие систему из состояния Si в состояние Sj, простейшие, то процесс протекающий в системе, будет марковским. Это и естественно, так как про­стейший поток не обладает последействием: в нем «бу­дущее» не зависит от «прошлого». Если система находится в каком-то состоянии Si, из которого есть непосредственный переход в другое состояние Sj (стрелка, ведущая из Si в Si на графе состояний), то мы это будем представлять так, как будто на систему, пока она находится в состоянии Si, действует простейший поток событий, переводящий ее по стрелке Si –> Sj. Как только появится первое со­бытие этого потока, происходит «перескок» системы из Si в Sj . Для наглядности на графе состояний у каждой стрелки принято проставлять интенсивность того по­тока событий, который переводит систему по данной стрелке. Обозначим ij интенсивность потока событий, переводящего систему из состояния Si в Sj. На Рисунке 2.1 приведен пример графа состояний системы с проставленными интенсивностями переходов. Рисунок 2.1. — Граф состояний системы с ребрами графа, размеченными интенсивностями переходов Интенсивности потоков событий, переводящих сис­тему из состояния в состояние, будем вычислять, пред­полагая, что среднее время ремонта узла не зависит от того, ремонтируется ли один узел или оба сразу. Это будет именно так, если ремонтом каждого узла занят отдельный специалист. Найдем все интенсивно­сти потоков событий, переводящих систему из состоя­ния в состояние. Пусть система находится в состоянии Sо. Какой поток событий переводит ее в состояние S1? Очевидно, это поток отказов первого узла. Его интенсив­ность 01 среднее время безотказной работы равна единице, деленной на первого узла. Какой поток собы­тий переводит систему обратно из S1 в S0? Очевидно, поток «окончаний ремонтов» первого узла. Интен­сивность этого потока 10 =1/Tрем1 , где Tрем1 — среднее время ремонта первого узла. Аналогично вычисляются интен­сивности потоков событий, переводящих систему по всем стрелкам графа. Имея в своем распоряжении размеченный граф состояний системы, легко построить математическую модель данного процесса. Пусть рассматривается система, имеющая п возможных состояний S1, S2, ..., Sn. Назо­вем вероятностью i-го состояния вероятность Pi(t) того, что в момент t система будет находиться в состоянии Si . Очевидно, что в любой момент времени система должна находиться в каком-либо одном из состояний, то есть для любого момента времени сумма всех вероятностей состояний равна единице: n ∑ Pi(t )= 1 i=1 Имея в своем распоряжении размеченный граф со­стояний, можно найти все вероятности состояний Pi(t) как функции времени. Для это­го составляются и решаются так называемые уравнения Колмогорова — особого ви­да дифференциальные уравне­ния, в которых неизвестными функциями являются вероятно­сти состояний. Покажем на конкретном примере, как эти уравнения со­ставляются. Пусть система имеет четыре состояния: S0. S1. S2. S3, размеченный граф которых показан на Рисунке 2.2. Отсутствие направленной связи между состояниями указывает на невозможность непосредственного перехода, например, из состояния S3 в состояние S0 и обратно. Рисунок 2.2 — Размеченный граф состояний для построения уравнений Колмогорова Рассмотрим вероятность того, что в некоторый момент времени t +Δt система окажется в состоянии S1 . Как это может произойти? Возможны два варианта этого события: 1) в предыдущий момент времени t система находилась в этом состоянии и не перешла ни в какое другое состояние, в которое система могла бы перейти согласно графу состояний — это состояние S2. или S3, 2) в предыдущий момент времени система находилась в состоянии S0. и перешла в состояние S1 или система находилась в состоянии S3 и перешла в состояние S1. Найдем вероятность первого варианта. Вероятность того, что в момент t система была в состоянии S1, рав­на P1(t). Эту вероятность нужно умножить на веро­ятность того, что, находившись в момент t в состоянии S1, система за время Δt не перейдет из него ни в S2, ни в S3., то есть P1(t)*(1- λ12*Δt - λ13Δt ). Суммарный поток событий, выводящий систе­му из состояния S1, тоже будет простейшим, с интен­сивностью λ12 + λ13 (при наложении — суперпозиции — двух простейших потоков получается опять простей­ший поток, так как свойства стационарности, ординарности и отсутствия последействия сохраняются). Зна­чит, вероятность того, что за время Δt система выйдет из состояния S1, равна (λ12 + λ13) Δt ; вероятность того, что не выйдет, равна: (1 — (λ12+λ13)Δt). Отсюда вероятность первого варианта равна P1(t)(1 — (λ12 +λ 13) Δt). Найдем вероятность второго варианта. Она равна, во-первых, вероятности того, что в момент t система будет в со­стоянии S0, а за время Δt перейдет из него в состоя­ние S1, т. е. она равна P0(t)λ01Δt, и во-вторых, вероятности того, что в момент t система будет в со­стоянии S3, а за время Δt перейдет из него в состоя­ние S1, т. е. она равна P3(t)λ31Δt . Складывая вероятности обоих вариантов (по прави­лу сложения вероятностей), получим: P1(t +Δt)= P1(t)[1-(λ12+λ13)Δt]+ P0(t)λ01Δt + P3(t)λ31Δt. Раскроем квадратные скобки, перенесем P1(t) в ле­вую часть и разделим обе части на Δt: [P1(t +Δt) - P1(t)] / Δt = - P1(t) (λ12+λ13)+ P0(t)λ01 + P3(t)λ31. Устремляя, как и полагается в подобных случаях, Δt к нулю (время перехода системы из одного состояния в другое в моделях ТМО считается бесконечно малым), в левой части равенства получим в пределе первую производную функции P1(t), то есть dP1(t)/dt, а вправой части –– выражение для вычисления значения этой производной. Таким образом, запишем дифферен­циальное уравнение для P1(t): dP1/dt = - P1(t) (λ12+λ13)+ P0(t)λ01 + P3(t)λ31 Сформулируем теперь общее правило составления уравнений Колмогорова. В левой части каждого из них стоит производная вероятности какого-то (i-ro) состоя­ния. В правой части — сумма произведений вероятно­стей всех состояний, из которых идут стрелки в дан­ное состояние, на интенсивности соответствующих по­токов событий, минус суммарная интенсивность всех потоков, выводящих систему из данного состояния, умноженная на вероятность данного (i-ro) состояния. Пользуясь этим правилом, запишем уравнения Кол­могорова для системы, размеченный граф состояний которой дан на Рисунке 3: dP0/dt = - P0(t) (λ01+λ02)+ P2(t)λ20 dP1/dt = - P1(t) (λ12+λ13)+ P0(t)λ01 + P3(t)λ31 dP2/dt = - P2(t) λ20+P0(t)λ02+P1(t)λ12+P3(t)λ32 dP3/dt = - P3(t)(λ31+ λ32)+ P1(t) +λ13 Чтобы решить уравнения Колмогорова и найти ве­роятности состояний, прежде всего надо задать на­чальные условия. Если мы точно знаем начальное со­стояние системы Si, то в начальный момент (при t = 0) Рi(0) = 1, а все остальные начальные вероятно­сти равны нулю. Так, например, уравнения естественно решать при начальных условиях Р0(0) = 1, P1(0) = Р2(0) =Рз(0) = 0 (в начальный момент оба уз­ла исправны). Таким образом, уравнения Колмогорова дают воз­можность найти все вероятности состояний как функ­ции времени. Поставим теперь вопрос: что будет происходить с вероятностями состояний при t -»∞? Будут ли Р1(t), Р2(t),... стремиться к каким-то пределам? Если эти пределы существуют и не зависят от начального со­стояния системы, то они называются финальными вероятностями состояний. В теории случай­ных процессов доказывается, что если число п состоя­ний системы конечно и из каждого из них можно (за конечное число шагов) перейти в любое другое, то финальные вероятности существуют. Предположим, что это условие выполнено и фи­нальные вероятности существуют: Lim Рi(t) = Рi , (i= 1,2, ...,n). t -»∞ Финальные вероятности мы будем обозначать теми же буквами Р1, Р2, ..., что и сами вероятности состоя­ний, но разумея под ними уже не переменные величи­ны (функции времени), а постоянные числа. Очевидно, они тоже образуют в сумме единицу: n ∑ Рi =1. i=1 Как понимать эти финальные вероятности? При t -»∞ в системе устанавливается предельный, ста­ционарный режим, в ходе которого система случайным образом меняет свои состояния, но их вероятности уже не зависят от времени. Финальную вероятность состоя­ния можно истолковать как среднее относи­тельное время пребывания системы в этом состоянии. Например, если система имеет четыре состояния S0. S1. S2. S3, и их финальные вероятности рав­ны 0,2, 0,3, 0,1 и 0,4, это значит, что в предельном, стацио­нарном режиме система в среднем две десятых време­ни проводит в состоянии S0, три десятых — в состоя­нии S1, одну десятую –– в состоянии S2. и четыре десятых времени — в состоянии S3. Как же вычислить финальные вероятности? Очень просто. Если вероятности S0, S1, ..., S3 постоянны, то их производные равны нулю. Значит, чтобы найти фи­нальные вероятности, нужно все левые части в урав­нениях Колмогорова положить равными нулю и ре­шить полученную систему уже не дифференциальных, а линейных алгебраических уравнений. Для первого состояния алгебраическое уравнение имеет вид: - P1(t) (λ12+λ13)+ P0(t)λ01 + P3(t)λ31 = 0 Пользуясь этим правилом, напишем линейные алгебраические уравнения для финальных вероятно­стей всех состояний системы: - P0(t) (λ01+λ02)+ P2(t)λ20 = 0 - P1(t) (λ12+λ13)+ P0(t)λ01 + P3(t)λ31 = 0 - P2(t) λ20+P0(t)λ02+P1(t)λ12+P3(t)λ32 = 0 - P3(t)(λ31+ λ32)+ P1(t) +λ13 = 0 Заметим, что, учитывая свойство стационарности, можно в дальнейшем параметр t не показывать, так как вероятности как интегральные характеристики состояний системы не зависят от времени. Кроме того, пользуясь тем, что в любой момент времени система должна находиться в одном из состояний и, следовательно, справедливо уравнение, которое назовем нормирующим: P0 + P1+P2 +P3 = 1. При этом следует иметь ввиду, что одно из уравнений системы (любое, кроме нормирующего) получается лишним и его можно отбросить. Тогда решение системы уравнений состоит в определении любой из вероятностей Рi как функций, зависящих от интенсивностей, значения которых являются исходными данными i=0,1,2,3 можно выразить через другие. Таким образом, для расчета характеристик моделируемой системы, представленной графом из 4-х состояний на Рисунке 2.2, записывается система из 4-х уравнений Колмогорова, содержащей четыре неизвестных переменных P0 , P1,P2 ,P3 , и нормирующего уравнения – суммы вероятностей всех состояний моделируемой системы: - P0 (λ01+λ02)+ P2λ20 = 0 - P1 (λ12+λ13)+ P0λ01 + P3λ31 = 0 - P2 λ20+P0λ02+P1λ12+P3λ32 = 0 - P3(λ31+ λ32)+ P1 +λ13 = 0 P0+ P1 +P2+P3 = 1 Решение системы уравнений сводится к получению уравнений - зависимостей вероятностей P0, P1, P2,P3 всех состояний системы через известные, задаваемые в качестве исходных данных, интенсивности переходов системы из одного состояния в другое. В заключение этого параграфа сформулируем в общем виде правило построения уравнений Колмогорова и рассмотрим его применение на простейшей схеме одноканальной СМО бех очереди (с отказами). Сформулируем правило составления уравнений Колмогорова в общем виде. В левой части каждого из уравнений стоит производная вероятности i-го состояния, которая при стационарном режиме работы СМО равна 0 (в большинстве случаев будем считать, что режим работы СМО стационарный). В правой части записывается сумма произведений вероятностей всех состояний (из которых идут стрелки в данное состояние) на интенсивности соответствующих потоков событий, минус суммарная интенсивность всех потоков, выводящих систему из данного состояния, умноженная на вероятность данного (i-го состояния). 2.2. Алгоритм построения аналитических моделей дискретных процессов и систем Алгоритм – это последовательность действий (операций), приводящих к результату. Алгоритм построения аналитической модели дискретной системы сводится к выполнению следующих взаимосвязанных действий: 1. Построить схему моделируемой системы (см. тему 3). 2. В соответствии с работой моделируемой системы, отображаемой схемой, построить граф состояний системы (количество состояний может быть как конечное – ограниченное, так и неограниченное – см. тему 4). Суть состояний системы рекомендуется прокомментировать. 3. По графу состояний построить систему уравнений Колмогорова, каждое из которых связывает зависимость вероятности состояния от интенсивностей входных потоков и интенсивностей обслуживания заявок, поступающих всистему. 4. Дополнить систему уравнений нормирующим уравнением и удалить одно из уравнений Колмогорова. 5. Решить систему уравнений (вручную - методом подстановок…), Результат решения системы уравнений – получение формул для расчёта всех вероятностей состояний… 6.Применяя полученные формулы и свойства (особенности моделируемой системы) построить ряд формул для вычисления других различных характеристик системы (см. тему 4). Далее, в разделе ТЕМА 3 рассматривается классификация СМО как объектов моделирования. ТЕМА 3. Классификация СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ как объектов моделирования 3.1 Системы массового обслуживания (их составные компоненты и особенности организации работы) 3.1.1 Структура систем массового обслуживания Система массового обслуживания (СМО) характеризуется структурой, которая определяется составом элементов и функциональными связями между ними. Элементами СМО являются: • входной поток заявок; • каналы – как устройства обслуживания (в телефонии – одно- и многоканальные системы); • очереди заявок, ожидающих обслуживания; • выходной поток заявок. Общий вид схемы системы массового обслуживания, состоящей из одного канала, в который поступает поток заявок, образующих очередь, показан на Рисунке 3.1, а вид схемы СМО, содержащей группу из n параллельно и независимо друг от друга работающих каналов, показан на Рисунке 3.2. Эти схемы могут быть усложнены, если системы будут состоять из ряда последовательных каналов или из ряда последовательно и параллельно связанных каналов или они имеют еще более сложную сетевую структуру. Возможны системы, в которых отсутствует очередь (системы с отказами). 3.1.2 Входной поток заявок Входной поток представляет собой совокупность заявок, которые поступают в систему и нуждаются в обслуживании. Заявку можно рассматривать как запрос на удовлетворение какой–то потребности. Примером входного потока является поток информации, поступающей на обработку в ЭВМ, поток клиентов, приходящих в парикмахерскую, поток покупателей в магазин, поток деталей автомашины в сборочном цехе завода, самолеты противника, налетающие на объект удара. Процесс поступления в систему массового обслуживания потока заявок является случайным (вероятностным) и представляет собой поток однородных или неоднородных событий, которые наступают через случайные промежутки времени. Случайные временные интервалы между наступлениями событий в потоке могут подчиняться различным законам распределения. Однако в подавляющем большинстве работ по теории массового обслуживания рассматривается пуассоновский (простейший) поток (строгое определение простейшего потока будет приведено ниже). Это объясняется следующими обстоятельствами. Во–первых, для других видов потоков не получены пока простые формульные зависимости количественной оценки характеристик качества функционирования систем массового обслуживания. Во–вторых, к простейшему потоку системам массового обслуживания приспособиться труднее. Если средства обслуживания рассчитывать на этот тяжелый случай, то обслуживание системой других случайных потоков заявок с одинаковой интенсивностью будет надежнее. В–третьих, простейший поток в теории массового обслуживания играет такую же роль, как нормальный закон распределения случайных величин в теории вероятностей. При сложении нескольких случайных потоков произвольных распределений образуется суммарный поток, который по своим характеристикам приближается к простейшему. 3.1.3 Каналы (устройства) обслуживания Каждой из систем массового обслуживания свойственна определенная структурная схема и организация работы. По своему составу системы массового обслуживания можно разделить на системы с одним обслуживающим каналом (устройством) и многими каналами обслуживания, соответственно называющимися одноканальными и многоканальными СМО. Примером одноканальной системы может служить телефон одного абонента, один продавец за прилавком, одиночный пункт отдела технического контроля на поточном производстве. Многоканальные системы состоят из однотипных (по производительности, быстродействию, времени обслуживания) каналов (устройств) обслуживания. Например, «многоканальный» телефон, группа кассиров-контролёров, обслуживающих очередь покупателей в универсаме. Естественно, что в многоканальных системах число каналов должно быть не меньше двух. Число каналов в многоканальных системах массового обслуживания всегда ограничено, конечно. 3.1.4 Наличие очереди в системе По наличию очереди все системы можно разбить на три большие группы: системы без очереди – СМО с отказами, системы с неограниченной длиной очереди –– СМО с обслуживанием, системы с ограниченной длиной очереди –– СМО с потерями заявок в случае заполнения всех мест очереди. В системах с отказами заявка, поступающая в момент, когда все каналы уже занятыми, покидает систему, то есть этой заявке отказано в обслуживании. Классическим примером систем с отказами может служить работа автоматической телефонной станции (АТС). Абонент, обратившийся на АТС, получает отказ, если необходимая линия связи уже занята. В системах с неограниченной длиной очереди (в системах без потерь заявок) поступившая заявка, застав все обслуживающие каналы занятыми, становится в очередь и ожидает до тех пор, пока не освободится какой–либо из обслуживающих каналов. Это наиболее многочисленная группа систем массового обслуживания. Системы смешанного типа (СМО с ограниченной длиной очереди или СМО с потерями) занимают промежуточное положение. Поступившая в такую систему заявка, застав все каналы занятыми, становится в очередь, если в ней остаётся свободным хотя бы одно место, иначе заявка покидает систему, то есть система теряет эту заявку. Примером такой СМО может быть АЗС, количество мест к которой для автомашин, ожидающих заправки, ограничено. Возможны также варианты организации работы. СМО с ограничением времени ожидания в очереди или даже с ограничением времени обслуживания. В ней заявка находится ограниченное время, после чего, не дождавшись обслуживания или даже окончания обслуживания, покидает систему. Примером подобной системы является ЭВМ, работающая в системах реального времени и обрабатывающая информацию, ценность которой ограничена во времени. 3.1.5. Дисциплина обслуживания заявок По правилам занятия свободных каналов вновь поступившими заявками системы различаются по следующим признакам: • каналы подключаются к обслуживанию в строгом порядке. Это может происходить тогда, когда система состоит из разнотипных каналов (устройств обслуживания) с различными преимуществами их использования; • каналы начинают обслуживать вновь поступившие заявки в порядке освобождения (например, технологические потоки по ремонту техники); • каналы занимаются в случайном порядке (например, зенитные комплексы при обстреле целей во время мощного воздушного налета). В системах с ожиданием и ограниченным временем ожидания могут быть особенности в дисциплине обслуживания очереди заявок. Они сводятся к следующим разновидностям: • заявки к обслуживанию принимаются в порядке очередности их поступления в систему (предприятия бытового обслуживания, магазины и др.); • в первую очередь к обслуживанию принимаются те заявки, которые имеют больший приоритет. Например, без очереди идут к врачу больные с острой болью и т. д.; • заявки принимаются к обслуживанию в случайном порядке (например в системе ПВО объекта при отражении воздушного налета противника). 3.1.6. Время обслуживания заявок Время обслуживания является важнейшей характеристикой каждого канала обслуживания системы и определяет ее пропускную способность. Время обслуживания, как правило, случайная величина. Причиной этого служит нестабильность, неопределенность по времени работы канала обслуживания (особенно с участием человека) и неидентичность поступающих в систему заявок. Например, время, затрачиваемое машиной скорой помощи на выезд по вызову, является величиной случайной. Оно зависит от расстояния от пункта скорой помощи до места несчастного случая и многих других причин. Поэтому величину времени обслуживания следует считать случайной величиной, полной характеристикой которой является закон распределения. Законы распределения могут быть самого различного вида. Однако, как в теоретических, так и в практических приложениях большое распространение получил показательный закон. При показательном законе распределения значительно упрощаются все результаты, тогда как разработка методов решения задач массового обслуживания с произвольным законом распределения времени обслуживания встречает большие трудности. Показательный закон распределения времени обслуживания предполагает, что значительная доля заявок будет обслуживаться быстро, что не всегда соответствует практике. Поэтому во многих случаях допущение о показательном законе распределения времени обслуживания кажется сомнительным. Однако, для стационарных условий функционирования систем массового обслуживания с отказами доказана справедливость формул, получаемых для этого закона, и при любых законах времени обслуживания (лишь бы среднее время обслуживания было постоянным). Для систем массового обслуживания, получивших наиболее широкое применение, это подтверждено с помощью метода статистических испытаний. 3.1.7 Выходной поток заявок Выходной поток — это поток заявок, покидающих систему. Заявки входного потока могут быть обслужены и не обслужены каналами системы. Распределение заявок в выходном потоке во времени зависит от интенсивности входного потока и характеристик работы каналов обслуживания системы. Исследование структуры выходного потока имеет большое значение, так как он может быть входным потоком для другой группы приборов. Это важно при рассмотрении многофазных систем массового обслуживания и систем с последовательно расположенными каналами. 3.1.8 Задание СМО перечислением свойств СМО можно задать (или представить) двумя способами: во-первых, схемой (см. раздел 3.2.1), а во-вторых, перечислением свойств, например, так: X1/X2/X3/X4/X5, где X1 –– характеристика входного потока заявок; X2 –– характеристика обслуживания заявок; X3 –– количество каналов обслуживания (1…n); X4 –– длина очереди (0, m, ∞), m –– длина очереди; X5 –– характеристика дисциплины обслуживания. Х5 может принимать значение: • Х5 = 0 –– без приоритетов; • Х5 = 1 –– относительный приоритет; • Х5 = 2 –– абсолютный приоритет (см. ниже). В качестве характеристик входного потока и обслуживания заявок принято в теории массового обслуживания (ТМО) задавать законы распределения в виде условных обозначений: 1. M –– экспоненциальный закон. 2. D –– регулярное поступление заявок. 3. Еk –– k–й закон Эрланга. 4. G –– произвольный закон. 3.1.9 Основная задача теории массового обслуживания Основной задачей теории массового обслуживания является определение количественных показателей (характеристик) функционирования систем массового обслуживания и их зависимости от параметров входного потока заявок и структуры собственно системы (ее состава и функциональных связей). Решение этой задачи дает возможность найти в системе слабые звенья, определить их влияние на эффективность обслуживания и найти пути их улучшения или при заданных характеристиках потока заявок и критериев качества обслуживания дать предложения о структуре системы, которая обеспечит выполнение поставленной задачи. Под качеством работы систем массового обслуживания понимается не то, как хорошо выполнено само обслуживание (качество ремонта, решения задачи и т. д.) –– это оценивается другими критериями, а как хорошо организовано обслуживание, насколько полно загружены обслуживающие каналы, не создается ли большая очередь или не слишком ли велик отказ в обслуживании, то есть удаление из системы не обслуженных заявок. 3.1.10 Показатели эффективности функционирования СМО Методика оценки показателей эффективности СМО иллюстрируется на примере одноканальной системы с потерями (без очереди) с экспоненциальным законом поступления заявок на вход системы и экспоненциальным законом обслуживания. В терминологии ТМО это система М/М/1/0. (Очевидно, что Х5=0 подразумевается). Эффективность СМО можно характеризовать большим числом различных показателей. К числу наиболее часто применяемых показателей относятся следующие показатели: • вероятность удаления заявки без обслуживания (вероятность отказа или потери заявки) pотк, Для систем без очереди или с ограниченной очередью с pотк, равна вероятности занятости всех обслуживающих приборов pn; • относительная пропускная способность системы q = 1 – pотк –– доля обслуженных заявок; • абсолютная пропускная способность системы A = q –– количество заявок, обслуженных системой за единицу времени; • вероятность того, что обслуживанием занято k каналов –– pk, частным случаем этого показателя являются pn –– вероятность занятости всех приборов и p0 –– вероятность того, что все приборы свободны; • среднее число занятых каналов nз = = ; • среднее число свободных каналов n0 = ; • коэффициент простоя каналов Kп = n0/n; • коэффициент занятости каналов Kз = nз/n; • средняя длина очереди = , ( = ); • среднее время ожидания в очереди = /; • среднее число заявок, находящихся в системе ; • средняя длительность обслуживания заявки ; • среднее время пребывания заявки в системе = + ; • вероятность того, что число заявок в очереди больше некоторого числа m Pr>m = . Для контроля получаемых результатов удобно пользоваться функциональными связями параметров системы: n0 + nз = n, = , = , = o+п, где o = A –– интенсивность обслуженных заявок, п –– интенсивность потерянных заявок. При оценке эффективности СМО могут быть использованы также стоимостные показатели: • qобс –– стоимость обслуживания заявки в системе; • qож –– стоимость потерь, связанная с простоем заявки в очереди; • qу –– стоимость убытков из–за потери заявки; • qk –– стоимость эксплуатации k–го каналов канала (прибора, устройства) в единицу времени; • qпk –– стоимость единицы времени простоя k–го канала; • c –– экономический эффект, получаемый при обслуживании заявки. При выборе оптимальных параметров СМО по экономическим показателям можно использовать функции потерь: • для систем с ожиданием: Сп = (qож+qпkn0 + qknз)T, где T –– интервал времени; • для систем с отказами: Сп = (qуpn + qknз)T; • для смешанных систем: Сп = (qож+qпkn0 + qуpn+ qknз)T. Оценку экономической эффективности системы можно производить по выражению: E = AcT – Сп . Другие параметры будут представлены при рассмотрении соответствующих систем. При исследовании и определении оптимального варианта обычно в качестве переменных выбирают параметры , , n, некоторую дисциплину обслуживания и структуру системы. 3.2 Классификация систем массового обслуживания Классификацию систем массового обслуживания (СМО) можно проводить по достаточно большому количеству признаков. Ниже приведена классификация по наиболее значимым признакам. СМО представлены в виде структурных схем, где обозначения элементов систем, как правило, не требуют пояснений. 3.2.1 По количеству параллельно работающих устройств СМО так же классифицируются по количеству параллельно работающих устройств. Они бывают: 1. Одноканальные СМО (Рисунок 3.1). 2. Многоканальные СМО (Рисунок 3.2). Рисунок 3.1 –– Одноканальная СМО с очередью Рисунок 3.2 –– n-канальная СМО с очередью На рисунках и А –– интенсивности входного и выходного потоков. 3.2.2 По количеству последовательно работающих устройств В качестве последовательно работающих устройств используется: Однофазные СМО (Рисунок 3.3). Рисунок 3.3 –– Одно- и n-канальная однофазные СМО с очередями Многофазные СМО, содержащие последовательно связанные устройства обслуживания потоков заявок, как, например, представленные на Рисунок 3.4 две схемы, где первая схема представляет собой трёхфазную систему обслуживания, каждая из которых представлена одноканальным устройством с неограниченной очередью, а вторая схема –– двухфазная, где первая фаза обслуживания –– это n-канальное устройство обслуживания с неограниченной очередью и вторая фаза – одноканальное устройство с неограниченной очередью. Рисунок 3.4 –– Трехфазная и двухфазная СМО 3.2.3 По длине очереди По длине очереди различают следующие СМО (Рисунок 3.5): 1. Длина очереди не ограничена, что условно обозначаем как m = ∞ (СМО без отказов). 2. Длина очереди m = 0 –– СМО без очереди или с отказами, так как если заявка поступает в СМО в тот момент, когда устройство занято обслуживанием ранее поступившей заявки, то эта заявка не сохраняется и удаляется из системы). 3. 0 < m <= Lmax –– СМО с ограниченной очередью (с потерями тех заявок, которые появляются на входе системы при занятости всех мест в очереди, предусмотренных условием задачи). Рисунок 3.5 –– Одноканальные СМО: а) с неограниченной очередью; б) без очереди (с отказами в обслуживании заявкам, поступающим в систему при занятости канала); в) с ограниченной очередью (с потерями заявок, поступающих в момент занятости всех мест в очереди) 3.2.4 По дисциплине обслуживания По дисциплине обслуживания различают: • FIFO –– дисциплина обслуживания «первой заявка пришла –– первая обслуживается», образуя очередь заявок без приоритета, то есть обслуживаемых в порядке поступления в очередь –– все предыдущие примеры СМО с очередями; • дисциплина обслуживания заявок, различающихся приоритетами, предполагает организацию числа очередей по количеству значений приоритетов заявок –– одна Очередь для заявок с одинаковыми относительными приоритетами, при этом относительный приоритет (Рисунок 3.6) учитывается только в момент освобождения канала и принятия решения о том, какая из заявок должна поступить в канал для обслуживания. Рисунок 3.6 –– Одноканальная СМО с двумя очередями заявок, имеющих различные относительные приоритеты При появлении очередной заявки с более высоким приоритетом обслуживание заявки с низким приоритетом не прекращается, а продолжается до завершения. Обычно приоритеты обозначаются целыми числами 1, 2, …М, где 1 –– наименьший приоритет. Очередь с абсолютным приоритетом (Рисунок 3.7): если в момент поступления в систему заявки с абсолютным приоритетом канал занят обслуживанием некоторой заявки без приоритета или с относительным приоритетом, то обслуживание заявки прерывается и канал захватывается заявкой с абсолютным приоритетом, а после завершения обслуживания этой заявки прерванная заявка поступает в канал для ее дообслуживания. Дисциплина обслуживания с абсолютным приоритетом называется LIFO (Last In First Out, то есть первой обслуживается заявка, пришедшая последней). Это в какой-то степени ассоциируется с обработкой информации в памяти типа стек. Рисунок 3.7 –– Одноканальная СМО с обслуживанием заявок с абсолютными приоритетами 3.2.5 По ограничению времени пребывания заявок в очереди и в системе По ограничению времени пребывания заявок в очереди и в системе выделяют: 1. СМО с ограничением времени ожидания в очереди (Рисунок 3.8):заявка, которая ждет в очереди дольше допустимого времени ожидания, удаляется. 2. СМО с ограничением времени пребывания в системе: заявка, даже если она находится в процессе обслуживания, удаляется, если общее время ее пребывания в системе превосходит заданное (Рисунок 3.9). Рисунок 3.8 –– Удаление заявки из очереди в СМО, если время ожидания в очереди превысило заданное Рисунок 3.9 –– Удаление заявки из СМО, если общее время нахождения заявки в системе превысило заданное 3.2.6 По наличию обратной связи По наличию обратной связи делят: 1. Разомкнутые СМО, в которых обратная связь отсутствует (Рисунки 3.1 – 3.9, то есть все представленные выше схемы). 2. Замкнутые СМО, в которых весь выходящий из системы поток заявок поступает на вход для повторного обслуживания: Рисунок 3.10, на котором представлен пример системы типа обслуживание некоторого комплекса, содержащего m подсистем, каждая из которых может выходить из строя и передаётся в случае обнаружения неисправности одной из n ремонтных бригад. 3. Смешанные СМО (Рисунок 3.11): некоторая часть потока заявок с выхода системы подается на вход, а остальные обслуженные заявки покидают систему. Такой режим работы характерен, например, для системы разделения времени: для обслуживания заявки выделяется квант времени, и если этого достаточно для завершения обслуживания, заявка, покидает систему, иначе заявка возвращается на вход, образуя новую очередь заявок, имеющих, например, меньший относительный приоритет, чем исходный поток заявок, для продолжения процесса обслуживания. Рисунок 3.10 –– Система технического обслуживания Рисунок 3.11 –– Обработка заявок квантами времени в системе разделения времени 3.2.7 По законам поступления заявок на вход системы Пуассоновское распределение (пуассоновский поток заявок), при котором вероятность появления k заявок за время t равна , где –– интенсивность поступления заявок. Для этого закона математическое ожидание M = , дисперсия D = , т.е. M = D –– это признак данного закона. Вероятность того, что заявок за время t не будет . Интервалы времени между заявками, поступающими по этому закону, имеют экспоненциальное распределение , для которого M = , D = . Считается, что пуассоновский поток заявок –– наихудший. Распределение Эрланга –– получается выборкой из пуассоновского потока (берем k–е событие). Плотность распределения интервалов времени между событиями для этого закона равна: Математическое ожидание и дисперсия здесь равны: M = , D = . Интенсивность поступления заявок этого закона равна: , где –– интенсивность порождающего потока. При k = 1 получим экспоненциальное распределение (смотрите выше). Пуассоновский поток случайных событий (заявок), он же простейший, обладает следующими свойствами: • стационарностью; • ординарностью; • отсутствием последействия. Напомним определения этих свойств (раздел 2.1). Поток стационарен, если вероятность попадания k событий на любой участок зависит только от его длительности, но не от его положения на оси времени. Поток ординарен, если вероятность попадания двух и более событий на элементарный участок несоизмеримо меньше вероятности появления одного события. Поток без последействия, если вероятности появления событий для любых непересекающихся интервалов времени не зависят друг от друга. Из теории вероятности известно, что сумма большого числа (>3) случайных потоков с произвольными законами распределения (без преобладания какого-либо одного закона распределения) асимптотически сходится к пуассоновскому потоку, Рисунок 3.12, а). Рисунок 3.12 –– Свойства пуассоновского потока Другим действием, часто выполняемым над потоками, является просеивание. Просеивание применительно к пуассоновскому потоку определяется следующим образом. Пусть имеется пуассоновский поток с интенсивностью , а операция просеивания задается так, что с вероятностью q очередное событие остается в потоке и с вероятностью 1 – q удаляется из потока. Результирующие потоки будут пуассоновскими с интенсивностями q и (1 – q) соответственно (Рисунок 3.12,б). Величина q при этом называется относительной пропускной способностью устройства 1. 3.2.8 По закону обслуживания заявок Экспоненциальное распределение (считается, что это самый тяжелый случай), при котором вероятность завершения обслуживания за время t равна: , где –– интенсивность обслуживания заявок, которая связана со средним временем обслуживания заявок: = 1/, где . Смещенное экспоненциальное распределение –– всегда есть некоторая постоянная составляющая времени на прием заявки. Регулярное обслуживание –– время обслуживания есть величина постоянная (нет случайного процесса). 3.2.9 По наличию взаимопомощи в обслуживании заявок По наличию взаимопомощи в обслуживании заявок выделяют: ▪ без взаимопомощи –– заявка обслуживается с интенсивностью µ одним из n параллельно работающих устройств (многоканальное устройство). ▪ со взаимопомощью –– предполагается, что процесс обслуживания заявки, поступающей на вход n-канального устройства, возможно распределить между n каналами, например, делением (декомпозицией) процесса на n равноценных по времени выполнения подпроцессов, тогда интенсивность обслуживания одной заявки возрастает до nµ. 4. ТЕМА: Построение аналитических моделей типовых схем дИСКРЕТНЫХ пРОЦЕССОВ как процессов в системах массового обслуживания (смо) Ведение. К типовым схемам СМО будем относить схемы, для которых можно выполнить построение математической модели – формулы расчета характеристик этой модели, то есть можно выполнить следующее: 1) построить по схеме СМО граф её состояний, по которому построить систему уравнений Колмогорова; 2) решить систему этих уравнений, то есть найти зависимости вероятностей всех состояний СМО от задаваемых интенсивностей входных потоков и обслуживания заявок в СМО 3) по формулам вероятностей состояний построить набор формул для вычисления других разнообразных характеристик СМО. Примечание. В разделе «Имитационное моделирование» будут рассмотрены примеры СМО, для которых в принципе нельзя выполнить эту последовательность действий построения математических моделей. Выделим прежде всего 6 (шесть) групп типовых схем СМО, наиболее часто встречающихся в практике решения задач моделирования реальных систем массового обслуживания: 1. Одноканальные СМО без очереди (с отказами); 2. Многоканальные СМО без очереди (с отказами); 3. Одноканальные СМО с неограниченной очередью (без отказов, то есть без потерь заявок); 4. Многоканальные СМО с неограниченной очередью (без отказов); 5. Одноканальные СМО с ограниченной очередью (с потерями); 6. Многоканальные СМО с ограниченной очередью (с потерями); Далее на простых примерах типовых схем СМО рассмотрим применение методики построения АМ. Вспомним принцип (мнемоническое правило, алгоритм) построения системы уравнений Колмогорова по графу состояний (это надо знать и уметь применять): Количество уравнений равно количеству состояний системы. Для каждой вершины графа записывается своё уравнение, в правой части каждого из уравнений стоит производная вероятности i-го состояния, которая при стационарном режиме работы СМО равна 0 (здесь и в большинстве случаев будем считать, что режим работы СМО стационарный). Для i-того состояния в левой части записывается сумма произведений вероятностей всех состояний, из которых идут стрелки в данное i-тое состояние, на интенсивности соответствующих потоков событий, минус суммарная интенсивность всех потоков, выводящих систему из данного состояния, умноженная на вероятность данного (i-го состояния). 4.1. Построение моделей расчёта характеристик одноканальных систем 4.1.0. ВЫВОД ФОРМУЛ ДЛЯ ОКУ С ОТКАЗАМИ Работа этой системы характеризуется двумя состояниями: S0 –– система свободна от заявок и S1 –– система занята обслуживанием заявки. Замечание: состояние = это условное обозначение того, что происходит с системой в течение некоторого интервала времени - детерминированного (постоянного) или случайного. λ-интенсивность входного потока заявок (количество заявок за единицу времени), которые поступают в случайные моменты времени, и среднее время появления заявки на входе Твх = 1/ λ. Время обслуживания заявок – тоже случайная величина и Т обсл=1/ µ. Все случайные величины характеризуются законами распределения (экспоненциальный, Пуассоновский и др. – см. моё уч. пособие - ???). Система в процессе функционирования переходит из одного состояния в другое с интенсивностями, соответственно, λ и µ (Рисунок ниже). Пусть требуется провести расчет характеристик системы в стационарном режиме, при котором вероятности состояний не зависят от времени: при t производные = 0. Требуется прежде всего найти P0 и P1. Составим систему алгебраических уравнений (уравнений Колмогорова – см. лекции и учебники). – λ P0 + µ P1 = 0, (1) λ P0 – µ P1 = 0, - совпадает с первым с точностью до знака P0 + P1 = 1. (2) Надо решить эту систему – найти формулы зависимости Р0 и Р1от интенсивностей. Введём принятое отношение интенсивностей для СМО ρ = λ/µ , которое, в частности, только для ОКУ и только при условии , что ρ = λ/µ < 1, является коэффициентом нагрузки ОКУ. Очевидно, что коэф.нагрузки любой системы может быть < или = 1 (100%-ная загрузка работой и не более). Из (1) получаем . Подставив P1 в (2), получаем . Откуда . Или Р0 = µ/( λ +µ) . С учетом (2) . Параметры и характеристики системы: • λ –– интенсивность поступления заявок; • µ –– интенсивность обслуживания (µ = 1/, где  –– средняя длительность обслуживания заявки); • ρ = λ/µ –– загрузка системы (µ<>0 ), 0≤ ρ ≤1; • ρ = 1 –– полная загрузка – система в насыщении; • ρ = 0 –– система свободна; • = q = 1 – P1 –– относительная пропускная способность –– доля обслуженных заявок; • = Ротказа –– вероятность отказа (устройство занято); • А = λq –– абсолютная пропускная способность –– среднее число обслуженных заявок в единицу времени. 4.1.1. Одноканальная Система с одноместной очередью Рассмотрим систему М/М/1/1 –– это одноканальная система с одноместной очередью, поток заявок и обслуживание экспоненциальные. Структурная схема системы показана на Рисунке 4.1. Рисунок 4.1 –– Одноканальная СМО с одноместной очередью Эта система имеет три состояния: 1. S0 –– система свободна (устройство обслуживания не занято, очередь пуста). 2. S1 –– устройство занято, очередь пуста. 3. S2 –– система занята (устройство и место в очереди заняты). Граф состояний системы показан на Рисунок 4.2. Рисунок 4.2 –– Граф состояний одноканальной СМО с одноместной очередью Система уравнений Колмогорова, построенная по графу состояний, имеет вид: – λ P0 + µ P1=0; (1) λ P0 – (λ+µ) P1 +µ P2=0; (2) λ P1 – µ P2=0; (3) P0 + P1+ P2 =1. (4) Особенностью системы уравнений Колмогорова является то, что одно уравнение всегда лишнее, но только не последнее – нормирующее. Одно из уравнений, например, уравнение (2), из данной системы уравнений удалим как избыточное: для определения 3 неизвестных (вероятности состояний) достаточно трёх уравнений, включая обязательное –– нормирующее уравнение. – λ P0 + µ P1=0; (1) – λ P1 – µ P2=0; (2) P0 + P1+ P2 =1 (3) Из (1) находим . Из (2) находим . Тогда уравнение (3) получаем в виде , из которого получаем P0 = 1/(1+ ρ + ρ2) = (1– ρ)/(1– ρ3), так как 1+ ρ + ρ2 = (1– ρ3)/(1– ρ) –– как сумма членов геометрической прогрессии, первый член которой =1, знаменатель = ρ<1. 4.1.2. Одноканальную СМО с ограниченной очередью длины m –– систему М/М/1/m. Структурная схема этой системы аналогична схеме системы М/М/1/1, только длина очереди не 1, а m. Граф состояний системы показан на Рисунке 4.3. Система имеет m + 2 состояния: • S0 –– система свободна; • S1 –– устройство занято, очереди нет; • S2 –– в очереди 1 заявка; • S3 –– в очереди 2 заявки; • … • Sm –– в очереди m – 1 заявка; • Sm+1 –– в очереди m заявок (следующей заявке будет отказано). Рисунок 4.3 –– Граф состояний одноканальной СМО с ограниченной очередью длины m Система уравнений КОЛМОГОРОВА: –λ P0 + µ P1 = 0; λ P0 –( λ+µ) P1 +µ P2 = 0; λ P1 – ( λ +µ) P2 + µ P3 = 0; … λ Pm–1 – ( λ +µ) Pm + µ Pm+1 = 0; λ Pm – µ Pm+1 = 0; P0 + P1 + P2 + … + Pm + Pm+1 = 1 или . Используя результаты, полученные при расчете характеристик системы М/М/1/1, здесь будем иметь следующие результаты решения системы уравнений: P1 = ρ P0; P2 = ρ2 P0; P3 = ρ3 P0 ; … Pm = ρm P0; Pm+1 = ρm+1 P0. P0=1/(1+ ρ+ ρ2+ ρ3 +.... + ρm+1) = (1 – ρ)/(1 – ρm+2), так как в знаменателе снова имеем геометрическую прогрессию с первым членом, равным 1, и знаменателем ρ<>1. Характеристики одноканальной СМО с ограниченной очередью: 1. Вероятность простоя системы P0= (1 – ρ)/(1 – ρm+2). 2. Вероятность потерь (отказов):, ρ<>1. 3. Относительная пропускная способность (доля обслуженных заявок). 4. Абсолютная пропускная способность А = λq –– интенсивность потока обслуженных заявок. 5. Среднее число заявок в очереди . Вероятности соответствующего числа заявок в очереди: • нет заявок в очереди P0 + P1; • одна заявка в очереди P2; • две заявки в очереди P3 и т.д. = 1ρ2P0 + 2 ρ3P0 +...+ m ρm+1P0 = ρ2 P0(1 + 2ρ +...+ mρm–1) = = ρ P0= . Ряд, представленный в полученном выражении суммой, можно свернуть, но получаемая при этом формула сложна. Вот что получается При вычислениях (особенно на компьютере) удобнее воспользоваться выражением = ρ P0. 6. Среднее число заявок на обслуживании вычисляется по формуле: = 0*P0 + 1*(1 – P0), так как в состоянии S0 на обслуживании заявок нет заявок, а в остальных состояниях на обслуживании находится одна заявка (как при отсутствии очереди, так и наличии её!). Для вероятности 1– P0 получаем 1 – P0 = ((1 – ρm+2) – (1 – ρ))/(1 – ρm+2) = (ρ – ρm+2)/(1 – ρm+2). Поэтому = (ρ – ρm+2)/(1 – ρm+2). 7. Среднее число заявок в системе (в очереди и на обслуживании): . 8. Среднее время ожидания в очереди определяется из следующих соображений. первая заявка в очереди ждет, пока будет обработана заявка, находящаяся на обслуживании в приборе, вторая заявка в очереди ждет, пока будут обработаны заявка, находящаяся в приборе, и первая заявка в очереди, т.е. пока будут обработаны две заявки, и т.д. Вероятность нахождения заявки только в канале равна P1, вероятность того, что длина очереди равна 1, равна P2 и т.д. Воспользовавшись формулой оценки математического ожидания случайной величины, получаем среднее время ожидания заявки в очереди Умножив и разделив это выражение на ρ, получаем 9. Среднее время пребывания заявки в системе . 4.1.3. Одноканальная система без потерь Это система М/М/1/∞, в которой очередь не ограничена. Граф состояний и система уравнений Колмогорова здесь бесконечны, поэтому параметры системы получим следующим образом. Для системы с очередью длины m имеем Если устремить m к бесконечности, то , так как . Поэтому = 1 – ρ; P1 = ρ = ρ(1 – ρ); P2 = ρ2 = ρ2(1 – ρ); … Pk = ρk = ρk(1 – ρ). … –– средняя длина очереди. Выражение получено следующим образом: в S0 и S1 очереди нет, поэтому: • = 1P2+2P3+…+kPk+ …= 1ρ2(1– ρ) + 2ρ3(1– ρ) +...+kρk(1– ρ)+…= = ρ(1– ρ)(ρ + 2ρ2 + 3ρ3 +...+ kρk+…) = ρ(1– ρ) ρ/(1– ρ)2 = ρ2/(1– ρ). ПРИМЕЧАНИЕ: Сумма бесконечно убывающей геометрической прогрессии с первым членом ρ и общим членом kρ k равна ρ/(1 – ρ)2. • q = 1 –– вероятность того, что заявка будет обслужена, равна 1 (очередь не ограничена, нет потерь); • А = λ; • = P0+(1 – P0) = 0 + (1 – 1+ ρ) = ρ –– среднее число заявок на обслуживании; • –– среднее число заявок в системе; • ; обс=1/µ; • . 4.2. Построение моделей расчёта характеристик многоканальных систем массового обслуживания Практика моделирования, анализа и исследования экономических процессов (производственных, транспортных, логистических, процессов в сфере обслуживания) показывает, что более актуальными, отражающими реальные физические и информационные процессы в различных областях человеческой деятельности, являются модели многоканальных СМО с различными нюансами –– отказы, ограничения длительности очередей, времени ожидания в очереди или пребывания в системе и т.д. Далее на примере конкретных задач рассмотрим три типовые схемы многоканальных СМО, характеристики которых могут быть рассчитаны методами теории массового обслуживания. 4.2.1. Многоканальная СМО с отказами Задача 1. На вход трехпроцессорной вычислительной системы поступает пуассоновский поток заявок с интенсивностью λ заявок в минуту. Среднее время обработки заявки в процессоре равно Тобр минут (для построения АМ принимаются – см. понятие простейшего потока случайных величин - только экспоненциальные распределения входных потоков и потоков обслуживания ). Заявка, поступающая в систему при занятости всех процессоров, удаляется из системы без обслуживания: система М/М/3/0. Структурная схема представлена на Рисунке 4.4. Граф состояний системы показан на Рисунке 4.5. Найти следующие характеристики системы: вероятности простоя системы и отказа обслуживания в системе, вероятности других состояний системы, среднее число занятых процессоров, относительную и абсолютную пропускную способность системы и др. В соответствии с условием задачи все процессоры однородны, то есть имеют одинаковые свойства и функциональные возможности обслуживания заявок, работают независимо друг от друга, но нельзя их выделять – первый, второй канал…, нет, это единое целое – многоканальное устройство (МКУ), в котором в процессе функционирования может быть занят один канал, или два, или три канала, …, или n каналов – в n-канальном устройстве. Рисунок 4.4 –– Условное обозначение трехканальной системы с отказами Состояния системы: 1. S0 –– все процессоры свободны. 2. S1 –– один процессор работает. 3. S2 –– два процессора работают. 4. S3 –– три процессора работают. Рисунок 4.5 –– Граф состояний системы М/М/3/0 По графу состояний построим систему уравнений Колмогорова (количество алгебраических уравнений равно количеству состояний в графе): S0: – λP0+μP1 = 0; S1: + λP0 – ( λ+μ)P1 + 2μP2 = 0; S2: λP1 – (2μ+λ)P2+3μP3 = 0; S3: λP2 – 3μP3 = 0. К этим уравнения надо добавить нормирующее уравнение, соответствующее тому факту, что в любой момент времени функционирования системы она может и должна находиться в одном из этих состояний P0 , P1 , P2 , P3: P0+P1+P2+P3 = 1. Аналитический расчет характеристик системы с отказами: P0 = = ; ; Pотк = P3; –– относительная пропускная способность системы; –– абсолютная пропускная способность системы; –– среднее число работающих процессоров. 4.2.2. Многоканальная СМО с ограниченной очередью (ЭТО НАИБОЛЕЕ ОБЩИЙ ВАРИАНТ построения моделей СМО) Задача 2. На вход трёхпроцессорной ВС с ограниченной очередью (m = 2) поступает пуассоновский поток заявок с заданной интенсивностью λ заявок в единицу времени. Среднее время обработки заявки в процессоре равно Тобсл единиц времени (экспоненциальное распределение - условие для аналитических моделей). Структурная схема системы M/M/3/2 представлена на Рисунке 4.6. Рисунок 4.6 –– Структурная схема и граф состояний в системы M/M/3/2 Алгоритм построения математической (аналитической ) модели СМО. Во-первых, количество состояний – это количество возможных вариантов наличия заявок в СМО. В данной системе – от 0 до 5, следовательно, от S0 до S5. Далее следует обратить ваше внимание на то, как строится ГРАФ СОСТОЯНИЙ, особенно на интенсивности, определяющие переходы системы из одного состояния в другое. Рассмотрим особенности условий переходов: переход из S0 в S1 означает, что заявка поступила и заняла одно (а не первое) из устройств обслуживания, а обратный переход означает завершение ОДНОГО процесса обслуживая и удаление заявки. Система из S2 (две заявки обслуживаются в 2-х каналах ) может перейти в S3, то есть может поступить извне ещё одна заявка с интенсивностью λ, или возможен переход из S2 в S1, означающий завершение ОДНОГО из ДВУХ процессов, выполняющихся независимо – в разных устройствах системы МКУ, а время обслуживания – случайная величина, т.е. завершение любого из двух процессов обслуживания – равновероятно, поэтому частота (интенсивность этого события) должна равняться сумме интенсивностей обоих процессов, но интенсивности равны, поэтому переход из S2 в S1 происходит с интенсивностью 2*µ , переход из S3 в S2 происходит с интенсивностью 3*µ . Структурная схема системы и её граф состояний представлены на Рисунках. Вопрос: а можно ли перейти из S3 в S1или в S0?, т.е. перепрыгнуть через состояние? НЕТ, нельзя, запрещено в теории массового обслуживания, которая основывается на ряде аксиом, как и любая теория. Вспоминаем, если кто-то читал первую лекцию.!!! ТМО основывается на некоторых предположениях, например, что случайные процессы в СМО должны удовлетворять условиям стационарности (это очень важно для имитационного моделирования, в моделях GPSS) – вероятностные характеристики (оценки средних значений, и.т.д.) не зависят от времени, и ординарности – в любой текущий момент времени не может произойти 2 и более событий (для нас –это изменение состояний). Найти наиболее значимые, важные для оценки качества работы системы: вероятность отказа обслуживания в системе и вероятности других состояний системы, среднюю длину очереди, среднее число занятых процессоров, среднее время ожидания заявок в очереди и обслуживания в системе в целом (время отклика системы на поступивший запрос обслуживание заявки). Аналитический расчет характеристик многоканальной СМО с ограниченной очередью 1. Вероятность того, что все приборы свободны: 2. Вероятности других состояний системы (состояния определяются числом заявок в системе): ; при k – очереди нет, ; при , r – длина очереди. 3. Вероятность того, что все каналы заняты: 4. Вероятность наличия хотя бы одного свободного канала (заявка будет обслужена без ожидания в очереди): P00 = 1 – Pзан. 5. Вероятность отказа в обслуживании заявки: –– все n каналов и m мест в очереди заняты. 6. Относительная пропускная способность –– доля обслуженных заявок: q = 1 – Pотк . 7. Абсолютная пропускная способность: А = λ q –– среднее число обслуженных заявок в единицу времени. 8. Среднее число занятых устройств : =А/. 9. Средняя длина очереди: 10. Среднее время ожидания в очереди: = . 11. Среднее число заявок в системе . 12. Среднее время нахождения заявки в системе (время отклика) –– определяется делением среднего числа заявок в системе на интенсивность входного потока заявок. 4.2.3. Многоканальная СМО без потерь (Очень важно!!!) Рассмотрим методику построения математической или аналитической модели (сокращение применяем дальше АМ – в отличие от имитационной ИМ) рассмотрим на конкретном примере трёхканальной СМО (n=3). На вход трехканальной СМО с неограниченной очередью (Рисунок 4.7) поступает пуассоновский поток заявок с заданными интенсивностью и временем обработки заявки в одном канале (экспоненциальное распределение). Система М/М/3/. Рисунок 4.7 –– Структурная схема системы M/M/3/ Найти вероятность обслуживания тех заявок, которые поступают в систему при условии отсутствия очереди и наличия хотя бы одного свободного канала, и вероятности других состояний системы, среднюю длину очереди, среднее число занятых процессоров, среднее время ожидания в очереди и обслуживания в системе. ПРИМЕЧАНИЕ.-очень важно для понимания, при выполнении заданий. В одно- и в многоканальной СМО с обслуживанием всех поступающих в систему заявок (то есть без отказов) предполагается наличие неограниченной очереди. При этом естественным является требование обеспечения работы системы в ненасыщенном режиме, то есть при неограниченном времени наблюдения за процессом функционированиния такой СМО длина очереди не должна расти неограниченно сильно. Практически это означает, что отношение интенсивности входного потока заявок к общей интенсивности обслуживания в n каналах (n=1 – для одноканальных СМО) должна быть меньше 1 , то есть ((λ/(n*µ) < 1) и это отношение будем называть (только для СМО с неограниченной очередью)коэффициентом загрузки многоканального (одноканального) устройства. При нарушении этого условия расчёт невозможен для таких СМО и любая программная система моделирования должна быть защищена от некорректного задания исходных данных: «Коэффициент загрузки системы (λ/(n*µ) > 1, то есть сверхнасыщенный режим работы системы, не допускается». Таким образом, при задании исходных данных следует выполнять условие существования в многоканальной системе стационарного режима, т.е. когда P0, P1,…, Pn+m имеют конечные значения: (n – число каналов). Аналитический расчет характеристик СМО без потерь У системы без потерь за счет неограниченной очереди множество состояний должно быть неограниченным и, соответственно, граф состояний и система алгебраических уравнений (уравнений Колмогорова) должны быть бесконечными. Поэтому формулы для аналитического расчета характеристик этой системы получают из формул для системы с ограниченной очередью при m. 1. 2. Доля обслуженных заявок или относительная пропускная способность ЛЮБОЙ системы с неограниченной очередью q = 1 –– система без потерь. 3. Абсолютная пропускная способность системы А = . 4. Вероятность того, что все каналы свободны: P0 = . 5. Вероятности других состояний системы (состояния определяются числом заявок в системе k) ; при k – очереди нет, , при , r – длина очереди. 6. Средняя длина очереди: 7. Среднее время ожидания в очереди: = . 8. Вероятность того, что все приборы заняты: = 9. Вероятность обслуживания заявки без помещения ее в очередь: P00 = 1–Pзан. 10. Среднее число занятых каналов: . 11. Среднее число заявок в системе: . 12. Среднее время нахождения заявки в системе (время отклика) –– определяется делением среднего числа заявок в системе на интенсивность входного потока заявок. Лекция 2 5. ТЕМА: ПОСТРОЕИЕ АНАЛИТИЧЕСКИХ МОДЕЛЕЙ ЗАМКНУТЫХ СИСТЕМ По признаку «наличие обратных связей в схемах» СМО делятся на 3 группы: 1. Разомкнутые СМО, в которых обратная связь отсутствует, это все ранее рассматриваемые нами схемы, в которых есть внешний источник заявок и перемещение заявки по схеме завершается выходом-удалением из системы. Заявки представляют собой запрос на выполнение какой-то работы, которая в модели имитируется задержкой на интервал времени, задаваемый по соответствующему закону случайной величины. 2. Замкнутые СМО, в которых весь выходящий из системы поток заявок поступает на вход для повторного обслуживания: Рисунок 5.1, на котором представлен пример системы типа «обслуживание некоторого комплекса», содержащего m подсистем, каждая из которых может выходить из строя и передаётся в случае обнаружения неисправности одной из n ремонтных бригад. На рисунке схемы не показаны очереди, но очевидно, что в принципе очереди должны быть. 3. Смешанные СМО (Рисунок 5.2): некоторая часть потока заявок с выхода системы подается на вход, а остальные обслуженные заявки покидают систему. Такой режим работы характерен, например, для системы разделения времени: для обслуживания заявки выделяется квант времени, и если этого достаточно для завершения обслуживания, заявка, покидает систему, иначе заявка возвращается на вход, образуя новую очередь заявок, имеющих, например, меньший относительный приоритет, чем исходный поток заявок, для продолжения процесса обслуживания. Рисунок 5.1 –– Система технического обслуживания Рисунок 5.2 –– Обработка заявок квантами времени в системе разделения времени Рассмотрим особенности моделирования чисто замкнутых СМО. Главной особенностью таких СМО является тот факт, что интенсивность потока поступающих заявок зависит от состояния самой СМО. Другая особенность замкнутых систем – это, как правило, СМО многофазные, на рисунке 5.1 – двухфазная СМО. Рассмотрим в качестве системы моделирования цех, в котором обрабатываются на станках некоторые детали. Эффективность работы цеха определяется по количеству обработанных деталей, например, за смену, при некоторой известной производительности каждого станка. Станки могут выходить из строя. Вышедшим из строя станком в тот же момент начинает заниматься рабочий-ремонтник, количество которых также ограничено, поэтому может образовываться очередь станков, ожидающих ремонта. Отремонтированный станок включается без задержки в работу. В задаче работы цеха со станками источниками заявок являются сами станки, имеющиеся в ограниченном количестве и подающие или не подающие заявки на ремонт в зависимости от их состояний: при выходе станка из строя он перестаёт быть источником новых заявок. Следовательно, интенсивность общего потока заявок на ремонт, с которым приходится иметь дело рабочим, зависит от того, сколько имеется неисправных станков, т.е. сколько заявок связано с процессом обслуживания (непосредственно обслуживается или стоит в очереди). Характерным для замкнутой СМО является наличие ограниченного числа источников заявок. Рассмотрим в рамках общей схемы марковских процессов задачу об одном рабочем – наладчике (ремонтнике). Система, включающая одного рабочего и n станков, имеет ряд состояний, которые удобно нумеровать от 0 до n , по числу неисправных станков (станков, связанных с обслуживанием): S0, S1, S2, …, Sn. Очевидно, что состояния от S2 до Sn отражают наличие очереди станков длиной от 1 до n-1, ожидающих ремонта (при одном рабочем). Построив граф состояний (постройте самостоятельно, имея ввиду, что переход из S0 в S1 имеет интенсивность n* λ, из S1в S2 интенсивность (n-1)* λ и т.д. , а обратные переходы имеют интенсивности одинаковые и равные µ при наличии одного рабочего. Тогда, пользуясь, как обычно, общим решением задачи о предельных вероятностях состояний системы для «схемы гибели и размножения», получим формулы предельных вероятностей состояний: P1=( n* λ/ µ)*Р0 или P1= n* ρ*Р0; и т.д. (вывести формулы самостоятельно). В силу своеобразия замкнутой СМО, характеристики ее эффективности будут отличны от тех, которые мы принимали для СМО с неограниченным количеством источников заявок. Роль «абсолютной пропускной способности» в данном случае будет играть среднее количество неисправностей, устраняемых рабочим в единицу времени. Рабочий занят ремонтом станка с вероятностью Рзан= 1- Р0. Если он занят, то обслуживает µ станков в единицу времени. Тогда пропускная способность системы А=(1-Р0) µ Относительная пропускная способность замкнутой системы всегда равна 1, т.к. любая заявка в конце концов будет обслужена: Q=1. Среднее число неисправных станков, т.е. связанных с обслуживанием, вычисляется по формуле Кст = 1*Р1 + 2*Р2+…+n*Рn. Средняя потеря L производительности при известной производительности v одного исправного станка вычисляется по формуле L= Кст * v. Система, включающая m рабочих и n станков Состояния системы : S0, S1, S2,…, Sm, Sm+1, Sm+2,…, Sn, где S0- все станки работают, рабочие не заняты; S1- один станок остановился и 1 рабочий занят; Sm - m станков остановилось, m рабочих занято; Sm+1 – m+1 станков остановилось, из них налаживаются m станков, один стоит в очереди ; Sn - все станки остановились, m из них налаживаются, (n – m) стоит в очереди. Возможна и другая нумерация состояний, например, Sijr, где i – количество отказавших станков, j – количество занятых рабочих, r – количество станков, образующих очередь на ремонт. Попробуйте для нижепредставленных заданий такую нумерацию. На мой взгляд, это удобнее, т.к. по числовым значениям состояний очевидно, например, S945 - при отказе 9-тистанков 4 находятся в ремонте и 5 – в очереди Тогда нумерация состояний будет определяться отношением i=j+k. 6. ТЕМА : УНИВЕРСАЛЬНАЯ МЕТОДИКА ПОСТРОЕНИЯ АМ СМО С ОГРАНИЧЕННОЙ ОЧЕРЕДЬЮ И ЗАМКНУТЫХ СМО 6.1. Схема процесса гибели и размножения (СГиР) В теории массового обслуживания широкое распространение имеет специальный класс моделей случайных процессов — так называемый процесс гибели и размножения. Название этого процесса связано с рядом биологических задач, где он является математической моделью изменения численности биологических популяций. Для разработки и исследования моделей этого класса разработана методика построения математических (аналитических) моделей, основанная на тех же принципах , что и рассмотренные нами методики построения моделей типовых СМО. Суть этой методики состоит в следующем. Граф состояний процесса гибели и размножения имеет вид, показанный на рис..1 (см. файл – Рисунки к теме 6). Рассмотрим упорядоченное множество состояний системы S0, S1, $2, ..., Sk,…, Sn. Переходы могут осуществляться из любого стояния только в состояния с соседними номерами, т.е. из состояния Sk возможны переходы только либо в состояние Sk+1, либо в состояние Sk-1 . Предположим, что все потоки событий, переводящие систему по стрелкам графа, простейшие с соответствующими интенсивностями k,k+1 или k+1,k. По графу, представленному на рис..1, составим и решим алгебраические уравнения для предельных вероятностей состояний (их существование вытекает из возможности перехода из каждого состояния в каждое другое и конечности – ограниченности - числа состояний). В соответствии с правилом составления таких уравнений получим: для состояния S0 - 01P0 =10P1 , для состояния S1 - (12 + 10 )P1 =10P0 +21P2 , которое с учётом первого приводится к виду 12 P1 =21P2 . Аналогично, записывая уравнения для предельных вероятностей других состояний, можно получить систему из n уравнений: 01P0 =10P1 , 12 P1 =21P2 , …………………………… n-1,n Pn-1 =n,n+1Pn . к которой добавляется нормировочное условие P0 +P1 +P2 +….+Pn = 1. Решая эту систему, можно получить прежде всего формулу для вычисления РО, а затем и для всех остальных вероятностей состояний, зависящих от РО и от задаваемых интенсивностей (см. рис.2). Легко заметить, что в формулах для P1 ,P2, …., Pn коэффициенты при P0 есть слагаемые, стоящие после единицы в формуле для P0). Числители этих коэффициентов представляют произведение всех интенсивностей, стоящих у стрелок, ведущих слева направо до данного состояния Sk (k=l, 2, ..., n), а знаменатели — произведение всех интенсивностей, стоящих у стрелок, ведущих справа налево до состояния Sk. 2. Применение методики СГиР для построения математических (аналитических) моделей типовых схем одноканальных и многоканальных СМО с ограниченной очередью. Прежде всего требуется для заданной схемы СМО построить граф состояний, по структуре совпадающий с графом СГиР, но имеющий особенноси, определяемые спецификой заданной СМО – закономерностями изменения интенсивностей появления заявок и интенсивностей обслуживания этих заявок.. В качестве исходных данных для расчета характеристик СМО должно быть определено, во-первых, k – общее число состояний СМО, и во-вторых , две группы наборов значений интенсивностей как весов рёбер графа , связывающих k состояний в цепочку. При этом наборы интенсивностей определяются из графа состояний, построенного для заданной конкретной схемы СМО. В кчестве примера ниже приводятся результаты расчёта характеристик трёхканальной СМО с очередью, ограниченной двумя местами (Рекомендую нарисовать самостоятельно схему именно этой СМО и построить граф состояний этой СМО с указание на графе конкретных чисел, умножаемых на и µ). Общее число состояний k =6 (на схеме ниже это n=6). Пусть интенсивность входного потока заявок равна 5 заявок в секунду, интенсивность обслуживания µ в одном канале равна 1,5 заявки в секунду. Тогда интенсивности нижнего ряда определяются количеством процессов обслуживания µ, 2µ, 3µ, 3µ, 3µ, (количество одновременно работающих каналов от 1 до 3), выполняемых трёхканальным устройством в соответствующем состоянии СМО: 1,5; 3; 4,5; 4,5; 4,5: (Ниже приведены результаты работы «Автоматизированной системы расчёта характеристик типовых схем дискретных процессов и систем массового обслуживания ») Рекомендую в качестве практики провести свои расчёты Ро и Р5 и сравнить с приведёнными выше. Наиболее эффективным, и, как мне кажется, очевидным, с точки зрения простоты понимания, применением этой методики является построение моделей СМО, графы состояний которых содержат многообразие вариантов изменения интенсивностей переходов в ту и другую сторону линейной структуры графа. Для иллюстрации сказанного рекомендую самостоятельно найти вероятности состояний совсем простого графа некоторой СМО, содержащего три состояния S0, S1, S2 c интенсивностями перехода , заданными числами: 1 из S0 в S1, 2 из S1 в S2, и обратно 3 из S2 в S1, 4 из S1 в S0. Для самопроверки расчётов привожу результат для Р0=0,706, Р1=0.1765. Я надеюсь, что именно эта методика позволит успешно справиться с заданием по теме «Замкнуты системы» . Жду выполнения этого задания также и по методике ГиР.