Моделирование систем массового обслуживания и метод Монте-Карло

Содержание

Введение 3

1. Понятие о задачах  теории массового  обслуживания 4

2. Основы математического  аппарата анализа  простейших СМО 5

3. Основные характеристики  СМО 9

5. Дисциплина ожидания  и приоритеты 12

6. Моделирование систем массового обслуживания и метод Монте-Карло 14

Заключение 16

Список  литературы: 17 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

  Введение 

  Буквально с момента рождения вам приходится сталкиваться c очередями. Ваши родители сидят в очереди в ЗАГСе, чтобы официально зафиксировать этот факт... Вы стоите в очереди в школьный гардероб... Вы набираете телефонный номер вашей подруги и слышите продолжительные гудки ... Не дозвонившись, вы решаете для экономии времени воспользоваться собственным лимузином и попадаете в традиционную "пробку"...  

  Очереди являются бедствием нашей эпохи, бедствием неизбежным, если мы не устраним всякую свободу выбора, и не будем планировать каждую мелочь, касающуюся людей и продуктов производства, - a это нетерпимо для цивилизованного общества и, как правило, неосуществимо. Но если ожидание неизбежно, его можно в какой-то степени контролировать: систему или организацию, на входе которой образуется очередь, можно преобразовать и улучшить с точки зрения обслуживания. 

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

  1. Понятие о задачах  теории массового  обслуживания 

  Эта теория представляет особый раздел теории случайных  процессов и использует, в основном, аппарат теории вероятностей. Первые публикации в этой области относятся  к 20-м гг. XX в. и принадлежат датчанину  А. Эрлангу, занимавшемуся исследованиями функционирования телефонных станций - типичных СМО, где случайны моменты  вызова, факт занятости абонента или  всех каналов, продолжительность разговора. В дальнейшем теория очередей нашла  развитие в работах К.Пальма, Ф.Поллачека, А.Я.Хинчина, Б.В.Гнеденко, А.Кофмана, Р.Крюона, Т. Cаати и других советских и зарубежных математиков.  

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

   

  

 

  В зависимости  от характеристик этих элементов  СМО классифицируются следующим образом:

• по характеру поступления заявок. Если интенсивность входного потока (количество заявок в единицу времени) постоянна или является заданной функцией от времени, поток называют регулярным. Если параметры потока независимы от конкретного момента времени, поток называют стационарным;
• по количеству одновременно поступающих заявок. Поток с вероятностью одновременного появления двух и более заявок равной нулю называется ординарным;
• по связи между заявками. Если вероятность появления очередной заявки не зависит от количества предшествующих заявок, имеем дело с потоком без последействия;
• по однородности заявок выделяют однородные и неоднородные потоки;
• по ограниченности потока заявок различают замкнутые и разомкнутые системы (система с ограниченной клиентурой называется замкнутой). Так универсальный магазин является разомкнутой системой, тогда как оптовый магазин с постоянными клиентами - замкнутая система;
• по поведению в очереди системы делятся на системы с отказами (заявка покидает систему, если нет мест в очереди), c ограниченным ожиданием и с ожиданием без ограничения времени;
• по дисциплине выбора на обслуживание. Здесь можно выделить системы с обслуживанием в порядке поступления, в случайном порядке, в порядке, обратном поступлению (последний пришел - первым обслужен) или с учетом приоритетов;
• по числу каналов обслуживания системы разделяют на одно- и многоканальные;
• по времени обслуживания выделяют системы с детерминированным и случайным временем;
• по количеству этапов обслуживания различают однофазные и многофазные системы.

 
 

  2. Основы математического  аппарата анализа  простейших СМО 

  Рассмотрим  стационарный поток однородных заявок без последействия. Пусть P_k(t) вероятность появления k заявок в интервале времени t. Эта вероятность зависит только от длины этого интервала и не зависит от начала отсчета времени, от поступления заявок в предыдущих временных интервалах. Пусть к тому же поток является ординарным, т. е. P_k(dt) при k >1 бесконечно мала в сравнении с малым интервалом dt. Если обозначить через число заявок в единицу времени (интенсивность потока), то можно показать, что для такого простейшего потока  
 

   

  Формула (1) определяет распределение Пуассона. Для пуассоновского потока можно  обнаружить, что промежутки времени T между поступлениями заявок распределены по экспоненциальному (показательному) закону  
 
 

   (вероятность,  что промежуток времени не превышает t).  

Естественно, что  входной поток может описываться не только пуассоновским, но и другими распределениями (Эрланга, гиперэкспоненциальным и т.п.).  

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

   где  =1/t_обс - интенсивность обслуживания (среднее число обслуживаний в единицу времени), t_обс - среднее время обслуживания одной заявки.  

  Пусть S - множество состояний системы  и P(l, t + t / i, t) - вероятность того, что система, находившаяся в момент t в состоянии i, в момент t + t окажется в состоянии l. Для марковской системы (она привлекает нас отсутствием последействия) можно записать уравнения Чепмена-Колмогорова:  

    

   Если  под состояниями понимать число  заявок, то эти уравнения можно  записать в виде:  
 
 

  Рассмотрим  случай разомкнутой системы с  простейшим входным потоком интенсивности  и одним каналом обслуживания с интенсивностью .  

  Возьмем интервал времени [t, t+dt]. В силу разомкнутости системы множество состояний системы

  S = { S₀, S₁, S₂, . . ., S_k, S_k+1, . . . },

   где  S_k - состояние, когда в системе находится k заявок  

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

  Очевидно, что вероятность перехода S₀ в S₁ равна dt и вероятность перехода S₁ в S₀ равна dt P_k-1(t). Если в системе присутствовали k>0 заявок (состояние S_k), то для перехода в состояние S_k-1 необходимо, чтобы заявка была обслужена, и не поступило новой заявки; отсюда вероятность перехода S_k в S_k-1 равна

  dtP_k+1(t) Для перехода из состояния S_k в состояние S_k+1 необходимо, чтобы поступила новая заявка, но ни одна из ранее поступивших не была обслужена: вероятность перехода S_k в S_k+1 равна (1dt) P_k(t). Вероятность для системы остаться в том же состоянии составит 1 - (l+m)dt.  

  Тогда из (5) имеем

  

 

   При  dt в 0 получаем дифференциальные уравнения состояний СМО:

  

 

   Решение  (6) при заданных начальных условиях  достаточно сложно (здесь можно  использовать преобразование Лапласа  или численное решение задачи  Коши для системы обыкновенных  дифференциальных уравнений большого  порядка, но едва ли это посильно  непрофессионалу).  

  Ограничимся рассмотрением установившегося  режима, признаком которого является существование предела 

    
 

   В этом  случае (6) приведется к бесконечной  системе линейных алгебраических  уравнений с трехдиагональной матрицей коэффициентов  

  P₀ = P₁

    
 

   Обозначив 

   (9) 

имеем P₁=rP₀, P₂=r²P₀, P₃=r³P₀, P₄=r⁴P₀, ..., P_k=r^kP₀, ... , откуда с учетом P₀ + P₁ + P₂ + P₃ + ... + P_k+ ... = 1 получаем при r < 1  

    

Тогда  
 

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

  Теперь  обратимся к аналогичной замкнутой  системе с числом заявок, не превышающим n. Здесь система уравнений (6) приведется к конечной системе  

  

 

которая для установившегося режима дает конечную систему линейных алгебраических уравнений  

  

 

  Решение этой системы  

  

  дает  

  

 

   и 

  

 
 

  Полученные  выше решения можно обобщить на случай многоканальных систем c ограниченным ожиданием. Так, если СМО имеет N однотипных каналов обслуживания (интенсивность  обслуживания равна N), m мест в очереди и к тому же число n возможных заявок превышает N+m (в противном случае нет проблем), то возникает система

    

   из которой получаем для установившегося режима

    
 

   Решение  этой системы дает 

  

  

    
 

  Умение  найти значения P_k дает возможность отыскать и ряд основных характеристик СМО.  

  3. Основные характеристики  СМО 

  Значение P₀ определяет вероятность того, что все каналы обслуживания свободны (находятся в состоянии простоя).  

  Значение  P_k определяет вероятность того, что в системе (в очереди и на обслуживании) находятся k заявок. Если k не превышает числа каналов N, то все заявки находятся на обслуживании и очередь отсутствует; в противном случае все каналы заняты и k-N заявок находится в очереди.  

  Вероятность P_отк отказа в обслуживании определяется ситуацией занятости всех N каналов и всех m мест в очереди и равна P_N+m.  

  Среднее число занятых каналов N_зан определяется математическим ожиданием дискретной случайной величины:

   

  

 

  Среднее число свободных каналов

  

  

     Коэффициент простоя каналов

    

  Коэффициент занятости каналов 

    

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