Каждая СМО состоит из определенного числа обслуживающих единиц (приборов, устройств, пунктов, станций), которые будем называть каналами обслуживания. Каналами могут быть линии связи, рабочие точки, вычислительные машины, продавцы и др. По числу каналов СМО подразделяют на одноканальные и многоканальные.
Заявки поступают в СМО обычно не регулярно, а случайно, образуя так называемый случайный поток заявок (требований). Обслуживание заявок, вообще говоря, также продолжается какое-то случайное время. Случайный характер потока заявок и времени обслуживания приводит к тому, что СМО оказывается загруженной неравномерно: в какие-то периоды времени скапливается очень большое количество заявок (они либо становятся в очередь, либо покидают СМО необслуженными), в другие же периоды СМО работает с недогрузкой или простаивает.
Предметом теории массового обслуживания является построение математических моделей, связывающих заданные условия работы СМО (число каналов, их производительность, характер потока заявок и т.п.) с показателями эффективности СМО, описывающими ее способность справляться с потоком заявок.
В качестве показателей эффективности СМО используются: среднее (здесь и в дальнейшем средние величины понимаются как математические ожидания соответствующих случайных величин) число заявок, обслуживаемых в единицу времени; среднее число заявок в очереди; среднее время ожидания обслуживания; вероятность отказа в обслуживании без ожидания; вероятность того, что число заявок в очереди превысит определенное значение и т.п.
СМО делят на два основных типа (класса)
: СМО с отказами и href="cmo_length.php">СМО с ожиданием (очередью). В СМО с отказами заявка, поступившая в момент, когда все каналы заняты, получает отказ, покидает СМО и в дальнейшем процессе обслуживания не участвует (например, заявка на телефонный разговор в момент, когда все каналы заняты, получает отказ и покидает СМО необслуженной).
В СМО с ожиданием заявка, пришедшая в момент, когда все каналы заняты, не уходит, а становится в очередь на обслуживание.
СМО с ожиданием подразделяются на разные виды в зависимости от того, как организована очередь: с ограниченной или неограниченной длиной очереди, с ограниченным временем ожидания и т.п.
Процесс работы СМО представляет собой случайный процесс.
Под случайным (вероятностным или стохастическим) процессом
понимается процесс изменения во времени состояния
какой-либо системы в соответствии с вероятностными закономерностями.
Процесс называется процессом с дискретными состояниями,
если его возможные состояния S 1 , S 2 , S 3 … можно заранее перечислить, а переход системы из состояния в состояние происходит мгновенно (скачком). Процесс называется процессом с непрерывным временем,
если моменты возможных переходов системы из состояния в состояние не фиксированы заранее, а случайны.
Процесс работы СМО представляет собой случайный процесс c дискретными состояниями и непрерывным временем. Это означает, что состояние СМО меняется скачком в случайные моменты появления каких-то событий (например, прихода новой заявки,
окончания обслуживания и т.п.).
Математический анализ работы СМО существенно упрощается, если процесс этой работы - марковский. Случайный процесс называется марковским
или случайным процессом без последствия,
если для любого момента времени t 0 вероятностные характеристики процесса в будущем зависят только от его состояния в данный момент t 0 и не зависят от того, когда и как система пришла в это состояние.
Пример марковского процесса: система S - счетчик в такси. Состояние системы в момент t характеризуется числом километров (десятых долей километров), пройденных автомобилем до данного момента. Пусть в момент t 0 счетчик показывает S 0 .
Вероятность того, что в момент t > t 0 счетчик покажет то или иное число километров (точнее, соответствующее число рублей) S 1 , зависит от S 0 , но не зависит от того, в какие моменты времени изменялись показания счетчика до момента t 0 .
Многие процессы можно приближенно считать марковскими. Например, процесс игры в шахматы; система S -
группа шахматных фигур. Состояние системы характеризуется числом фигур противника, сохранившихся на доске в момент t 0 . Вероятность того, что в момент t > t 0 материальный перевес будет на стороне одного из противников, зависят в первую очередь от того, в каком состоянии находится система в данный момент t 0 ,
а не того, когда и в какой последовательности исчезли фигуры с доски до момента t 0 .
В ряде случаев предысторией рассматриваемых процессов можно просто пренебречь и применять для их изучения марковские модели.
При анализе случайных процессов с дискретными состояниями удобно пользоваться геометрической схемой - так называемым графом состоянии.
Обычно состояния системы изображаются прямоугольниками (кружками), а возможные переходы из состояния в состояние - стрелками (ориентированными дугами), соединяющими состояния.
Задача 1 .
Построить граф состояний следующего случайного процесса: устройство S состоит из двух узлов, каждый из которых в случайный момент времени может выйти из строя, после чего мгновенно начинается ремонт узла, продолжающийся заранее неизвестное случайное время.
Решение.
Возможные состояния системы: S 0 - оба узла исправны; S 1 - первый узел ремонтируется,
второй исправен; S 2 - второй узел ремонтируется, первый исправен; S 3 - оба узла ремонтируются. Граф системы приведен на рис.1.
Рис. 1
Стрелка, направленная, например, из S 0 в S 1 означает переход системы в момент отказа первого узла, из S 1 в S 0 - переход в момент окончанияремонта этого узла.
На графе отсутствуют стрелки из S 0 , в S 3 и из S 1 в S 2 . Это объясняется тем, что выходы узлов из строя предполагаются независимыми друг от друга и, например,
вероятностью одновременного выхода из строя двух узлов (переход из S 0 в S 3) или одновременного окончания ремонтов двух узлов (переход из S 3 в S 0) можно пренебречь.
Поток событий
Для математического описания марковского случайного процесса с дискретными состояниями и непрерывным временем, протекающего в СМО, познакомимся с одним из важных понятий теории вероятностей - понятием потока событий.Под потоком событий понимается последовательность однородных событий, следующих одно за другим в какие-то случайные моменты времени (например, поток вызовов на телефонной станции, поток отказов ЭВМ, поток покупателей и т.п.).
Поток характеризуется интенсивностью l - частотой появления событий или средним числом событий, поступающих в СМО в единицу времени.
Поток событий называется регулярным, если события следуют одно за другим через определенные равные промежутки времени. Например, поток изделий на конвейере сборочного цеха (с постоянной скоростью движения) является регулярным.
Поток событий называется стационарным, если его вероятностные характеристики не зависят от времени. В частности, интенсивность стационарного потока есть величина постоянная: l(t)= l. Например, поток автомобилей на городском проспекте не является стационарным в течение суток, но этот поток можно считать стационарным в течение суток, скажем, в часы пик. Обращаем внимание на то, что в последнем случае фактическое число проходящих автомобилей в единицу времени (например, в каждую минуту) может заметно отличаться друг от друга, но среднее их число будет постоянно и не будет зависеть от времени.
Поток событий называется потоком без последействия, если для любых двух непересекающихся участков времени t 1 и t 2 - число событий, попадающих на один из них, не зависит от числа событий, попадающих на другие. Например, поток пассажиров, входящих в метро, практически не имеет последействия. А, скажем, поток покупателей, отходящих с покупками от прилавка, уже имеет последействие (хотя бы потому, что интервал времени между отдельными покупателями не может быть меньше, чем минимальное время обслуживания каждого из них).
Поток событий называется ординарным, если вероятность попадания на малый (элементарный) участок времени Dt двух и более событий пренебрежимо мала по сравнению с вероятностью попадания одного события. Другими словами, поток событий ординарен, если события появляются в нем поодиночке, а не группами. Например, поток поемов, подходящих к станции, ординарен, а поток вагонов не ординарен.
Поток событий называется простейшим (или стационарным пуассоновским), если он одновременно стационарен, ординарен и не имеет последействия. Название "простейший" объясняется тем, что СМО с простейшими потоками имеет наиболее простое математическое описание. Заметим, что регулярный поток не является "простейшим", так как он обладает последействием: моменты появления событий в таком потоке жестко зафиксированы.
Простейший поток в качестве предельного возникает в теории случайных процессов столь же естественно, как в теории вероятностей нормальное распределение получается в качестве предельного для суммы случайных величин: при наложении (суперпозиции) достаточно большого числа n независимых, стационарных и ординарных потоков (сравнимых между собой по интенсивностям l 1 (i=1,2, ..., п) получается поток, близкий к простейшему с интенсивностью l, равной сумме интенсивностей входящих потоков, т.е.
Рассмотрим на оси времени Ot (рис. 2) простейший поток событий как неограниченную последовательность случайных точек.
Рис. 2
Можно показать, что для простейшего потока число т событий (точек), попадающих на произвольный участок времени t, распределено по закону Пуассона
, (1)
для которого математическое ожидание случайной величины равно ее дисперсии: a= s 2 = l t.
В частности, вероятность того, что за время t не произойдет ни одного события (m=0), равна (2)
Найдем распределение интервала времени Т между произвольными двумя соседними событиями простейшего потока.
В соответствии с (15.2) вероятность того, что на участке времени длиной t не появится ни одного из последующих событий, равна (3)
а вероятность противоположного события, т.е. функция распределения случайной величины Т, есть (4)
Плотность вероятности случайной величины есть производная ее функции распределения (рис. 3), т.е.
(5)
Рис. 3
Распределение, задаваемое плотностью вероятности (5) или функцией распределения (4), называется показательным (или экспоненциальным). Таким образом, интервал времени между двумя соседними произвольными событиями имеет показательное распределение, для которого математическое ожидание равно среднему квадратическому отклонению случайной величины (6)
и обратно по величине интенсивности потока l.
Важнейшее свойство показательного распределения (присущее только показательному распределению) состоит в следующем: если промежуток времени, распределенный по показательному закону, уже длился некоторое время t, то это никак не влияет на закон распределения оставшейся части промежутка (T-t): он будет таким же, как и закон распределения всего промежутка Т.
Другими словами, для интервала времени Т между двумя последовательными соседними событиями потока, имеющего показательное распределение, любые сведения о том, сколько времени протекал этот интервал, не влияют на закон распределения оставшейся части. Это свойство показательного закона представляет собой, в сущности, другую формулировку для "отсутствия последействия" - основного свойства простейшего потока.
Для простейшего потока с интенсивностью l вероятность попадания на элементарный (малый) отрезок времени Dt хотя бы одного события потока равна согласно (4)
(7)
(Заметим, что эта приближенная формула, получаемая заменой функции e - l Dt лишь двумя первыми членами ее разложения в ряд по степеням Dt, тем точнее, чем меньше Dt).
Федеральное агентство по образованию РФ
ФГОУ СПО «Перевозский строительный колледж»
по дисциплине «Математические методы»
на тему «СМО с ограниченным временем ожидания. Замкнутые СМО»
Введение.......................................................................................................... 2
1. Основы теории массового обслуживания.................................................. 3
1.1 Понятие случайного процесса.................................................................. 3
1.2 Марковский случайный процесс.............................................................. 4
1.3 Потоки событий......................................................................................... 6
1.4 Уравнения Колмогорова для вероятностей состояний. Финальные вероятности состояний......................................................................................................... 9
1.5 Задачи теории массового обслуживания............................................... 13
1.6 Классификация систем массового обслуживания.................................. 15
2. Системы массового обслуживания с ожиданием..................................... 16
2.1 Одноканальная СМО с ожиданием........................................................ 16
2.2 Многоканальная СМО с ожиданием...................................................... 25
3. Замкнутые СМО........................................................................................ 37
Решение задачи............................................................................................. 45
Заключение.................................................................................................... 50
Список литературы....................................................................................... 51
В данном курсе мы будем рассматривать различные системы массового обслуживания (СМО) и сети массового обслуживания (СеМО).
Под системой массового обслуживания (СМО) понимают динамическую систему, предназначенную для эффективного обслуживания потока заявок (требований на обслуживание) при ограничениях на ресурсы системы.
Модели СМО удобны для описания отдельных подсистем современных вычислительных систем, таких как подсистема процессор - основная память, канал ввода-вывода и т. д. Вычислительная система в целом представляет собой совокупность взаимосвязанных подсистем, взаимодействие которых носит вероятностный характер. Заявка на решение некоторой задачи, поступающая в вычислительную систему, проходит последовательность этапов счета, обращения к внешним запоминающим устройствам и устройствам ввода-вывода. После выполнения некоторой последовательности таких этапов, число и продолжительность которых зависит от трудоемкости программы, заявка считается обслуженной и покидает вычислительную систему. Таким образом, вычислительную систему в целом можно представлять совокупностью СМО, каждая из которых отображает процесс функционирования отдельного устройства или группы однотипных устройств, входящих в состав системы.
Совокупность взаимосвязанных СМО называется сетью массового обслуживания (стохастической сетью).
Для начала мы рассмотрим основы теории СМО, затем перейдем к ознакомлению в подробном содержании к СМО с ожиданием и замкнутым СМО. Также в курс включена практическая часть, в которой мы подробно познакомимся с тем, как применить теорию на практике.
Теория массового обслуживания составляет один из разделов теории вероятностей. В этой теории рассматриваются вероятностные задачи и математические модели (до этого нами рассматривались детерминированные математические модели). Напомним, что:
Детерминированная математическая модель отражает поведение объекта (системы, процесса) с позиций полной определенности в настоящем и будущем.
Вероятностная математическая модель учитывает влияние случайных факторов на поведение объекта (системы, процесса) и, следовательно, оценивает будущее с позиций вероятности тех или иных событий.
Т.е. здесь как, например, в теории игр задачи рассматриваются в условиях неопределенности .
Рассмотрим сначала некоторые понятия, которые характеризуют «стохастическую неопределенность», когда неопределенные факторы, входящие в задачу, представляют собой случайные величины (или случайные функции), вероятностные характеристики которых либо известны, либо могут быть получены из опыта. Такую неопределенность называют еще «благоприятной», «доброкачественной».
Строго говоря, случайные возмущения присущи любому процессу. Проще привести примеры случайного, чем «неслучайного» процесса. Даже, например, процесс хода часов (вроде бы это строгая выверенная работа – «работает как часы») подвержен случайным изменениям (уход вперед, отставание, остановка). Но до тех пор, пока эти возмущения несущественны, мало влияют на интересующие нас параметры, мы можем ими пренебречь и рассматривать процесс как детерминированный, неслучайный.
Пусть имеется некоторая система S (техническое устройство, группа таких устройств, технологическая система – станок, участок, цех, предприятие, отрасль промышленности и т.д.). В системе S протекает случайный процесс , если она с течением времени меняет свое состояние (переходит из одного состояния в другое), причем, заранее неизвестным случайным образом.
Примеры:
1. Система S – технологическая система (участок станков). Станки время от времени выходят из строя и ремонтируются. Процесс, протекающий в этой системе, случаен.
2. Система S – самолет, совершающий рейс на заданной высоте по определенному маршруту. Возмущающие факторы – метеоусловия, ошибки экипажа и т.д., последствия – «болтанка», нарушение графика полетов и т.д.
Случайный процесс, протекающий в системе, называется Марковским , если для любого момента времени t 0 вероятностные характеристики процесса в будущем зависят только от его состояния в данный момент t 0 и не зависят от того, когда и как система пришла в это состояние.
Пусть в настоящий момент t 0 система находится в определенном состоянии S 0 . Мы знаем характеристики состояния системы в настоящем и все, что было при t <t 0 (предысторию процесса). Можем ли мы предугадать (предсказать) будущее, т.е. что будет при t >t 0 ? В точности – нет, но какие-то вероятностные характеристики процесса в будущем найти можно. Например, вероятность того, что через некоторое время система S окажется в состоянии S 1 или останется в состоянии S 0 и т.д.
Пример . Система S – группа самолетов, участвующих в воздушном бою. Пусть x – количество «красных» самолетов, y – количество «синих» самолетов. К моменту времени t 0 количество сохранившихся (не сбитых) самолетов соответственно – x 0 , y 0 . Нас интересует вероятность того, что в момент времени численный перевес будет на стороне «красных». Эта вероятность зависит от того, в каком состоянии находилась система в момент времени t 0 , а не от того, когда и в какой последовательности погибали сбитые до момента t 0 самолеты.
На практике Марковские процессы в чистом виде обычно не встречаются. Но имеются процессы, для которых влиянием «предыстории» можно пренебречь. И при изучении таких процессов можно применять Марковские модели (в теории массового обслуживания рассматриваются и не Марковские системы массового обслуживания, но математический аппарат, их описывающий, гораздо сложнее).
В исследовании операций большое значение имеют Марковские случайные процессы с дискретными состояниями и непрерывным временем.
Процесс называется процессом с дискретным состоянием , если его возможные состояния S 1 , S 2 , … можно заранее определить, и переход системы из состояния в состояние происходит «скачком», практически мгновенно.
Процесс называется процессом с непрерывным временем , если моменты возможных переходов из состояния в состояние не фиксированы заранее, а неопределенны, случайны и могут произойти в любой момент.
Пример . Технологическая система (участок) S состоит из двух станков, каждый из которых в случайный момент времени может выйти из строя (отказать), после чего мгновенно начинается ремонт узла, тоже продолжающийся заранее неизвестное, случайное время. Возможны следующие состояния системы:
S 0 - оба станка исправны;
S 1 - первый станок ремонтируется, второй исправен;
S 2 - второй станок ремонтируется, первый исправен;
S 3 - оба станка ремонтируются.
Переходы системы S из состояния в состояние происходят практически мгновенно, в случайные моменты выхода из строя того или иного станка или окончания ремонта.
При анализе случайных процессов с дискретными состояниями удобно пользоваться геометрической схемой – графом состояний . Вершины графа – состояния системы. Дуги графа – возможные переходы из состояния в состояние. Для нашего примера граф состояний приведен на рис. 1.
Рис. 1. Граф состояний системы
Примечание. Переход из состояния S 0 в S 3 на рисунке не обозначен, т.к. предполагается, что станки выходят из строя независимо друг от друга. Вероятностью одновременного выхода из строя обоих станков мы пренебрегаем.
Поток событий – последовательность однородных событий, следующих одно за другим в какие-то случайные моменты времени.
В предыдущем примере – это поток отказов и поток восстановлений. Другие примеры: поток вызовов на телефонной станции, поток покупателей в магазине и т.д.
Поток событий можно наглядно изобразить рядом точек на оси времени O t – рис. 2.
Рис. 2. Изображение потока событий на оси времени
Положение каждой точки случайно, и здесь изображена лишь какая-то одна реализация потока.
Интенсивность потока событий ( ) – это среднее число событий, приходящееся на единицу времени.
Рассмотрим некоторые свойства (виды) потоков событий.
Поток событий называется стационарным , если его вероятностные характеристики не зависят от времени.
В частности, интенсивность стационарного потока постоянна. Поток событий неизбежно имеет сгущения или разрежения, но они не носят закономерного характера, и среднее число событий, приходящееся на единицу времени, постоянно и от времени не зависит.
Поток событий называется потоком без последствий , если для любых двух непересекающихся участков времени и (см. рис. 2) число событий, попадающих на один из них, не зависит от того, сколько событий попало на другой. Другими словами, это означает, что события, образующие поток, появляются в те или иные моменты времени независимо друг от друга и вызваны каждое своими собственными причинами.
Поток событий называется ординарным , если события в нем появляются поодиночке, а не группами по нескольку сразу.
Поток событий называется простейшим (или стационарным пуассоновским), если он обладает сразу тремя свойствами:
1) стационарен;
2) ординарен;
3) не имеет последствий.
Простейший поток имеет наиболее простое математическое описание. Он играет среди потоков такую же особую роль, как и закон нормального распределения среди других законов распределения. А именно, при наложении достаточно большого числа независимых, стационарных и ординарных потоков (сравнимых между собой по интенсивности) получается поток, близкий к простейшему.
Для простейшего потока с интенсивностью интервал T между соседними событиями имеет так называемое показательное (экспоненциальное) распределение с плотностью:
где - параметр показательного закона.
Для случайной величины T , имеющей показательное распределение, математическое ожидание есть величина, обратная параметру, а среднее квадратичное отклонение равно математическому ожиданию:
Рассматривая Марковские процессы с дискретными состояниями и непрерывным временем, подразумевается, что все переходы системы S из состояния в состояние происходят под действием простейших потоков событий (потоков вызовов, потоков отказов, потоков восстановлений и т.д.). Если все потоки событий, переводящие систему S из состояния в состояние простейшие, то процесс, протекающий в системе, будет Марковским.
Итак, на систему, находящуюся в состоянии , действует простейший поток событий. Как только появится первое событие этого потока, происходит «перескок» системы из состояния в состояние (на графе состояний по стрелке ).
Для наглядности на графе состояний системы у каждой дуги проставляют интенсивности того потока событий, который переводит систему по данной дуге (стрелке). - интенсивность потока событий, переводящий систему из состояния в . Такой граф называется размеченным . Для нашего примера размеченный граф приведен на рис. 3.
Рис. 3. Размеченный граф состояний системы
На этом рисунке - интенсивности потока отказов; - интенсивности потока восстановлений.
Предполагаем, что среднее время ремонта станка не зависит от того, ремонтируется ли один станок или оба сразу. Т.е. ремонтом каждого станка занят отдельный специалист.
Пусть система находится в состоянии S 0 . В состояние S 1 ее переводит поток отказов первого станка. Его интенсивность равна:
где - среднее время безотказной работы первого станка.
Из состояния S 1 в S 0 систему переводит поток «окончаний ремонтов» первого станка. Его интенсивность равна:
где - среднее время ремонта первого станка.
Аналогично вычисляются интенсивности потоков событий, переводящих систему по всем дугам графа. Имея в своем распоряжении размеченный граф состояний системы, строится математическая модель данного процесса.
Пусть рассматриваемая система S имеет -возможных состояний . Вероятность -го состояния - это вероятность того, что в момент времени , система будет находиться в состоянии . Очевидно, что для любого момента времени сумма всех вероятностей состояний равна единице:
Для нахождения всех вероятностей состояний как функций времени составляются и решаются уравнения Колмогорова – особого вида уравнения, в которых неизвестными функциями являются вероятности состояний. Правило составления этих уравнений приведем здесь без доказательств. Но прежде, чем его приводить, объясним понятие финальной вероятности состояния .
Что будет происходить с вероятностями состояний при ? Будут ли стремиться к каким-либо пределам? Если эти пределы существуют и не зависят от начального состояния системы, то они называются финальными вероятностями состояний .
где - конечное число состояний системы.
Финальные вероятности состояний – это уже не переменные величины (функции времени), а постоянные числа. Очевидно, что:
Финальная вероятность состояния – это по–существу среднее относительное время пребывания системы в этом состоянии.
Например, система S имеет три состояния S 1 , S 2 и S 3 . Их финальные вероятности равны соответственно 0,2; 0,3 и 0,5. Это значит, что система в предельном стационарном состоянии в среднем 2/10 времени проводит в состоянии S 1 , 3/10 – в состоянии S 2 и 5/10 – в состоянии S 3 .
Правило составления системы уравнений Колмогорова : в каждом уравнении системы в левой его части стоит финальная вероятность данного состояния , умноженная на суммарную интенсивность всех потоков, ведущих из данного состояния , а в правой его части – сумма произведений интенсивностей всех потоков, входящих в -е состояние , на вероятности тех состояний, из которых эти потоки исходят.
Пользуясь этим правилом, напишем систему уравнений для нашего примера :
.
Эту систему четырех уравнений с четырьмя неизвестными , казалось бы, можно вполне решить. Но эти уравнения однородны (не имеют свободного члена), и, значит, определяют неизвестные только с точностью до произвольного множителя. Однако можно воспользоваться нормировочным условием: 
и с его помощью решить систему. При этом одно (любое) из уравнений можно отбросить (оно вытекает как следствие из остальных).
Продолжение примера . Пусть значения интенсивностей потоков равны: .
Четвертое уравнение отбрасываем, добавляя вместо него нормировочное условие:
.
Т.е. в предельном, стационарном режиме система S в среднем 40% времени будет проводить в состоянии S 0 (оба станка исправны), 20% - в состоянии S 1 (первый станок ремонтируется, второй работает), 27% - в состоянии S 2 (второй станок ремонтируется, первый работает), 13% - в состоянии S 3 (оба станка ремонтируются). Знание этих финальных вероятностей может помочь оценить среднюю эффективность работы системы и загрузку ремонтных органов.
Пусть система S в состоянии S 0 (полностью исправна) приносит в единицу времени доход 8 условных единиц, в состоянии S 1 – доход 3 условные единицы, в состоянии S 2 – доход 5 условных единиц, в состоянии S 3 – не приносит дохода. Тогда в предельном, стационарном режиме средний доход в единицу времени будет равен: условных единиц.
Станок 1 ремонтируется долю времени, равную: . Станок 2 ремонтируется долю времени, равную: . Возникает задача оптимизации . Пусть мы можем уменьшить среднее время ремонта первого или второго станка (или обоих), но это нам обойдется в определенную сумму. Спрашивается, окупит ли увеличение дохода, связанное с ускорением ремонта, повышенные расходы на ремонт? Нужно будет решить систему четырех уравнений с четырьмя неизвестными.
Примеры систем массового обслуживания (СМО): телефонные станции, ремонтные мастерские, билетные кассы, справочные бюро, станочные и другие технологические системы, системы управления гибких производственных систем и т.д.
Каждая СМО состоит из какого–то количества обслуживающих единиц, которые называются каналами обслуживания (это станки, транспортные тележки, роботы, линии связи, кассиры, продавцы и т.д.). Всякая СМО предназначена для обслуживания какого–то потока заявок (требований), поступающих в какие-то случайные моменты времени.
Обслуживание заявки продолжается какое–то, вообще говоря, случайное время, после чего канал освобождается и готов к приему следующей заявки. Случайный характер потока заявок и времени обслуживания приводит к тому, что в какие–то периоды времени на входе СМО скапливается излишне большое количество заявок (они либо становятся в очередь, либо покидают СМО не обслуженными). В другие же периоды СМО будет работать с недогрузкой или вообще простаивать.
Процесс работы СМО – случайный процесс с дискретными состояниями и непрерывным временем. Состояние СМО меняется скачком в моменты появления каких-то событий (прихода новой заявки, окончания обслуживания, момента, когда заявка, которой надоело ждать, покидает очередь).
Предмет теории массового обслуживания – построение математических моделей, связывающих заданные условия работы СМО (число каналов, их производительность, правила работы, характер потока заявок) с интересующими нас характеристиками – показателями эффективности СМО. Эти показатели описывают способность СМО справляться с потоком заявок. Ими могут быть: среднее число заявок, обслуживаемых СМО в единицу времени; среднее число занятых каналов; среднее число заявок в очереди; среднее время ожидания обслуживания и т.д.
Математический анализ работы СМО очень облегчается, если процесс этой работы Марковский, т.е. потоки событий, переводящие систему из состояния в состояние – простейшие. Иначе математическое описание процесса очень усложняется и его редко удается довести до конкретных аналитических зависимостей. На практике не Марковские процессы с приближением приводятся к Марковским. Приведенный далее математический аппарат описывает Марковские процессы.
Первое деление (по наличию очередей):
1. СМО с отказами;
2. СМО с очередью.
В СМО с отказами заявка, поступившая в момент, когда все каналы заняты, получает отказ, покидает СМО и в дальнейшем не обслуживается.
В СМО с очередью заявка, пришедшая в момент, когда все каналы заняты, не уходит, а становится в очередь и ожидает возможности быть обслуженной.
СМО с очередями подразделяются на разные виды в зависимости от того, как организована очередь – ограничена или не ограничена . Ограничения могут касаться как длины очереди, так и времени ожидания, «дисциплины обслуживания».
Итак, например, рассматриваются следующие СМО:
· СМО с нетерпеливыми заявками (длина очереди и время обслуживания ограничено);
· СМО с обслуживанием с приоритетом, т.е. некоторые заявки обслуживаются вне очереди и т.д.
Кроме этого СМО делятся на открытые СМО и замкнутые СМО.
В открытой СМО характеристики потока заявок не зависят от того, в каком состоянии сама СМО (сколько каналов занято). В замкнутой СМО – зависят. Например, если один рабочий обслуживает группу станков, время от времени требующих наладки, то интенсивность потока «требований» со стороны станков зависит от того, сколько их уже исправно и ждет наладки.
Классификация СМО далеко не ограничивается приведенными разновидностями, но этого достаточно.
Рассмотрим простейшую СМО с ожиданием - одноканальную систему (n - 1), в которую поступает поток заявок с интенсивностью ; интенсивность обслуживания (т.е. в среднем непрерывно занятый канал будет выдавать обслуженных заявок в единицу (времени). Заявка, поступившая в момент, когда канал занят, становится в очередь и ожидает обслуживания.
Система с ограниченной длиной очереди. Предположим сначала, что количество мест в очереди ограничено числом m, т.е. если заявка пришла в момент, когда в очереди уже стоят m-заявок, она покидает систему не обслуженной. В дальнейшем, устремив m к бесконечности, мы получим характеристики одноканальной СМО без ограничений длины очереди.
Будем нумеровать состояния СМО по числу заявок, находящихся в системе (как обслуживаемых, так и ожидающих обслуживания):
Канал свободен;
Канал занят, очереди нет;
Канал занят, одна заявка стоит в очереди;
Канал занят, k-1 заявок стоят в очереди;
Канал занят, т-заявок стоят в очереди.
ГСП показан на рис. 4. Все интенсивности потоков событий, переводящих в систему по стрелкам слева направо, равны , а справа налево - . Действительно, по стрелкам слева направо систему переводит поток заявок (как только придет заявка, система переходит в следующее состояние), справа же налево - поток «освобождений» занятого канала, имеющий интенсивность (как только будет обслужена очередная заявка, канал либо освободится, либо уменьшится число заявок в очереди).
Рис. 4. Одноканальная СМО с ожиданием
Изображенная на рис. 4 схема представляет собой схему размножения и гибели. Напишем выражения для предельных вероятностей состояний:
(5)
или с использованием: :
(6)
Последняя строка в (6) содержит геометрическую прогрессию с первым членом 1 и знаменателем р, откуда получаем:
(7)
в связи с чем предельные вероятности принимают вид:
(8).
Выражение (7) справедливо только при < 1 (при = 1 она дает неопределенность вида 0/0). Сумма геометрической прогрессии со знаменателем = 1 равна m+2, и в этом случае:
Определим характеристики СМО: вероятность отказа , относительную пропускную способность q, абсолютную пропускную способность А, среднюю длину очереди , среднее число заявок, связанных с системой , среднее время ожидания в очереди , среднее время пребывания заявки в СМО .
Вероятность отказа. Очевидно, заявка получает отказ только в случае, когда канал занят и все т-мест в очереди тоже:
(9).
Относительная пропускная способность:
(10).
Средняя длина очереди. Найдем среднее число -заявок, находящихся в очереди, как математическое ожидание дискретной случайной величины R-числа заявок, находящихся в очереди:
С вероятностьюв очереди стоит одна заявка, с вероятностью- две заявки, вообще с вероятностьюв очереди стоят k-1 заявок, и т.д., откуда:
(11).
Поскольку , сумму в (11) можно трактовать как производную по от суммы геометрической прогрессии:
Подставляя данное выражение в (11) и используя из (8), окончательно получаем:
(12).
Среднее число заявок, находящихся в системе. Получим далее формулу для среднего числа -заявок, связанных с системой (как стоящих в очереди, так и находящихся на обслуживании). Поскольку , где - среднее число заявок, находящихся под обслуживанием, а k известно, то остается определить . Поскольку канал один, число обслуживаемых заявок может равняться 0 (с вероятностью ) или 1 (с вероятностью 1 - ), откуда:
.
и среднее число заявок, связанных с СМО, равно:
(13).
Среднее время ожидания заявки в очереди. Обозначим его ; если заявка приходит в систему в какой-то момент времени, то с вероятностью канал обслуживания не будет занят, и ей не придется стоять в очереди (время ожидания равно нулю). С вероятностью она придет в систему во время обслуживания какой-то заявки, но перед ней не будет очереди, и заявка будет ждать начала своего обслуживания в течение времени (среднее время обслуживания одной заявки). С вероятностью в очереди перед рассматриваемой заявкой будет стоять еще одна, и время ожидания в среднем будет равно , и т.д.
Если же k=m+1, т.е. когда вновь приходящая заявка застает канал обслуживания занятым и m-заявок в очереди (вероятность этого ), то в этом случае заявка не становится в очередь (и не обслуживается), поэтому время ожидания равно нулю. Среднее время ожидания будет равно:
если подставить сюда выражения для вероятностей (8), получим:
(14).
Здесь использованы соотношения (11), (12) (производная геометрической прогрессии), а также из (8). Сравнивая это выражение с (12), замечаем, что иначе говоря, среднее время ожидания равно среднему числу заявок в очереди, деленному на интенсивность потока заявок.
(15).
Среднее время пребывания заявки в системе. Обозначим - матожидание случайной величины - время пребывания заявки в СМО, которое складывается из среднего времени ожидания в очереди и среднего времени обслуживания . Если загрузка системы составляет 100%, очевидно, , в противном же случае:
.
Пример 1. Автозаправочная станция (АЗС) представляет собой СМО с одним каналом обслуживания (одной колонкой).
Площадка при станции допускает пребывание в очереди на заправку не более трех машин одновременно (m = 3). Если в очереди уже находятся три машины, очередная машина, прибывшая к станции, в очередь не становится. Поток машин, прибывающих для заправки, имеет интенсивность =1 (машина в минуту). Процесс заправки продолжается в среднем 1,25 мин.
Определить:
вероятность отказа;
относительную и абсолютную пропускную способности АЗС;
среднее число машин, ожидающих заправки;
среднее число машин, находящихся на АЗС (включая обслуживаемую);
среднее время ожидания машины в очереди;
среднее время пребывания машины на АЗС (включая обслуживание).
Иначе говоря, среднее время ожидания равно среднему числу заявок в очереди, деленному на интенсивность потока заявок.
Находим вначале приведенную интенсивность потока заявок: =1/1,25=0,8; =1/0,8=1,25.
По формулам (8):
Вероятность отказа 0,297.
Относительная пропускная способность СМО: q=1-=0,703.
Абсолютная пропускная способность СМО: A==0,703 машины в мин.
Среднее число машин в очереди находим по формуле (12):
т.е. среднее число машин, ожидающих в очереди на заправку, равно 1,56.
Прибавляя к этой величине среднее число машин, находящихся под обслуживанием:
получаем среднее число машин, связанных с АЗС.
Среднее время ожидания машины в очереди по формуле (15):
Прибавляя к этой величине , получим среднее время, которое машина проводит на АЗС:
Системы с неограниченным ожиданием. В таких системах значение т не ограничено и, следовательно, основные характеристики могут быть получены путем предельного перехода в ранее полученных выражениях (5), (6) и т.п.
Заметим, что при этом знаменатель в последней формуле (6) представляет собой сумму бесконечного числа членов геометрической прогрессии. Эта сумма сходится, когда прогрессия бесконечно убывающая, т.е. при <1.
Может быть доказано, что <1 есть условие, при котором в СМО с ожиданием существует предельный установившийся режим, иначе такого режима не существует, и очередь при будет неограниченно возрастать. Поэтому в дальнейшем здесь предполагается, что <1.
Если, то соотношения (8) принимают вид:
(16).
При отсутствии ограничений по длине очереди каждая заявка, пришедшая в систему, будет обслужена, поэтому q=1, 
.
Среднее число заявок в очереди получим из (12) при :
Среднее число заявок в системе по формуле (13) при :
.
Среднее время ожиданияполучим из формулы (14) при:
.
Наконец, среднее время пребывания заявки в СМО есть:
Система с ограниченной длиной очереди. Рассмотрим канальную СМО с ожиданием, на которую поступает поток заявок с интенсивностью ; интенсивность обслуживания (для одного канала) ; число мест в очереди .
Состояния системы нумеруются по числу заявок, связанных системой:
нет очереди:
Все каналы свободны;
Занят один канал, остальные свободны;
Заняты -каналов, остальные нет;
Заняты все -каналов, свободных нет;
есть очередь:
Заняты все n-каналов; одна заявка стоит в очереди;
Заняты все n-каналов, r-заявок в очереди;
Заняты все n-каналов, r-заявок в очереди.
ГСП приведен на рис. 17. У каждой стрелки проставлены соответствующие интенсивности потоков событий. По стрелкам слева направо систему переводит всегда один и тот же поток заявок с интенсивностью , по стрелкам справа налево систему переводит поток обслуживании, интенсивность которого равна , умноженному на число занятых каналов.
Рис. 17. Многоканальная СМО с ожиданием
Граф типичен для процессов размножения и гибели, для которой решение ранее получено. Напишем выражения для предельных вероятностей состояний, используя обозначение : (здесь используется выражение для суммы геометрической прогрессии со знаменателем ).
Таким образом, все вероятности состояний найдены.
Определим характеристики эффективности системы.
Вероятность отказа. Поступившая заявка получает отказ, если заняты все n-каналов и все m-мест в очереди:
(18)
Относительная пропускная способность дополняет вероятность отказа до единицы:
Абсолютная пропускная способность СМО:
(19)
Среднее число занятых каналов. Для СМО с отказами оно совпадало со средним числом заявок, находящихся в системе. Для СМО с очередью среднее число занятых каналов не совпадает со средним числом заявок, находящихся в системе: последняя величина отличается от первой на среднее число заявок, находящихся в очереди.
Обозначим среднее число занятых каналов . Каждый занятый канал обслуживает в среднем -заявок в единицу времени, а СМО в целом обслуживает в среднем А-заявок в единицу времени. Разделив одно на другое, получим:
Среднее число заявок в очереди можно вычислить непосредственно как математическое ожидание дискретной случайной величины:
(20)
Здесь опять (выражение в скобках) встречается производная суммы геометрической прогрессии (см. выше (11), (12) - (14)), используя соотношение для нее, получаем:
Среднее число заявок в системе:
Среднее время ожидания заявки в очереди. Рассмотрим ряд ситуаций, различающихся тем, в каком состоянии застанет систему вновь пришедшая заявка и сколько времени ей придется ждать обслуживания.
Если заявка застанет не все каналы занятыми, ей вообще не придется ждать (соответствующие члены в математическом ожидании равны нулю). Если заявка придет в момент, когда заняты все n-каналов, а очереди нет, ей придется ждать в среднем время, равное (потому что «поток освобождений» -каналов имеет интенсивность ). Если заявка застанет все каналы занятыми и одну заявку перед собой в очереди, ей придется в среднем ждать в течение времени (по на каждую впереди стоящую заявку) и т. д. Если заявка застанет в очереди -заявок, ей придется ждать в среднем в течение времени . Если вновь пришедшая заявка застанет в очереди уже m-заявок, то она вообще не будет ждать (но и не будет обслужена). Среднее время ожидания найдем, умножая каждое из этих значений на соответствующие вероятности:
(21)
Так же, как и в случае одноканальной СМО с ожиданием, отметим, что это выражение отличается от выражения для средней длины очереди (20) только множителем , т. е.
.
Среднее время пребывания заявки в системе, так же, как и для одноканальной СМО, отличается от среднего времени ожидания на среднее время обслуживания, умноженное на относительную пропускную способность:
.
Системы с неограниченной длиной очереди. Мы рассмотрели канальную СМО с ожиданием, когда в очереди одновременно могут находиться не более m-заявок.
Так же, как и ранее, при анализе систем без ограничений необходимо рассмотреть полученные соотношения при .
Вероятности состояний получим из формул предельным переходом (при ). Заметим, что сумма соответствующей геометрической прогрессии сходится при и расходится при >1. Допустив, что <1 и устремив в формулах величину m к бесконечности, получим выражения для предельных вероятностей состояний:
(22)
Вероятность отказа, относительная и абсолютная пропускная способность. Так как каждая заявка рано или поздно будет обслужена, то характеристики пропускной способности СМО составят:
Среднее число заявок в очереди получим при из (20):
,
а среднее время ожидания - из (21):
.
Среднее число занятых каналов , как и ранее, определяется через абсолютную пропускную способность:
.
Среднее число заявок, связанных с СМО, определяется как среднее число заявок в очереди плюс среднее число заявок, находящихся под обслуживанием (среднее число занятых каналов):
Пример 2. Автозаправочная станция с двумя колонками (n = 2) обслуживает поток машин с интенсивностью =0,8 (машин в минуту). Среднее время обслуживания одной машины:
В данном районе нет другой АЗС, так что очередь машин перед АЗС может расти практически неограниченно. Найти характеристики СМО.
Поскольку<1, очередь не растет безгранично и имеет смысл говорить о предельном стационарном режиме работы СМО. По формулам (22) находим вероятности состояний:
и т. д.
Среднее число занятых каналов найдем, разделив абсолютную пропускную способность СМО А==0,8 на интенсивность обслуживания =0,5:
Вероятность отсутствия очереди у АЗС будет:
Среднее число машин в очереди:
Среднее число машин на АЗС:
Среднее время ожидания в очереди:
Среднее время пребывания машины на АЗС:
СМО с ограниченным временем ожидания. Ранее рассматривались системы с ожиданием, ограниченным только длиной очереди (числом m-заявок, одновременно находящихся в очереди). В такой СМО заявка, разраставшая в очередь, не покидает ее, пока не дождется обслуживания. На практике встречаются СМО другого типа, в которых заявка, подождав некоторое время, может уйти из очереди (так называемые «нетерпеливые» заявки).
Рассмотрим СМО подобного типа, предполагая, что ограничение времени ожидания является случайной величиной.
Предположим, что имеется n-канальная СМО с ожиданием, в которой число мест в очереди не ограничено, но время пребывания заявки в очереди является некоторой случайной величиной со средним значением, таким образом, на каждую заявку, стоящую в очереди, действует своего рода пуассоновский «поток уходов» с интенсивностью:
Если этот поток пуассоновский, то процесс, протекающий в СМО, будет марковским. Найдем для него вероятности состояний. Нумерация состояний системы связывается с числом заявок в системе - как обслуживаемых, так и стоящих в очереди:
нет очереди:
Все каналы свободны;
Занят один канал;
Заняты два канала;
Заняты все n-каналов;
есть очередь:
Заняты все n-каналов, одна заявка стоит в очереди;
Заняты все n-каналов, r-заявок стоят в очереди и т. д.
Граф состояний и переходов системы показан на рис. 23.
Рис. 23. СМО с ограниченным временем ожидания
Разметим этот граф, как и раньше; у всех стрелок, ведущих слева направо, будет стоять интенсивность потока заявок . Для состояний без очереди у стрелок, ведущих из них справа налево, будет, как и раньше, стоять суммарная интенсивность потока обслуживании всех занятых каналов. Что касается состояний с очередью, то у стрелок, ведущих из них справа налево, будет стоять суммарная интенсивность потока обслуживания всех n-каналов плюс соответствующая интенсивность потока уходов из очереди. Если в очереди стоят r-заявок, то суммарная интенсивность потока уходов будет равна .
Как видно из графа, имеет место схема размножения и гибели; применяя общие выражения для предельных вероятностей состояний в этой схеме (используя сокращенные обозначения , запишем:
(24)
Отметим некоторые особенности СМО с ограниченным ожиданием сравнительно с ранее рассмотренными СМО с «терпеливыми» заявками.
Если длина очереди не ограничена и заявки «терпеливы» (не уходят из очереди), то стационарный предельный режим существует только в случае (при соответствующая бесконечная геометрическая прогрессия расходится, что физически соответствует неограниченному росту очереди при ).
Напротив, в СМО с «нетерпеливыми» заявками, уходящими рано или поздно из очереди, установившийся режим обслуживания при достигается всегда, независимо от приведенной интенсивности потока заявок . Это следует из того, что ряд для в знаменателе формулы (24) сходится при любых положительных значениях и .
Для СМО с «нетерпеливыми» заявками понятие «вероятность отказа» не имеет смысла - каждая заявка становится в очередь, но может и не дождаться обслуживания, уйдя раньше времени.
Относительная пропускная способность, среднее число заявок в очереди. Относительную пропускную способность q такой СМО можно подсчитать следующим образом. Очевидно, обслужены будут все заявки, кроме тех, которые уйдут из очереди досрочно. Подсчитаем, какое в среднем число заявок покидает очередь досрочно. Для этого вычислим среднее число заявок в очереди:
На каждую из этих заявок действует «поток уходов» с интенсивностью . Значит, из среднего числа -заявок в очереди в среднем будет уходить, не дождавшись обслуживания, -заявок в единицу времени и всего в единицу времени в среднем будет обслуживаться -заявок. Относительная пропускная способность СМО будет составлять:
Среднее число занятых каналов по-прежнему получаем, деля абсолютную пропускную способность А на :
(26)
Среднее число заявок в очереди. Соотношение (26) позволяет вычислить среднее число заявок в очереди , не суммируя бесконечного ряда (25). Из (26) получаем:
а входящее в эту формулу среднее число занятых каналов можно найти как математическое ожидание случайной величины Z, принимающей значения 0, 1, 2,..., n с вероятностями ,:
В заключение заметим, что если в формулах (24) перейти к пределу при (или, что то же, при ), то при получатся формулы (22), т. е. «нетерпеливые» заявки станут «терпеливыми».
До сих пор мы рассматривали системы, в которых входящий поток никак не связан с выходящим. Такие системы называются разомкнутыми. В некоторых же случаях обслуженные требования после задержки опять поступают на вход. Такие СМО называются замкнутыми. Поликлиника, обслуживающая данную территорию, бригада рабочих, закрепленная за группой станков, являются примерами замкнутых систем.
В замкнутой СМО циркулирует одно и то же конечное число потенциальных требований. Пока потенциальное требование не реализовалось в качестве требования на обслуживание, считается, что оно находится в блоке задержки. В момент реализации оно поступает в саму систему. Например, рабочие обслуживают группу станков. Каждый станок является потенциальным требованием, превращаясь в реальное в момент своей поломки. Пока станок работает, он находится в блоке задержки, а с момента поломки до момента окончания ремонта - в самой системе. Каждый рабочий является каналом обслуживания.
Пусть n - число каналов обслуживания, s - число потенциальных заявок, n <s , - интенсивность потока заявок каждого потенциального требования, μ - интенсивность обслуживания:
Вероятность простоя системы определяется формулой
Р
0
= 
.
Финальные вероятности состояний системы:
P k
=
при k
Через эти вероятности выражается среднее число занятых каналов
=P 1 + 2P 2 +…+n(P n +P n+ 1 +…+P s) или
=P 1 + 2P 2 +…+(n- 1)P n- 1 +n( 1-P 0 -P 1 -…-P n-1 ).
Через находим абсолютную пропускную способность системы:
а также среднее число заявок в системе
М =s- =s- .
Пример 1 . На вход трехканальной СМО с отказами поступает поток заявок с интенсивностью =4 заявки в минуту, время обслуживания заявки одним каналом t обсл =1/μ =0,5 мин. Выгодно ли с точки зрения пропускной способности СМО заставить все три канала обслуживать заявки сразу, причем среднее время обслуживания уменьшается втрое? Как это скажется на среднем времени пребывания заявки в СМО?
Решение. Находим вероятность простоя трехканальной СМО по формуле
ρ = /μ =4/2=2, n=3,
Р 0 = = = 0,158.
Вероятность отказа определяем по формуле:
Р отк =Р n ==
P отк = 0,21.
Относительная пропускная способность системы:
Р обсл = 1-Р отк 1-0,21=0,79.
Абсолютная пропускная способность системы:
А= Р обсл 3,16.
Среднее число занятых каналов определяем по формуле:
1,58, доля каналов, занятых обслуживанием,
q = 0,53.
Cреднее время пребывания заявки в СМО находим как вероятность того, что заявка принимается к обслуживанию, умноженную на среднее время обслуживания: t СМО 0,395 мин.
Объединяя все три канала в один, получаем одноканальную систему с параметрами μ= 6, ρ= 2/3. Для одноканальной системы вероятность простоя:
Р 0 = = =0,6,
вероятность отказа:
Р отк =ρ Р 0 = = 0,4,
относительная пропускная способность:
Р обсл = 1-Р отк =0,6,
абсолютная пропускная способность:
А= Р обсл =2,4.
t СМО =Р обсл = =0,1 мин.
В результате объединения каналов в один пропускная способность системы снизилась, так как увеличилась вероятность отказа. Среднее время пребывания заявки в системе уменьшилось.
Пример 2 . На вход трехканальной СМО с неограниченной очередью поступает поток заявок с интенсивностью =4 заявки в час, среднее время обслуживания одной заявки t =1/μ=0,5 ч. Найти показатели эффективности работы системы.
Для рассматриваемой системы n =3, =4, μ=1/0,5=2, ρ= /μ=2, ρ/n =2/3<1. Определяем вероятность простоя по формуле:
Р=
.
P
0
= 
=1/9.
Среднее число заявок в очереди находим по формуле:
L
=
.
L = = .
Среднее время ожидания заявки в очереди считаем по формуле:
t = = 0,22 ч.
Среднее время пребывания заявки в системе:
Т=t+ 0,22+0,5=0,72.
Пример 3 . В парикмахерской работают 3 мастера, а в зале ожидания расположены 3 стула. Поток клиентов имеет интенсивность =12 клиентов в час. Среднее время обслуживания t обсл =20 мин. Определить относительную и абсолютную пропускную способность системы, среднее число занятых кресел, среднюю длину очереди, среднее время, которое клиент проводит в парикмахерской.
Для данной задачи n =3, m =3, =12, μ =3, ρ =4, ρ/n =4/3. Вероятность простоя определяем по формуле:
Р
0
=
.
P
0
= 
0,012.
Вероятность отказа в обслуживании определяем по формуле
Р отк =Р n+m = .
P отк =P n + m 0,307.
Относительная пропускная способность системы, т.е. вероятность обслуживания:
P обсл =1-P отк 1-0,307=0,693.
Абсолютная пропускная способность:
А= Р обсл 12 .
Среднее число занятых каналов:
.
Средняя длина очереди определяется по формуле:
L
=
L= 
1,56.
Среднее время ожидания обслуживания в очереди:
t = ч.
Среднее число заявок в СМО:
M=L + .
Среднее время пребывания заявки в СМО:
Т=М/ 0,36 ч.
Пример 4 . Рабочий обслуживает 4 станка. Каждый станок отказывает с интенсивностью =0,5 отказа в час, среднее время ремонта t рем =1/μ=0,8 ч. Определить пропускную способность системы.
Эта задача рассматривает замкнутую СМО, μ =1,25, ρ=0,5/1,25=0,4. Вероятность простоя рабочего определяем по формуле:
Р
0
=
.
P
0
= 
.
Вероятность занятости рабочего Р зан = 1-Р 0 . А=( 1-P 0 )μ =0,85μ станков в час.
Задача:
Два рабочих обслуживают группу из четырех станков. Остановки работающего станка происходят в среднем через 30 мин. Среднее время наладки составляет 15 мин. Время работы и время наладки распределено по экспоненциальному закону.
Найдите среднюю долю свободного времени для каждого рабочего и среднее время работы станка.
Найдите те же характеристики для системы, в которой:
а) за каждым рабочим закреплены два станка;
б) два рабочих всегда обслуживают станок вместе, причем с двойной интенсивностью;
в) единственный неисправный станок обслуживают оба рабочих сразу (с двойной интенсивностью), а при появлении еще хотя бы одного неисправного станка они начинают работать порознь, причем каждый обслуживает один станок (вначале опишите систему в терминах процессов гибели и рождения).
Решение:
Возможны следующие состояния системы S:
S 0 – все станки исправны;
S 1 – 1 станок ремонтируется, остальные исправны;
S 2 – 2 станок ремонтируется, остальные исправны;
S 3 – 3 станок ремонтируется, остальные исправны;
S 4 – 4 станок ремонтируется, остальные исправны;
S 5 – (1, 2) станки ремонтируются, остальные исправны;
S 6 – (1, 3) станки ремонтируются, остальные исправны;
S 7 – (1, 4) станки ремонтируются, остальные исправны;
S 8 – (2, 3) станки ремонтируются, остальные исправны;
S 9 – (2, 4) станки ремонтируются, остальные исправны;
S 10 – (3, 4) станки ремонтируются, остальные исправны;
S 11 – (1, 2, 3) станки ремонтируются, 4 станок исправен;
S 12 – (1, 2, 4) станки ремонтируются, 3 станок исправен;
S 13 – (1, 3, 4) станки ремонтируются, 2 станок исправен;
S 14 – (2, 3, 4) станки ремонтируются, 1 станок исправен;
S 15 – все станки ремонтируются.
Граф состояний системы…
Данная система S является примером замкнутой системы, так как каждый станок является потенциальным требованием, превращаясь в реальное в момент своей поломки. Пока станок работает, он находится в блоке задержки, а с момента поломки до момента окончания ремонта – в самой системе. Каждый рабочий является каналом обслуживания.
Если рабочий занят, он налаживает μ-станков в единицу времени, пропускная способность системы:
Ответ:
Средняя доля свободного времени для каждого рабочего ≈ 0,09.
Среднее время работы станка ≈ 3,64.
а) За каждым рабочим закреплены два станка.
Вероятность простоя рабочего определяется по формуле:
Вероятность занятости рабочего:
Если рабочий занят, он налаживает μ-станков в единицу времени, пропускная способность системы:
Ответ:
Средняя доля свободного времени для каждого рабочего ≈ 0,62.
Среднее время работы станка ≈ 1,52.
б) Два рабочих всегда обслуживают станок вместе, причем с двойной интенсивностью.
в) Единственный неисправный станок обслуживают оба рабочих сразу (с двойной интенсивностью), а при появлении еще хотя бы одного неисправного станка они начинают работать порознь, причем каждый обслуживает один станок (вначале опишите систему в терминах процессов гибели и рождения).
Сравнение 5 ответов:
Наиболее эффективным способом организации рабочих за станками будет являться начальный вариант задачи.
Выше были рассмотрены примеры простейших систем массового обслуживания (СМО). Понятие «простейшие» не означает «элементарные». Математические модели этих систем применимы и успешно используются в практических расчетах.
Возможность применения теории принятия решений в системах массового обслуживания определяется следующими факторами:
1. Количество заявок в системе (которая рассматривается как СМО) должно быть достаточно велико (массово).
2. Все заявки, поступающие на вход СМО, должны быть однотипными.
3. Для расчетов по формулам необходимо знать законы, определяющие поступление заявок и интенсивность их обработки. Более того, потоки заявок должны быть Пуассоновскими.
4. Структура СМО, т.е. набор поступающих требований и последовательность обработки заявки, должна быть жестко зафиксирована.
5. Необходимо исключить из системы субъектов или описывать их как требования с постоянной интенсивностью обработки.
К перечисленным выше ограничениям можно добавить еще одно, оказывающее сильное влияние на размерность и сложность математической модели.
6. Количество используемых приоритетов должно быть минимальным. Приоритеты заявок должны быть постоянными, т.е. они не могут меняться в процессе обработки внутри СМО.
В ходе выполнения работы была достигнута основная цель – изучен основной материал «СМО с ограниченным временем ожидания» и «Замкнутые СМО», которая была поставлена преподавателем учебной дисциплины. Также мы ознакомились применением полученных знаний на практике, т.е. закрепили пройденный материал.
1) http://www.5ballov.ru.
2) http://www.studentport.ru.
3) http://vse5ki.ru.
4) http://revolution..
5) Фомин Г.П. Математические методы и модели в коммерческой деятельности. М: Финансы и статистика, 2001.
6) Гмурман В.Е. Теория вероятностей и математическая статистика. М: Высшая школа, 2001.
7) Советов Б.А., Яковлев С.А. Моделирование систем. М: Высшая школа, 1985.
8) Лифшиц А.Л. Статистическое моделирование СМО. М., 1978.
9) Вентцель Е.С. Исследование операций. М: Наука, 1980.
10) Вентцель Е.С., Овчаров Л.А. Теория вероятностей и её инженерные приложения. М: Наука, 1988.
Транскрипт
1 АН Моисеев АА Назаров Асимптотический анализ высокоинтенсивного полумарковского потока 9 УДК 5987 АН Моисеев АА Назаров Асимптотический анализ высокоинтенсивного полумарковского потока событий Представлено исследование высокоинтенсивного полумарковского потока событий Показано что для рассматриваемого потока распределение вероятностей числа событий наступивших за фиксированный интервал времени при условии неограниченного роста интенсивности потока может быть аппроксимировано нормальным распределением В работе получены параметры этого распределения Ключевые слова: высокоинтенсивный поток событий полумарковский поток асимптотический анализ Одним из базовых элементов систем и сетей массового обслуживания является входящий поток заявок Современные телекоммуникационные сети и системы распределенной обработки информации предполагают высокую пропускную способность каналов передачи информации Таким образом в этих системах количество пакетов данных поступающих на обработку в единицу времени очень высоко В терминах теории массового обслуживания в таких случаях говорят о высокой интенсивности входящего потока В частности в работе модель высокоинтенсивного потока применяется для моделирования потока входящих сообщений многофазной системы распределенной обработки данных В работах были изучены свойства высокоинтенсивных рекуррентных MMPP- и MAPпотоков В настоящей же работе представлен анализ свойств высокоинтенсивного полумарковского (Semi-Markovian или SM-) потока как наиболее общей модели потоков событий Математическая модель Рассмотрим полумарковский поток однородных событий заданный следующим образом Пусть {ξ n τ n } стационарный двумерный марковский процесс с дискретным временем Здесь ξ n дискретная компонента принимающая значения от до K τ n непрерывная компонента принимающая неотрицательные значения Будем полагать что эволюция процесса определяется элементами так называемой полумарковской матрицы A (x) = { Ak ν } k ν= следующим K образом: x Akν (x) = P ξ n+ =ν τ n+ < ξ n = k N Здесь N некоторая большая величина которая введена искусственно чтобы явным образом подчеркнуть малость величин τ n В теоретических исследованиях будем полагать N и таким образом τ n На практике полученные результаты можно использовать для аппроксимации соответствующих величин при достаточно больших значениях N (в условии высокой интенсивности потока) Пусть в момент времени t = произошло изменение состояния процесса {ξ n τ n } Последовательность моментов времени t n определяемая рекуррентным выражением tn+ = tn+τ n+ для n = называется полумарковским потоком случайных событий определяемым полумарковской матрицей A(x) Процесс ξ n =ξ(t n) называют вложенной в полумарковский поток цепью Маркова Поскольку средняя длина интервалов τ n обратно пропорциональна N то при N интенсивность наступления событий в таком потоке будет неограниченно расти Такой поток событий будем называть высокоинтенсивным полумарковским или HISM-потоком (от High-Intensive Semi- Markovian) Ставится задача нахождения числа событий m(t) наступивших в этом потоке в течение интервала времени (t) Вывод уравнений Колмогорова Пусть z(t) длина интервала времени от момента t до момента наступления следующего события в потоке; k(t) случайный процесс значения которого на каждом из интервалов = () Отсюда получаем матричное дифференциальное уравнение относительно функции R(z): R (z) = R ()[ I A (z) ] (3) граничное условие для которого при z имеет вид R () = λr (4) где λ некоторый коэффициент вектор-строка r есть стационарное распределение состояний вложенной цепи Маркова Этот вектор является решением уравнения Колмогорова r= r P где P= lim A (z) есть стохастическая матрица определяющая вероятности переходов вложенной цепи z Маркова Таким образом решение уравнения (3) имеет вид z R() z = R ()[ I A () x ] dx (5) Пусть R= R () есть стационарное распределение значений полумарковского процесса k(t) тогда при z из (5) получаем R= R ()[ I A(x) ] dx=λ r[ I A(x) ] dx=λr [ P A(x) ] dx=λra (6) где A матрица с элементами Akν = [ Pkν Akν(x) ] dx Умножая левую и правую части равенства (6) на единичный вектор-столбец E получим RE = =λrae откуда находим значение коэффициента λ: λ= (7) rae Доклады ТУСУРа 3 (9) сентябрь 3
3 АН Моисеев АА Назаров Асимптотический анализ высокоинтенсивного полумарковского потока jum Введем обозначение Hkuzt () = e Pkmzt () где j = мнимая единица а u некоторая переменная Умножая () на e jum и суммируя по m от до получаем m= Hkuzt () Hkuzt () Hku (t) K ju Hku (t) = + e Aν k (z) N ν= С учетом обозначения в виде вектор-строки H(u z t) = {H(u z t) H(K u z t)} данное уравнение примет вид H(uzt) H(uzt) H(u t) ju = + e A(z) I (8) N Дифференциальное матричное уравнение (8) будем решать асимптотически методом в условии неограниченно растущей интенсивности λn рассматриваемого полумарковского потока те при N Асимптотика первого порядка Введем обозначения N =ε u= ε w H(uzt) = F (wzt ε) Из (8) получим F(wzt ε) F(wzt ε) F(w t ε) jwε ε = + e A(z) I (9) Теорема Асимптотическое решение F(wzt) = lim F (wzt ε) уравнения (9) имеет вид ε () () jw λ F wzt = R ze t () где R(z) определяется выражением (5) Доказательство Выполним в (9) предельный переход ε получим уравнение F(wzt) F(w t) = + [ A(z) I ] которое имеет вид аналогичный () Следовательно функцию F (w z t) можно представить в виде F(wzt) = R (z) Φ(wt) () где Φ (w t) некоторая скалярная функция Выполним в (9) предельный переход z и просуммируем все компоненты этого уравнения (для этого умножим справа обе его части на единичный вектор-столбец E) Получим F(w t ε) F(w t ε) ε E= e P I E Подставим сюда выражение () воспользуемся разложением e = + jε w+ O(ε) поделим обе части на ε и произведем предельный переход ε: Φ(wt) RE = jwr () PE Φ(wt) откуда с учетом (4) получаем дифференциальное уравнение относительно функции Φ (w t): Φ(wt) = jwλφ (wt) Решая это уравнение при начальном условии Φ (w) = получаем решение jwλt Φ (wt) = e Подставим это выражение в () получим () Теорема доказана ju Nt Асимптотика второго порядка Выполним в (8) замену H(uzt) = H (uzte) λ: H(uzt) H(uzt) H(u t) ju + juλ H(u z t) = + e A(z) I () N Введем обозначения N =ε u= ε w H(uzt) = F (wzt ε) (3) Доклады ТУСУРа 3 (9) сентябрь 3
4 УПРАВЛЕНИЕ ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА И ИНФОРМАТИКА Тогда () перепишется в виде F(wzt ε) F(wzt ε) F(w t ε) ε + λf (wzt ε) = + e A(z) I (4) Теорема Асимптотическое решение F(wzt) = lim F (wzt ε) уравнения (4) имеет вид ε (jw) F (wzt) = R (z)exp (λ+κ) t (5) где R(z) определяется выражением (5) κ= fe (6) вектор-строка f удовлетворяет системе линейных алгебраических уравнений f I P =λ rp R λ a (7) f AE= a = rae A = x da (x) Доказательство Выполним в (4) предельный переход ε получим уравнение F(wzt) F(w t) = + [ A(z) I ] которое имеет вид аналогичный () Следовательно функцию F (w z t) можно представить в виде F(wzt) = R (z) Φ(wt) (8) где Φ (w t) некоторая скалярная функция Решение уравнения (4) будем искать в виде разложения F(wzt ε) =Φ (wt) R(z) + jε wf (z) + O(ε) (9) где f(z) некоторая вектор-функция (строка) Подставляя это выражение в (4) и применяя разложение e = + jε w+ O(ε) после некоторых преобразований получим { } λφ (wt) R() z=φ (wt) R() z+ f () z+ R() A() z I + R() A() z+ f () A() z I+ A () z + O(ε) Учитывая (3) (4) поделив обе части на jεw и сокращая Φ (w t) получаем λ R(z) = f (z) +λ ra(z) + f ()[ A(z) I ] + O(ε) Отсюда при ε получаем дифференциальное уравнение относительно неизвестной векторфункции f(z) f (z) = f ()[ I A(z) ] λ[ ra(z) R (z) ] интегрируя которое при начальном условии f() = получаем выражение z f(z) = { f ()[ I A(x) ] λ[ ra(x) R (x) ]} dx () Будем искать f(z) в классе функций удовлетворяющих условию lim { f ()[ I A(x) ] λ[ ra(x) R (x) ]} = x Отсюда получаем f ()[ I P] λ[ rp R ] = () Вычитая левую часть этого равенства из подынтегрального выражения () с учетом (6) получаем f() = f () A+λrA λ [ R R (x) ] dx () Можно показать что [ R R (x) ] dx= λ ra где A = x da (x) С учетом этого умножая обе части () справа на единичный вектор E получим Доклады ТУСУРа 3 (9) сентябрь 3
5 АН Моисеев АА Назаров Асимптотический анализ высокоинтенсивного полумарковского потока 3 λ a [ f () A f()] E = (3) где a = rae Полагая что f() E = и обозначая f = f () из () и (3) получаем систему уравнений (7) Выполним в (4) предельный переход z и домножим обе части уравнения на E справа получим F(w t ε) F(w t ε) jw (w t) jw jw (w t) ε ε e F ε ε E+ ε λf ε E= P I E= E (e) () 3 Подставим сюда (9) и применим разложение e = + jε w+ + O(ε) получаем Φ(wt) (jεw) 3 ε RE+ λφ (wt) RE =Φ (wt)[ R () + f ()] E jw ε + + O(ε) Приводя подобные сокращая на ε используя обозначение (6) и переходя к пределу при ε получаем следующее дифференциальное уравнение относительно неизвестной функции Φ (w t): Φ(wt) (jw) = Φ(wt) (λ+κ) (jw) решая которое при начальном условии Φ (w) = получаем Φ (wt) = exp (λ+κ) t Подставляя это выражение в (8) получаем (5) Теорема доказана Аппроксимация распределения числа событий наступивших в HISM-потоке Выполняя в (5) замены обратные к (3) и возвращаясь к функции H(u z t) получаем (ju) H(u z t) R (z)exp juλ Nt + (λ+κ) Nt Таким образом характеристическая функция числа событий наступивших в высокоинтенсивном полумарковском потоке в течение времени t удовлетворяет соотношению (ju) hut () = H(u t) E exp juλ Nt+ (λ+κ) Nt То есть при достаточно больших значениях N распределение числа событий наступивших в HISM-потоке за время t может быть аппроксимировано нормальным распределением с математическим ожиданием λnt и дисперсией (λ + κ)nt где λ и κ определяются выражениями (7) и (6) Численные результаты В качестве примера для численных расчетов рассмотрим задачу моделирования событий в высокоинтенсивном полумарковском потоке заданном полумарковской матрицей A(x) третьего порядка записанной в форме A(x) = P * G(x) где P стохастическая матрица; G(x) матрица составленная из некоторых функций распределения; операция * адамарово произведение матриц Будем рассматривать пример когда элементы матрицы G(x) соответствуют функциям гамма-распределения с параметрами формы α kν и масштаба β kν k ν = 3 которые представим в виде матриц α и β соответственно Выберем следующие конкретные значения параметров: P = 3 5 α = 5 4 β = В результате расчетов получили следующие значения параметров: λ 99; κ 96 Для данной задачи было выполнено имитационное моделирование потока при значениях N = 3 и построены эмпирические распределения числа событий в интервалах длины t = Ряды распределений эмпирических данных и соответствующих аппроксимаций для N = и N = представлены графически на рис (для остальных значений N графики практически совпадают и на рисунке становятся неразличимы) Доклады ТУСУРа 3 (9) сентябрь 3
6 4 4 УПРАВЛЕНИЕ ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА И ИНФОРМАТИКА 5 8 N = N = Рис Сравнение полигона относительных частот эмпирического распределения () и аппроксимирующего ряда распределения () Для оценки точности аппроксимации распределения будем использовать расстояние Колмогорова Dq = sup Fq(x) F(x) Здесь F q (x) эмпирическая функция распределения F(x) функция x распределения нормальной случайной величины с найденными выше характеристиками В таблице представлены Зависимость качества аппроксимации от величины N N δ относительные погрешности вычисления математического a δ D D q 8% 6% 464 ожидания δ a и дисперсии δ D а также расстояние Колмогорова D q для рассмотренных случаев 9% 7% % 5% На рис представлен график демонстрирующий % 4% 44 убывание расстояния Колмогорова между эмпирическим и 8% % аналитическим (нормальным) распределениями с ростом значения N D q Можно заметить что уже при 5 N > 3 достигается достаточно высокое качество гауссовской аппроксимации числа событий в рассмотренном высокоинтенсивном полумар- 4 ковском потоке (расстояние Колмогорова не превышает) 3 Рис Изменение расстояния Колмогорова D q в зависимости от интенсивности потока (логарифмическая шкала по N) N Заключение В работе представлено исследование высокоинтенсивного полумарковского потока событий Показано что в условии неограниченного роста его интенсивности распределение числа событий наступивших в данном потоке в течение интервала времени фиксированной длины может быть аппроксимировано нормальным распределением В работе получены параметры этого распределения Рассмотренные числовые примеры демонстрируют применимость полученных асимптотических результатов для HISM-потоков событий Аналогичные результаты были получены ранее и для других типов высокоинтенсивных потоков: рекуррентного MMPP MAP Доклады ТУСУРа 3 (9) сентябрь 3
7 АН Моисеев АА Назаров Асимптотический анализ высокоинтенсивного полумарковского потока 5 Литература Гнеденко БВ Введение в теорию массового обслуживания / БВ Гнеденко ИН Коваленко 4-е изд испр М: Изд-во ЛКИ 7 4 с Грачев ВВ Многофазная модель массового обслуживания системы распределенной обработки данных / ВВ Грачев АН Моисеев АА Назаров ВЗ Ямпольский // Доклады ТУСУРа (6) ч С Moiseev A Investigation of High Intensive General Flow / A Moiseev A Nazarov // Proc of the IV International Conference «Problems of Cybernetics and Informatics» (PCI) Baku: IEEE P Moiseev A Investigation of the High Intensive Markov-Modulated Poisson Process / A Moiseev A Nazarov // Proc Of The International Conference On Application Of Information And Communication Technology And Statistics In Economy And Education (ICAICTSEE-) Sofia: University Of National And World Economy P Моисеев АН Исследование высокоинтенсивного MAP-потока / АН Моисеев АА Назаров // Изв Том политехн ун-та 3 Т 3 С Королюк ВС Стохастические модели систем Киев: Наук думка с 7 Назаров АА Теория вероятностей и случайных процессов: учеб пособие / АА Назаров АФ Терпугов -е изд испр Томск: Изд-во НТЛ 4 с 8 Назаров АА Метод асимптотического анализа в теории массового обслуживания / АА Назаров СП Моисеева Томск: Изд-во НТЛ 6 с 9 Корн Г Справочник по математике для научных работников и инженеров / Г Корн Т Корн М: Наука с Рыков ВВ Математическая статистика и планирование эксперимента: учеб пособие / ВВ Рыков ВЮ Иткин М: МАКС Пресс 38 с Моисеев Александр Николаевич Канд техн наук доцент каф программной инженерии Томского государственного университета (ТГУ) Тел: 8 (38-) Эл почта: Назаров Анатолий Андреевич Д-р техн наук профессор зав каф теории вероятностей и математической статистики ТГУ Тел: 8 (38-) Эл почта: Moiseev AN Nazarov AA Asymptotic analysis of the high-intensive semi-markovian arrival process Investigation of the high-intensive semi-markovian arrival process is presented in the paper It is shown that a distribution of the number of arrivals in the process during some period under asymptotic condition of an infinite growth of the process rate can be approximated by normal distribution The characteristics of the approximation are obtained as well The analytical results are supported by numeric examples Keywords: high-intensive arrival process semi-markovian process asymptotic analysis Доклады ТУСУРа 3 (9) сентябрь 3
СПИСОК ЛИТЕРАТУРЫ. Баласанян С.Ш. Стратифицированная модель для оценки и анализа эффективности функционирования сложных технологических систем со многими состояниями // Известия Томского политехнического
АСИМПТОТИЧЕСКИЙ АНАЛИЗ РАЗОМКНУТОЙ НЕМАРКОВСКОЙ СЕТИ МАССОВОГО ОБСЛУЖИВАНИЯ HIMMPP (GI) K А. Назаров, А. Моисеев Томский государственный университет Томск, Россия [email protected] В работе представлено
ВЕСТНИК ТОМСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА 2008 Управление вычислительная техника и информатика 3(4) УДК 6239; 592 СВ Лопухова ИССЛЕДОВАНИЕ ММР-ПОТОКА АСИМПТОТИЧЕСКИМ МЕТОДОМ -го ПОРЯДКА В работе рассматривается
С.А. Матвеев, А.Н. Моисеев, А.А. Назаров. Применение метода начальных моментов 9 УДК 59.87 С.А. Матвеев, А.Н. Моисеев, А.А. Назаров Применение метода начальных моментов для исследования многофазной системы
ВЕСТНИК ТОМСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА 7 Управление вычислительная техника и информатика УДК 5987 ТА Карлыханова МЕТОД ПРОСЕЯННОГО ПОТОКА ДЛЯ ИССЛЕДОВАНИЯ СИСТЕМЫ GI/GI/ Для системы массового обслуживания
УДК 6.39.; 59. С.В. Лопухова А.А. Назаров ИССЛЕДОВАНИЕ МАР-ПОТОКА МЕТОДОМ АСИМПТОТИЧЕСКОГО АНАЛИЗА N -го ПОРЯДКА Рассматривается МАР-поток. Выполнено исследование данного потока методом асимптотического
ВЕСТНИК ТОМСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА 8 Управление вычислительная техника и информатика 4(5) МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ УДК 59.87 В.А. Вавилов А.А. Назаров МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ НЕУСТОЙЧИВЫХ
Филиал Кемеровского государственного университета в г. Анжеро-Судженске Национальный исследовательский Томский государственный университет Кемеровский государственный университет Институт проблем управления
ВЕСТНИК ТОМСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА Управление вычислительная техника и информатика 3() УДК 59.87 И.А. Ивановская С.П. Моисеева ИССЛЕДОВАНИЕ МОДЕЛИ ПАРАЛЛЕЛЬНОГО ОБСЛУЖИВАНИЯ КРАТНЫХ ЗАЯВОК
ВЕСТНИК ТОМСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА 2011 Управление, вычислительная техника и информатика 3(16) ОБРАБОТКА ИНФОРМАЦИИ УДК 519.872 И.Л. Лапатин, А.А. Назаров ХАРАКТЕРИСТИКИ МАРКОВСКИХ СИСТЕМ МАССОВОГО
А.А. Назаров И.А. Семенова. Сравнение асимптотических и допредельных характеристик 187 УДК 4.94:519.872 А.А. Назаров И.А. Семенова Сравнение асимптотических и допредельных характеристик системы МАР/М/
Филиал Кемеровского государственного университета в г Анжеро-Судженске Национальный исследовательский Томский государственный университет Кемеровский государственный университет Институт проблем управления
Статистическая радиофизика и теория информации Лекция 7 8.Марковские цепи с непрерывным временем Марковские цепи с непрерывным временем представляют собой марковский случайный процесс X t, состоящий из
ВЕСТНИК ТОМСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА 9 Управление вычислительная техника и информатика (7) МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ УДК 5987 ВА Вавилов МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ НЕУСТОЙЧИВЫХ СЕТЕЙ СЛУЧАЙНОГО
ГЛАВА 5. МАРКОВСКИЕ ПРОЦЕССЫ С НЕПРЕРЫВНЫМ ВРЕМЕНЕМ И ДИСКРЕТНЫМ МНОЖЕСТВОМ СОСТОЯНИЙ В результате изучения данной главы студенты должны: знать определения и свойства Марковских процессов с непрерывным
На правах рукописи Задиранова Любовь Александровна ИССЛЕДОВАНИЕ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ ПОТОКОВ В БЕСКОНЕЧНОЛИНЕЙНЫХ СМО С ПОВТОРНЫМ ОБСЛУЖИВАНИЕМ ТРЕБОВАНИЙ 05.13.18 Математическое моделирование, численные
ВЕСТНИК ТОМСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА 7 Управление вычислительная техника и информатика УДК 59 НВ Степанова АФ Терпугов УПРАВЛЕНИЕ ЦЕНОЙ ПРИ ПРОДАЖЕ СКОРОПОРТЯЩЕЙСЯ ПРОДУКЦИИ Рассматривается управление
ВЕСТНИК ТОМСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА Управление, вычислительная техника и информатика () УДК 59.865 К.И. Лившиц, Я.С. Бублик ВЕРОЯТНОСТЬ РАЗОРЕНИЯ СТРАХОВОЙ КОМПАНИИ ПРИ ДВАЖДЫ СТОХАСТИЧЕСКОМ
УДК 6-5 Спектральные характеристики линейных функционалов и их приложения к анализу и синтезу стохастических систем управления К.А. Рыбаков В статье вводится понятие спектральных характеристик линейных
На правах рукописи Лапатин Иван Леонидович ИССЛЕДОВАНИЕ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ ВЫХОДЯЩИХ ПОТОКОВ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ С НЕОГРАНИЧЕННЫМ ЧИСЛОМ ПРИБОРОВ 05.13.18 Математическое моделирование, численные
Оглавление Глава Случайные процессы Простая однородная цепь Маркова Уравнение Маркова Простая однородная цепь Маркова 4 Свойства матрицы перехода 5 Численный эксперимент: стабилизация распределения вероятностей
ИНСТИТУТ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ГЕОФИЗИКИ СИБИРСКОГО ОТДЕЛЕНИЯ РОССИЙСКОЙ АКАДЕМИИ НАУК МАРЧУКОВСКИЕ НАУЧНЫЕ ЧТЕНИЯ 017 5 июня 14 июля 017 года Труды Редакционная коллегия академик
ИССЛЕДОВАНИЕ RQ-СИСТЕМЫ M GI 1 МЕТОДОМ АСИМПТОТИЧЕСКОГО АНАЛИЗА В УСЛОВИИ БОЛЬШОЙ ЗАГРУЗКИ Е. Моисеева, А. Назаров Томский государственный университет Томск, Россия [email protected] В работе рассмотрена
УДК 6-5:59 НС Демин СВ Рожкова ОВ Рожкова ФИЛЬТРАЦИЯ В ДИНАМИЧЕСКИХ СИСТЕМАХ ПО НЕПРЕРЫВНО-ДИСКРЕТНЫМ НАБЛЮДЕНИЯМ С ПАМЯТЬЮ ПРИ НАЛИЧИИ АНОМАЛЬНЫХ ПОМЕХ II НЕПРЕРЫВНО-ДИСКРЕТНЫЕ НАБЛЮДЕНИЯ В данной работе
Численные методы Тема 2 Интерполяция В И Великодный 2011 2012 уч год 1 Понятие интерполяции Интерполяция это способ приближенного или точного нахождения какой-либо величины по известным отдельным значениям
Український математичний вiсник Том 5 (28), 3, 293 34 О краевых задачах для обыкновенного дифференциального оператора с матричными коэффициентами Анна В Агибалова (Представлена М М Маламудом) Аннотация
Лекция 2. Статистики первого типа. Точеченые оценки и их свойства Буре В.М., Грауэр Л.В. ШАД Санкт-Петербург, 2013 Буре В.М., Грауэр Л.В. (ШАД) Лекция 2. Статистики первого типа. Точеченые Санкт-Петербург,
Управление вычислительная техника и информатика УДК 6-5:59 ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ ДИСКРЕТНОГО КАНАЛА НАБЛЮДЕНИЯ С ПАМЯТЬЮ В ЗАДАЧЕ ЭКСТРАПОЛЯЦИИ НС Дёмин ОВ Рожкова* Томский государственный университет
Статистическая радиофизика и теория информации Лекция 6 7. Марковские* случайные процессы и марковские цепи. *Марков Андрей Андреевич (род. 1890) русский математик, академик Марковский случайный процесс
Сибирский математический журнал Июль август, 2003 Том 44, 4 УДК 51921+5192195 О КОМПОНЕНТАХ ФАКТОРИЗАЦИОННОГО ПРЕДСТАВЛЕНИЯ ДЛЯ ВРЕМЕНИ ПРЕБЫВАНИЯ ПОЛУНЕПРЕРЫВНЫХ СЛУЧАЙНЫХ БЛУЖДАНИЙ В ПОЛОСЕ В С Лугавов
На правах рукописи Горбатенко Анна Евгеньевна ИССЛЕДОВАНИЕ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ С КОРРЕЛИРОВАННЫМИ ПОТОКАМИ В СПЕЦИАЛЬНЫХ ПРЕДЕЛЬНЫХ УСЛОВИЯХ 05.13.18 Математическое моделирование, численные методы
Управление вычислительная техника и информатика УДК 59. ИНФОРМАЦИОННЫЙ АСПЕКТ В СОВМЕСТНОЙ ЗАДАЧЕ НЕПРЕРЫВНО-ДИСКРЕТНОЙ ФИЛЬТРАЦИИ И ИНТЕРПОЛЯЦИИ. АНАЛИЗ С.В. Рожкова О.В. Рожкова Томский политехнический
Сибирский математический журнал Июль август, 2005. Том 46, 4 УДК 519.21 О ФАКТОРИЗАЦИОННЫХ ПРЕДСТАВЛЕНИЯХ В ГРАНИЧНЫХ ЗАДАЧАХ ДЛЯ СЛУЧАЙНЫХ БЛУЖДАНИЙ, ЗАДАННЫХ НА ЦЕПИ МАРКОВА В. И. Лотов, Н. Г. Орлова
Лекция 3 Устойчивость равновесия и движения системы При рассмотрении установившихся движений уравнения возмущенного движения запишем в виде d dt A Y где вектор-столбец квадратная матрица постоянных коэффициентов
Глава 1 Дифференциальные уравнения 1.1 Понятие о дифференциальном уравнении 1.1.1 Задачи, приводящие к дифференциальным уравнениям. В классической физике каждой физической величине ставится в соответствие
Лекция ХАРАКТЕРИСТИЧЕСКАЯ ФУНКЦИЯ ЦЕЛЬ ЛЕКЦИИ: построить метод линеаризации функций случайных величин; ввести понятие комплексной случайной величины и получить ее числовые характеристики; определить характеристическую
Моделирование систем с использованием Марковских случайных процессов Основные понятия Марковских процессов Функция X(t) называется случайной, если ее значение при любом аргументе t является случайной величиной.
1. КОНЕЧНЫЕ ОДНОРОДНЫЕ ЦЕПИ МАРКОВА Рассмотрим последовательность случайных величин ξ n, n 0, 1,..., каждая из коорых распределена дискретно и принимает значения из одного и того же множества {x 1,...,
Глава 6 Основы теории устойчивости Лекция Постановка задачи Основные понятия Ранее было показано, что решение задачи Коши для нормальной системы ОДУ = f, () непрерывно зависит от начальных условий при
Sin cos R Z cos ImZ cos sin sin Найденные таким образом решения образуют фундаментальную систему решений и следовательно общее решение системы имеет вид или подробнее sin cos cos sin cos cos cos sin sin
Структурная надежность. Теория и практика Каштанов В.А. УПРАВЛЕНИЕ СТРУКТУРОЙ В МОДЕЛЯХ МАССОВОГО ОБСЛУЖИВАНИЯ И НАДЕЖНОСТИ С использованием управляемых полумарковских процессов исследуется оптимальная
МАТЕМАТИЧЕСКАЯ МОДЕЛЬ СТРАХОВОЙ КОМПАНИИ В ВИДЕ СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ M M И. Синякова, С. Моисеева Национальный исследовательский Томский государственный университет Томск, Россия [email protected]
УДК 59. ТЕОРЕМА РАЗДЕЛЕНИЯ В СЛУЧАЕ НАБЛЮДЕНИЙ С ПАМЯТЬЮ Н.С. Демин, С.В. Рожкова Томский государственный университет Томский политехнический университет E-mail: [email protected] Приводится доказательство
По условию теоремы L B (m Тогда в силу линейности оператора L имеем: m m m L L ] B [ Системы линейных дифференциальных уравнений с постоянными коэффициентами Собственные значения и собственные векторы
СПИСОК ЛИТЕРАТУРЫ Калашникова ТВ Извеков НЮ Интеграция метода ориентации на спрос в систему ценообразования сети розничной торговли // Известия Томского политехнического университета Т 3 6 С 9 3 Фомин
ИНСТИТУТ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ГЕОФИЗИКИ СИБИРСКОГО ОТДЕЛЕНИЯ РОССИЙСКОЙ АКАДЕМИИ НАУК МАРЧУКОВСКИЕ НАУЧНЫЕ ЧТЕНИЯ 217 25 июня 14 июля 217 года Труды Редакционная коллегия академик
ТЕМА 7. Случайные процессы. Цель контента темы 7 дать начальные понятия о случайных процессах и цепях Маркова в частности; очертить круг экономических задач, которые используют в своем решении модели,
Лекция 4. Доверительные интервалы Буре В.М., Грауэр Л.В. ШАД Санкт-Петербург, 2013 Буре В.М., Грауэр Л.В. (ШАД) Лекция 4. Доверительные интервалы Санкт-Петербург, 2013 1 / 49 Cодержание Содержание 1 Доверительные
Сибирский математический журнал Январь февраль, 2. Том 41, 1 УДК 517.948 АСИМПТОТИКА РЕШЕНИЯ СИНГУЛЯРНО ВОЗМУЩЕННЫХ НЕЛИНЕЙНЫХ ИНТЕГРОДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ М. К. Дауылбаев Аннотация: Рассмотрено сингулярно
Лекция Моделирование систем с использованием Марковских случайных процессов Основные понятия Марковских процессов Функция X(t) называется случайной, если ее значение при любом аргументе t является случайной
7 (), 9 Г. В. Бойкова Î íåêîòîðîì íåèçâåñòíîì ðåøåíèè îäíîðîäíîãî äèôôåðåíöèàëüíîãî óðàâíåíèÿ âòîðîãî ïîðÿäêà Аннотация: для дифференциального уравнения второго порядка найдено решение, которое представляет
ЕСТЕСТВЕННЫЕ И ТОЧНЫЕ НАУКИ УДК 57977 ОБ УПРАВЛЯЕМОСТИ ЛИНЕЙНЫХ СИНГУЛЯРНО ВОЗМУЩЕННЫХ СИСТЕМ С МАЛЫМ ЗАПАЗДЫВАНИЕМ Канд физ-мат наук доц КОПЕЙКИНА Т Б ГУСЕЙНОВА А С Белорусский национальный технический
Компьтерное моделирование. СМО. Лекция 2 1 Оглавление Глава 2. Представление СМО марковским случайным процессом... 1 I. Классификация СМО по Кендалл... 1 II. Марковский случайный процесс... 2 III. Марковские
48 Вестник РАУ Серия физико-математические и естественные науки, 1, 28, 48-59 УДК 68136 ОЦЕНКА ХАРАКТЕРИСТИК НАДЕЖНОСТИ СИСТЕМ ДИСТАНЦИОННОГО ОБУЧЕНИЯ ЧАСТЬ 2 ХВ Керобян, НН Хубларян, АГ Оганесян Российско-Армянский
Основные понятия теории разностных схем. Примеры построения разностных схем для начально-краевых задач. Большое количество задач физики и техники приводит к краевым либо начальнокраевым задачам для линейных
4 (0) 00 Байесовский анализ когда оцениваемый параметр является случайным нормальным процессом Рассмотрена задача байесовского оценивания последовательности неизвестных средних значений q q... q... по
РОССИЙСКИЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ МИРЭА ДОПОЛНИТЕЛЬНЫЕ ГЛАВЫ ВЫСШЕЙ МАТЕМАТИКИ ГЛАВА 3. СИСТЕМЫ ДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ Работа посвящена моделированию динамических систем с использованием элементов
СИСТЕМЫ ЛИНЕЙНЫХ ДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ С ПОСТОЯННЫМИ КОЭФФИЦИЕНТАМИ Приведение к одному уравнению -го порядка С практической точки зрения очень важны линейные системы с постоянными коэффициентами
1 Заглавие документа Овсянников А.В. СТАТИСТИЧЕСКИЕ НЕРАВЕНСТВА В СВЕРХРЕГУЛЯРНЫХ СТАТИСТИЧЕСКИХ ЭКСПЕРИМЕНТАХ ТЕОРИИ ОЦЕНИВАНИЯ // Вест нацыянальнай акадэм навук Беларус, 009. Сер фз-мат. навук. С.106-110
УДК 59 ЕВ Новицкая АФ Терпугов ОПРЕДЕЛЕНИЕ ОПТИМАЛЬНОГО ОБЪЕМА ПАРТИИ ТОВАРА И РОЗНИЧНОЙ ЦЕНЫ ПРОДАЖИ НЕПРЕРЫВНО ПОРТЯЩЕЙСЯ ПРОДУКЦИИ Рассматривается задача определения оптимального объема партии товара
ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ Московский государственный технический университет имени НЭ Баумана Факультет «Фундаментальные науки» Кафедра «Математическое моделирование» ÀÍ Êàíàòíèêîâ, ÀÏ Êðèùåíêî ÀÍÀËÈÒÈ
Math-Net.Ru Общероссийский математический портал А. А. Назаров, Т. В. Любина, Немарковская динамическая RQ-система с входящим MMP-потоком заявок, Автомат. и телемех., 213, выпуск 7, 89 11 Использование
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ КРАСНОЯРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ УДК ББК Составитель: Н.А. Пинкина КАФЕДРА ВЫСШЕЙ МАТЕМАТИКИ Линейная алгебра. Решение типовых примеров. Варианты контрольных
Лекция 2 Решение систем линейных уравнений. 1. Решение систем 3-х линейных уравнений методом Крамера. Определение. Системой 3-х линейных уравнений называется система вида В этой системе искомые величины,
Вычислительные технологии
Том 13, Специальный выпуск 5, 2008
Исследование полумарковского потока событий
А. А. Назаров, С. В. Лопухова Томский государственный университет, Россия e-mail: nazarov@f pmk. tsu. ru, lopuchovasv@mail. ru
И.Р. Гарайшина
Филиал Кемеровского государственного университета в г. Анжеро-Судженске, Россия e-mail: [email protected]
In the submitted work, the semimarkovian process is considered. Limiting model is considered. Results of analytical treatment of limiting model are compared with results, obtained by the asymptotical method.
Введение
Существует проблема расширения класса математических моделей потоков однородных событий. Зачастую классические модели случайных потоков событий не могут быть адекватны реальным информационным, телекоммуникационным потокам. Моделей пуассоповского и простейшего потоков часто бывает недостаточно для более правдоподобного, приближенного к реальности описания входящих потоков для систем массового обслуживания. Несмотря на то что существуют потоки фазового типа и модулированные пуассоновские потоки, которые более адекватны реальным ситуациям, большой интерес представляют модели полумарковского потока, частным случаем которых являются потоки марковского восстановления и все вышеперечисленные потоки. Методы исследования таких моделей достаточно сложны и приводят к значительным математическим проблемам. Поэтому наряду с задачей расширения классов потоков существует проблема развития методов их исследования.
1. Математическая модель
Случайным потоком однородных событий (потоком) будем называть упорядоченную последовательность
t\ < ¿2 < ■ ■ ■ случайных величин tm - моментов наступления событий в потоке. Пусть задана полумарковская матрица A(x) с элемента ми Aklk2 (x), Матрн ца P = lim A(x) является стохастической, поэтому при заданном начальном распределении она определяет некоторую цепь Маркова k (tm) с дискретным временем, которую будем называть вложенной в полумарковский поток цепью Маркова, © Институт вычислительных технологий Сибирского отделения Российской академии наук, 2008. А. А. Назаров, С. В. Лопухова, И. Р. Гарайшина Случайный поток однородных событий будем называть полумарковским, если вероятностный закон формирования последовательности (1) определяется начальным распределением и равенствами Ак1к2 (х) = Р {к(Ьт+1) = к2, Ьт+1 - Ьт < х ^^т) = к\ } при всех т > 1. Обозначим п(Ь) число событий полу марко веко го потока, наетуп ивших за время Ь па интервале . Задачей исследования данной работы является установление распределения вероятностей Р(п, Ь) = Р{п(Ь) = п} при стационарном функционировании эргодичеекой цепи Маркова к (1т). Очевидно, процесс п(Ь) - немарковский, поэтому определим еще два случайных процесса: г(Ь) - длину интервала от момента времени Ь до момента наступления очередного события в рассматриваемом потоке, к(Ь) - непрерывный слева процесс с непрерывным временем, значение которого на интервале (Ьт,Ьт+1] постоянны и определяются равенствами к (Ь) = к (Ьт+1). В силу сделанных определений случайный процесс {к(Ь), п(Ь), г(Ь)} является трехмерным марковским процессом с непрерывным временем. Заметим, что случайный процесс к(Ь) не является полумарковским в классическом определении , так как полумарковский процесс Б(Ь) непрерывен справа и, как указано в , для его переходных вероятностей не существует дифференциальных эволюционных уравнений Колмогорова, в то время как предложенный выше процесс {к(Ь), п(Ь), г(Ь)} - марковский, поэтому для его распределения вероятностей Р (к, п, г,Ь) = Р {к(Ь) = к, п(Ь) = п, г(Ь) < г} (2) нетрудно составить систему дифференциальных уравнений Колмогорова дР (к,п,г,Ь) дР (к,п,г,Ь) дР (к,п, 0,Ь) ^ дР (и,п - 1,0,Ь) ^ дГ (и,1Ь - 1, 0,Ь) А (\ 2-^- дЬ дг дг ^ дг Обозначим Н(к, и, г, г) = ^ е"иПР(к,п,г,Ь), где ] = ¡~ ~~ мнимая единица. Для этих функций из системы дифференциальных уравнений Колмогорова можно записать дН (к,и,г,Ь) дН (к,и,г,Ь) дН (к, и, 0,Ь) ,и ^ дН (и, и, 0,Ь) дЬ дг дг ^ дг Обозначим Н (и,г,Ь) = {Н (1,и,г,Ь) ,Н (2,и,г,Ь),...} строку вектор-функции, тогда систему уравнений (3) перепишем в матричном виде дН{и,г,г) _ дН{и,г,г) дН{и,0,г) Мц,г ч п т дг дг + дг 1 [) "" [ } решение которой удовлетворяет начальному условию H(u,z, 0) = R(z), где I - единичная матрица, а стационарное распределение R(z) двумерного марковского процесса {k(t), z(t)} является решением задачи Коши <Ш = <Ш(1-Мг)), и определяется равенством R{z) = seiт / (Р - A(x))dx, где aei = Здесь г - вектор- строка стационарного распределения вероятностей значений вложенной цепи Маркова k(tm); E - единичный вектор-столбец и матрица A = (P - A(x))dx. 2. Допредельная модель Пусть имеем дифференциальное уравнение (4), решение H (u,z,t) которого удовлетворяет начальному условию H(u, z, 0) = R(z). Тогда преобразование Фурье - Стилтьесса ф>(u,a,t) = / ejaz dz H (u, z, t) вектор-функ ции H (u,z,t) удовлетворяет уравнению дф(и,а,Ь) . . дН (и, 0,Ь) , .*. . гЛ, . т = ~заф{щ а, +-(е?иА*{а) - /) (5) и начальному условию ф(и,а, 0) = R*(a) = ^ ё>а2 где А*(а) = J е>а"2dA(z). Решение уравнения (5) имеет вид о ф(и, а,1) = е~заЬ [ II*{а) + I (¿>иА*{а) - I) dт ] . (6) Устремив Ь в бесконечность в выражении (6), получим преобразование Фурье по т дН (и, 0,т) ^ ^ " л от вектор-функции---. Выполнив обратное преобразование Фурье, определим, I e-j А. А. Назаров, С. В. Лопухова, И. Р. Рарайшшиа Теперь равенство (6) можно записать в виде ф(ща,г) = е-аЬ Я*(а) + + - / е]ат I е~зутК*(у) (/ - е>иА*(у)) 1 Ау (е"иА*(а) - /) <*г). (7) Зная, что Н(и, ж,г) = Н(и,г) = ф(и, 0,1), получим выражение для вектор-функции Н (и,г): Тогда распределение вероятностей Р(п, г) числа событий, наступивших за время г, явля- ции Н(и,Ь) = МеЭип(Ь = Н(и,Ь)Е, оно имеет вид 1 С а1 Г 1 - е-™Ь Р(п,1) = - е~зипНШ)Е(1и = - / -^-5 I - А* (у) А*(у)п-1Ейу, (8) I - А* (у) Е<1у Заключение Выполняя асимптотические исследования полу марко веко го потока событий, аналогичные исследованию потоков марковского восстановления , получим, что асимптотику третьего порядка для характеристической функции можно записать в виде МеГап(1) = ^«(ге^+^ае^+^аез*) где коэффициенты 831, а2, аз3 для полумарковского потока определяются аналогично тому, как это сделано в работах . Полученные равенства (8) определяют распределение вероятностей Р(п,г) числа событий, наступивших в стационарном полумарковском потоке, заданном полумарковской матрицей А(х) и ее преобразованием А*(х) Фурье - Стилтьесса, Численная реализация формул (8) позволяет находить численные значения вероятностей Р(п, г) для достаточно широкого клаееа матриц А* (х) и значений г. Но возможности численной реализации ограничены вычислительными ресурсами. Для достаточно больших значений г естественно применить метод асимптотического анализа полумарковского потока аналогично тому, как это выполнено для потока марковского восстановления в работе и просеянного потока марковского восстановления в работе . Наличие численного алгоритма (8) позволяет определить область применения асимптотических результатов. Для рассмотренных потоков с тремя состояниями вложенной цепи Маркова расстояние Колмогорова - Смирнова между распределениями, полученными асимптотически и по формулам (8), не превосходит 2-3 % для определенных значений t = Т, это позволяет утверждать, что при t > Т эффективно применение асимптотических результатов, а при t < Т целесообразно использовать формулы (8), полученные в данной работе. Список литературы Королюк B.C. Стохастические модели систем. Киев: Наук, думка, 1989. 208 с. Назаров A.A., Лопухова C.B. Исследование потока марковского восстановления асимптотическим методом второго порядка // Матер. Междунар. науч. конф. "Математические методы повышения эффективности функционирования телекоммуникационных сетей". Гродно, 2007. С. 170-174. Лопухова C.B. Исследование полумарковского потока асимптотическим методом третьего порядка // Матер. VI Междунар. научно-практ. конф. "Информационные технологии и математическое моделирование". Томск: Изд-во Том. ун-та, 2007. Ч. 2. С. 30-34. На практике мы почти никогда не имеем дела с марковскими процессами в чистом виде: реальные процессы почти всегда обладают тем или другим последействием. Для марковского процесса время пребывания системы подряд в каком-либо состоянии распределено по показательному закону; на самом деле это далеко не всегда бывает так. Например, если поток событий, переводящий систему из состояния в состояние есть поток отказов какого-то узла, то более естественно предположить, что оставшееся время безотказной работы узла зависит от того, сколько времени узел уже работал. При этом время пребывания узла в рабочем состоянии представляет собой случайную величину, распределенную не по показательному, а по какому-то иному закону. Возникает вопрос о том, можно ли приближенно заменять непуассоновские потоки - пуассоновскими и к каким ошибкам в предельных вероятностях состояний может привести подобная замена. Для этого необходимо уметь хотя бы приближенно исследовать случайные процессы, протекающие в системах с последействием. Рассмотрим некоторую физическую систему S, в которой протекает случайный процесс, направляемый какими-то непуассоновскими потоками событий. Если мы попробуем для этого процесса написать уравнения, выражающие вероятности состояний как функции времени, мы увидим, что в общем случае это нам не удастся. Действительно, для марковской системы мы вычисляли вероятность того, что в момент система будет в состоянии учитывая только то, в каком состоянии система была в момент t, и не учитывая, сколько времени она была в этом состоянии. Для немарковской системы этот прием уже непригоден: вычисляя вероятность перехода из одного состояния в другое за время мы должны будем учитывать, сколько времени система уже провела в данном состоянии. Это приводит, вместо обыкновенных дифференциальных уравнений, к уравнениям с частными производными, то есть к гораздо более сложному математическому аппарату, с помощью которого только в редких случаях можно получить нужные результаты. Возникает вопрос: а нельзя ли свести искусственно (хотя бы приближенно) немарковский процесс к марковскому? Оказывается, в некоторых случаях это возможно: а именно, если число состояний системы не очень велико, а отличающиеся от простейших потоки событий, участвующие в задаче, представляют собой (точно или приближенно) потоки Эрланга. Тогда, вводя в схему возможных состояний системы некоторые фиктивные «псевдосостояния», удается свести немарковский процесс к марковскому и описать его с помощью обыкновенных дифференциальных уравнений, которые при переходят в алгебраические уравнения для предельных вероятностей состояний. Поясним идею метода «псевдосостояний» на конкретном примере. Пример 1. Рассматривается система S - Техническое устройство, которое может выходить из строя под влиянием простейшего потока неисправностей с интенсивностью к. Отказавшее устройство немедленно начинает восстанавливаться. Время восстановления (ремонта) Т распределено не по показательному закону (как надо было бы для того, чтобы процесс был марковским), а по закону Эрланга порядка: Требуется свести данный немарковский процесс к марковскому и найти для него предельные вероятности состояний. Решение. Случайная величина Т - время восстановления - распределена по закону Эрланга и, значит, представляет собой сумму трех случайных величин распределенных по показательному закону (см. § 5 гл. 4) с параметром Истинных состояний системы всего два: Устройство исправно; Устройство восстанавливается. Граф этих состояний показан на (он относится к циклической схеме). Однако в виду того, что переход по стрелке происходит под влиянием не простейшего, а эрланговского потока событий, процесс, происходящий в системе, марковским не является, и для него мы не можем написать ни дифференциальных, ни алгебраических уравнений. Чтобы искусственно свести это процесс к марковскому, введем в цепочку состояний, вместо одного состояния три последовательных «псевдосостояния». Ремонт начинается; Ремонт продолжается; Ремонт заканчивается, т. е. разделим ремонт на три этапа или «фазы», причем время пребывания системы в каждой из фаз будем считать распределенным по показательному закону (10.2). Граф состояний будет иметь вид, показанный на рис. 4.48, где роль одного состояния будут играть три псевдосостояния Процесс, протекающий в такой системе, уже будет марковским. Обозначим - предельные вероятности пребывания системы в псевдосостояниях тогда Обозначая можем сразу написать (как для обычной циклической схемы) предельные вероятности состояний: Заметим, что величина представляет собой не что иное, как среднее время восстановления (ремонта) - оно равно сумме средних времен пребывания системы в каждой фазе ремонта. Переходя в формулах для от средних времен к интенсивностям потоков, по формулам получим: Таким образом, получен вывод: для нашего элементарного примера вероятность пребывания в каждом из двух состояний, как и для марковского цикла, равна относительному среднему времени пребывания подряд в каждом из состояний. Следующий пример будет несколько сложнее. Пример 2. Техническое устройство S состоит из двух одинаковых узлов, каждый из которых может выходить из строя (отказывать) под влиянием простейшего потока неисправностей с интенсивностью 1. Отказавший узел немедленно начинает ремонтироваться. Время ремонта Т распределено по закону Эрланга второго порядка: Требуется найти предельные вероятности состояний системы. Решение. Истинных состояний системы три (нумеруем их по числу отказавших узлов). Оба узла работают; Один узел работает, другой ремонтируется; Оба узла ремонтируются. Разделим условно ремонт на две фазы: ремонт начинается и ремонт заканчивается. Один узел работает, другой начинает ремонтироваться; Один узел работает, другой кончает ремонтироваться; Оба узла начинают рамонтироваться; Один узел начинает ремонтироваться, а другой кончает; Оба узла кончают ремонтироваться. Граф состояний системы с псевдосостояниями показан на рис. 4.49. На стрелках, ведущих из и из написано а не потому что перейти в следующую фазу ремонта (окончание ремонта) может любой из двух узлов. Уравнения для предельных вероятностей состояний имеют вид: Из третьего, пятого и шестого уравнений (10.4) имеем: что дает возможность уменьшить число неизвестных: подставляя (10.5) в оставшиеся три уравнения (10.4), получим: Из этих трех уравнений с тремя неизвестными можно по произволу отбросить любое, например, последнее, и добавить нормировочное условие: или, с учетом (10.5),
