Введение в теорию массового обслуживания. Пуассоновский поток событий. Обслуживание с ожиданием

Министерство образования  и науки Российской Федерации

Федеральное агентство по образованию

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

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

«Поволжская государственная  социально – гуманитарная академия»

Факультет начального образования

 

 

 

 

 

 

 

Реферат

 «Введение в теорию массового обслуживания. Пуассоновский поток событий. Обслуживание с ожиданием»

 

 

 

 

Выполнила:

студентка  51 группы

5 курса очной формы  обучения

Специальности «Педагогика  и методика

начального образования»

Казанцева Е.Ю.

 

 

 

 

 

 

 

 

 

 

 

 

 

Самара 2012

Содержание

Введение…………………………………………………………………………...31.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

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

 В реферате мы будем использовать книгу «Введение в теорию массового обслуживания» Б.В. Гнеденко и  И.Н. Коваленко, как основной источник информации. Настоящая книга посвящена строгому изложению математических основ теории массового обслуживания и используемых в ней аналитических и численных методов. Большое внимание уделено вероятностной интерпретации результатов и эргодическим соображениям, развивающим интуицию исследователя. Приведена созданная А.Я. Хинчиным теория потоков однородных событий, теория систем обслуживания в простейших предпосылках, теория однолинейных систем, в том числе приоритетных, основанная на полумарковских процессах, а также теория многолинейных систем, в основу изучения которых положены многомерные марковские процессы. Даны принципы статистического моделирования систем.

Авторы книги повествует о том, что практические требования телефонного дела, физики и рациональной организации массового обслуживания (билетные кассы, магазины, автоматы и пр.) выдвинули в начале XX столетия ряд интересных математических задач нового типа. Первоначально эти задачи касались преимущественно вопросов обслуживания абонентов телефонной станции, расчета запасов магазинов для бесперебойного снабжения покупателей, а также установления наиболее рационального числа продавцов и касс в торговых предприятиях. На первичное развитие этой теории особое влияние оказали работы известного датского ученого А.К.Эрланга (1878 – 1929) – многолетнего сотрудника Копенгагенской телефонной компании. Основные его исследования в этой области относятся к 1908 – 1922 гг. С того времени интерес к проблемам, выдвинутым Эрлангом, необычайно возрос. В результате значительно увеличилось число математиков и инженеров, а также экономистов, интересующихся и разрабатывающих подобные проблемы. Оказалось, что задачи типа телефонных возникают в самых разнообразных направлениях исследований: в естествознании, в технике, экономике, транспорте, военном деле, организации производства.

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

Цель реферата: рассмотреть  вопрос о введении в теорию массового обслуживания, пуассоновский поток событий и обслуживание с ожиданием.

Задачи:

• Охарактеризовать общие сведения о системах массового обслуживания;
• Рассмотреть основные свойства потоков событий;
• Простейший поток
• Выявить особенности весенних обрядов.

 

 

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

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

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

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

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

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

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

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

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

По времени пребывания требований в очереди до начала обслуживания системы делятся на три группы:

1) с неограниченным временем  ожидания (с ожиданием),

2) с отказами;

3) смешанного типа.

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

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

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

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2. Свойства потоков событий

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

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

Примерами могут быть:

- поток вызовов на телефонной  станции;

- поток включений приборов  в бытовой электросети;

- поток грузовых составов, поступающих на железнодорожную  станцию;

- поток неисправностей (сбоев)  вычислительной машины;

- поток выстрелов, направляемых  на цель, и т. д.

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

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

Рассмотрим потоки событий, обладающие некоторыми простыми свойствами [7].

1. Стационарность. Поток  называется стационарным, если вероятность  попадания того или иного числа  событий на элементарный участок  времени длиной т зависит только от длины участка и не зависит от того, где именно на оси t расположен этот участок.

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

На практике часто встречаются  потоки событий, которые (по крайней  мере, на ограниченном участке времени) могут рассматриваться как стационарные. Например, поток вызовов, поступающих  на телефонную станцию, скажем, на интервале  от 12 до 13 часов может считаться  стационарным. Тот же поток в течение  целых суток уже не будет стационарным (ночью интенсивность потока вызовов  гораздо меньше, чем днем). Заметим, что так же обстоит дело и с  большинством физических процессов, которые  мы называем «стационарными» — в  действительности они стационарны  только на ограниченном участке времени, а распространение этого участка  до бесконечности — лишь удобный  прием, применяемый в целях упрощения.

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

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

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

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

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

Если в неординарном потоке события происходят только парами, только тройками и т. д., то можно  его рассматривать как ординарный «поток пар», «поток троек» и т. д. Несколько  сложнее обстоит дело, если число  событий, образующих «пакет» (группу одновременно приходящих событий), случайно. Тогда  приходится наряду с потоком пакетов  рассматривать случайную величину X — число событий в пакете, и математическая модель потока становится более сложной.

 

 

 

3. Простейший поток

Рассмотрим поток событий, обладающий всеми тремя свойствами: стационарный, без последействия, ординарный. Такой поток называется простейшим (или стационарным   пуассоновским)  потоком. Название «простейший» связано с тем, что математическое описание событий, связанных с простейшими потоками, оказывается наиболее простым.

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

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

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

 

тогда как для простейшего  потока

 

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

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

(1)

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

Для стационарного (простейшего)  пуассоновского   потока  величина а равна интенсивности потока, умноженной на длину интервала:

 

т. е. не зависит от того, где  на оси t находится период Для нестационарного  пуассоновского   потока  величина а зависит от того, в какой точке начинается участок t.

Рассмотрим на оси t простейший поток событий с интенсивностью . Нас будет интересовать случайный интервал времени Т между соседними событиями в этом потоке; найдем его закон распределения. Сначала найдем функцию распределения:

т. е. вероятность того, что  величина Т будет иметь значение, меньшее, чем t. Отложим от начала интервала Т (точки ) отрезок t и найдем вероятность того, что интервал Т будет меньше t. Для этого нужно, чтобы на участок длины t, примыкающий к точке попало хотя бы одно событие потока. Вычислим вероятность этого F(t) через вероятность противоположного события (на участок t не попадет ни одного события потока):

Вероятность найдем по формуле (1), полагая m = 0:

откуда функция распределения  величины Т будет:

(2)

Чтобы найти плотность  распределения случайной величины Т, необходимо продифференцировать выражение (2) по t:

(3)

Закон распределения с  плотностью (3) называется показательным (или экспоненциальным). Величинаназывается параметром показательного закона.

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

Найдем числовые характеристики случайной величины Т — математическое ожидание (среднее значение) и дисперсию .

Имеем (интегрируя по частям):

(4)

Дисперсия величины T составляет:

. (5)

Извлекая корень квадратный из дисперсии, найдем среднее квадратическое отклонение случайной величины Т.

(6)

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

Приведем выражение для  так называемого «элемента вероятности  появления события» или вероятности  наступления на элементарном участке события потока.

Найдем вероятность того, что на участке  появится какое-то событие потока, т. е. участок не будет «пуст». Так как поток ординарен, вероятностью появления на участке более чем одного события можно пренебречь. Обозначим вероятность того, что на участке не будет события, а — вероятность того, что на нем появится одно событие.

В силу ординарности потока

а вероятность  определяется по (1):

откуда

Разлагая  в ряд и пренебрегая величинами высшего порядка малости, получаем:

(7)

Эта вероятность и называется «элементом вероятности появления  события».

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

 

 

 

 

 

 

 

4. Весенние обряды

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

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

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

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

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

Предположим, что  , и найдем предельные вероятности    для чистой системы с ожиданием. Для этого положим в формулах

,             ,                  . Получим:

,

или, суммируя прогрессию (что возможно только при ),

.                   (4.1)

Отсюда, пользуясь формулами 

                         и             ,           

найдем 

,     (4.2)

и аналогично для   

.                (4.3)

Среднее число заявок, находящихся  в очереди, определяется из формулы (4.1) при :

.                   (4.4)

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

Решение. Имеем  ;  . Так как , установившийся режим существует. По формуле (4.2) находим

;  ;  ;  .

Вероятность наличия очереди:

.

Средняя длина очереди по формуле (4.4) будет

 (заявки).