Введение в компьютерное моделирование. Л. В. Горчаков в в в в е е д д е е н н и и е е в в к к о о м м п п ь ь ю ю т т е е р р н н о о е е м м о о д д е е л л и и р р о о в в а а н н и и е е учебное пособие

• Название: Л. В. Горчаков в в в в е е д д е е н н и и е е в в к к о о м м п п ь ь ю ю т т е е р р н н о о е е м м о о д д е е л л и и р р о о в в а а н н и и е е учебное пособие
• Дата: 13.04.2023
• Размер: 1.03 Mb.
• Имя файла: Введение в компьютерное моделирование.pdf
• Тип: Учебное пособие; #1059250
• страница: 8 из 9

7.2. Интервалы времени между заказами
Пусть время обслуживания заказа – Т и распределение числа за- казов, поступивших в течение этого Т, имеет пуассоновский харак- тер, т.е. при среднем числе заказов

, поступающих в течение неко- торого промежутка времени, вероятность появления точно n зака- зов за это время определяется формулой
 
!
F n
e
n

 
(55)
Тогда, если средняя продолжительность интервала времени между заказами равна а, то среднее число поступивших заказов

= T/a. В теории массового обслуживания показано, что плотность распреде- ления вероятностей для промежутков времени
t
a
между моментами поступления заказов будет определяться по экспоненциальному закону
 
ta
a
P t
e

 
(56)
Если поток на одной станции подчиняется экспоненциальному за- кону распределения, то при заданной скорости поступления зака- зов

и постоянном времени обслуживания

средняя длина очере- ди задается выражением






2 1
2 1
n
    
  
(57)
Таким образом, характер поведения очереди зависит от

/

. При уменьшении

/

длина очереди сокращается. Решение проблемы очереди сводится к подбору определенного соотношения между затратами на сокращение длины очереди и издержками из-за недо- статочного использования средств обслуживания. Среднее время

78 ожидания на одной станции при экспоненциальном распределении с отрицательным показателем определяется выражением


1 1
t

    
, а среднее время обслуживания
t
s
= 1/

Иллюстрацию появления и движения заявок в очереди можно представить в виде рис. 21.
Рис. 21. Времена ожидания
Цифры на графике соответствуют порядку поступления заявок в систему, а время ожидания определяется по отношению к общей продолжительности рассматриваемого интервала. Легко видеть, что площадь под ступенчатой кривой равна произведению nT, где n среднее число заявок в системе. Общая площадь квадратов, поме- ченных цифрой 3, равна 6. Это означает, что общее время ожида- ния третьего требования на интервале Т составило 6 единиц. То же касается и требований 4,5,6. Площадь под кривой включает время ожидания требований, поступивших на интервале Т и обслуженных на нем, плюс время ожидания требований, поступивших до начала этого интервала, плюс время ожидания требований, попавших за интервал Т в систему, но не обслуженных за это время. Тогда

W = n, где W – среднее время ожидания, n – длина очереди,

– средняя интенсивность поступления требований на интервале.
7.3. Имитация задач теории массового обслуживания [3]
Раccмотрим одноканальную однофазовую модель. В ней систе- ма состоит из одной станции, на которую поступают заявки, обра- зующие очередь. Если станция свободна, то она приступает к об-

79 служиванию той заявки из очереди, которая стоит первой. Проме- жуток времени между появлениями двух последовательных заявок и время обслуживания считаются случайными величинами с задан- ными функциями распределения. Введем следующие обозначения:
WT – среднее время ожидания заявки в очереди,
IDT – среднее время простоя системы в ожидании очередного требования,
Wti – время ожидания i-ой заявки,
IDTi – время простоя системы в ожидании i-ой заявки,
Ati – интервал между появлениями i-ой и I + 1-ой заявками,
Sti – время обслуживания i-ой заявки, I = 1,2,3,…m,
F(AT) – функция распределения плотности вероятностей интер- вала времени между двумя последовательными заявками,
F(ST) – функция распределения плотности вероятностей време- ни обслуживания.
1 1
1
,
1
m
m
i
i
i
i
WT
m
WT
TWT m IDT
m
IDT
TIDT m








. (58)
Блок-схема программы приведена на рис. 22.
В блоке 1 обнуляется время появления первой заявки, время ее ожидания, время простоя системы в ожидании ее прихода, полное время ожидания и простоя и фиксируется факт появления первой заявки. Блок 2 генерирует относительное время появления следу- ющей заявки. Оно отсчитывается от момента прихода предыдуще- го требования. В блоке 3 из полученной величины отнимается вре- мя ожидания предыдущей заявки. Эта разность определяет новое значение относительного времени прибытия нового требования.
Его отсчет ведется теперь от момента начала обслуживания предыдущей заявки. Продолжительность этого обслуживания определяется в блоке 4. Если она превышает относительное время появления новой заявки, последней придется постоять в очереди.
Время ожидания нового требования в этом случае равно разности между продолжительностью обслуживания предыдущей заявки и относительным временем его появления. Эта разность вычисляется в блоке 7, после чего в блоке 8 пересчитывается полное время ожи- дания в системе. Если же относительное время появления новой заявки больше времени обслуживания предыдущего требования, ждать ей не придется, зато возникает простой, продолжительность которого вычисляется в блоке 12 как разность этих времен. В сле-

80 дующем блоке пересчитывается полное время простоя системы.
Если относительное время появления и время обслуживания равны, ни простоя, ни ожидания не возникает. Цикл, начинающийся с бло- ка 2, можно повторять много раз и таким образом рассматривать произвольное число заявок. В результате можно найти оценки ста- тистических характеристик системы.
Рис. 22. Блок-схема расчетов по одноканальной однофазовой модели массового обслуживания
Рассмотрим работу многоканальной системы массового обслу- живания с неограниченной очередью (рис. 23) [18]
Рис. 23. Система массового обслуживания с неограниченной очередью
В данной системе возможны два события:
1) поступление заявок из источника на обслуживание (если один из приборов свободен), либо в очередь;

81 2) окончание обслуживания очередной заявки, поступление ее на приемник и выбор следующей заявки из очереди (если очередь не пуста).
Блок управления моделью определяет, какое из событий настанет раньше и присваивает системному времени значение, равное вре- мени наступления этого события. Затем управление передается на блоки, имитирующие работу отдельных устройств, и выполняются действия, связанные с данным событием. Например, при поступле- нии очередной заявки из источника необходимо:
1) сгенерировать время поступления следующей заявки;
2) если все каналы заняты – увеличить длину очереди на одну заявку;
3) если есть свободный прибор, то пометить его как занятый и сгенерировать время окончания обслуживания заявки.
Обозначим t – модельное время,

– длина очереди, k – число заня- тых каналов, m – общее число каналов, ns – число обслуженных заявок,

– псевдослучайная величина, распределенная равномерно на отрезке [0,1], tp – время поступления очередной заявки в систе- му, ts[1: m] – упорядоченный по возрастанию массив времен окон- чания обслуживания заявок на занятых каналах,


и


– первый и второй моменты распределения длины очереди.
Считаем, что время между поступлением заявок распределено экспоненциально с параметром

, а время обслуживания также распределено экспоненциально с параметром

. Моделирование прекращаем после обслуживания 10 заявок. По определению, пер- вый и второй моменты распределения длины очереди равны




2 1
2 0
0
;
i
i
i P
i
i P
i




 

 
 
 


,
(59) где P(

= i) –вероятность того, что длина очереди равна i. В каче- стве оценки вероятности P(

= i) будем использовать отношение времени, которое длина очереди была равна i , к общему времени моделирования. Для исходных данных






m


блок- схема алгоритма приведена на рис. 24.

82
Рис. 24. Алгоритм моделирования

83
Задачи для самостоятельной работы
1. Время между последовательными прибытиями покупателей равномерно распределено в интервале от 1 до 20 минут. Для 50 % покупателей время обслуживания – 8 минут, для остальных – 14 минут. Какие генераторы нужно взять? Определите суммарное время ожидания покупателей и время простоя системы за 4 часа работы магазина.
2. По блок-схеме рис. 25 напишите программу и определите ве- роятности P(

= i),


и


Постройте таблицу значений t, tp, ts(1),
ts(2), ts(3), k,

, ns и график зависимости

от t.
3. Имеется одноканальная СМО с очередью ограниченной дли- ны. Время между поступлением заявок распределено равномерно на отрезке [0,2], время обслуживания имеет экспоненциальное рас- пределение с параметром

= 1. Длина очереди n = 1. Если очередь заполнена, то поступившее вновь требование покидает СМО без обслуживания. Моделирование закончить после обслуживания за- данного числа заявок. Построить заданные характеристики для длины очереди.
Имеем многоканальную СМО с отказами без очереди. Если все каналы заняты, заявка, вновь поступившая в систему, покидает си- стему без обслуживания. Время между поступлением заявок рас- пределено экспоненциально, с параметром

= 1. Количество кана- лов m = 2. Время обслуживания заявок на каждом приборе распре- делено равномерно на отрезке [0, 1]. Моделирование закончить при достижении заданного модельного времени Т. Постройте заданные характеристики для количества занятых каналов.
Блок-схемы алгоритмов для решения этих задач можно найти в
[16, 17].
7.4. Стохастическая модель дорожного движения [10]
Пусть машины по дороге движутся в один ряд так, что пешехо- ду требуется определенное время, чтобы пересечь улицу. Пусть пешеход приходит в точку, из которой начнет переход улицы в мо- мент, когда только что прошел автомобиль (рис. 25).

84
Рис. 25. Модель ожидания пешехода
Мы интересуемся ответами на такие вопросы: вероятность ожи- дания определенного времени (задержки) пешехода и величина времени ожидания. Правила поведения пешехода: решение начать переход зависит от близости и скорости ближайшего автомобиля. В задачах об ожидании временной интервал более существенен, чем пространственный. Учет их можно провести, наблюдая за времен- ными интервалами в потоке машин, т.е. за временем, которое тре- буется ближайшему автомобилю, чтобы доехать до пешехода.
Время между прохождениями двух последовательных автомобилей будем называть интервалом и измерять от времени появления в точке перехода переднего бампера автомобиля до времени появле- ния бампера второго автомобиля. Каждому человеку свойственен свой критический временной интервал между появлениями авто- мобилей. Простейшая из возможных моделей вида интервал- решение приведена на рис. 26 и имеет вид функции Г(t) = 0, если
t
T

и 1, если
t
T

Распределение во времени движения автомобилей определяется распределением вероятностей интервалов между автомобилями в ряду. Простейшим предположением относительно него является случайное распределение пуассоновского типа. Постоянная

определяет плотность транспортного потока, т.е. среднее число ав- томобилей, приходящих в точку перехода за единицу времени. Для плотности автомобилей более 600 авто в час, т.е. при среднем вре- менном интервале между автомобилями < 4.5 сек поток будет не пуассонов. Распределение числа машин определяет вероятность прибытия любого данного числа машин в данную точку за единицу

85 времени. Если обозначить P(k) – вероятность прибытия k машин за единицу времени, получим распределение Пуассона
 


!,
0,1, 2...
k
P k
e
k
k




(60)
Рис. 26. Ступенчатая функция интервал-решение
Другое – распределение интервалов – дает вероятность суще- ствования пробела или интервала длиной величины t. Это распре- деление будет экспоненциальным с плотностью вероятности вида
 
,
0
t
F t
e
t

 

(61)
(для предположения, что автомобиль имеет длину 0). Для конечной длины автомобиля

оно примет вид (рис. 27)
 


t
t
e
 

 
(62)
Рис. 27. Экспоненциальное распределение и экспоненциальное распределение со сдвигом
Вероятность появления интервала, превышающего данное Т, опре- деляется соотношением


интервал
T
T
t
T
P
T
e
dt
e








(63)

86
Для транспортного потока с плотностью 600 автомобилей в час

= 1/6 автомобиля в секунду. Если пешеходу требуется для пере- хода не менее 8 секунд, вероятность того, что он перейдет улицу без задержки составляет
8 6
0, 2636
e


. Действительное время ожидания получается суммированием случайных временных ин- тервалов. Так как автомобиль имеет длину, то время между про- хождениями двух автомобилей всегда больше 0. Средний времен- ной интервал при


0 равен (1/

+

). Распределение времени ожидания описывается функцией плотности вероятности
 
 
 


 



1 1
0 1 !
!
,
T
T
j
j
r
T
i
j
W t e
t
e
e
t jT
j
t jT
j









 

 
 







  







(64) где (r–1)T

t

rT, r =1, 2, .., а выражение для w

(s) в случае экспо- ненциального распределения имеет вид
  





s T
T
W s
s e
s
e
 

  
 
(65)
Стандартный результат теории вероятностей гласит:
– среднее время ожидания
 
0
s
dw s
ds


;
(66)
– дисперсия
 
 


2 2
2 0
s
d w s
ds
dw s ds


(67)
Это приводит к следующим выражениям:
– среднее время ожидания


1 1
T
e
T


  
;
(68)
– средняя дисперсия времени ожидания


2 2
1 2
1
T
T
e
Te



 

(69)
Таким образом, при Т = 8с,

= 1/6 машин/c среднее значение вре- мени ожидания равно 6[e
4/3
–7/3] = 8.8c.

87
8.
Я
ЗЫКИ ИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ
Для решения задач компьютерного моделирования кроме обыч- ных алгоритмических языков программирования и оболочек типа
Mathcad используются также специализированные алгоритмиче- ские языки имитационного моделирования (SPL). Полное изложе- ние таких языков и способов решения задач с их помощью выходит за рамки намеченных целей. Поэтому мы ограничимся лишь крат- ким обзором. Языки SPL разрабатывались в качестве аппарата про- граммного обеспечения имитационного подхода и изучения опре- деленного класса систем. К ним относятся, например такие языки как CSL-язык работ, GPSS- язык транзактов, Симула-язык процес- сов, Симскрипт-язык событий. Имитация здесь представляет собой метод воспроизведения функционирования моделирующей систе- мы во времени. Чтобы смоделировать на ЭВМ поведение сложной реальной системы в языке должны быть предусмотрены:
1) способы организации данных, обеспечивающие простое и эффективное моделирование,
2) удобные средства формализации и воспроизведения динами- ческих свойств моделируемой системы,
3) возможности имитации стохастических систем, т.е. процеду- ры генерирования и анализа случайных величин и временных ря- дов.
Языки имитационного моделирования должны позволять опи- сывать статическую и динамическую структуру модели (возмож- ные формы существования системы – классы объектов, свойства объектов, связи объектов между собой и со средой, формирование системного времени и управляющую программу). Например, в языке GPSS элементы потока называются транзактами. При ими- тации они создаются и уничтожаются. Транзакт имеет набор пара- метров. Отношения между транзактами устанавливаются разбие- нием их на группы, допускающие анализ и модификацию своего состава. Для моделирования обслуживающих объектов системы, подверженных воздействию транзактов, предусмотрен специаль- ный класс элементов: установки, склады и переключатели. В каж- дый момент времени установка может обслуживать только один транзакт. На складе могут находиться одновременно несколько транзактов. Переключатели регулируют потоки и имеют два поло- жения, которые меняются по указаниям самих транзактов. Для

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

89