Output Summary 1 страница

14 'Av. facility utilization = 15]Percent idleness (%) =

16 /laximum queue length:

17 «v queue length, Lq =

18 iAv nbr in system, Ls =

19 Av queue time. Wq = Й A«■system time, Ws =

21 'Sum(ServiceTime) -

22 Sum(Wq) =

23Sum(Ws)= _

0 92 7.92

1 13

2 05 15.33 •?-! B7

250 75 306 63 557 38

Press F9 to

trigger a

new simulation run

Nbr llnterArvlTirrServiceTime ArrvlTime DeparfXime,	Wq	Ws
	5 53	10.83	0 00	10.83	0.00	10.83
	14 32	10 35	5.53	21.19	5 30	15.66
	25 87	12.66	19.85	33.85	1 34	14 00
	1 63	12 11	45 72	57 83	0.00	12 11
	4 18	12.541	47.35	70 37	10 48	23.02
	6.91	12 86	51.53,	83.23	18 84	31 70
	4 84	12.08	58 43	95.30	24.79	36 87
	22 12	10.18	63 27	105 48	32.03	42 21
	1 86	13 18	85.39	118.67	20 09	33 28
	20 41	14.98	87.25	133.65	31.42	46 40
	6 47	13.41	107 66	147 06	25.99	39.40
	10.82	14 12	114.13!	161 17	32.93	47 04
	11.50	12.32	124.95	173.50	36.22	48 54
	43 87	14.67'	136 45	188 16	37.04	51.71
		13.62'	180.32	201 78	7.84	21.46
	10.15		196.13	215.25	5.65
	15.23	13.96	206.28	229 21	8.96	22 93
	18 58	10.88	221.51	240 09	7.70	18 58
	21 65	11.97)	240.10	252.06	0 00	11 97
	13.62	10.561	261.75	272.31	0 00	10 56

Рис. 18.9. Результаты имитации модели с одним сервисом в Excel

В шаблоне каждому поступлению клиента в систему соответствует одна строка. Время между поступлениями и время обслуживания для каждого клиента гене­рируются на основе исходных данных. Предполагается, что первое поступление

18.5. Механика дискретной имитации

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

(время ухода клиента 1) = (время прихода клиента 1) 4- (время сюслуживания клиента 1) =

= 0+ 14,35 = 14,35,

(время прихода клиента 2) = (время прихода клиента 1) + (время между прихо­дами клиентов) = = 0+ 15,15= 15,15.

Для определения времени ухода других клиентов i используется следующая формула:

(время ухода^ \(время прихода^ (время ухода^ j (время обслуживания^

^ клиента; J Н клиента/)' у клиента /-lj] ^ клиента/

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

время ухода клиента 3 = тах{18,89, 26,41} + 14,86 = 41,25.

Теперь обратим внимание на то, как формируются статистические данные мо­дели. Сначала заметим, что для клиента i время ожидания в очереди W (I) и время пребывания в системе W_s(i) вычисляется по таким формулам:

время ухода^\ (время прихода⁴] (время обслуживания ^ клиента / J ^ клиента / J ^ клиента /

^ (время ухода⁴ время прихода^ ^ клиента /) \ клиента /)

Может показаться, что для вычисления оставшихся статистических данных имитации модели необходимо отслеживать изменения в использовании сервиса и длины очереди, как это делалось в разделе 18.5.1. Но, применяя формулы, при­веденные в конце раздела 18.5.1 (объяснение к которым дано на рис. 18.8), вычис­ления можно упростить, если использовать следующие соотношения.

1. Область под кривой использования сервиса = сумма времени обслуживания всех клиентов.

2. Область под кривой длины очереди = сумма времени ожидания всех клиентов.

Для использования этих соотношений вычисляется три суммы (ячейки Е21:Е23 на рис. 18.9):

сумма времени обслуживания = 248,66,

сумма значений W = 513,14,

сумма значений W_t = сумма значений W_q + сумма времени обслуживания = = 761,80 (= 248,66 + 513,14).

Поскольку последний клиент (клиент 20) ушел в момент времени Т = 252,64, следовательно

среднее время использования сервиса = 248,66/252,64 = 0,9842, средняя длина очереди = 513,14/252,64 = 2,03,

среднее время простоя сервиса, выраженное в процентах, вычисляется как

(1 - 0,9842) х 100 = 1,575 %. Остальные статистические данные вычисляются обычным образом.

Глава 18. Имитационное моделирование

Среднее время ожидания в очереди = сумма значений W^/число клиентов =

= 513,14/20 = 25,66.

Среднее время пребывания в системе = сумма значений И^/число клиентов =

= 761,81/20 = 38,09.

Максимальное количество клиентов, генерируемое шаблоном, не должно пре­вышать 500.

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

УПРАЖНЕНИЯ 18.5.2

1. Используя исходные данные из раздела 18.5.1, выполните в Excel имитацию 10 поступлений клиентов и постройте график изменения использования сер­виса и длины очереди как функцию от времени имитации. Проверьте, что площади под соответствующими кривыми равны сумме времени обслужива­ния и сумме времени ожидания.

2. Имитируйте модель типа М/М/1 для 500 поступлений при условии, что интен­сивность поступлений X равна 4 клиентам в час и интенсивность обслуживания ц составляет 6 клиентов в час. Повторите имитацию 5 раз (обновив значения на рабочем листе нажатием клавиши <F9>) и определите 95%-ные доверитель­ные интервалы для всех полученных оценок показателей работы модели.

3. Комплектующие для телевизоров поступают по конвейеру каждые 11,5 мин. для проверки на испытательном стенде, обслуживаемом одним оператором. Детальная информация по работе испытательного стенда недоступна. Тем не менее, по оценке оператора, он тратит "в среднем" 9,5 мин. на проверку од­ной детали. В наихудшем случае время проверки не превышает 15 мин., а для некоторых комплектующих время проверки составляет менее 9 мин.

a) Используйте шаблон Excel для имитации проверки 200 комплектующих для телевизоров.

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

18.6. МЕТОДЫ СБОРА СТАТИСТИЧЕСКИХ ДАННЫХ

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

1. Наблюдения имеют стационарные распределения, т.е. распределения не из­меняются во время проведения эксперимента.

2. Наблюдения подчиняются нормальному распределению.

3. Наблюдения независимы.

18.6. Методы сбора статистических данных

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

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

Рассмотрим теперь второе требование, состоящее в том, что наблюдения над имитационной моделью должны иметь нормальное распределение. Это требование можно выполнить, если привлечь центральную предельную теорему (см. раз­дел 12.4.4), утверждающую, что распределение среднего выборки является асим­птотически нормальным независимо от распределения генеральной совокупности, из которой взята выборка. Центральная предельная теорема, таким образом, есть главное средство удовлетворения требования о нормальности распределения.

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

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

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

18.6.1. Метод подынтервалов

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

Глава 18. Имитационное моделирование

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

Переходный

период Группа 1 Группа 2

Группа п

Время имитации

Рис. 18.10. Иллюстрация к методу интервалов

Пример 18.6.1

На рис. 18.11 показано изменение длины очереди в системе обслуживания с одним сервисом (модель простой очереди) как функции времени. Период имитации со­ставляет Т= 35 часов, а длина переходного периода оценивается в 5 часов. Необхо­димо получить 5 наблюдений, т.е. п = 5. Соответствующая длина интервала времени для каждой группы равна (35 - 5)/5 = 6 часов.

Длина

очереди Q

Переходный
период | Группа 1 _ Группа 2	, Группа 3,	Группа 4	Группа 5,
~*--Н**-* _._,J L ^2='оГ	т*-»1 |Lj3=n	**-** А4=6Г>	**-Н
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1	|.....1	_1 . 1 Г.. 1	Л5=15Ц 1 1 1 1 1 1

J_I_I_I_I_I_I_I_I_I_I_I_I_I_I_I_I_I_I_I_I_I_I_I_I_I_I_I_I_I_I_I

5 10 15 20 25 30 35

Время имитации Рис. 18.11. Изменение длины очереди

Пусть g представляет среднюю длину очереди в группе /'. Так как длина очереди является переменной, зависящей от времени, то

Q,=—, / = 1,2,...,5, t

где А-, — площадь под кривой длины очереди, t — длина интервала времени для группы. В рассматриваемом примере t = 6 часов.

18.6. Методы сбора статистических данных 729

Анализ данных, приведенных на рис. 18.11, приводит к следующей таблице.

Наблюдение/
А
а	2,33	1,67	1,83	1,00	2,5
Выборочное среднее	= 1,87		Выборочная дисперсия = 0,35

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

Вычисление выборочной дисперсии в этом примере основано на использовании следующей хорошо известной формулы:

5>.-*)²

Эта формула является лишь приближением точного значения дисперсии, так как не учитывает эффекта автокорреляции между последовательными группами. Точ­ную формулу можно найти в работе [2].

18.6.2. Метод повторения

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

Преимуществом этого метода является то, что каждый имитационный прогон модели определяется своей последовательностью случайных чисел из интервала [О, 1], что действительно обеспечивает статистическую независимость получаемых наблюдений. Недостаток состоит в том, что все наблюдения могут оказаться под сильным влиянием начальных переходных условий. Этот недостаток можно смяг­чить, увеличив длину прогона модели.

Группа п

Т Т

Рис. 18.12. Иллюстрация к методу повторения

Глава 18. Имитационное моделирование

18.6.3. Метод циклов

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

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

Вычисление среднего для цикла i в рассматриваемом методе определяется в ви­де отношения двух случайных величин а, и т.е. в виде х_: = ajb_r Определение ве­личин а₍ и Ъ_: зависит от вычисляемой переменной. Например, если переменная яв­ляется функцией времени, то а, представляет площадь под кривой, а Ь₍ — длительность соответствующего интервала времени. Если же переменная является функцией количества событий, то a_t — общая сумма наблюдений этой величины в пределах цикла i, а Ь_{ — общее число событий внутри соответствующего цикла.

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

±У. п

где

па (п-\)(па-а,)

)',=-=----=--, / = 1,2,

b nb -b_:

а=^—, Ь=^—. п п

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

Пример 18.6.2

На рис. 18.13 показано число занятых обслуживающих устройств в одноканальной сис­теме обслуживания с тремя параллельными обслуживающими устройствами. Длина периода имитации — 35 единиц времени, а длина переходного периода — 4 единицы времени. Требуется оценить среднее значение использования сервисов методом циклов.

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

18.6. Методы сбора статистических данных

Занятость Переходный оборудования / период

	/ Группа]	Группа 2 Группа 3	Группа 4
3 2 1	• 1111111! 1	,I!i!I I i i!!!I i.
	5 10	15 20 25	30 35
		Время имитации
Рис. 18.13. Изменение количества занятых сервисов как функция времени
Цикл;	а,	bi

а =8,5

Ъ =7,75

Вычисление_у, проводится в соответствии со следующей формулой:

4x8,5 (4-1)(4х8,5-а,),,_Л 102-За,

у, =----—-— = 4,39--'-.

7,75 4x7,75-/5, 31-6,

Эти вычисления выполняет шаблон Excel chl8Regenerative.xls, показанный на рис. 18.14.

	А I В	С	D		" E 1
	Regenerat	ive (Cycles) Method
	Input Data	_Output Results
	No. Batches __4
	•i bi
	12 9	1.3870968	i-		8 5000
	6 6	1 1563275	N	7 7500
	10 10	i 0.9585253	Average yi =	1.0973
В	6 7	0 8870968	Std Dev yi =	0 2243

Рис. 18.14. Вычисление в Excel задачи примера 18.6.2

УПРАЖНЕНИЯ 18.6

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

2. Пусть в имитационной модели используется метод подынтервалов для вы­числения средних величин в циклах. Переходный период — 100 единиц времени, длина каждого цикла также составляет 100 единиц времени. Ис­пользуя приведенные ниже данные, которые представляют время ожидания клиентов, как функцию времени имитации, определите 95%-ный довери­тельный интервал для среднего времени ожидания.

Глава 18. Имитационное моделирование

Интервал времени	Времена ожидания
0-100	10, 20,13, 14, 8,15, 6,8
100-200	12, 30, 10, 14, 16
200 - 300	15, 17, 20, 22
300 - 400	10, 20, 30, 15, 25, 31
400 - 500	15, 17, 20, 14, 13
500 - 600	25, 30, 15

3. Пусть в условиях примера 18.6.2 начальные точки циклов совпадают с теми моментами времени, когда все три обслуживающих устройства становятся не­занятыми. На рис. 18.13 эти точки соответствуют моментам времени t = 10, 17, 24 и 33. Определите 95%-ный доверительный интервал для занятости обслужи­вающих устройств, основываясь на новом определении точек начала циклов.

4. Для сервисной системы с одним обслуживающим устройством проводится имитация ее работы на протяжении 100 часов. Результаты имитации пока­зывают, что обслуживающее устройство было занято на протяжении таких интервалов времени: (0, 10), (15, 20), (25, 30), (35, 60), (70, 80) и (90, 95). Ос­тальное время из интервала имитации обслуживающее устройство было сво­бодно. Длина переходного периода равна 10 часов.

a) Определите начальные точки, необходимые для применения метода циклов.

b) Методом циклов определите 95%-ный доверительный интервал для вре­мени занятости обслуживающего устройства.

c) С помощью метода подынтервалов решите ту же задачу при числе интер­валов п = 5. Определите соответствующий 95%-ный доверительный ин­тервал и сравните его с результатом, полученным методом циклов.

18.7. ЯЗЫКИ ИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ

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

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

1. Языки, ориентированные на планирование событий.

2. Языки, ориентированные на обработку процессов (процедур).

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

18.7. Языки имитационного моделирования

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

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

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

Наиболее известными языками программирования, ориентированными на пла­нирование событий, являются SIMSCRIPT, SLAM и SIMAN. Развитие этих языков на протяжении многих лет привело к тому, что они включают и возможности процедур­но-ориентированных языков. Все эти языки позволяют пользователю создавать мо­дели (или их отдельные части) на языках высокого уровня, таких как FORTRAN и С. Это необходимо для того, чтобы дать возможность пользователю программировать сложные логические операции, которые невозможно или трудно осуществить обыч­ными средствами этих языков. Главной причиной этого является ограничительная и, возможно, запутанная процедура, с помощью которой данные языки перемещают транзакции (или объекты) между очередью и сервисами, присутствующими в модели.

Первым процедурно-ориентированным языком был GPSS. Этот язык, первая версия которого появилась в начале 1960-х годов, совершенствовался на протяже­нии нескольких лет, чтобы удовлетворить новым требованиям, связанным с моде­лированием сложных систем. Чтобы эффективно использовать этот язык, пользо­вателю необходимо настроить примерно восемьдесят различных блоков. Несмотря на многие годы использования GPSS, язык все еще имеет некоторые трудно объяс­нимые особенности моделирования. Примером может служить необходимость ап­проксимировать непрерывные распределения вероятностей их кусочно-линейными аналогами. Справедливости ради заметим, что некоторые последние версии этого языка обеспечивают возможности использования и непрерывных распределений (например, экспоненциального и нормального). Однако при имеющихся громад­ных возможностях современных компьютеров трудно понять, почему такое пре­пятствие продолжает так долго существовать.

В настоящее время на рынке программных продуктов для моделирования доми­нируют коммерческие пакеты, такие как Arena, AweSim и GPSS/H. Эти пакеты об­ладают развитым интерфейсом, что упрощает пользователю процесс создания ими­тационных моделей. Они также имеют анимационные средства, визуализирующие изменения, происходящие в модели во время имитации. Однако для опытных поль­