Инвестиции в В 14 страница

4. Время между приходом клиентов в парикмахерскую описывается следую­щим распределением:

/(/)=у, 12 < г < 20.

Время стрижки является случайной величиной, плотность вероятности которой

/,(/) = £, 18<г<22.

Константы k_x и к_г выбираются из условия, что функции f_t(x) и f₂(x) являются плотностями вероятностей. Используйте метод отбора (и случайные числа из табл. 18.1), чтобы определить время ухода первого клиента из парикмахер­ской и время прихода второго клиента. Предположите, что первый клиент приходит в момент времени Т = 0.

18.4. ГЕНЕРИРОВАНИЕ СЛУЧАЙНЫХ ЧИСЕЛ

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

В имитационном моделировании единственным подходящим методом генера­ции случайных чисел из интервала [0, 1] является метод, основанный на арифме­тических операциях. Такие числа не являются истинно случайными, так как они могут быть определены заранее, поэтому их называют псевдослучайными.

Наиболее часто используется мультипликативный метод сравнений, который генерирует случайные числа из интервала [0, 1] с использованием арифметических операций. В соответствии с этим методом псевдослучайное число R_n при заданных значениях параметров и₀, b,c,nm можно вычислить по следующей формуле:

^ип ⁼ {bu_n__x +c)mod(/w), «= 1,2,..., „и.

*.=—. «= 1.2,.»

18.4. Генерирование случайных чисел

Начальное значение параметра и₀ обычно называют начальным числом генератора случайных чисел.

Варианты мультипликативного метода сравнений, которые генерируют случайные числа с улучшенными статистическими характеристиками, описаны в книге [2].

Пример 18.4.1

Используя мультипликативный метод сравнений, сгенерируем три случайных чис­ла при следующих начальных данных: 6 = 9, с = 5, и₀=11или=12.

ы, =(9xli + 5)modl2 = 8, R, =^ = 0,6667,

и₂ =(9x8 + 5)modl2 = 5, Л₂ =^- = 0,4167,

M₃=(9x5 + 5)modl2 = 4, Л, = — = 0,3333.

Шаблон Excel chl8RandomNumberGenerator.xls реа­лизует описанный мультипликативный метод сравнений.⁶ На рис. 18.7 показаны случайные числа, сгенерированные в соответствии с начальными данными этого примера. Отме­тим, что сгенерированная последовательность случайных чисел состоит только из четырех различных чисел, затем эти числа повторяются. Конкретный выбор параметров и₀, Ь, с, и т яв­ляется решающим фактором, определяющим статистические качества генератора случайных чисел, а также длины его цикла (по окончании цикла генерируемая последовательность начи­нает повторять себя, как на рис. 18.7). Исполь­зование параметров, выбранных "наобум", не дает хорошего генератора случайных чисел. Надежные генераторы, наряду с достаточно большой длиной цикла генерируемых случай­ных чисел, должны пройти соответствующие статистические проверки, чтобы гарантировать равномерное распределение на интервале [0, 1] полученной последовательности. На это усло­вие нужно обращать внимание при использова­нии непроверенного программного обеспечения в качестве генератора случайных чисел.

	А	в
	Multiplicative Congruential Method
	Input data
	b =
	c =
	u0 =
	m =
	How many numbers?
_R_	Output results^^^^^
	Preii to <j»nei.
	Generated random numbers
		0.66667
		0 41667
		0.16667
		0 91667
		0.66667
16 17		0 41667
		0.91667
	s	0.66667
20,		0.41667

Рис. 18.7. Сгенерированные в Excel случайные числа

Excel обладает несколькими встроенными средствами генерирования случайных чисел. Так, функция СЛЧИС генерирует равномерно распределенные на интервале [0, 1] числа, средство Генерация случайных чисел из надстройки Пакет анализа позволяет генерировать случайные числа, имеющие различные вероятностные распределения, в том числе равно­мерное, нормальное, Пуассона. — Прим. ред.

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

УПРАЖНЕНИЯ 18.4

1. С помощью шаблона chl8RandomNumberGenerator.xls сгенерируйте последо­вательность случайных чисел с начальными параметрами Ь = 17, с= 111, и₀ = 7 и/71= 103 (см. пример 18.4.1) и определите длину цикла этой последовательности.

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

18.5. МЕХАНИКА ДИСКРЕТНОЙ ИМИТАЦИИ

Как указывалось выше, все дискретные имитационные модели в той или иной форме представляют ситуации, связанные с очередями, в которых есть два типа ос­новных событий: прибытие и уход. Эти события определяют моменты, в которые могут происходить изменения в статистике системы. В этом разделе детально об­суждаются вопросы сбора статистических данных, полученных в процессе наблю­дений над имитационной моделью. В разделе 18.5.1 на числовом примере детально рассмотрена имитация простой модели очереди с одним сервисом. В разделе 18.5.2 показана реализация такого же процесса в электронной таблице Excel.

18.5.1. Ручная имитация модели очереди с одним сервисом

Время между приходом клиентов в парикмахерскую является случайной вели­чиной, изменяющейся по экспоненциальному закону с математическим ожидани­ем 15 мин. В парикмахерской работает один мастер, который выполняет мужскую стрижку от 10 до 15 мин., время стрижки имеет равномерное распределение на этом интервале. Клиенты обслуживаются в порядке очереди. Требуется определить следующие параметры работы парикмахерской.

1. Среднюю занятость парикмахера.

2. Среднее количество ожидающих клиентов.

3. Среднее время ожидания клиента в очереди.

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

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

2. Если средство обслуживания (парикмахер) свободно,

а) начать обслуживание поступившего клиента, изменить состояние систе­мы на рабочее и скорректировать данные использования системы;

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

3. Если средство обслуживания занято, поставить поступившего клиента в оче­редь и увеличить ее длину на единицу.

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

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

1. Если очередь пуста, объявить систему свободной. Скорректировать данные использования системы.

2. Если очередь не является пустой,

а) начать обслуживание первого в очереди клиента. Уменьшить длину оче­реди на единицу и скорректировать данные использования системы;

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

В рассматриваемом примере время между приходом клиентов изменяется по экспоненциальному закону с математическим ожиданием 15 мин., а время обслу­живания распределено равномерно в интервале от 10 до 15 мин. Обозначим через р и q случайные значения времени между прибытием клиентов и их обслуживанием соответственно. Используя результаты раздела 18.3.2, получаем

р = -10 1п(Д) мин., 0 < R <1,

q = 10 + 5Rмин., 0<R <1.

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

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

Прибытие клиента 1 в момент Т = 0. Второй клиент прибудет в момент времени

Т = 0 +р, = -15 1п(0,0589) = 42,46 мин.

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

Г=0+д₁ = 10 + 5х 0,6733 = 13,37 мин. Получаем следующий хронологический перечень будущих событий

Время Т	Событие
13,37	Уход клиента 1
42,48	Приход клиента 2

Уход клиента 1 в момент Т = 13.37. Так как очередь пуста, средство обслужива­ния становится свободным. В то же время фиксируем, что система была занята от момента времени 7' = 0 до Т'=13,37. Имеем следующий скорректированный пере­чень будущих событий (в данном случае имеется только одно событие).

Время Т	Событие
42,48	Приход клиента 2

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

Прибытие клиента 2 в момент Т = 42,48. Третий клиент прибудет в момент времени

Т = 42,48 + [-15 1п(0,4799)] = 53,49 мин.

Так как средство обслуживания свободно, начинается обслуживание второго клиен­та, и система объявляется занятой. Второй клиент оставит систему в момент времени

Т = 42,48 + (10 + 5 х 0,9486) = 57,22 мин.

Список будущих событий изменяется следующим образом.

Время Т	Событие
53,49	Приход клиента 3
57,22	Уход клиента 2

Прибытие клиента 3 в момент Т = 53,49. Клиент 4 прибудет в момент времени

Т = 53,49 + [-15 1п(0,6139)] = 60,81 мин.

Так как система в это время занята (она занята до Т = 57,22), третий клиент по­мещается в очередь в момент Т — 53,49. Откорректированный список будущих со­бытий принимает следующий вид.

Время Г	Событие
57,22	Уход клиента 2
60,81	Приход клиента 4

Уход клиента 2 в момент Т = 57,22. Клиент 3 покидает очередь для начала об­служивания. Время его ожидания в очереди равно

W₃ = 57,22 - 43,22 = 3,73 мин.

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

Т = 57,22 + (10 + 5 х 0,5933) = 70,19 мин.

Список будущих событий принимает следующий вид.

Время Т	Событие
60,81	Приход клиента 4
70,19	Уход клиента 3

Прибытие клиента 4 в момент Т = 60,81. Клиент 5 прибудет в момент времени

Т = 60,81 + [-15 1п(0,9341)] = 61,83 мин.

Так как система занята до Т = 70,19, четвертый клиент помещается в очередь. Откорректированный список будущих событий принимает следующий вид.

Время 7"	Событие
61,83	Приход клиента 5
70,19	Уход клиента 3

Приход клиента 5 в момент Т = 61,83. Поскольку наша имитация ограничива­ется пятью клиентами, время прибытия шестого клиента генерировать не будем.

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

Так как средство обслуживания в момент прихода клиента 5 занято, он в момент времени Т = 61,83 помещается в очередь. Имеем список будущих событий.

Время Т	Событие
70,19	Уход клиента 3

Уход клиента 3 в момент Т = 70,19. Первый клиент в очереди (клиент 4) начи­нает обслуживаться. Его время ожидания в очереди составляет

W₄ = 70,19 - 60,81 = 9,38 мин.

Время ухода клиента 4:

Т = 70,19 + (10 + 5 х 0,1782) = 81,08 мин. Откорректированный список будущих событий принимает такой вид.

Время Т	Событие
81,08	Уход клиента 4

Уход клиента 4 в момент Т = 81,08. Клиент 5 начинает обслуживаться. Его вре­мя ожидания в очереди составляет

W₅ = 81,08 - 61,83 = 19,25 мин. Время ухода клиента 5:

Т = 81,08 + (10 + 5 х 0,3473) = 92,82 мин. Откорректированный список будущих событий принимает такой вид.

Время Т	Событие
92,82	Уход клиента 5

Уход клиента 5 в момент Т = 92,82. Клиентов в системе (в очереди и на обслу­живании) больше нет. Имитация заканчивается.

На рис. 18.8 показаны изменения длины очереди и использование сервиса (занятость системы) как функции времени имитации.

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

(Среднее значение переменнойЛ Площадь под кривой ^ зависящей от времени) Период имитации

Применяя эту формулу для данных, показанных на рис. 18.8, получаем Средняя длина очереди = (А, + А₂)/92,82 = 32,36/92,82 = 0,349 (клиента), Средняя занятость системы = (А₃ + А₄)/92,82 = 63,71/92,82 = 0,686 (парикмахера).

Среднее время ожидания в очереди является переменной, зависящей от количе­ства происшедших событий, и ее значение вычисляется по формуле

(Среднее значение переменной, ") _ Сумма наблюдений ^зависящей от количества событий) Количество событий

Из рис. 18.8 видно, что площадь под кривой длины очереди в действительности рав­на сумме времен ожидания трех клиентов, которые формировали очередь. Поэтому

W, + W₂ + W₃ + W_t + W_s = 0 + 0 + 3,73 + 9,38 + 19,25 = 32,36 мин.

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

Среднее время ожидания в очереди равно

W= 32,36/5 = 6,47 мин.

Длина очереди

г* ■Wc

_|_

JL _|_

А_г= 28,63 _I_

0 10 Занятость системы

20 30 40 50 60 70 80 90

-»i4
Л,=13,37 1		1 1	At = 50,34 1 1 1 1 1
0 10		30 40		60 70	80 90

Рис. 18.8. Изменение длины очереди и использование сервиса во времени имитации

УПРАЖНЕНИЯ 18.5.1

1. Предположим, что в парикмахерской, о которой шла речь в разделе 18.5.1, работают два парикмахера, и клиенты обслуживаются согласно принципу "первым пришел — первым обслуживаешься". Предположим также, что время стрижки является случайной величиной, равномерно распределенной на интервале от 15 до 30 мин.; время между приходом клиентов распределе­но по экспоненциальному закону с математическим ожиданием 10 мин. Смо­делируйте вручную работу системы на протяжении 75 единиц времени. Из полученных результатов имитации определите среднее время ожидания кли­ента, среднее число ожидающих клиентов и среднюю занятость парикмахе­ров. Используйте случайные числа из табл. 18.1.

2. Классифицируйте следующие переменные как зависящие либо от количества событий, либо от времени.

a) Время отказа электронного прибора.

b) Объем запаса некоторого изделия.

c) Объем заказа на некоторый товар, внесенный в инвентарную опись.

d) Количество бракованных изделий в партии.

e) Время, необходимое для оценки результатов теста.

f) Количество автомобилей на стоянке агентства по прокату автомобилей.

3. Следующая таблица представляет изменение числа ожидающих в очереди клиентов в зависимости от времени имитации.

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

Время имитации Т(часы)	Число ожидающих клиентов
0< Т<3
3< Т<4
4< Т<6
6< Т<7
7 < Т< 10
10< Т< 12
12< Т< 18
18 < Т<20
20 < Т<25
Определите следующие величины.
а) Среднюю длину очереди.
Ь) Среднее время ожидания в очереди.
Предположим, что в парикмахерской (раздел 18.5.1) работают три парик-
махера; их занятость характеризуется следующей таблицей.
Время имитации Т(часы)	Число занятых парикмахеров
0< Т< 10
10 < Т<20
20 < Т<30
30 < Г < 35
35 < Т<40
40 < Т<60
60 < Т<70
70 < Т<75
75 < Т<80
80 < Т<90
90 < Т< 100

Определите следующие величины.

a) Среднее время работы парикмахеров.

b) Среднее время простоя парикмахеров.

18.5.2. Имитация модели очереди с одним сервисом в электронной таблице

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

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

использование специального программного обеспечения значительно облегчает эту работу (см. раздел 18.7).

В разделе 18.5.1 было показано, что для имитации модели очереди с одним сер­висом необходимы два основных элемента.

1. Список событий модели, упорядоченный в хронологическом порядке.

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

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

На рис. 18.9 показан шаблон рабочей книги Excel (файл chl8SingleServer-Simulator.xls). Входные данные позволяют представить время между поступле­ниями и время обслуживания одним из четырех способов: в виде константы или случайных чисел, имеющих экспоненциальное, равномерное или треугольное рас­пределения. Треугольное распределение полезно, поскольку с его помощью можно приближенно представить любое другое распределение. Для этого введите три чис­ла а, Ь и с, которые соответствуют наименьшему, наиболее вероятному и наиболь­шему значениям времени между поступлениями клиентов в систему или времени их обслуживания. Кроме того, необходимо ввести еще один параметр имитируемой модели — длительность имитации, которая в этой модели определяется количест­вом сгенерированных поступлений.

~Ё F G Hi J К [ М N О _01 Simulation of a Single-Server Queueing Model _

Simulation Calculations