Размещено на http: //www. allbest. ru/

Размещено на http: //www. allbest. ru/

Министерство образования и науки Украины

Национальный технический университет

«Харьковский политехнический институт»

Кафедра: «Распределенных информационных систем и облачных технологий»

КУРСОВАЯ РАБОТА

по дисциплине: «Математические методы исследования операций»

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

Выполнила:

студентка гр.КИТ-95

Кравченко Ю.В.

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

Иванчихин Ю.В.

Харьков 2017



Содержание

Задание

Введение

1. Теория массового обслуживания, определение, классификация, показатели эффективности

2. Теоретическое описание методов решения задания

2.1 СМО с отказами

2.2 СМО с очередью

3. Практическое решение заданий

3.1 Анализ систем массового обслуживания с отказами

3.2 Анализ эффективности систем массового обслуживания с ожиданием



Задание

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

На входе n-канальной СМО с отказами поступает пуассоновский поток заявок интенсивность л=8/час. Интенсивность обслуживания равна м=4/час. За каждую обслуженную заявку система получает доход, равный =30. Стоимость эксплуатации каждого канала системы в единицу времени равна . Эффективность системы оценивается величиной средней прибыли, получаемой системой в единицу времени:

Прибыль = Доход - Затраты

Pr = * л * - * n, - вероятность обслуживания заявки.

НЕОБХОДИМО:

1.Найти рациональное значение числа каналов, обеспечивающее максимальную среднюю прибыль. Задачу решить для л=****, м= ***.

2.При фиксированном n=2 найти рациональное значение интенсивности обслуживания, считая, что зависимость стоимости эксплуатации канала от интенсивности обслуживания имеет вид =3 /час.

3.Подготовить отчет, который должен содержать:

- график зависимости прибыли, получаемой СМО от числа каналов,

- график зависимости прибыли от значения интенсивности обслуживания.

Анализ эффективности систем массового обслуживания с ожиданием

На входе n-канальной СМО с ограничением по длине очереди поступает пуассоновский поток заявок интенсивность л=14/час. Интенсивность обслуживания равна м=7/час. Заявка, поступившая в момент, когда все каналы заняты, занимает очередь, максимальная длинна которой равна q=4 и ждет освобождения какого-либо из каналов. За каждую обслуженную заявку система получает доход, равный единиц. Стоимость эксплуатации системы зависит от числа каналов и максимально допустимой длины очереди по формуле

= n + q.

n, q .

НЕОБХОДИМО:

1.Найти рациональное значение числа каналов, для исходных данных.

2.Найти рациональную допустимую длину очереди для тех же данных, считая n=2.

3.Подготовить отчет, который должен содержать:

- график зависимости прибыли, получаемой СМО от числа каналов,

- график зависимости прибыли от допустимой длины очереди.



Введение

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

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

Использование теории массового обслуживания позволяет фирме избежать подобных неприятностей. Основоположником теории массового обслуживания считается датский ученый А. К. Эрланг (опубликовал в 1909 году работу «Теория вероятностей и телефонные переговоры»). Значительный вклад в создание и разработку общей теории массового обслуживания внес выдающийся советский математик Александр Яковлевич Хинчин (1984 - 1959), который предложил сам термин теория массового обслуживания.



1. Теория массового обслуживания, определение, классификация, показатели эффективности

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

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

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

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

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

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

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

- Среднее время ожидания на обслуживание;

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

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

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

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



2 - очередь - требования, ожидающие обслуживания. Очередь оценивается средней длиной - числом объектов или клиентов, ожи-дающих обслуживания.

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

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

5 - замыкание (возможное) СМО - состояние системы, при котором входящий поток требований зависит от выходящего.

Классификация СМО :

1.По ограничениям на длину очереди:

* СМО с потерями - требование покидает СМО необслуженным, если в момент его поступления все каналы заняты;

* СМО без потерь - требование занимает очередь, даже если все каналы заняты;

* СМО с ограничениями по длине очереди т или времени ожидания: если су-ществует ограничение на очередь, то вновь поступившее требование выбывает из системы необслуженным.

2. По количеству каналов обслуживания п:

* одноканальные: n = 1;

* многоканальные n > 2.

3. По типу обслуживающих каналов:

* однотипные (универсальные);

* разнотипные (специализированные).

4. По порядку обслуживания:

* однофазовые - обслуживание производится на одном аппарате (посту);

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

5. По приоритетности обслуживания:

* без приоритета - требования обслуживаются в порядке их поступления на СМО;

* с приоритетом - требования обслуживаются в зависимости от присвоенного им при поступлении ранга приоритетности.

6. По величине входящего потока требований:

* с неограниченным входящим потоком;

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

7. По структуре СМО:

* замкнутые - входящий поток требований при прочих равных условиях зависит от числа ранее обслуженных требований (комплексное АТП, обслуживающее только свои автомобили ;

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

Для всех видов СМО используются следующие показатели эффективности:

· относительная пропускная способность - это средняя доля поступающих заявок, обслуживаемых системой;

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

· вероятность отказа - это вероятность того, что заявка покинет систему без обслуживания;

· среднее число занятых каналов - для многоканальных СМО.



2. Теоретическое описание методов решения задания

2.1 СМО с отказами

Одноканальная система (СМО) с отказами

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

Система S (СМО) имеет два состояния : - канал свободен; - канал занят.

Важнейшими показателями эффективности СМО с отказами являются следующие параметры:

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

2. Относительная пропускная способность системы.

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

,

где - интенсивность потока заявок; - интенсивность потока обслуживания.

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



.

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

.

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

5. .

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

.

Учитывая нормировочное условие

; .



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

р = .

Многоканальная система (СМО) с отказами

Имеется n каналов, на которые поступает поток заявок с интенсивностью л, поток обслуживания имеет интенсивность м. Система S (СМО) имеет следующие состояния : , ,,…,,…,, где - состояние системы, когда в ней находится k заявок, т.е. занято k каналов.

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

В многоканальных системах массового обслуживания с предельными вероятностями используют формулы для предельных вероятностей состояния, которые получили название формул Эрланга в честь А.К. Эрланга (конец XIX - начало XX в.) - Датского инженера, математика, основателя теории массового обслуживания.

Вероятность отказа системы массового обслуживания - это предельная вероятность того, что все n каналов системы будут заняты, то есть:



,

Относительная пропускная способность - вероятность того, что заявка будет обслужена определяется:

.

Абсолютная пропускная способность рассчитывается:

A=

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

или = .

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



2.2 СМО с очередью

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

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

2) -- среднее время пребывания заявки в системе;

3) -- среднее число заявок в очереди (длина очереди);

4)-- среднее время пребывания заявки в очереди;

5) -- вероятность того, что канал занят (степень загрузки канала).

Одноканальная система с неограниченной очередью

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

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



=

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

Поэтомy и с учетом соотношений :

, , …, ,

найдем предельные вероятности других состояний

, , , …, , …

Предельные вероятности образуют убывающую геометрическую профессию со знаменателем р<1, следовательно, вероятность -- наибольшая. Это означает, что если СМО справляется с потоком заявок (при ), то наиболее вероятным будет отсутствие заявок в системе.

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

(при p < 1).



Найдем среднее число заявок в очереди . Очевидно, что

где -- среднее число заявок, находящихся под обслуживанием.

Среднее число заявок под обслуживанием определим по формуле математического ожидания числа заявок под обслуживанием, принимающего значения 0 (если канал свободен) либо 1 (если канал занят):

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

В силу = p , тo

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

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

.



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

Имеется n-канальная СМО с неограниченной очередью. Поток заявок, поступающих в СМО, имеет интенсивность , а поток обслуживании -- интенсивность . Система может находиться в одном из состояний ,…, нумеруемых по числу заявок, находящихся в СМО:  -- в системе нет заявок (все каналы свободны); -- занят один канал, остальные свободны; -- заняты два канала, остальные свободны; -- занято k каналов, остальные свободны; -- заняты все n каналов (очереди нет); -- заняты все n каналов, в очереди одна заявка; -- заняты все n каналов, r заявок стоит в очереди, и т.д.

, …,

, …, …

Вероятность того, что заявка окажется в очереди,



Среднее число занятых каналов

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

Среднее число заявок в системе

Среднее время пребывания заявки в очереди и среднее время пребывания заявки в системе, как и ранее, находятся по формулам Литтла. Для СМО с неограниченной очередью при p < 1 любая заявка, пришедшая в систему, будет обслужена, т.е. вероятность отказа , относительная пропускная способность Q=1, а абсолютная пропускная способность равна интенсивности входящего потока заявок, т.е. A=.

СМО с ограниченной очередью

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

СМО с ограниченным временем ожидания

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

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



3. Практическое решение заданий

3.1 Анализ систем массового обслуживания с отказами.

А) Задана многоканальная СМО с отказами. Она имеет состояния:

- в СМО нет ни одной заявки;

- в СМО находится одна заявка (один канал занят, остальные свободны),

-- в СМО находится k заявок (k каналов заняты, остальные свободны),

-- в СМО находится п заявок (все n каналов заняты).

Найдем интенсивность нагрузки канала, учитывая, что л=8/час, м=4/час, =30,

, ,

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

=1/4= 0,25 ч.

(15 мин) в систему поступает в среднем 2 заявки.

Воспользуемся формулами Эрланга, постепенно увеличивая число каналов.

При n=1 относительная пропускная способность СМО равна:

= = 0,33



т.е. в среднем только 33% поступающих заявок будут обслужены. Соответственно вероятность отказа в обслуживании составит

Абсолютная пропускная способность СМО:

=

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

.

С этого прибыль будет равна

л - n = 30 * 8 * 0.33 - 15 * 1 = 64.2

При n=2 имеем:

=

Относительная пропускная способность - вероятность того, что заявка будет обслужена:



т.е. в среднем 60% поступающих заявок будут обслужены. Соответственно вероятность отказа в обслуживании составит

Абсолютная пропускная способность СМО:

= 8*0.6 = 4.8

т.е. в среднем в час будут обслужены 4.8 заявки.

В таком случае доход будет составлять

.

С этого найдем прибыль:

л - n = 30 * 8 * 0.6 - 15 * 2 = 114.

При n=3 имеем:

= .

= 1.33 * 0.16 = 0.21.

Относительная пропускная способность - вероятность того, что заявка будет обслужена:



т.е. в среднем 79% поступающих заявок будут обслужены.

Абсолютная пропускная способность СМО:

= 8 * 0.79 = 6.32

т.е. в среднем в час будут обслужены 6.32 заявки.

В таком случае доход будет составлять

.

С этого найдем прибыль:

л - n = 30 * 8 * 0.79 - 15 * 3 = 144.6

При n=4 имеем:

= .

= * 0.14 = 0.09.

Относительная пропускная способность - вероятность того, что заявка будет обслужена:

т.е. в среднем 91% поступающих заявок будут обслужены.

Абсолютная пропускная способность СМО:

= 8 * 0.91 = 7,28



т.е. в среднем в час будут обслужены 7,28 заявки.

В таком случае доход будет составлять

С этого найдем прибыль:

л - n = 30 * 8 * - 15 * 4 = 158.4

При n=5 имеем:

=. = * 0.14 = 0.04

Относительная пропускная способность - вероятность того, что заявка будет обслужена:

т.е. в среднем 96% поступающих заявок будут обслужены.

Абсолютная пропускная способность СМО:

= 8 * = 7.68

т.е. в среднем в час будут обслужены 7,68 заявки.

В таком случае доход будет составлять



С этого найдем прибыль:

л - n = 30 * 8 * - 15 * 5 = 155.4

При n=6 имеем:

=0.14

= * 0.14 = 0.01

Относительная пропускная способность - вероятность того, что заявка будет обслужена:

т.е. в среднем 99% поступающих заявок будут обслужены.

Абсолютная пропускная способность СМО:

= 8 * = 7.92

т.е. в среднем в час будут обслужены 7.92 заявки.

В таком случае доход будет составлять



С этого найдем прибыль:

л - n = 30 * 8 * - 15 * 6 = 147.6

При n=7 имеем:

=0.14

= * 0.14 = 0

Относительная пропускная способность - вероятность того, что заявка будет обслужена:

Абсолютная пропускная способность СМО:

= 8 * = 8

т.е. в час будут обслужены все 8 заявок.

В таком случае доход будет составлять

С этого найдем прибыль:

л - n = 30 * 8 * - 15 * 7 = 135.



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

B) Задано каналов n=2, зависимость стоимости эксплуатации канала от интенсивности обслуживания имеет вид:

=3 /час,

интенсивность входящего потока л=8 з/час ,

л - n = 114, то

л - n = 30 * * 0.6 - 2 = 144 - 6.

114 = 144 - 6,

= 25.

То есть при фиксированном n=2 рациональное значение интенсивности обслуживания равно заявок в час.

3.2 Анализ эффективности систем массового обслуживания с ожиданием

Система с ограниченной длиной очереди. Рассмотрим n- канальную СМО с ожиданием, на которую поступает поток заявок с интенсивностью л=14/час; интенсивность обслуживания (для одного канала) ; число мест в очереди q=4. При чем стоимость эксплуатации системы зависит от числа каналов и максимально допустимой длины очереди по формуле

= n + q, n, q .



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

-- все каналы свободны;

-- занят один канал, остальные свободны;

-- заняты k-каналов, остальные нет;

-- заняты все n-каналов, свободных нет;

есть очередь:

-- заняты все n-каналов; одна заявка стоит в очереди;

-- заняты все n-каналов, т - заявок в очереди.

Найдем интенсивность нагрузки канала:

= = 2,

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

ч.

в систему поступает в среднем 2 заявки. По условию ). Очередь не будет возрастать до бесконечности при условии , т.е. при . Таким образом, минимальное количество контролеров-кассиров .

При n=1 имеем:

= n + q = 0.8*1+0.2*4 = 1.6



При n=2 имеем:

= n + q = 0.8*2 + 0.2*4 = 2.4

При n=3 имеем:

= n + q = 0.8*3 + 0.2*4 = 3.2

При n=4 имеем:

= n + q = 0.8*4 + 0.2*4 = 4

При n=5 имеем:

= n + q = 0.8*5 + 0.2*4 = 4.8

При n=6 имеем:

= n + q = 0.8*6 + 0.2*4 = 5.6

При n=7 имеем:

= n + q = 0.8*7 + 0.2*4 = 6.4

Размещено на Allbest.ru