Автоматизация процесса вычисления по моделям чистого рождения и чистой гибели

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

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

Содержание

• Введение
• 1. Общие положения системы массового обслуживания
• 1.1 Предмет и цели СМО
• 1.2 Характеристики эффективности СМО
• 2. Классификация моделей массового обслуживания
• 2.1 СМО с отказами
• 2.2 СМО с ограничением на длину волны
• 2.3 СМО с неограниченным ожиданием
• 3. Модели рождения и гибели
• 3.1 Модель чистого рождения. Формулы рассчета чистого рождения
• 3.2 Модель чистой гибели. Формула рассчета чистой гибели
• 4. Создание программы
• 4.1 Требования к ОС. Алгоритм программы
• 4.2 Описание работы программы. Примеры
• Заключение
• Список используемой литературы
• Введение
• Теория массового обслуживания является одним из важных разделов экономико-математического моделирования и представляет собой теоретические основы эффективного конструирования и эксплуатации систем массового обслуживания. Системы массового обслуживания (СМО) встречаются во многих областях экономики и предназначены для многократного использования при выполнении схожих задач.
• Примерами СМО могут быть: магазины, банки, ремонтные мастерские, парикмахерские, почтовые отделения, аудиторские фирмы.
• Интересно, что на английском языке теория массового обслуживания звучит как «Queuing theory», что в переводе означает «теория очередей». И действительно, теория массового обслуживания в значительной степени посвящена изучению очередей, возникающих в различных системах. Яркий пример - очередь в магазине. При слишком долгом ожидании в очереди или при отказе в обслуживании клиент останется неудовлетворенным, и маловероятно, что он вернется сюда вновь. А использование теории массового обслуживания позволит просчитать среднюю интенсивность клиентов в разное время суток и выявить оптимальную пропускную способность системы, что позволит избежать подобных проблем.
• Однако не всегда СМО будет представлена очередью. Иногда модель обслуживающей системы представляется только поступлением клиентов и называется моделью чистого рождения, или же только выходом клиентов из системы - моделью чистой гибели. Примером первой модели является процесс оформления свидетельства о рождении детей, примером второй модели может быть изъятие хранящихся на складе запасов. Обе эти модели имеют достаточно сложные формулы, которые влекут за собой громоздкие вычисления. Поэтому для оптимизации расчетов целесообразно применять программы, упрощающие и автоматизирующие данные вычисления.
• Целью данной работы является изучение основных аспектов теории массового обслуживания и создание программы на языке Делфи, автоматизирующей процесс вычисления по моделям чистого рождения и чистой гибели.
• Задачи работы:
• - изучить модели чистого рождения и чистой гибели;
• - написать программу по моделям чистого рождения и чистой гибели.
• В первой главе речь идёт о целях и задачах систем массового обслуживания и об эффективности работы системы.
• Во второй главе рассматриваются основные характеристики системы: система с отказами, система с ограничением на длину волны и система с неограниченным ожиданием.
• В третьей главе освещены основные аспекты модели чистого рождения и модели чистой гибели, представлены формулы для их вычисления.
• Четвертая глава посвящена созданию и разработке программы на языке Делфи для автоматизированного расчета по моделям рождения и гибели.
• В приложении приводится листинг программы на языке Делфи.
• 1. Общие положения системы массового обслуживания
• 1.1 Предмет и цели СМО
• Во многих областях финансов, экономики, производства и быта важную роль играют системы специального вида, реализующие многократное выполнение однотипных задач. Подобные системы называют системами массового обслуживания (СМО). В качестве примеров СМО можно привести системы, представляющие собой банки различных типов (коммерческие, инвестиционные, ипотечные, инновационные, сберегательные), страховые организации (государственные, акционерные общества, компании, фирмы, ассоциации, кооперативы), налоговые инспекции, аудиторские службы, различные системы связи (в том числе телефонные станции), погрузочно-разгрузочные комплексы и различные предприятия и организации сферы обслуживания (магазины, справочные бюро, парикмахерские, больницы). Такие системы как компьютерные сети, системы сбора, хранения и обработки информации, транспортные системы, различные военные системы, в частности системы противовоздушной или противоракетной обороны, также могут рассматриваться как своеобразные системы массового обслуживания.
• Каждая СМО включает в себя некоторое число обслуживающих устройств, которые называют каналами обслуживания. Роль каналов могут играть различные приборы или лица, выполняющие те или иные операции (кассиры, операторы, парикмахеры, продавцы), а также линии связи, автомашины, ремонтные бригады, железнодорожные пути.
• Система массового обслуживания предназначена для выполнения некоторого потока заявок, поступающих на вход системы большей частью не регулярно, а в случайные моменты времени. Обслуживание заявок также длится не постоянное, заранее известное, а случайное время, которое зависит от многих, порой неизвестных нам, причин. После обслуживания заявки канал освобождается и готов к приему следующей заявки. Случайный характер потока заявок и времени их обслуживания приводит к неравномерной загруженности СМО: в некоторые промежутки времени на входе СМО могут скапливаться не обслуженные заявки, что приводит к перегрузке СМО, в некоторые же другие интервалы времени при свободных каналах на входе СМО заявок не будет, что приводит к простаиванию каналов. Заявки, скапливающиеся на входе СМО, либо "становятся" в очередь (т.е. образуют список объектов подлежащих обработке), либо по какой-то причине невозможности дальнейшего пребывания в очереди покидают СМО не обслуженными. Закон, определяющий порядок обслуживания входных заявок, называется дисциплиной очереди. Для примера рассмотрим автозаправочную станцию с одной колонкой (рисунок 1). Площадка при станции, на которой машины ожидают заправку, может вместить не более трех машин одновременно, и если она занята, то очередная машина, прибывшая к станции, в очередь не становится, а проезжает на соседнюю станцию. В среднем машины прибывают на станцию каждые две мин. Процесс заправки полной машины продолжается в среднем 2,5 мин. Моделью данной АЗС является одноканальная СМО с ожиданием и ограничением на длину очереди (m=3). Каналом является колонка.
• Рисунок 1 - Схема СМО в общем виде
• Таким образом, во всякой системе массового обслуживания можно выделить следующие основные элементы:
• а) входящий поток заявок;
• б) очередь;
• в) каналы обслуживания;
• г) выходящий поток обслуженных заявок.
• Каждая СМО имеет свои параметры:
• 1 характер потока заявок;
• 2 число каналов обслуживания;
• 3 производительность каналов;
• 4 правила организации работы.
• И в зависимости от этих параметров определяется пропускная способность (эффективность функционирования) СМО, позволяющая ей более или менее успешно справляться с потоком заявок.
• СМО является предметом теории массового обслуживания. Цель теории массового обслуживания - выработка рекомендаций по рациональному построению СМО, рациональной организации их работы и регулированию потока заявок для обеспечения высокой эффективности работы СМО. Для достижения этой цели ставятся задачи теории массового обслуживания, состоящие в установлении зависимостей эффективности функционирования СМО от ее параметров.
• 1.2 Классификация эффективности СМО
• Основными элементами модели массового обслуживания являются клиент (заявка на обслуживание) и сервис (обслуживающее устройство). Клиенты, поступив в сервис, могут сразу же попасть на обслуживание или стать в очередь, если сервис занят.
• Важным фактором при анализе СМО является принцип построения очереди, определяющий порядок, согласно которому выбираются клиенты из очереди для обслуживания. Наиболее распространенный принцип построения очереди - "первым пришел - первым обслужился " (это правило часто обозначается аббревиатурой FIFO - от английского First-In-First-Out, т.е. "первым вошел -- первым вышел"). Среди других правил, определяющих принципы построения очередей, следует отметить "последним пришел -- первым обслуживаешься" (обычно обозначается как LIFO-- от английского Last-In-First-Out, т.е. "последним вошел -- первым вышел") и дисциплину очереди, определяемую случайным правилом отбора заявок. Кроме того, клиенты могут быть выбраны из очереди в соответствии с заданным приоритетом. Например, в производственном цехе срочные работы выполняются раньше обычных.
• При анализе систем с очередями важным фактором является поведение клиента, нуждающегося в обслуживании. Клиенты при наличии параллельного обслуживания могут перейти из одной очереди в другую в надежде сократить продолжительность ожидания, или же покинуть очередь, простояв в ней какое-то время и придя к выводу, что и так уже слишком много времени потеряно. Поэтому очень важно следить за эффективностью работы системы массового обслуживания: увеличивать или уменьшать количество сервисов в зависимости от интенсивности поступления заказов или увеличивать работоспособность сервисов по необходимости.
• В общем случае в качестве характеристик эффективности функционирования СМО можно выбрать три основные группы показателей:
• 1 Показатели эффективности использования СМО:
• 1.1 Абсолютная пропускная способность СМО - среднее число заявок, которое сможет обслужить СМО в единицу времени.
• 1.2 Относительная пропускная способность СМО - отношение среднего числа заявок, обслуживаемых СМО в единицу времени, к среднему числу поступивших заявок за это же время.
• 1.3 Средняя продолжительность периода занятости СМО.
• 1.4 Коэффициент использования СМО - средняя доля времени, в течение которого СМО занята обслуживанием клиентов.
• 2 Показатели качества обслуживания заявок:
• 2.1 Среднее время ожидания заявки в очереди.
• 2.2 Среднее время пребывания заявки в СМО.
• 2.3 Вероятность отказа заявке в обслуживании без ожидания.
• 2.4 Вероятность того, что поступившая заявка немедленно будет принята к обслуживанию.
• 2.5 Закон распределения времени ожидания заявки в очереди.
• 2.6 Закон распределения времени пребывания заявки в СМО.
• 2.7 Среднее число заявок, находящихся в очереди.
• 2.8 Среднее число заявок, находящихся в СМО.
• 3 Показатели эффективности функционирования пары "СМО -- потребитель", где под "потребителем" понимают всю совокупность заявок или некий их источник (например, средний доход, приносимый СМО в единицу времени, который рассчитывается по формуле I=c₁-c₂ где - среднее число заявок в очереди, - среднее число свободных обслуживающих приборов с₁ - стоимость ожидания одной заявки в единицу времени, с₂ - стоимость простоя одного прибора в единицу времени ).
• Третья группа показателей оказывается полезной в тех случаях, когда доход, получаемый от обслуживания заявок, и затраты на обслуживание измеряются в одних и тех же единицах. Эти показатели обычно носят конкретный характер и определяются спецификой СМО обслуживаемых заявок и дисциплиной обслуживания.
• 2. Классификация систем массового обслуживания
• Системы массового обслуживания делятся на типы по ряду признаков. По числу каналов СМО подразделяют на одноканальные (когда имеется один канал обслуживания) и многоканальные, точнее n - канальные (когда количество каналов n>2). Предполагается, что каждый канал одновременно может обслуживать только одну заявку, и если заранее не оговорено, то каждая находящаяся под обслуживанием заявка обслуживается только одним сервисом. Многоканальные СМО могут состоять или из однородных, или из разнородных каналов, отличающихся длительностью обслуживания одной заявки. «Практически время обслуживания каналом одной заявки Т - непрерывная случайная величина, однако при абсолютной однородности поступающих заявок и каналов время обслуживания может быть константой (Т =const)» [5].
• По ограничению потока заявок СМО делятся на замкнутые и открытые. «Если поток заявок ограничен и заявки, покинувшие систему, могут в нее возвращаться, то СМО является замкнутой, в противном случае - открытой »[4]. Классическим примером замкнутой СМО служит работа группы наладчиков в цеху. Станки являются источниками заявок на обслуживание, и их количество ограничено, наладчики -- каналы обслуживания. После проведения ремонтных работ вышедший из строя станок снова становится источником заявок на обслуживание.
• По количеству этапов обслуживания СМО делятся на однофазные и многофазные системы. « Если каналы СМО однородны, т.е. выполняют одну и ту же операцию обслуживания, то такие СМО называются однофазными. Если каналы обслуживания расположены последовательно и они неоднородны, так как выполняют различные операции обслуживания, то СМО называется многофазной.»[1] Примером работы многофазной СМО может служить обслуживание автомобилей на станции технического обслуживания (мойка, диагностирование).
• По дисциплине обслуживания СМО подразделяют на три класса:
• 1. СМО с отказами (нулевым ожиданием), в которых заявка, поступившая на вход СМО в момент, когда все каналы заняты, получает "отказ" и покидает СМО. Чтобы эта заявка все же была обслужена, она должна снова поступить на вход СМО и рассматриваться при этом как заявка, поступившая впервые. Примером СМО с отказами может служить работа АТС: если набранный телефонный номер занят, то заявка получает отказ, и, чтобы дозвониться по этому номеру, следует его набрать еще раз (заявка должна поступить на вход как новая).
• 2. СМО с ожиданием. В таких системах заявка, поступившая в момент занятости всех каналов, становится в очередь и ожидает освобождения канала, который примет ее к обслуживанию. Каждая заявка, поступившая на вход, в конце концов будет обслужена. Такие СМО часто встречаются в торговле, в сфере бытового и медицинского обслуживания, а также на предприятиях (например, очередь в парикмахерскую).
• 3. СМО смешанного типа (ограниченным ожиданием). Это такие системы, в которых на пребывание заявки в очереди накладываются некоторые ограничения, в большинстве случаев ограничения накладываются на длину очереди, т.е. максимально возможное число заявок, которые одновременно могут находиться в очереди. В качестве примера такой системы можно привести мастерскую по ремонту автомобилей, имеющую ограниченную по размерам стоянку для неисправных машин, ожидающих ремонта.
• 2.1 СМО с отказами (одно - и многоканальная)
• Простейшей одноканальной моделью с вероятностным входным потоком и процедурой обслуживания является модель, которая «может характеризоваться показательным распределением длительностей интервалов между поступлениями заявок и распределением длительностей обслуживания»[2]. При этом плотность распределения длительностей интервалов между поступлениями требований имеет вид:

f₁(t) = л*e ^(-л*t) , (1)

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

f₂(t)=µ*e^-µ*t, µ=1/t_{об ,} (2 )

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

q = . (3)

Эта величина равна вероятности, что канал обслуживания свободен. Абсолютная пропускная способность (А) -- среднее число заявок, которое может обслужить система массового обслуживания в единицу времени:

A= л*q = (4)

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

P = 1 - = . (5)

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

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

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

- вероятности отказа Р.

Решение:

Определим интенсивность потока обслуживания по формуле 2: .Вычислим относительную пропускную способность: q =.Величина q означает, что в установившемся режиме система будет обслуживать примерно 35% прибывающих на пост автомобилей. Абсолютную пропускную способность определим по формуле: А=лЧq=1Ч0,356=0,356. Это говорит о том , что система способна осуществить в среднем 0,356 обслуживания автомобилей в час. Вероятность отказа: Р_отк=1-q=1-0,356=0,644. Это означает, что около 65% прибывших автомобилей на пост ЕО получат отказ в обслуживании. Определим номинальную пропускную способность данной системы А_ном: А_ном= (автомобилей в час).

Однако в подавляющем большинстве случаев система массового обслуживания является многоканальной, то есть параллельно может обслуживаться несколько заявок. Процесс СМО, описываемый данной моделью, характеризуется интенсивностью входного потока л, при этом параллельно может обслуживаться не более n клиентов. Средняя продолжительность обслуживания одной заявки равняется 1/м. «Режим функционирования обслуживающего канала не влияет на режим функционирования других обслуживающих каналов системы, причем длительность процедуры обслуживания каждым из каналов является случайной величиной, подчиненной экспоненциальному закону распределения. Конечная цель использования параллельно включенных обслуживающих каналов - повышение скорости обслуживания заявок за счет обслуживания одновременно n клиентов.»[3] Решение такой системы имеет вид:

; . (6)

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

P_отк=P_n=*P₀. (7)

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

. (8)

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

(9)

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

. (10)

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

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

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

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

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

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

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

Решение.

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

.

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



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

(11)

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

. (12)

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

. (13)

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

. (14)

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

. (15)

Таким образом, при установившемся режиме работы СМО в среднем будет занято 1,5 компьютера из трех - остальные полтора будут простаивать. Пропускную способность ВЦ при данных л и м можно увеличить только за счет увеличения числа ПЭВМ.

2.2 СМО с ожиданием (одно- и многоканальная)

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

Обозначим P_n - вероятность того, что в системе находится n заявок:

(16)

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

. (17)

С учетом этого можно обозначить

(18)

Определим характеристики одноканальной СМО с ожиданием и ограниченной длиной очереди, равной (N-1). Вероятность отказа в обслуживании заявки:

P_отк = Р_N = (19)

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

(20)

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

А=q•л; (21)

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

 (22)

среднее время пребывания заявки в системе:

; (23)

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

W_q=W_s- 1/м; (24)

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

L_q=л(1-P_N)W_q. (25)

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

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

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

Решение: Интенсивность потока обслуживаний автомобилей: Приведенная интенсивность потока автомобилей определяется как отношение интенсивностей л и м, т.е.

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

P₁=r•P₀=0,893•0,248=0,221; P₂=r²•P₀=0,893²•0,248=0,198; P₃=r³•P₀=0,893³•0,248=0,177; P₄=r⁴•P₀=0,893⁴•0,248=0,158.

Вероятность отказа в обслуживании автомобиля: P_отк=Р₄=r⁴•P₀?0,158.

Относительная пропускная способность поста диагностики: q=1-P_отк=1-0,158=0,842.

Абсолютная пропускная способность поста диагностики : А=л•q=0,85•0,842=0,716 (автомобиля в час).

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

L_S

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

часа.

Средняя продолжительность пребывания заявки в очереди на обслуживание: W_q=W_s-1/м=2,473-1/0,952=1,423часа. Среднее число заявок в очереди (длина очереди):

L_q=л•(1-P_N)•W_q=0,85•(1-0,158)•1,423=1,02.

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

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

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

, (26)

. (27)

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

. (28)

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

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

; (29)

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

L_S=L_q+с; (30)

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

; (31)

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

. (32)

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

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

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

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

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

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

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

Решение:

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

Приведенная интенсивность потока заявок: с=л/м=2,5/2,0=1,25, при этом л/м •с=2,5/2•3=0,41<1.

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

Вероятность отсутствия очереди у мастерской:

Р_отк?Р₀+Р₁+Р₂+Р₃ ? 0,279+0,394+0,218+0,091 = 0,937.

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

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

L_s=L_q+=0,111+1,25=1,361.

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

суток.

Средняя продолжительность пребывания механизма в мастерской (в системе):

суток.

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

Перейдем теперь к рассмотрению одноканальной СМО с ожиданием без ограничения на вместимость блока ожидания (т.е. Н > ?). Остальные условия функционирования СМО остаются без изменений. «Устойчивое решение в такой системе существует только тогда, когда л<м, то есть заявки должны обслуживаться с большей скоростью, чем поступают, в противном случае очередь может разрастись до бесконечности»[7]. Вероятность того, что в системе находится n заявок, вычисляется по формуле:

P_n=(1-r)r ⁿ, n=0,1,…,где r =л/м<1. (33)

Характеристики одноканальной СМО с ожиданием, без ограничения на длину очереди, следующие:

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

(34)

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

; (35)

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

L_q=L_S - ; (36)

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

W_q=. (37)

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

1 вероятности состояний системы (поста диагностики);

2 среднее число автомобилей, находящихся в системе (на обслуживании и в очереди);

3 среднюю продолжительность пребывания автомобиля в системе (на обслуживании и в очереди);

4 среднее число автомобилей в очереди на обслуживании;

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

Решение Параметр потока обслуживания и приведенная интенсивность потока автомобилей с определены в предыдущем примере: м=0,952; с=0,893. Вычислим предельные вероятности системы по формулам:

P₀=1-r=1-0,893=0,107;

P₁=(1-r)·r=(1-0,893)·0,893=0,096;

P₂=(1-r)·r²=(1-0,893)·0,893²=0,085;

P₃=(1-r)·r³=(1-0,893)·0,893³=0,076;

P₄=(1-r)·r⁴=(1-0,893)·0,893⁴=0,068;

P₅=(1-r)·r⁵=(1-0,893)·0,893⁵=0,061 .

Следует отметить, что Р₀ определяет долю времени, в течение которого пост диагностики вынужденно бездействует (простаивает). В нашем примере она составляет 7%, так как Р₀=0,107. Среднее число автомобилей, находящихся в системе:

ед.

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

час.

Среднее число автомобилей в очереди на обслуживание:

.

Средняя продолжительность пребывания автомобиля в очереди: час. Относительная пропускаемая способность системы равна единицы, так как все поступившие заявки рано или поздно будут обслужены: q=1.

Абсолютная пропускная способность: A=л•q=0,85•1=0,85. Количество мест для стоянки прибывших автомобилей в предыдущем примере было равно трем. Частота m возникновения ситуаций, когда прибывающий на пост диагностике автомобиль не имеет возможности присоединить к очереди: m=л•P_N. В нашем примере при N=3+1=4 и r=0,893, m=л•P₀•r⁴=0,85•0,248•0,8934 =0,134 автомобиля в час. При 12-часовом режиме работы поста диагностики это эквивалентно тому, что пост диагностики в среднем за смену (день) будет терять 12•0,134=1,6 автомобиля.

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

3. Модели рождения и гибели

3.1 Модель чистого рождения

Модель обслуживающей системы, представленная только поступлением клиентов называется моделью чистого рождения. Пусть p₀(t) -- вероятность отсутствия событий (поступления клиентов) за период времени t. «При условии, что длина интервала времени Т между поступлениями клиентов описывается экспоненциальным распределением с интенсивностью л, будем иметь p₀(t) = P{интервал времени T ? t} = 1- P{интервал времени T ? t} = 1 - (1 - e-лt) = e - лt »[6] . При достаточно малом интервале времени h > 0 имеем

p0(h) = e-лh = 1 - лh + (лh)2/2! - ... = 1 - лh + O(h2). (38)

«Экспоненциальное распределение базируется на предположении, что на достаточно малом временном интервале h > 0 может наступить не более одного события (поступления клиента). Следовательно, при h > 0 p₁(h) = 1 - p₀(h) ? лh»[7].

Этот результат показывает, что вероятность поступления клиента на протяжении интервала h прямо пропорциональна h с коэффициентом пропорциональности, равным интенсивности поступлений л.

Чтобы получить распределение числа клиентов, поступивших на протяжении некоторого интервала времени, обозначим через p_n(t) вероятность поступления n клиентов на протяжении времени t. При достаточно малом h > 0 имеем следующее:

pn(t+h)?pn(t)(1-лh)+ pn-1(t)лh, n>0, (39)

p0(t + h) ? p0(t)(1 - лh), n = 0. (40)

Из первого уравнения следует, что поступление n клиентов на протяжении времени t + h возможно в двух случаях: если имеется n поступлений на протяжении времени t и нет поступлений за время h, или существует n - 1 поступлений за время t и одно поступление за время h. Любые другие комбинации невозможны вследствие того, что на протяжении малого периода h возможно наступление только одного события. В соответствии с условием независимости событий к правой части уравнения применим закон умножения вероятностей. Во втором уравнении отсутствие поступлений клиентов на протяжении интервала t + h возможно лишь тогда, когда нет поступлений клиентов за время h.

Перегруппировывая члены и переходя к пределу при h > 0, получаем следующее.

(41)

Решение приведенных выше разностно-дифференциальных уравнений имеет следующий вид:

(42)

В данном случае мы получили дискретную плотность вероятности распределения Пуассона с математическим ожиданием M{n|t}=лt поступлений за время t. Полученный результат означает, что «всякий раз, когда временные интервалы между моментами последовательных поступлений заявок распределены по экcпоненциальному закону с математическим ожиданием 1/л, число поступлений заявок в интервале, равном t единиц времени характеризуется распределением Пуассона с математическим ожиданием лt»[1]. Верным является и обратное утверждение.

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

Решение: Вычислим интенсивность рождений за день: л = (24 * 60) / 12 = 120 рождений за день. Интенсивность рождений в штате за год равна лt = 120 * 365 = 43800 рождений. Вероятность того, что на протяжении одного дня не родится ни один ребенок, вычисляется с использованием пуассоновского распределения p0(1) = [(120 * 1)^{0 *} e^{(-120 * 1)}]/0! ? 0.

Для вычисления вероятности выдачи 50 свидетельств о рождении к концу третьего часа при условии, что на протяжении последних двух часов было выдано 40 таких свидетельств, заметим, что, поскольку распределение числа рождений является пуассоновским, искомая вероятность сводится к вероятности появления 10 (= 50 - 40) рождений за один (= 3 - 2) час. Так как л = 60/12 = 5 рождений за час, то p10(1) = [(5 * 1)¹⁰ * e^{(-5 * 1)} ]/10! = 0,01813.

3.2 Модель чистой гибели

В данной модели предполагается, что «система начинает функционировать, когда в момент времени t в ней имеется N клиентов и не допускается ни одного нового поступления клиента»[7]. Обслуженные клиенты выбывают из системы с интенсивностью м клиентов в единицу времени. Пусть p_n(t) -- вероятность того, что после t временных единиц в системе остается n клиентов. Для получения разностно-дифференциальных уравнений относительно pn(t) обычно следуют логике рассуждений, использованных в модели чистого рождения .Поэтому имеем

pN(t + h) = pN(t)(1 - мh), (43)

pn(t + h) = pn(t)(1 - мh) + pn+1(t)мh, 0 < n < N, (44)

p0(t + h) = p0(t) + p1(t)мh. (45)

При h > 0 получим pN ' (t) = - мpN(t), (46)

pn'(t) = - мpn(t) + мpn+1(t), 0 < n < N, (47)

p0'(t) = мp1(t). (48)

Эти уравнения имеют решение

, (49)

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

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

Так как розы покупаются с интенсивностью м = 3 дюжины в день, то вероятность того, что заказ будет размещен в конце дня t, равна



Среднее количество роз, которые будут ликвидированы к концу недели (t= 7) вычисляется следующим образом :

Ответ: 0,664 дюжины роз в среднем будут ликвидированы к концу недели.

отказ гибель программа

4. Создание программы

4.1 Требования к ОС. Алгоритм программы

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

Основные требования к операционной системе для оптимальной работы программы: Microsoft Windows XP / Vista / 7; процессор Pentium IV , или AMD Athlon XP 1700+ и выше ; ОЗУ 256 Мб; 500 Кб свободной памяти, клавиатура; мышь.Наличие установленной среды Делфи не обязательно.

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

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

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

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

-наращиваемость за счет встраивания новых компонент и инструментов в среду Делфи;

-возможность разработки новых компонент и инструментов собственными средствами Делфи;

-удачная проработка иерархии объектов;

-мощные средства отладки (вплоть до пошагового выполнения команд процессора);

-встроенные компоненты доступа к данным: BDE, ODBC или ADO;

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

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

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

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

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

1 выбор модели СМО;

2 ввод данных для каждой из моделей;

3 расчет по формуле;

4 вывод на печать.

Рисунок 2 - Общая схема работы программы

4.2 Описание работы программы. Примеры

При запуске программы появляется основное окно (рисунке 3) с 2 кнопками : « close» и « >> ».

Рисунок 3 - Приветственное окно

Нажав на левую кнопку, мы закроем программу, а выбрав « >> », переходим в следующее окно для выбора необходимой модели СМО. Оно изображено на рисунке 4.

Рисунок 4 - Выбор модели

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

Рисунок 5 - Рассчет по модели рождения

В данном окне можно устанавливать интенсивность потока X (количество заявок в определенный момент времени), период времени поступления клиентов t, а также ограничить n - максимально возможное кол-во клиентов. Затем выбираем кнопку «посчитать», и рядом в окне появится результат, нужно лишь выбрать необходимое n . Для закрытия данного окна выбираем кнопку « close».

Для подсчета по модели чистой гибели нужно выбрать нижнюю крайнюю левую кнопку с надписью « модель чистой гибели». Появится окно (рисунок 6) для ввода данных: интенсивности выбывания обслуженных клиентов v, периода времени t работы системы, общего количества клиентов N и ограничения по n - максимальное количество оставшихся клиентов. Следует учитывать, что общее количество клиентов N должно быть больше количества оставшихся клиентов. Для расчета по модели необходимо нажать кнопку «посчитать » и выбрать нужное n. Для закрытия данного окна выбираем кнопку « close».



Рисунок 6 - рассчет по модели гибели

Все файлы проекта располагаются в директории с наименованием СМО. В проект входят: файл проекта Delphi SMO. dpr, файлы исходного текста:

Unit1 - основной модуль;

Unit2 - модуль для расчета по модели чистого рождения;

Unit3 - модуль для расчета по модели чистой гибели;

Unit4 - модуль для выбора определенной формулы для расчета по моделям.

Основные процедуры:

procedure TForm2.Button2Click(Sender: TObject) - процедура для расчета по формуле чистого рождения .

procedure TForm3.Button2Click(Sender: TObject) - процедура для расчета по формуле чистой гибели.

Пример чистого рождения:

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

Поскольку распределение числа рождений является пуассоновским, искомая вероятность сводится к вероятности появления 10 (= 50 - 40) рождений за один (= 3 - 2) час. Так как л = 60/12 = 5 рождений за час, то p₁₀(1) = [(5 * 1)¹⁰e^{-5 * 1}]/10! = 0,01813.

Рассмотрим реализацию модели чистого рождения с помощью программы на языке делфи. Ниже показаны выходные данные(рисунок 7) полученные для модели чистого рождения с интенсивностью 5 х 1 = 5 рождений за день.

Рисунок 7 - Пример 1

Выбираем n = 10 и видим, что p_n = p₁₀=0,01813.

Пример 2. Время между прибытиями посетителей в ресторан распределено по экспоненциальному закону со средним значением 5 минут. Ресторан открывается в 11:00. Требуется вычислить вероятность того, что в 11:12 в ресторане окажется 10 посетителей при условии, что в 11:05 в ресторане было 8 посетителей.

Поскольку распределение является пуассоновским, искомая вероятность сводится к вероятности появления 2 (= 10 - 8) посетителей за 7 (= 12 - 5) мин. Т.к. л = 1/5, то P2(t = 7) = [(1/5 * 7)2 * e(-1/5 * 7)]/2 = 0.2416 (Рисунок 8).



Рисунок 8 - Пример 2

Рассмотрим реализацию программы на примере модели гибели.

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

-вероятность размещения заказа к концу каждого дня недели;

-среднее количество роз, которые будут ликвидированы к концу недели.

Так как розы покупаются с интенсивностью м = 3 дюжины в день, то вероятность того, что заказ будет размещен в конце дня t, равна

P₁=0.0001 (рисунок 9).



Рисунок 9 - вероятность размещения заказа к концу 1 дня P₂=0.0001 (рисунок 10).

Рисунок 10 - вероятность размещения заказа к концу 2 дня

В таблице выбираем значение P(n) при n = 5 (т.к новый заказ делается, как только уровень запаса снижается до 5 дюжин).

Таблица 1 - Расчет результатов

t (дни)	1	2	3	4	5	6	7
мt	3	6	9	12	15	18	21
pn ? 5(t)	0,0001	0,0052	0,0504	0,1055	0,0956	0,0509	0,0188

Заключение

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

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

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

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

Список использованной литературы

1 Коваленко И.Н. «Теория массового обслуживания», 1963 год, издательство ВИНИТИ, 125 с.

2 Лаврусь О.Е., Миронов Ф.С. «Теория массового обслуживания» методические указания, учебная программа и задания для контрольных работ №1, 2 для студентов заочной формы обучения специальности «Информационные системы в технике и технологиях », Самара, 2002 год.

3 Лазарева Т.Я., Диденко И.В. «Системы массового обслуживания», методические разработки к практическим и индивидуальным занятиям для студентов 4 курса специальности дневного отделения по дисциплине «Теория принятия решений», методические разработки, 2001 год.

4 Саакян Г.Р. лекции «Теория массового обслуживания» для студентов экономических специальностей очной, заочной и дистанционной форм обучения, г. Шахты, 2006 год.

5 Саати Т.Л. «Элементы теории массового обслуживания и ее приложения», перевод с английского Е.Г. Коваленко, под редакцией И.Н. коваленко и Р.Д. Когана, 1965 год, издательство Советское радио, 500 с.

6 Системы массового обслуживания: Методические разработки / Составители Т.Я. Лазарева, И.В.Диденко, Рецензент В.Г. Серегина, Тамбов. Тамбовский государственный технический университет, 2001 год.

7 М.В. Швецкий Информатика и программирование Шаг за шагом.

8 Таха Х.А. «Введение в исследование операций », 7-е издание, перевод с английского и редакция канд. Физ.-мат. Наук А.А. Минько, 2005 год, издательский дом «Вильямс»,912 с.

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

...