Теория массового обслуживания

Оглавление
ВВЕДЕНИЕ	2
1.	ЗАДАЧА ТЕОРИИ МАССОВОГО ОБСЛУЖИВАНИЯ	4
1.2.Классификация систем массового обслуживания	5
2.	ВЫЯВЛЕНИЕ ОСНОВНЫХ ОСОБЕННОСТЕЙ, ВЗАИМОСВЯЗЕЙ И КОЛИЧЕСТВЕННЫХ ЗАКОНОМЕРНОСТЕЙ	8
3.	МНОГОКАНАЛЬНАЯ СМО С ОТКАЗАМИ	9
3.1 Разработка модели СМО	13
4. ПРАКТИЧЕСКАЯ ЧАСТЬ	15
4.1. Постановка задачи	15
4.2. Решение задачи	16
ЗАКЛЮЧЕНИЕ	27
СПИСОК ЛИТЕРАТУРЫ	29



    ВВЕДЕНИЕ

     Теория массового обслуживания – область прикладной математики, занимающаяся анализом процессов в системах производства, обслуживания, управления, в которых однородные события повторяются многократно, например, на предприятиях бытового обслуживания; в системах приема, переработки и передачи информации; автоматических линиях производства и др.
     Предметом теории массового обслуживания является установление зависимостей между характером потока заявок, числом каналов обслуживания, производительностью отдельного канала и эффективным обслуживанием с целью нахождения наилучших путей управления этими процессами.
     Под системой массового обслуживания (СМО) понимают динамическую систему, предназначенную для эффективного обслуживания потока заявок (требований на обслуживание) при ограничениях на ресурсы системы.
     Модели СМО удобны для описания отдельных подсистем современных вычислительных систем, таких как подсистема процессора - основная память, канал ввода-вывода и т. д. Вычислительная система в целом представляет собой совокупность взаимосвязанных подсистем, взаимодействие которых носит вероятностный характер. Заявка на решение некоторой задачи, поступающая в вычислительную систему, проходит последовательность этапов счета, обращения к внешним запоминающим устройствам и устройствам ввода-вывода. После выполнения некоторой последовательности таких этапов, число и продолжительность которых зависит от трудоемкости программы, заявка считается обслуженной и покидает вычислительную систему. Таким образом, вычислительную систему в целом можно представлять совокупностью СМО, каждая из которых отображает процесс функционирования отдельного устройства или группы однотипных устройств, входящих в состав системы.
     Совокупность взаимосвязанных СМО называется сетью массового обслуживания (стохастической сетью).
     Целью данного дипломного проекта является определение:
      параметров работы системы;
      оптимального числа инспекторов на посту при сохранении остальных условий задачи;
      оптимальных затрат на оборудование при неизменных остальных условиях задачи
      параметров работы системы при паре оптимальных параметров.
     Для начала мы рассмотрим основы теории СМО, затем перейдем к ознакомлению в подробном содержании к СМО с ожиданием и замкнутым СМО. Также в работу включена практическая часть, в которой мы подробно познакомимся с тем, как применить теорию на практике.
 
ЗАДАЧА ТЕОРИИ МАССОВОГО ОБСЛУЖИВАНИЯ
     
     Задача теории массового обслуживания – установить зависимость результирующих показателей работы системы массового обслуживания (вероятности того, что заявка будет обслужена; математического ожидания числа обслуженных заявок и т.д.), от входных показателей (количества каналов в системе, параметров входящего потока заявок и т.д.). Результирующими показателями или интересующими нас характеристиками СМО являются – показатели эффективности СМО, которые описывают, способна ли данная система справляться с потоком заявок.
     Системы массового обслуживания могут быть одноканальными или многоканальными.
     Заметим, что за последние годы область применения математических методов теории массового обслуживания непрерывно расширяется и все больше выходит за пределы задач, связанных с "обслуживающими организациями" в буквальном смысле слова. Как своеобразные системы массового обслуживания могут рассматриваться: электронные цифровые вычислительные машины; системы сбора и обработки информации; автоматизированные производственные цехи, поточные линии; транспортные системы; системы противовоздушной обороны и т. д.
     Задачи массового обслуживания условно делят на задачи анализа и задачи синтеза - оптимизации систем массового обслуживания. Первые предполагают определение основных параметров функционирования системы массового обслуживания при неизменных, наперед заданных исходных характеристиках: структура системы, дисциплина обслуживания, потоки требований и законы распределения времени на их обслуживание. Вторые направлены на поиск оптимальных параметров систем массового обслуживания.
     Оптимизационные модели широко используются в экономике и технике. Среди них задачи подбора сбалансированного рациона питания, оптимизации ассортимента продукции, транспортная задача и пр., и пр.
     Задача оптимизации – задача выбора из множества возможных вариантов наилучшего, оптимального. Оптимизация – от латинского слова «оптимус» - наилучший – поиск наилучшего, поиск наилучшего проектного изделия.
     Каждая задача оптимизации обязательно должна иметь три компонента:
      неизвестные (что ищем, то есть, план);
      ограничение на неизвестные (область поиска);
      целевая функция (цель, для которой ищем экстремум).
     Математическая модель, та которая определена с помощью математических формализмов. Математическая модель не является точной, а является идеализацией.
     Определение параметров состояния - задача моделирования. Определение переменных проектирования – задачи проектирования или задачи оптимизации.
     
1.2.Классификация систем массового обслуживания

    Систему массового обслуживания можно представить как совокупность последовательно связанных между собой входящих потоков требований на обслуживание (машин, самолетов, пользователей и т.д.), очередей, каналов обслуживания (станция техобслуживания, аэродром, ЭВМ и т.д.) и выходящих потоков требований после обслуживания.
    Системы массового обслуживания по наличию того или иного признака можно классифицировать таким образом:
    1. По характеру поступления требований - на системы с регулярным и случайным потоками поступления требований в систему.
    Случайный поток требований в систему подразделяется на стационарный и нестационарный:
    - если количество требований, поступающих в систему в единицу времени (интенсивность потока), постоянно или является заданной функцией времени, то мы имеем систему с регулярным потоком поступления, в противном случае - со случайным;
    — если параметры потока требований не зависят от расположения рассматриваемого интервала на оси времени, то поток требований - стационарный, в противном случае - нестационарный. Например, если число покупателей, приходящих в магазин, не зависит от времени суток, то поток требований (покупателей) - стационарный
    2. По количеству поступающих требований в момент времени — на системы с ординарным и неординарным потоками требований. Если вероятность поступления двух или более требований одновременно равна нулю или имеет столь малую величину, что ею можно пренебречь, то имеем систему с ординарным потоком требований. Например, поток требований - самолетов, поступающих на взлетно-посадочную полосу аэродрома (ВПП), - можно считать ординарным, так как вероятность поступления двух и более самолетов в канал обслуживания (ВПП) в одно и то же время очень мала и ею можно пренебречь.
    3. По связи между требованиями — на системы без последействия от поступивших требований и с последействием. Если вероятность поступления требований в систему в некоторый момент времени не зависит от того, сколько требований уже поступило, то есть не связана с предысторией изучаемого процесса, то мы имеем задачу без последействия, в противном случае - с последействием. Примером задачи с последействием может служить поток студентов, сдающих зачет преподавателю.
    4. По характеру поведения требования - в системе с отказами, с ограниченным и неограниченным ожиданием:
    - если вновь поступившее требование на обслуживание застает все каналы обслуживания уже занятыми и покидает систему, то имеем систему с отказами. Требование может выйти из системы и в том случае, когда очередь достигла определенных размеров. Если ракета противника появляется, когда все противоракетные установки заняты уничтожением (обслуживанием) других ракет, то она благополучно покидает данную область;
    - если поступившее требование застает все каналы обслуживания занятыми и становится в очередь, но находится в ней ограниченное время, после чего, не дождавшись обслуживания, покидает систему, то имеем систему с ограниченным ожиданием. Примером такого «нетерпеливого требования» может быть автосамосвал с раствором. Если время ожидания велико, то во избежание затвердения раствора он может быть разгружен в другом месте;
    - если поступившее требование, застав все каналы обслуживания занятыми, вынуждено ожидать своей очереди до тех пор, пока оно не будет обслужено, то имеем систему с ожиданием без ограничения. Пример: самолет, который находится на аэродроме до тех пор, пока не освободится взлетная полоса.
    5. По способу выбора требований на обслуживание - с приоритетом, по мере поступления, случайно, последний обслуживается первым. Иногда в таком случае говорят о дисциплине обслуживания:
    - если система массового обслуживания охватывает несколько категорий требований и по каким-либо соображениям необходим определенный подход к их отбору, то имеем систему с приоритетом. Так, при поступлении изделий на стройплощадку в первую очередь монтируются те, которые необходимы в данный момент;
    - если освободившийся канал обслуживает требование, поступившее в систему ранее других, то имеем систему с обслуживанием требований по мере их поступления. Это наиболее распространенный класс систем. Например, покупатель, подошедший первым к продавцу, обслуживается первым. Этот способ выбора требований на обслуживание применяется там, где в силу технических, технологических или организационных условий требования не могут опережать друг друга;
    - если требования из очереди в канал обслуживания поступают в случайном порядке, то имеем систему со случайным выбором требований на обслуживание. Пример: выбор слесарем-сантехником одной из нескольких заявок, поступивших от жильцов. Выбор здесь, как правило, определяется местоположением самого слесаря: он выбирает заявку из места, наиболее близко расположенного к нему, если никакие другие факторы не влияют на выбор;
    - последний обслуживается первым. Этот способ выбора требований на обслуживание используется в тех случаях, когда удобнее или экономнее брать на обслуживание требование, позже всех поступившее в систему. Так, при укладке строительных изделий в штабель удобнее брать из штабеля (очере ди) изделие, поступившее последним.
    6. По характеру обслуживания требований - на системы с детерминированным и случайным временем обслуживания. Если интервал времени между моментом поступления требования в канал обслуживания и моментом выхода требования из этого канала постоянен, то имеем систему с детерминированным временем обслуживания, в противном случае — со случайным.
    7. По числу каналов обслуживания — на одноканальные и многоканальные системы. Так, при монтаже дома может быть использован один подъемный кран (один канал обслуживания) или несколько (много каналов) для обслуживания прибывающих на стройку изделий.
    8. По количеству этапов обслуживания - на однофазные и многофазные системы. Если каналы обслуживания расположены последовательно и они неоднородны, так как выполняют различные операции, то имеем многофазную систему массового обслуживания. Примером такой системы может служить, например, обслуживание автомобилей на станции техобслуживания (мойка, ' диагностика и т.д.).
    9. По однородности требований, поступающих на обслуживание, - на системы с однородными и неоднородными потоками требований. Так, если под погрузку прибывают фургоны одной грузоподъемности, то такие требования называются однородными, в противном случае - неоднородными.
    10. По ограниченности потока требований - на замкнутые и разомкнутые системы. Если поток требований ограничен и требования, покинувшие систему, ^ через некоторое время в нее возвращаться, то имеем замкнутую систему, в противном случае - разомкнутую. Примером замкнутой системы может служить ремонтная бригада и обслуживаемое ею оборудование. Если изучены или заданы входящие потоки требований, механизм (число каналов обслуживания, продолжительность обслуживания и т.д.) и дисциплина обслуживания, то это дает основание для построения математической модели системы.
    Задачи массового обслуживания условно делят на задачи анализа и синтеза оптимизации систем массового обслуживания. Первые предполагают определение  основных параметров функционирования системы массового обслуживания при неизменных, наперед заданных исходных характеристиках: структуpa системы, дисциплина обслуживания, потоки требований и законы распределения времени на их обслуживание. Вторые Направлены на поиск оптимальных параметров систем массового обслуживания.
     Как мы уже рассмотрели, системы массового обслуживания делятся на типы (или классы) по ряду признаков. Первое деление: СМО с отказами и СМО с очередью. 
     В СМО с отказами заявка, поступившая в момент, когда все каналы заняты, получает отказ, покидает СМО и в дальнейшем процессе обслуживания не участвует. Примеры СМО с отказами встречаются в телефонии: заявка на разговор, пришедшая в момент, когда все каналы связи заняты, получает отказ и покидает СМО не обслуженной. В СМО с очередью заявка, пришедшая в момент, когда все каналы заняты, не уходит, а становится в очередь и ожидает возможности быть обслуженной. На практике чаще встречаются (и имеют большее значение) СМО с очередью; недаром теория массового обслуживания имеет второе название: «теория очередей».
     СМО с очередью подразделяются на разные виды, в зависимости от того, как организована очередь — ограничена она или не ограничена. Ограничения могут касаться как длины очереди, так и времени ожидания (так называемые «СМО с нетерпеливыми заявками»). При анализе СМО должна учитываться также и «дисциплина обслуживания» — заявки могут обслуживаться либо в порядке поступления (раньше пришла, раньше обслуживается), либо в случайном порядке. Нередко встречается так называемое обслуживание с приоритетом — некоторые заявки обслуживаются вне очереди. Приоритет может быть как абсолютным — когда заявка с более высоким приоритетом «вытесняет» из-под обслуживания заявку с низшим (например, пришедший в парикмахерскую клиент высокого ранга прогоняет с кресла обыкновенного клиента), так и относительным—когда начатое обслуживание доводится до конца, а заявка с более высоким приоритетом имеет лишь право на лучшее место в очереди.
     Существуют СМО с так называемым многофазовым обслуживанием, состоящим из нескольких последовательных этапов или «фаз» (например, покупатель, пришедший в магазин, должен сначала выбрать товар, затем оплатить его в кассе, затем получить на контроле).
     Кроме этих признаков, СМО делятся на два класса:
      «открытые»;
       «замкнутые». 
     В открытой СМО характеристики потока заявок не зависят от того, в каком состоянии — сама СМО (сколько каналов занято). В замкнутой СМО—зависят. Например, если один рабочий обслуживает группу станков, время от времени требующих наладки, то интенсивность потока «требований» со стороны станков зависит от того, сколько их уже неисправно и ждет наладки. Это — пример замкнутой СМО. Классификация СМО далеко не ограничивается приведенными их разновидностями, но мы ограничимся ими.
     Оптимизация работы СМО может производиться под разными углами зрения: с точки зрения организаторов (или владельцев) СМО или с точки зрения обслуживаемых клиентов. С первой точки зрения желательно «выжать все, что возможно» из СМО и добиться того, чтобы ее каналы были предельно загружены. С точки зрения клиентов желательно всемерное уменьшение очередей, которые зачастую становятся настоящим «бичом быта», приводя к бессмысленной трате сил и времени и, в конечном итоге, к понижению производительности труда. При решении задач оптимизации в теории массового обслуживания существенно необходим «системный подход», полное и комплексное рассмотрение всех последствий каждого решения. Например, с точки зрения клиентов СМО желательно увеличение числа каналов обслуживания; но ведь работу каждого канала надо оплачивать, что удорожает обслуживание. Построение математической модели позволяет решить оптимизационную задачу о разумном числе каналов с учетом всех «за» и «против». Поэтому мы не выделяем в задачах массового обслуживания какого-либо одного показателя эффективности, а сразу ставим эти задачи как многокритериальные.
     
 
ВЫЯВЛЕНИЕ ОСНОВНЫХ ОСОБЕННОСТЕЙ, ВЗАИМОСВЯЗЕЙ И КОЛИЧЕСТВЕННЫХ ЗАКОНОМЕРНОСТЕЙ
     
     Функционирование любой системы массового обслуживания можно представить через все возможные состояния ее и интенсивность перехода из одного состояния в другое. Основными параметрами функционирования СМО являются вероятности ее состояния, то есть возможности наличия n требований в системе - Рn.
     Важным параметром функционирования СМО является также среднее число требований, находящихся в системе Nsyst, то есть в очереди на обслуживание, а также средняя длина очереди Noch. Исходными параметрами, характеризующими систему массового обслуживания, являются: число каналов обслуживания - n; число требований - m; интенсивность поступления одного требования на обслуживание - ?, то есть число поступлений требований в единицу времени; интенсивность обслуживания требований - ?.
     Интенсивность поступления требования на обслуживание определяется как величина, обратная времени возвращения требования 1воз.
     Интенсивность обслуживания требований определяется как величина, обратная времени обслуживания одного требования - to6c.
   В задачах анализа СМО в качестве основных показателей функционирования системы могут быть использованы:

- вероятность простоя канала обслуживания P0;

- вероятность того, что в системе находится n требований - Pn;

- среднее число требований, находящихся в системе (сфере обслуживания) N_сист=?_(n=1)^???nP_n ?;

- среднее число требований, находящихся в очереди, N_оч=?_(n=N_k)^???(n-N_k ?)*P_n, где Nk - число каналов обслуживания;

- среднее время ожидания требований в очереди Tоч:

для разомкнутой системы   где  - интенсивность поступления потока требований в систему;

для замкнутой системы  где m – число требований, нуждающихся в обслуживании;

- среднее время ожидания требований в системе ;

- среднее число свободных каналов обслуживания 

- среднее число занятых каналов обслуживания 

 
среднее число заявок, находящихся на обслуживании в период 
 
 формула Литтла, где  - средняя интенсивность поступления требований,  - средняя продолжительность обслуживания одной заявки.
 
	Задачи анализа одноканальных систем массового обслуживания
 
Как видно из приведённой классификации СМО, имеется большое число разновидностей СМО. Ограничимся наиболее часто встречающимися СМО:

- детерминированной одноканальной;

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

(Пуассоново распределение – распределение случайной величены, при котором она может принимать дискретные значения из счётного множества 0, 1, 2, … с вероятностью

параметр распределения).

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

Рис. 5.1.1. Размеченный граф состояний одноканальной замкнутой системы массового обслуживания
    Первый прямоугольник с вероятностью Р0 определяет состояние системы массового обслуживания, при котором канал обслуживания простаивает из-за отсутствия требований в ней. Из этого положения система массового обслуживания может перейти с интенсивностью m? только в состояние Р1 ; тогда в системе появится одно требование, так как входной поток - ординарный. С интенсивностью ? система может перейти также из состояния Р1 в состояние Р0; когда в системе находилось одно требование, но оно было обслужено раньше, чем появилось новое. Из состояния Р1 система массового обслуживания может перейти с интенсивностью (m - 1) ? в состояние Р2; тогда в системе появятся два требования. С интенсивностью ? система может перейти также из состояния Р2 в состояние Р1; когда в системе находилось два требования, но одно из них было обслужено раньше, чем появилось новое, и т.д.
    Рассмотрим установившийся режим работы системы массового обслуживания, когда основные вероятностные характеристики ее постоянны во времени, например в течение часа. В этом случае интенсивности входных и выходных потоков для каждого состояния будут сбалансированы:
    P0 m?=P1 ?
    P1 (?+(m-1)?)= P0m ?+ P2 ?
    P2 (?+(m-2) ?) = P1(m-1) ? + P3 ?
    ………………………………
    Pn (?+(m-n) ?) = P n-1(m-(n-1)) ? + P n+1 ?
    …………………….
    Pm ?=Pm-1 ?
    Обозначим величину ? /m через ?, и назовем ее коэффициентом загрузки. Из первого уравнения можно найти значение Р1:
    P1 =Pm ?/ ?=P 0 m ?
    Из второго уравнения найдем значение Р2:
    P2=P1+P1(m-1)?/? –P0m ?/?
    Но первый член – Р1 = Р0 m?/?, следовательно, первый и третий сокращаются:
    Р2 = Р1 (m- 1) ?/ ?= Ро m(m - 1) ?2.
    Из третьего уравнения найдем значение Р3:
    Р3 = Р2 + Р2(m - 2) ?/ ? – Р1 (m - 1) ?/ ?
    Но первый член - Р2 = Р1 (m - 1) ?/ ?, следовательно, первый и третий сокращаются:
    Р3 = Р2(m - 2) ?/ ? = Р0 m (m - 1)(m - 2) ?3 и т.д.;
    Рn = Рn-1 (m - (n - 1)) ?/ ?= P0 m (m - 1)...(m - (n - 1)) ?n = P0 ?n (m!/(m-n)!
    Используя очевидное равенство ?Рn = 1, получим: 1 = PQ ??n m!/(m-n)! от n = 0 до m.
    Зная вероятность простоя канала обслуживания Р0, можно определить его фактическую производительность:
    Pf=(l-P0) ? G,
    где G, например, количество груза, помещенного за одно обслуживание в машину.
    Для установившегося режима работы системы средняя интенсивность поступления требований во входном потоке равна аналогичной характеристике выхода требований из канала обслуживания:
    (m-Nсист)? = (l-P0)?,
    где nсист - среднее число обслуживаемых требований, находящихся в системе. Из данного равенства можно легко найти среднее число требований (покупателей, рабочих, заданий, машин, неполадок), находящихся в системе nсист:
    Nсист = m-(l-P0)/?.
    Среднее же число требований (машин), находящихся в очереди, будет вычислено так:
    noч - nсист - (1 – Р0) = m - (1 - P0)(1/? + 1).
    Пусть задан комплект машин «экскаватор - автосамосвалы». Экскаватор погружает за один рабочий цикл ga = 1 т грунта. Грузоподъемность автосамосвала ga = 7 т. Число машин, обслуживающих экскаватор, m = 5. Время рабочего цикла экскаватора составляет tрц= 18 с, а время обращения автосамосвала tобр = 10 мин. Тогда время погрузки одного грузовика составит:
    tпог=
    Интенсивность погрузки автосамосвала экскаватором составит
    29 погрузок в час.
    Интенсивность же поступления автосамосвала на погрузку составит
    6 обращении в час.
    t-воз 1"
    Коэффициент ?=?/? будет равен ? = 0,207. Вероятность простоя экскаватора в этом случае составит:
    Таким образом, фактическая производительность данного комплекта машин будет на 27,1% ниже технической.
    Вероятности наличия n машин в системе:
    Р1= Р0 m ?= 0,281
    Р2= Р1 (m - 1) ?= 0,233
    Р3=Р2(m-2) ? = 0,144
    Р4 = Р3 (m - 3) ? = 0,06
    Р5=Р4(m-4) ? = 0,012 ;,
    Фактическая производительность комплекта машин:
    Pf - (1 - Р„) ? G = (1 - 0,271) X 29 X 7 = 147,947 т/час.
    Среднее число машин, находящихся в системе:
    Nсист = m-(l-P0)/ ? = 1,477.
    Среднее число машин, находящихся в очереди:
       No4 - NCИCT - (1 - Р0) = m - (1 - Р0) (1 / ? + 1) = 0,749.



 
МНОГОКАНАЛЬНАЯ СМО С ОТКАЗАМИ
     
     Рассмотрим n-канальную СМО с отказами. Будем нумеровать состояния системы по числу занятых каналов (или, что в данном случае то же, по числу заявок, связанных с системой). Состояния будут:
      S0 - все каналы свободны,
      S1 - занят ровно один канал, остальные свободны,
      Sk - заняты ровно k каналов, остальные свободны, 
      Sn - заняты все n каналов.
     Граф состояний СМО представлен на рис.1. Разместим граф, т.е. проставим у стрелок интенсивности соответствующих потоков событий. По стрелкам слева направо систему переводит один и тот же поток - поток заявок с интенсивностью ?.
     
     Рис.1
     Если система находится в состоянии Sk (занято k каналов) и пришла новая заявка, система переходит (перескакивает) в состояние Sk+1
     Определим интенсивности потоков событий, переводящих систему по стрелкам справа налево.
     Пусть система находиться в состоянии S1 (занят один канал). Тогда, как только закончиться обслуживание заявки, занимающей этот канал, система перейдет в S0; значит, поток событий, переводящий систему по стрелке S1 ? S0, Имеет интенсивность µ. Очевидно, если обслуживанием занято два канала, а не один, поток обслуживаний, переводящий систему по стрелке S2 ? S1, будет вдвое интенсивнее (2µ); если занято k каналов - в k раз интенсивнее (kµ). Проставим соответствующие интенсивности у стрелок, ведущих справа налево.
     Из рис.1 видно, что процесс, протекающий в СМО, представляет собой частный случай процесса гибели и размножения.
     Пользуясь общими правилами, можно составить уравнения Колмогорова для вероятностей состояний:
     (1)
     Уравнения (1) называются уравнениями Эрланга. Естественными начальными условиями для их решения являются:
     p0(0)=1; p1(0)=p2(0)=...=pn(0)=0 (в начальный момент система свободна).
     Интегрирование системы уравнений (1) в аналитическом виде довольно сложно; на практике такие системы дифференциальных уравнений обычно решаются численно, на ЭВМ. Такое решение дает нам все вероятности состояний p0(t), p1(t),..., pn(t) как функции времени.
     Естественно, нас больше всего будут интересовать предельные вероятности состояний p0 , p1 ,..., pk ,..., pn, характеризующие установившийся режим работы СМО. Для нахождения предельных вероятностей воспользуемся уже готовым решением задачи, полученным для схемы гибели и размножения. Согласно этому решению,
     (2)
     В этих формулах интенсивность потока заявок ? и интенсивность потока обслуживаний (для одного канала) µ не фигурируют по отдельности, а входят только своим отношением ? /µ. Обозначим это отношение ? /µ=р и будем называть величину р "приведенной интенсивностью" потока заявок. Физический смысл ее таков: величина р представляет собой среднее число заявок, приходящих в СМО за среднее время обслуживания одной заявки.
     С учетом этого обозначения, формулы (2) примут вид:
     (3)
     Формулы (3) называются формулами Эрланга. Они выражают предельные вероятности всех состояний системы в зависимости от параметров ?, µ и n (? - интенсивность потока заявок, µ - интенсивность обслуживания, n - число каналов СМО).
     Зная все вероятности состояний p0 , p1 ,..., pk ,..., pn, можно найти характеристики эффективности СМО: относительную пропускную способность - q, абсолютную пропускную способность - A и вероятность отказа - Pотк.
     Действительно, заявка получает отказ, если приходит в момент, когда все n каналов заняты. Вероятность этого равна:
        (4)
     Вероятность того, что заявка будет принята к обслуживанию (она же относительная пропускная способность q) дополняет Pотк до единицы:
     	(5)
     Абсолютная пропускная способность:
     	(6)
     Одной из важных характеристик СМО с отказами является среднее число занятых каналов (в данном случае оно совпадает со средним числом заявок, находящихся в системе). Обозначим это среднее число k-.
     Величину k- можно вычислить непосредственно через вероятности p0 , p1,..., pnпо формуле:
     	(7)
как математическое ожидание дискретной случайной величины, принимающей значения 0,1,...,n с вероятностями p0 , p1,..., pn. однако значительно проще выразить среднее число занятых каналов через абсолютную пропускную способность А, которую мы уже знаем. Действительно, А есть не что иное, как среднее число заявок, обслуживаемых в единицу времени; один занятый канал обслуживает в среднем за единицу времени m заявок; среднее число занятых каналов получится делением А на m:
     
     или, переходя к обозначению ?/µ = p,
     		(8)
     
     
3.1 Разработка модели СМО
     
     Цель работы заключается в разработке модели, имитирующей работу поста ГИБДД. Такая задача была поставлена для того, чтобы выявить эффективность работы системы обслуживания поста ГИБДД для дальнейшей ее оптимизации.
     В данном отчете предлагается к использованию одна из методик, которая предполагает разделение процесса моделирования на две части. Первая часть – обеспечивает нахождение параметров работы исходной задачи. Вторая часть – производится оптимизация определенных параметров при неизменных остальных параметров в таблицах MS Excel. Строятся графики функций. Производится их анализ и делаются выводы.
     Рассмотрим подробнее математическую модель работы поста ГИБДД как системы массового обслуживания. Для решения задачи было принято допущение, что очередь клиентов ограничена, и, следовательно, данная модель является СМО с ограниченной очередью, где n – количество каналов обслуживания. Также принимаем допущение, что все потоки событий (случайные события) в системе являются Марковскими. Напомним, что случайный процесс, протекающий в системе, называется Марковским, если для любого момента времени t0 вероятностные характеристики процесса в будущем зависят только от его состояния в данный момент t0 и не зависят от того, когда и как система пришла в это состояние.
     Поток нарушителей в систему поступают с интенсивностью . 
     Тогда 
     Вероятность отказа: .
     Относительная пропускная способность: .
     Абсолютная пропускная способность: .
     Среднее число заявок, связанных с системой: .
     Средняя длина очереди: .
     Количество, ожидающих в очереди: .
     Время в очереди: .
     Время в системе: .
     В результате планируется получить наиболее приближенную к реальности модель работы поста ГИБДД. Практическая значимость данной работы очевидна: модель позволяет путем экспериментов выявить наиболее оптимальное распределение ресурсов для повышения эффективности его работы. Также можно предположить применение данной модели на реальном объекте.



4. ПРАКТИЧЕСКАЯ ЧАСТЬ

     4.1. Постановка задачи

     На шоссе проверяет скорость пост ГИБДД. На посту в течении дня работает 5 инспекторов. Рабочий день инспектора равен 10 часам. Режим работы – раз в трое суток. Затраты на одного инспектора равны 35000рублей в месяц (зарплата, налоги, спецобмундирование и др.). Инспектор оформляет протокол примерно за 12 минут. В течение часа скоростной режим нарушают в среднем 35 водителей. Инспекторы останавливают машину, если ожидают оформления не более четырех машин. Средний размер штрафа равен 250 рублям.
     Определить параметры работы системы. Найти процент оштрафованных нарушителей. Каково среднее время, которое тратит водитель в ожидании оформления протокола? Сколько, в среднем, машин ожидает оформления? Какова средняя сумма от штрафов за месяц? Каковы месячные затраты на пост ДПС? Определить «прибыль» поста за месяц. (Ознакомительная задача).
     Определить оптимальное (с точки зрения прибыли) число инспекторов на посту при сохранении остальных условий задачи.
     Имеется возможность арендовать оборудование, позволяющее ускорить процесс оформления протокола. Стоимость аренды оборудования для одного инспектора линейно зависит от его эффективности и изображения на графике. Максимально возможная скорость – 10 протоколов в час. Определить оптимальные затраты на оборудование при неизменных остальных условиях задачи (число инспекторов равно пяти) и при числе инспекторов, полученных в п. 2. определить параметры работы системы при этих затратах.
     
     Рис. 2.
     Провести оптимизацию по двум параметрам: числу инспекторов и затратам на ускоряющее оборудование. Определить параметры работы системы при паре оптимальных параметров. Сравнить с оптимизацией по каждому отдельному параметру.
     

     4.2. Решение задачи

     Формализуем задачу:
     Данную задачу можно отнести к задачам СМО с ограниченной очередью. Максимальная длина очереди равна m=5. Интенсивность потока требований (в качестве которого выступает поток нарушителей) равна водителей в час. Исходно имеется пять каналов обслуживания (пять инспекторов находятся на посту единовременно): n=5. Среднее время обслуживания одним каналом (среднее время, которое тратит инспектор на один автомобиль) равно , тогда  авт./мин  авт./час.
     Найдем параметры работы исходной задачи.
     
     
     
     
     
     30,4 % нарушителей не будет оштрафовано.
      
     Процент оштрафованных нарушителей равен 69,6 %.
     
     В среднем 24,35 автомобилей будет оштрафовано в час.
     
     Почти все инспекторы (4,8 из 5)заняты.
     Найдем среднюю длину очереди:
     
     
     В среднем ожидает оформления 3 машины.
     
     Время в очереди и системе:	
      часа = 7,2 мин.
     
     Таким образом, среднее время, которое тратит водитель в ожидании оформления протокола, равно 7,2 мин.
     Найдем среднюю сумму штрафов за месяц . Так как авт./час., сумма штрафа в среднем равна 250 руб., в месяце 30 дней по 10 рабочих часов, то:
      тыс.руб.
     Так как затраты на одного инспектора равны f=35000 руб./мес., а инспекторов по трижды по 5 человек, то месячные затраты на пост ДПС равны:
     руб. = 525 тыс. руб.
    .......................