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

Содержание

Введение 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_зан определяется математическим ожиданием дискретной случайной величины:

   

  

 

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

  

  

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

    

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

    

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

    

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

  Средняя длина очереди

  

 
 
 

  Cреднее число заявок, находящихся в системе, складывается из средних значений занятости каналов и длины очереди

    

  Среднее время пребывания заявки в очереди  равно 

    

  Общее время  пребывания заявки в очереди будет  складываться из T_очер и среднего времени обслуживания

    

  Полученные  характеристики дают возможность анализа  замкнутых и разомкнутых систем с отказами (=0), с очередью или с ожиданием при простейшем входном потоке и однотипных параллельных каналах обслуживания с показательным законом длительности обслуживания (в частности, с фиксированной длительностью).  

  4. Примеры систем  с ограниченной  очередью 

  Пример 1. Пусть на аэродром самолеты прибывают  с интенсивностью 27 самолетов в  час, время приземления составляет 2 минуты, допускается нахождение над  аэродромом не более  = 10 самолетов. Нужно определить число N посадочных полос, гарантирующее вероятность отказа, не превышающую 0.05, и среднее время ожидания, не превышающее 5 минут.  

  Здесь =27, = 30, R= / = 0.9.  

  Отыскиваем  вероятность простоя диспетчеров  службы посадки (19):

  

  Вероятность отказа в посадке равна 

  

 

  Среднее время ожидания в воздухе согласно (28) и (26)

  

   где 

  

   Выполняя  арифметические действия при  N=1, обнаруживаем, что 

  

   и что  одной посадочной полосы при  указанных условиях вполне достаточно.  

  Пример 2. Пусть имеются станки, которые  могут выходить из строя с частотой в среднем 2 раза за смену. Продолжительность  ремонта одним оператором составляет около трех часов (оператор одновременно может ремонтировать лишь один станок и не переходит к другому, не отремонтировав предыдущий). Хотелось бы определить число  операторов, при котором потери от простоя станков и оплаты лишнего  числа операторов были бы минимальны.  

  Такую замкнутую  систему можно представить системой с N каналами (операторами) и очередью с m местами ожидания (совпадает с  числом станков). Если известны потери С_п от простоя станка в течение часа и оплата Ср часа работы оператора, то при семичасовой смене задача сводится к нахождению значения N , которое минимизировало бы значение

  

   где  T_очер определяется (26) и (28) при =2/7, =1/3, R= / =6/7.  

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

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

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

  Можно показать, что и в случае случайного выбора на обслуживание полученные выше оценки не претерпят изменения, но их дисперсия (разброс относительно ожидаемой величины) возрастет. Очевидно, что среднее время сидения в очереди не изменится от того, что кто-то пройдет без очереди, но для отдельных клиентов время ожидания увеличится. Так отношение дисперсий времени ожидания в неупорядоченной и упорядоченной очереди имеет порядок (2+R)/(2-R), где R= / (мы обычно предпочитаем систему с жесткой дисциплиной обслуживания из-за предсказуемости ее поведения и всякое "возмущение" в ее работе отрицательно действует на нашу психику).  

  Существует  множество систем, в которых присутствует N>1 входных потоков с различной  интенсивностью _i(i = 1,..,N), время обслуживания заявок которых распределено по показательному закону с параметрами _i. Здесь при условии пуассоновости входных потоков можно считать, что суммарный поток будет пуассоновским с интенсивностью  функция распределения времени обслуживания заявок суммарного потока в одноканальной системе

  

   

  среднее время ожидания определяется формулой Полачека-Хинчина:

  

   которая для данного случая дает и в случае стационарности режима (R_{N < 1})

  

 

  Определенный  интерес представляют системы, где  каждому входному потоку сопоставлено целое число k - показатель приоритета потока (наивысший приоритет определяется k=1).  

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

  Можно показать, что поскольку время ожидания заявки с приоритетом k складывается из времени завершения обработки требования, вошедшего в канал, времени обслуживания ранее поступивших требований приоритета от 1 до k-1 и ранее поступивших требований с приоритетом k, то его среднее значение равно

  

 

  На этой основе можно определить среднюю  длину очереди заявок k -го приоритета L_k = _kW_k и среднее число таких заявок в системе L_k+R_k. Показано, что введение приоритетов улучшает функционирование системы, если более высокое преимущество присваивается заявкам с меньшей длительностью обслуживания. Если учитывать стоимостные характеристики, то более высокое преимущество предоставляется заявкам с большим значением С_{k k}, где С_k - средняя стоимость ожидания.

  

 

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

  

 

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

  где - издержки на ожидание заявки k -го приоритета в единицу времени, более высокий приоритет давать заявкам с наибольшим значением . 

  Исключительно сложно установить разумные приоритеты в случае многофазных систем, где  заявка проходит обслуживание в нескольких последовательных подсистемах. Здесь относительно простые выводы удается сделать лишь для случая двух подсистем, и для получения выводов для более сложных систем приходится прибегать к моделированию.  

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

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

  Суть математического моделирования системы заключается в следующем.  

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

  Очевидно, что ни о каком ручном моделировании  не может быть речи (объем работы здесь слишком велик для нормального  индивида). Здесь приходится использовать компьютер с встроенным или программным  датчиком псевдослучайных чисел  с равномерным законом распределения  в интервале от 0 до 1. Псевдослучайные  числа получаются по какому-то алгоритму, но в совокупности подчиняются всем законам проверки на случайность (мы не останавливаемся на методах их получения, так как есть отличные программные датчики во всех системах программирования).  

  В процессе моделирования возникает необходимость  генерации случайных чисел с  законом распределения, отличным от вышеуказанного.  

  Пусть R - случайные числа с равномерным  законом распределения в [0,1] и X - создаваемые случайные числа  с плотностью распределения p(X). Между  ними можно установить соотношение  
 

  Для равномерного распределения в [a,b] c очевидностью X=a+(b-a)R. Получение дискретных случайных чисел сводится к поиску наименьшего значения X, при котором

  

 

  Если взятие интеграла и представление X через R составит затруднение, можно воспользоваться  методом Неймана. Здесь при неограниченности области значений X усекаем ее до некоторого интервала [a,b]; например, для нормального распределения концы интервала берем отстоящими от среднего на 3-4 стандартных отклонения. Затем генерируется пара случайных чисел R₁ и R₂; если то берем X=a+(b-a)R₂ и в противном случае берем следующую пару случайных чисел.  

  Таким путем  мы можем моделировать интервалы  времени между заявками входного потока, продолжительность обслуживания заявки, вероятность выхода канала из строя и т.п.  

  Вопрос  о числе N отдельных реализаций системы  решается на основе закона больших чисел и вывода о том, что погрешность оценок имеет порядок

  

 

  Существуют многочисленные примеры успешного моделирования вполне реальных. 

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

  Заключение 

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

  Соответственно, появилось достаточно много компьютерных разработок, позволяющих пользователю, не слишком искушенному в области  математики и не умеющему писать программы  даже на уровне обычных алгоритмических  языков, успешно решать задачи исследования операций. Например, в популярной среде  электронных таблиц Excel предусмотрена стандартная процедура "Поиск решения", позволяющая достаточно просто записать ограничения на значения переменных (ячеек) и потребовать найти сочетание этих значений так, чтобы содержимое т.н. целевой ячейки приняло максимальное, минимальное или конкретное значение. Для реализации такого поиска можно выбрать итерационный подход (модифицированный метод Ньютона или метод сопряженных градиентов) и задать начальные приближения для искомых переменных.