Федеральное государственное образовательное  учреждение

среднего  профессионального образования 

«Омский промышленно-экономический колледж» 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Курсовая  работа

по  дисциплине «Математические  методы»

на  тему «Основные понятия теории очередей» 
 
 
 
 

Выполнил:

Плешивых  С.А.        

Руководитель 

Белгородцева  Н.А.

Оценка:________________

Дата  защиты:___________ 
 
 
 
 

2010

Содержание 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Введение

 

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

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

Обзор литературы

1.Системы массового обслуживания

 

     Теория  массового обслуживания опирается  на теорию вероятностей и математическую статистику.

         На первичное развитие теории  массового обслуживания оказали  особое влияние работы датского  ученого А.К. Эрланга (1878-1929).

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

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

     Системы массового обслуживания могут быть одноканальными или многоканальными.

     Механизм  обслуживания определяется характеристиками самой процедуры обслуживания и  структурой обслуживающей системы. К характеристикам процедуры  обслуживания относятся: продолжительность процедуры обслуживания и количество требований, удовлетворяемых в результате выполнения каждой такой процедуры. Для аналитического описания характеристик процедуры обслуживания оперируют понятием «вероятностное распределение времени обслуживания требований».

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

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

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

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

     1.вероятностным распределением моментов поступлений заявок на обслуживание (единичных или групповых);

     2.вероятностным распределением времени продолжительности обслуживания;

     3.конфигурацией обслуживающей системы (параллельное, последовательное или параллельно-последовательное обслуживание);

     4.количеством и производительностью обслуживающих каналов;

     5.дисциплиной очереди;

     6.мощностью источника требований.

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

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

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

     3.относительная и абсолютная пропускная способность системы;

     4.средний процент заявок, получивших отказ в обслуживании;

     5.среднее время ожидания в очереди;

     6.средняя длина очереди;

     7.средний доход от функционирования системы в единицу времени и т.п. 

2.Системы массового обслуживания с отказами

2.1.Одноканальная СМО с отказами

 

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

При этом система  массового обслуживания состоит  только из одного канала (n = 1) и на нее  поступает пуассоновский поток заявок с интенсивностью λ , зависящей, в общем случае, от времени: λ= λ(t)

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

ƒ(t)=µe^-µt (t>0)

Из этого следует, что «поток обслуживания» — простейший, с интенсивностью λ. Чтобы представить себе этот поток, вообразим один непрерывно занятый канал, который будет выдавать обслуженные заявки потоком с интенсивностью µ.

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

Пример. Пусть одноканальная СМО с отказами представляет собой один пост ежедневного обслуживания для мойки автомобилей. Заявка — автомобиль, прибывший в момент, когда пост занят, — получает отказ в обслуживании. Интенсивность потока автомобилей λ 1,0 (автомобиль в час). Средняя продолжительность обслуживания — t_об=1,8 часа.

     Требуется  определить в установившемся  режиме предельные значения:

     относительной  пропускной способности q;

     абсолютной  пропускной способности А;

     вероятности отказа Р_отк;

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

     Решение

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

Вычислим относительную пропускную способность:

q =µ/(λ+ µ)=0,555/(1+0,555)=0,356

Величина q означает, что в установившемся режиме система  будет обслуживать примерно 35% прибывающих  на пост автомобилей.

     Абсолютную  пропускную способность определим  по формуле: А=λ×q=1×0,356=0,356.

     Это  означает, что система способна  осуществить в среднем 0,356 обслуживания  автомобилей в час.

     Вероятность  отказа:

     Ротк=1-q=1-0,356=0,644.

     Это  означает, что около 65% прибывших  автомобилей на пост ЕО получат  отказ в обслуживании.

     Определим  номинальную пропускную способность  системы:

А_ном = 1/t_об =1/1,8=0,555 автомобилей в час

Оказывается, что  А_ном в 0,555/0,356≈1,5 раза  больше, чем фактическая пропускная способность, вычисленная с учетом случайного характера потока заявок и времени обслуживания.

2.2.Многоканальная СМО с отказами

 

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

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

     Туристические фирмы по продаже путевок имеют  два, три, четыре и более каналов, как, например, фирма Express-Line.

     Рассмотрим  многоканальную СМО с отказами в  обслуживании на рис. 3.2, на вход которой  поступает пуассоновский поток  заявок с интенсивностью λ.

     

     Поток обслуживания в каждом канале имеет интенсивность μ. По числу заявок СМО определяются ее состояния S_k, представленные в виде размеченного графа:

     S₀ – все каналы свободны k=0,

     S₁ – занят только один канал, k=1,

     S₂ – заняты только два канала, k=2,

     S_k – заняты k каналов,

     S_n – заняты все n каналов, k= n.

     Состояния многоканальной СМО меняются скачкообразно в случайные моменты времени. Переход из одного состояния, например S₀ в S₁, происходит под воздействием входного потока заявок с интенсивностью λ, а обратно – под воздействием потока обслуживания заявок с интенсивностью μ. Для перехода системы из состояния S_k в S_k-1 безразлично, какой именно из каналов освободиться, поэтому поток событий, переводящий СМО, имеет интенсивность kμ, следовательно, поток событий, переводящий систему из S_n в S_n-1, имеет интенсивность nμ. Так формулируется классическая задача Эрланга, названная по имени датского инженера – математика- основателя теории массового обслуживания.

<

p align="justify">     Случайный процесс, протекающий в СМО, представляет собой частный случай процесса «рождения- гибели» и описывается системой дифференциальных уравнений Эрланга, которые позволяют получить выражения для предельных вероятностей состояния рассматриваемой системы, называемые формулами Эрланга:

     

     Вычислив  все вероятности состояний n – канальной СМО с отказами р₀ , р₁, р₂, …,р_k,…, р_n, можно найти характеристики системы обслуживания.

     Вероятность отказа в обслуживании определяется вероятностью того, что поступившая заявка на обслуживание найдет все n каналов занятыми, система будет находиться в состоянии S_n:

       k=n.

     В системах с отказами события отказа и обслуживания составляют полную группу событий, поэтому 

     Р_отк+Р_обс=1

     На  этом основании относительная пропускная способность определяется по формуле

     Q = P_обс= 1-Р_отк=1-Р_n

     Абсолютную  пропускную способность СМО можно  определить по формуле 

     А=λ*Р_обс

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

     

     Пример. Пусть n-канальная СМО представляет собой вычислительный центр (ВЦ) с  тремя (n=3) взаимозаменяемыми ПЭВМ для  решения поступающих задач. Поток  задач, поступающих на ВЦ, имеет интенсивность λ=1 задача в час. Средняя продолжительность обслуживания tоб=1,8 час.

          Требуется вычислить значения:

          - вероятности числа занятых каналов  ВЦ;

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

          - относительной пропускной способности ВЦ;

          - абсолютной пропускной способности  ВЦ;

          - среднего числа занятых ПЭВМ  на ВЦ.

          Определите, сколько дополнительно  надо приобрести ПЭВМ, чтобы увеличить  пропускную способность ВЦ в  2 раза.

     Решение.

          Определим параметр μ потока обслуживаний:

     

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

     

     Предельные  вероятности состояний найдем по формулам Эрланга:

        

     Вероятность отказа в обслуживании заявки

     Р_отк = Р₃ = 0,18

     Относительная пропускная способность ВЦ

     

     Абсолютная  пропускная способность ВЦ:

     

     Среднее число занятых каналов – ПЭВМ

     

     Таким образом, при установившемся режиме работы СМО в среднем будет  занято 1,5 компьютера из трех – остальные  полтора будут простаивать. Работу рассмотренного ВЦ вряд ли можно считать  удовлетворительной, так как центр не обслуживает заявки в среднем в 18% случаев (Р3= 0,180). Очевидно, что пропускную способность ВЦ при данных λ и μ можно увеличить только за счет увеличения числа ПЭВМ.

       Определим, сколько нужно использовать ПЭВМ, чтобы сократить число не обслуженных заявок, поступающих на ВЦ, в 10 раз, т.е. чтобы вероятность отказа в решении задач не превосходила 0,0180. Для этого используем формулу вероятности отказа:

     

     Составим  следующую таблицу: 

 

     Анализируя  данные таблицы, следует отметить, что  расширение числа каналов ВЦ при  данных значениях λ и μ до 6 единиц ПЭВМ позволит обеспечить удовлетворение заявок на решение задач на 99,22%, так  как при n = 6 вероятность отказа в обслуживании (Ротк) составляет 0,0078.

3.Системы массового обслуживания с ожиданием

3.1.Одноканальная СМО с ожиданием и ограниченной очередью

Система массового обслуживания имеет один канал. Входящий поток заявок на обслуживание поток имеет интенсивность λ. Интенсивность потока обслуживания равна μ (т. е. в среднем непрерывно занятый канал будет выдавать μ обслуженных заявок). Длительность обслуживания — случайная величина, подчиненная показательному закону распределения. Заявка, поступившая в момент, когда канал занят, становится в очередь и ожидает обслуживания.

     Рассмотрим систему с ограниченной  очередью. Предположим, что независимо оттого, сколько требований поступает на вход обслуживающей системы, данная система (очередь + обслуживаемые клиенты) не может вместить более N-требований (заявок), из которых одна обслуживается, а (N-1) ожидают, Клиенты, не попавшие в ожидание, вынуждены обслуживаться в другом месте и такие заявки теряются. Наконец, источник, порождающий заявки на обслуживание, имеет неограниченную (бесконечно большую) емкость.

Обозначим  P_n - вероятность того, что в системе находится n заявок. Эта величина вычисляется по формуле:

Здесь P=λ/µ - приведенная интенсивность потока.  Тогда вероятность того, что канал обслуживания свободен и в системе нет ни одного клиента, равна:

абсолютная  пропускная способность:

     А=q∙λ;

Рассмотрим  пример одноканальной СМО с ожиданием: 

Специализированный  пост диагностики представляет собой  одноканальную СМО. Число стоянок  для автомобилей, ожидающих проведения диагностики, ограниченно и равно 3, то есть (N— 1)=3. Если все стоянки заняты, т. е. в очереди уже находится три автомобиля, то очередной автомобиль, прибывший на диагностику, в очередь на обслуживание не становится. Поток автомобилей, прибывающих на диагностику имеет интенсивность λ=0,85 (автомобиля в час). Время диагностики автомобиля распределено по показательному закону и в среднем равно t_oб =1,05 час.

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

     Решение

     Интенсивность потока обслуживаний  автомобилей:

µ=1/t_об =1/1,05=0,952

Приведенная интенсивность потока автомобилей  определяется как отношение интенсивностей λ и μ, т.е.

    P=λ/ µ=0,85/0,952=0,893

Вычислим вероятности нахождения P заявок в системе:

P1=r∙P0=0,893∙0,248=0,221;

     P2=r2∙P0=0,8932∙0,248=0,198;

     P3=r3∙P0=0,8933∙0,248=0,177;

     P4=r4∙P0=0,8934∙0,248=0,158.

Вероятность отказа в обслуживании автомобиля:

     Pотк=Р4=r4∙P0≈0,158.

     Относительная пропускная способность поста диагностики:

     q=1–Pотк=1-0,158=0,842.

     Абсолютная пропускная способность  поста диагностики 

     А=λ∙q=0,85∙0,842=0,716 (автомобиля в час).

     Среднее число автомобилей, находящихся  на обслуживании и в очереди (т.е. в системе массового обслуживания):

Среднее время пребывания автомобиля в системе:

часа.

Средняя продолжительность пребывания заявки в очереди на обслуживание:

     Wq=Ws-1/μ=2,473-1/0,952=1,423 часа.

     Среднее число заявок в очереди  (длина очереди):

     Lq=λ∙(1-PN)∙Wq=0,85∙(1-0,158)∙1,423=1,02.

     Работу рассмотренного поста  диагностики можно считать удовлетворительной, так как пост диагностики не  обнаруживает автомобили в среднем  в 15,8% случаев (Ротк=0,158).

3.2.Многоканальная СМО с ожиданием

Рассмотрим многоканальную систему массового обслуживания с ожиданием. Процесс массового  обслуживания при этом характеризуется  следующим: входной и выходной потоки имеют интенсивности λ и μ соответственно, параллельно обслуживаться могут не более С клиентов, то есть система имеет С каналов обслуживания. Средняя продолжительность обслуживания одного клиента равна  1/µ

Вероятности того, что в системе находятся P заявок (С обслуживаются, остальные ожидают в очереди) равна:

Где

Решение будет действительным, если выполняется следующее условие:

Остальные вероятностные характеристики функционирования в стационарном режиме многоканальной СМО с ожиданием и неограниченной очередью определяется по следующим  формулам:

     среднее число клиентов в очереди на обслуживание

среднее число  находящихся в системе клиентов (заявок на обслуживание и в очереди)

     Ls=Lq+ρ;

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

средняя продолжительность  пребывания клиента в системе

Рассмотрим пример многоканальной системы массового обслуживания с ожиданием.

Пример. Механическая мастерская завода с тремя постами (каналами) выполняет ремонт малой  механизации. Поток неисправных  механизмов, прибывающих в мастерскую,  - пуассоновский и имеет интенсивность λ=2,5 механизма в сутки, среднее время ремонта одного механизма распределено по показательному закону и равно tоб=0,5 сут. Предположим, что другой мастерской на заводе нет, и, значит, очередь механизмов перед мастерской может расти практически неограниченно.

     Требуется  вычислить следующие предельные  значения вероятностных характеристик  системы:

     - вероятность состояний системы;

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

     - среднее число находящихся в  системе заявок;

     - среднюю продолжительность пребывания  заявки в очереди;

     - среднюю продолжительность пребывания  заявки в системе.

Решение

     Определим  параметр потока обслуживаний

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

     ρ=λ/μ=2,5/2,0=1,25,

    при этом λ/μ ∙с=2,5/2∙3=0,41<1.

     Поскольку  λ/μ∙с<1, то очередь не растет  безгранично и в системе наступает  предельный стационарный режим  работы.

     Вычислим  вероятности состояний системы: