Лабораторная работа № 3
Моделирование торгового центра
I. Цель работы
Цельюработы является:
1. Освоение основныхэлементов систем массового обслуживания
2. Изучение основныхпринципов моделирования систем массового обслуживания на ПЭВМ
3. Получение практическихнавыков моделирования на примере исследования торгового центра
II.Теоретическиесведения
2.1Основные элементы систем массового обслуживания
Системоймассового обслуживания (СМО) называется система, на которую в случайные моментывремени поступают заявки, нуждающиеся в том или ином виде обслуживания в течениенекоторого случайного отрезка времени. Из- за случайного характера потока заявокв системе, в какие-то моменты времени могут возникнуть очереди, а в другие моментысистема может работать с недогрузкой или вообще простаивать. Поэтому на практикевозникают насущные задачи количественной оценки эффективности работы таких систем.СМО должна обеспечить минимизацию суммарных затрат, связанных с ожиданием и потерямиот простоя средств обслуживания.
Основнымиэлементами систем массового обслуживания являются:
· Входной поток
· Очередь
· Прибор или канал обслуживания
· Выходной поток
Общаяфункциональная схема системы имеет вид (Рис 1)/> /> /> /> /> /> /> /> /> />
Очередь
Прибор обслуживания
Выходной поток />
Входной поток />
/>/>/>/> />
М
Рис1. Функциональная схема СМО
Где/> — интенсивность потока заявок (среднее количество заявок,поступивших в единицу времени)
М –интенсивность обслуживания заявок (среднее количество заявок, обслуживаемых приборомв единицу времени)
Входнойпоток заявок представляет собой последовательность однородных событий следующиходно за другим в случайные моменты времени t0
/>
t
/>
t0 t1 t2……...ti-1 ti…………..tn
Рис.2Входной поток заявок
Гдеτi = ti -ti-1 — интервал между двумя соседними моментамипоступления заявок
Еслиτi= const, то токай поток называется регулярным. Если τiменяется случайным образом, то такойпоток называется случайным .
Случайныйпоток называется простейшим или стационарным Пуассоновским потоком, если он обладаетсвойствами:
· Стационарности
· Безпоследействия
· Ординарности
Свойствостационарности означает, что все вероятностные характеристики потока не зависятот времени. Свойство безпоследействия означает, что все события являются независимымидруг от друга, т.е. появление каждого события не зависит от предистории. Свойствоординарности означает, что все события наступают (заявки приходят) поодиночке. Поэтомуинтервалы времени поступления заявок в Пуассоновском потоке распределены по экспоненциальномузакону с плотностью- вероятностью
f(τ)=λe-λτ, (1)
гдеλ – интенсивность потока:
τ>0-интервал времени поступления заявок.
Длямоделирования интервала поступления заявок используется формула:
τi=-/>ln(xi) (i=1,n) (2)
гдеxi -случайные числа равномерно-распределенныев интервале [0,1].
Тогдапоступление заявок определяется по формуле
Дляполучения случайных чисел х необходимо обратиться к стандартной функции или генераторуслучайных чисел, равномерно-распределенных в интервале RND(x).
Очередь– это линейная цепочка выстроившихся в ряд один за другим заявок, нуждающихся втом или ином виде обслуживания. Законы, по которым регламентируется поведение очередиобразуют дисциплину обслуживания в очереди. Разделяют дисциплину заполнения очередии дисциплину выбора заявок из очереди.
Дисциплиназаполнения очереди включает 4 типа:
· Естественную формузаполнения очереди, когда пришедшая заявка встает в очередь последней одна за другой
· Кольцевую форму заполненияочереди, когда заявка становится первой в очередь, если вся очередь полностью заполнена
· Поисковую форму заполненияочереди, когда заявка встает в очередь на свободное место
· Приоритетную формузаполнения очереди, когда заявки с высшим приоритетом встают в очередь первыми поотношению к заявкам с низшим приоритетом.
Дисциплинавыбора заявок из очереди предусматривает 3 принципа:
· «первым пришел – первымобслужен»
· «последним пришел– последним обслужен»
· по приоритету, т.е.заявки с высшим приоритетом обслуживаются первыми.
Приэтом бывают абсолютные приоритеты и относительные приоритеты. Заявки с абсолютнымприоритетом полностью выбивают заявки с низшим приоритетом, которые в последствиипокидают систему и не обслуживаются. Заявки с относительными приоритетами выбиваютзаявки с низшим приоритетом, которые в последствии либо дообслуживаются, либо обслуживаютсязаново.
Приборили канал обслуживания – это устройство, в котором проводится непосредственное обслуживаниезаявки. В зависимости от количества приборов обслуживания системы массового обслуживанияразделяются на одноканальные, однофазные, многоканальные, многофазные и смешанныеили комбинированные. В многоканальных системах несколько приборов обслуживания соединеныпараллельно, а в многофазных – последовательно.
Основнойхарактеристикой прибора обслуживания является продолжительность обслуживания, т.е.среднее время обслуживания одной заявки τобс, которая равна
τобс = /> (3)
гдеМ – интенсивность обслуживания.
Выходнойпоток заявок характеризуется потоком обслуженных и не обслуженных заявок. Но данныехарактеристики не позволяют судить о качестве функционирования СМО. Поэтому в качествевходного потока используются различные вероятностные характеристики качества обслуживания:
А –абсолютная пропускная способность системы, т.е. среднее количество заявок обслуженныхв единицу времени
q – относительная пропускнаяспособность, т.е. средняя доля обслуженных заявок
Ротк– вероятность отказа системы
Робс– вероятность обслуживания
/> — среднее количество заявок в очереди
/>ож –среднеевремя ожидания в очереди
/>сист -среднеевремя пребывания заявок в системе
/> -среднее количествозанятых каналов обслуживания
Кпр-коэфицентпростоя системы
Методымоделирования СМО
Длямоделирования СМО на ЭВМ ее процесс функционирования преобразуется в моделирующийалгоритм, с помощью которого имитируются все элементарные явления составляющие данныйпроцесс. При этом в алгоритме сохраняется логическая структура, последовательностьпротекания во времени, характер и состав информации о состояниях процесса.
Моделирующийалгоритм представляется в виде структурной схемы (блок- схемы), содержащей последовательностьблоков, каждый из которых отображает одну или группу элементарных операций. Примоделировании СМО на ЭВМ используются три основных метода:
1. Принцип ∆t
2. Принцип особых состояний
3. Принцип последовательнойпроводки заявок
Согласнопринципу ∆t процесс перехода системы из одного состоянияв другое рассматривается во времени на каждом шаге ∆t, начиная с момента времени t0. Конкретное состояние системы Si(t)выбирается по жребию. Так, если система имеет состояния: S1 — поступление заявки, S2-освобождение прибора и т.д. то на оси времени (Рис.3)через каждыеинтервалы ∆t по жребию определяется наступило это состояниеили нет. Если да, система переводится в это состояние, а если нет, то делается новыйшаг ∆t и так далее.
∆t ∆t
/>
/>/>/>/>/>/>/>/>/> t
/>/> t0 t1 t2 t3 t4 t5 ………………... tn
Рис.3 Переход системы из одного состояния в другое по принципу ∆t
Нарисунке показано, что в момент времени t2 пришла заявка. Поэтому она встает на обслуживание, а в моментt4 прибор освобождается.
К недостаткамэтого метода относятся:
1. метод имеет множество“холостых ходов”, когда система не изменяет своего состояния
2. метод критичен к выборуинтервала ∆t
3. метод наименее экономиченс точки зрения времени реализации его на ЭВМ
Принципособых состояний заключается в том, что в отличии от принципа ∆t в нем фиксируются только моменты переходов системы из одного состоянияв другое. Выделяют моменты наступления событий и особые состояния. Начиная с моментавремени t0на оси системного времени определяют первый момент (приходзаявки), по нему в зависимости от состояния системы следует перевести ее в новоесостояние. Затем выбирается второй момент (освобождение заявки), по нему опять системапереводится в новое состояние и т.д… В этом случае переход системы производитсяот одного события к другому. Общая схема моделирующего алгоритма по особому состояниюпредставляется в виде (Рис. 4).
/>
Б.О.О.С.
/> /> /> /> /> /> /> />
Б.А.С.N
……. /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> />
БМС1, Р
БМС1,1
БМСN.M
БМСN.1
БМС2, К
БМС2,1 />
/>/>/>/>/>/> .. .. .. ../> /> /> /> /> /> /> /> /> /> /> /> /> /> />
Рис.4Блок- схема моделирующего алгоритма по принципу особого состояния
Б.О.О.С-блок определения очередного события
Б.А.С.– блок анализа состояния
БМС–блок модификации состояния
БООСопределяет моменты времени наступления событий на оси системного времени, фиксируетвремя события, которое происходит за минимальное время. Затем БАС анализирует состояниеили ситуацию в системе (например, прибор занят, свободен или ремонтируется). В зависимостиот состояния системы БМС изменяет ее состояние (например, отметить, что он освободилсяи т.п.) После изменения состояния переходят к новому событию на БООС. В этом жеблоке также отмечается начало и окончание моделирования.
Прииспользовании данного метода удобно выделить события и состояния, которые можнопредставить в виде матрицыаij:
Очередноесобытие Состояние прибора
Свободен Занят Ремонт
Началомоделирования а11 а12 а13
Поступлениезаявок а21 а22 а23
Началоремонта а31 а32 а33
Освобождениеприбора после ремонта
а41
а42
а43
Освобождениеприбора после обслуживания
а51
а52
а53
Окончаниемоделирования а62 а62 а63
Тогдав зависимости от события и состояния в СМО производится соответствующее изменениесостояния.
Принциппоследовательной проводки заявок является наиболее экономичным из всех принципов.Он заключается в том, что судьба каждой заявки прослеживается в порядке ее поступленияв систему до ее выхода из нее. Заявка проходит все этапы обработки: она может поступитьв очередь или на обслуживание; покинуть прибор полностью или частично быть обслуженной;перейти вновь в очередь или к другому прибору обслуживания и т.д. В соответствиис данным принципом моделирующий алгоритм должен отказать работу всех элементов СМО.Дополняя его блоками управления и анализа состояний, получим следующую блок- схемумоделирующего алгоритма (Рис.5)
/> /> /> /> /> /> /> /> />
10 Рисунок5. Обобщенная блок- схема/>/>
моделирующего алгоритма СМО
III.Заданиена выполнение работы
Имеетсяторговый центр, в котором работает n продавцов.Центр обслуживает поток покупателей, приходящих с интенсивностью λ (чел/мин)среднее время обслуживания одного покупателя каждым продавцом составляет />обс(мин).Помещение, в котором располагается торговый центр, может поместить (во время образованияочередей) не более m покупателей. Покупатель, прибывающий,когда все m мест в очереди заняты, покидает торговыйцентр, т.е. не обслуживается и получает отказ.
Необходимоопределить оптимальное количество продавцов в торговом центре, чтобы среднее времяпребывания покупателей в торговом центре не превышало заданного времени tзад. (мин), т.е. чтобы выполнялось условиеtсист/> tзад, а также вероятностные характеристики обслуживания покупателейв данном центре при найденном оптимальном количестве продавцов:
1. Вероятность отказа;
2. Относительную и абсолютнуюпропускную способности;
3. Среднее число покупателейстоящих в очереди;
4. среднее число занятыхпродавцов;
5. Коэффициент простоязанятых продавцов;
6. Среднее время пребыванияпокупателей в торговом центре;
Исходныеданные к заданию приведены в Таблице 1. Варианты задания выбираются в соответствиис порядковым номером студента по групповому журналу.
IV Порядок выполненияработы
Длявыполнения задания необходимо:
1.Представить торговый центр в виде системы массового обслуживания. Для чего следуетпроизвести постановку задачи, проанализировать условия задачи, определить параметры(элементы) СМО и сформулировать цель решения задачи.
2.описать основные принципы моделирования СМО на ЭВМ
3.Разработать моделирующий алгоритм и составить блок — схему имитации торгового центрана ПЭВМ.
4.Составить программу моделирования торгового центра на одном из языков программирования.
5.Получить результаты моделирования на ПЭВМ и дать их физическую интерпретацию
6.Привести листинг программы с полученными результатами моделирования.
7.Оформить отчет.
/> /> /> /> /> /> /> /> /> /> /> /> /> /> />
/>
/> Да/> /> /> /> /> /> /> /> /> />
/> Нет
/>
/>
/>
/>/> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> />
Листингпрограммы
/>
Private Sub Command1_Click()
Dim l As Integer, m As Integer, tzad As Integer, Kmax As Integer
Dim Tobs As Variant
Dim Tosv() As Double
Dim Toch() As Double
Dim Potk As Double
Dim q As Double
SumL = 0
n = 1
5: SumP = SumP + Pmin
n = n + 1
x = 0.5
k = 0
Kotk = 0
Noch = 0
Toj = 0
Tsis = 0
Kobs = 0
Tnezan = 0
Tpost = 0
l = Val(Text1.Text)
Tobss = Val(Text2.Text)
m = Val(Text3.Text)
tzad = Val(Text4.Text)
Kmax = Val(Text5.Text)
ReDim Toch(m) As Double
ReDim Tosv(n) As Double
For i = 1 To n
Tosv(i) = 0
Next i
10: x = Rnd(x)
T = -1 / l * Log(x)
Tpost = Tpost + T
k = k + 1
If k > Kmax Then
GoTo 100
End If
30: Pmin = 1
Tmin = Tosv(1)
For i = 1 To n
If Tosv(i)
Pmin = i
Tmin = Tosv(i)
End If
Next i
If Tpost
GoTo 20
Else
GoTo 40
End If
20: If Noch = m Then
Kotk = Kotk + 1
GoTo 10
Else
Noch = Noch + 1
SumL = SumL + Noch
Toch(Noch) = Tpost
GoTo 10
End If
40: If Noch = 0 Then
Kobs = Kobs + 1
Tnezan = Tpost — Tosv(Pmin)
x = Rnd(x)
Tobs = -1 / (1 / Tobss) * Log(x)
Tosv(Pmin) = Tpost + Tobs
Tsis = Tsis + Tobs
GoTo 10
Else
Voj = Tosv(Pmin) — Toch(1)
For i = 1 To Noch — 1
Toch(i) = Toch(i + 1)
Next i
Noch = Noch — 1
Toj = Toj + Voj
x = Rnd(x)
Tobs = -1 / (1 / Tobss) * Log(x)
Tsis = Tsis + Tobs + Voj
If Tsis > tzad Then GoTo 5
Tosv(Pmin) = Tosv(Pmin) + Tobs
Kobs = Kobs + 1
oTo 30
End If
100: Potk = Kotk / Kmax
q = 1 — Potk
A = q * l
Ls = SumL / Kmax
Ps = SumP / n
Kpr = Tnezan / Tsis
Text6.Text = Str(Potk)
Text7.Text = Str(q)
Text8.Text = Str(A)
Text9.Text = Str(Ls)
Text10.Text = Str(Ps)
Text11.Text = Str(Kpr)
Text12.Text = Str(Tsis)
Text13.Text = Str(n)
EndSub