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

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

Глава 17. Системы массового обслуживания

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

Количество звонков в час	Частота
Время обслуживания (в минутах) для каждого филиала примерно одинако-
вое. Приведенная ниже таблица содержит типичное распределение времени
обслуживания для одного из филиалов.
Время обслуживания, t	Частота
0< t< 10
10 < г < 20
20 < f < 30
30 < t < 40
40 < t < 50
50 < г < 60
60 < t < 70
70 < f < 80
80 < f < 90
90 < t < 100

Выработайте рекомендации для руководства компании.

17.4. Джон, молодой инженер, недавно принят на работу в машиностроительную компанию. Компания владеет цехом, насчитывающим 30 станков, для под­держания которых в рабочем состоянии содержит штат из шести механи­ков. Цех работает в одну смену с 8:00 до 16:00. Джон получил первое зада­ние: изучить эффективность ремонтной службы цеха. С этой целью Джон собрал следующие данные из протокола регистрации ремонта трех станков, выбранных случайным образом.

Комплексные задачи

Станок 5 Станок 18 Станок 23

Время поломки	Время ремонта	Время поломки	Время ремонта	Время поломки	Время ремонта
8:05	8:15	8:01	8:09	8:45	8:58
10:02	10:14	9:10	9:18	9:55	10:06
10:59	11:09	11:03	11:16	10:58	11:08
12:22	12:35	12:58	13:06	12:21	12:32
14:12	14:22	13:49	13:58	12:59	13:07
15:09	15:21	14:30	14:43	14:32	14:43
15:33	15:42	14:57	15:09	15:09	15:17
15:48	15:59	15:32	15:42	15:50	16:00

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

Общее количество сломанных станков по состоянию на

Дата	8:00	9:00	10:00	11:00	12:00	13:00	14:00	15:00
2/10
29/10
4/11
1/12
19/1

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

17.5. Таксомоторная компания владеет четырьмя машинами. Служба такси ра­ботает 10 часов каждый день. Заявки на обслуживание поступают в дис­петчерскую службу в соответствии с распределением Пуассона в среднем 20 заявок в час. Известно, что длительность поездки такси является экс­поненциально распределенной случайной величиной с математическим ожиданием 11,5 мин. В силу высокого уровня спроса на обслуживание компания ограничивает список клиентов в диспетчерской службе, ожи­дающих обслуживания, до 16 заявок. Когда этот предел достигается, кли­ентам советуют искать такси в другом месте, объяснив, что среднее время ожидания машины будет длительным.

Глава 17. Системы массового обслуживания

Управляющий компании Стоун опасается, что он, возможно, теряет много клиентов, и поэтому хочет рассмотреть вопрос об увеличении парка машин компании. Стоун считает, что средняя прибыль, получаемая компанией от обслуживания одного клиента, составляет примерно 5 долл. Новый автомо­биль, по его оценке, можно купить за 18 ООО долл. Новое такси использует­ся на протяжении пяти лет и затем продается за 3 500 долл. Стоимость со­держания и обслуживания такси на протяжении одного года составляет 20 ООО долл. Может ли мистер Стоун обосновать увеличение парка автомо­билей компании, и если да, то на сколько единиц? При анализе учтите 10 % ежегодного прироста клиентов.

ГЛАВА 18

ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ

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

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

Предшественником современного имитационного моделирования считается ме­тод Монте-Карло, основная идея которого состоит в использовании выборки слу­чайных чисел для получения вероятностных или детерминированных оценок ка­ких-либо величин. Основное различие между современными методами имитации и методом Монте-Карло заключается в том, что в последнем время не является обя­зательным фактором, а получаемые оценки "статичны". Метод Монте-Карло при­меняется для вычисления площадей фигур, ограниченных кривыми, или, в более общем случае, вычисления кратных интегралов; вычисления констант (например к, равной 3,14159...); обращения матриц и т.п.

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

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

18.1. МЕТОД МОНТЕ-КАРЛО

Для демонстрации метода Монте-Карло рассмотрим следующий пример. Здесь особо подчеркнута статистическая природа имитационного эксперимента.

Пример 18.1.1

Используем метод Монте-Карло для оценки площади круга, уравнение окружности которого имеет вид

(х - 1)² + (у-2)² = 25.

Круг имеет радиус г = 5 см, и его центр находится в точке (х, у) = (1, 2).

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

(-4, 7) _ (6, 7)

(-4,-3) (6,-3)

Рис. 18.1. Оценка площади круга методом Монте-Карло

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

т, \ т,,_п

площадь круга = —(площадь квадрата) =—(10x10). п п

Здесь координаты х и у точек квадрата представлены как равномерно распределен­ные случайные величины с плотностями вероятностей

/(*) = —. - 4 < х < 6, ^{v ;} 10

Обе функции равны нулю вне указанных интервалов.

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

18.1. Метод Монте-Карло

1, если 0 < д- < ], О в противном случае.

В табл. 18.1 приведен небольшой список случайных чисел из интервала [0, 1]. Эти числа сгенерированы с использованием специальных методов, которые опи­саны в разделе 18.4.

Таблица 18.1

0,0589	0,3529	0,5869	0,3455	0,7900	0,6307
0,6733	0,3646	0,1281	0,4871	0,7698	0,2346
0,4799	0,7676	0,2867	0,8111	0,2871	0,4220
0,9486	0,8931	0,8216	0,8912	0,9534	0,6991
0,6139	0,3919	0,8261	0,4291	0,1394	0,9745
0,5933	0,7876	0,3866	0,2302	0,9025	0,3428
0,9341	0,5199	0,7125	0,5954	0,1605	0,6037
0,1782	0,6358	0,2108	0,5423	0,3567	0,2569
0,3473	0,7472	0,3575	0,4208	0,3070	0,0546
0,5644	0,8954	0,2926	0,6975	0,5513	0,0305

Пусть Л, и Л₂ — различные случайные числа из интервала [0, 1]. Тогда координаты (х, у) точек квадрата можно выразить через эти случайные числа:

х = -4 + [6 - (-4)]Л, = -4 + ЮЛ,,

v = -3 + [7 - (-3)]Л₂ = -3 + 10Л₂.

Используя приведенные формулы, мы можем сгенерировать равномерно распреде­ленную случайную точку (х, у) квадрата для каждой пары случайных чисел (Л,,Л₂). Сгенерированная точка {х, у) попадает внутрь круга, если

(х- 1)² + Су-2)²<25.

Например, если Л, = 0,0589 и Л₂ = 0,6733, то

х = -4 + ЮЛ, = -4 + 10 х 0,0589 = -3,411,

у = -3 + 10Л₂ = -3 + 10 х 0,6733 = 3,733.

Так как величина (-3.411 - I)² + (3.733 - 2)² = 22,46 меньше 25, следовательно, точка (х, у) попадает внутрь круга.

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

Хотя вычисление отдельных выборочных значений относительно просто, создание выборки достаточно большого объема требует больших вычислений. Шаблон Excel chl8Circle.xls создан для выполнения вычислений рассматриваемого примера (рис. 18.2). Входными данными для вычислений являются радиус круга (ячейка С5), координаты центра круга (ячейки С6 и С7), размер выборки (ячейка С4) и количество прогонов (ячейка СЗ). В ячейку Е4 вводится число имитаций (т.е. количество полных повторений экспериментов с тем же количеством прогонов). Например, если объем вы­борки п равен 30 000 и число имитаций равно 3, то шаблон автоматически вычислит результаты для выборок объема 30 000, 60 000 (2 имитации) и 90 000 (3 имитации).

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

в	С	D
Monte Carlo Estimation of the Area of a Circle
2 Input data
3 Nbr Replications, N =
4 Sample size, n =	30.000	Steps =
5 Radius. r =
6 Center, cx =
7 Center, cy =
8:	Output results
9 1 Exact area =	78 5i,0
^ q Piess to Execute Monte Lailo
11 Monte Carlo Calculations
12j	n=30000	n=60000 n=
13 Replication 1	78.207	78 555	78 483
14 Replication 2	78.673	78 752	78 581
15 i Replication 3	78.300	78.288	78.281
16 Replication 4	78.503	78.347	78.343
17 Replication 5 18	78 983	78.775	78 760
19iMean =	78.533	78.543	78.490
20 3td Deviation =	0.308	0.225	0 191
22 J95% lower conf limit =	78 151	78.263	78.253
23 j95% upper conf. limit =	78.915*	78.823	78.727

Рис. 18.2. Вычисление в Excel оценки площади круга методом Монте-Карло

На рис. 18.2 показаны оценки площади круга для объема выборки 30 ООО, количе­ства выборок 5 и числа имитаций 3. Точная площадь круга равна 78,54 см², мето­дом Монте-Карло получили оценки от А = 78,533 до А = 78,490 см². Отметим, что стандартное отклонение изменяется от значения s = 0,308 при п = 30 ООО до s = 0,191 при п = 90 ООО. Это говорит о том, что точность оценки повышается при увеличении объема выборки.

Если в шаблоне щелкнуть на командной кнопке Press to Execute Monte Carlo (Выполнить метод Монте-Карло), то будут получены новые оценки путем повтор­ных вычислений с новой последовательностью случайных чисел.

Ввиду того, что оценки площади имеют разброс, важно, чтобы результаты экспе­римента, связанного с моделированием, были выражены в виде доверительных ин­тервалов, показывающих величину отклонения от точного значения. В рассматри­ваемом примере, если А представляет собой точное значение площади, а А и s" — среднее и дисперсию при числе экспериментов N, то 100(1 -а)%-ный доверитель­ный интервал для А задается в виде

^А " VF'^a/2-"-' ~^А~^А+7N^laJ2-^N-¹'

где t_{a/2 w}_, — (100а/2)% -ная точка /-распределения (распределения Стьюдента) с N- 1

степенями свободы (см. приложение В). Заметим, что N обозначает число экспери­ментов (прогонов), и его следует отличать от п, которое обозначает объем выборки ("продолжительность" прогона модели). В рассматриваемом примере мы заинтересо­ваны в установлении доверительного интервала, полученного для выборки наиболь­шего объема (т.е. п = 90 ООО). При N=5, А = 78,490 см², s = 0,191 см² и = 2,776 результирующим 95% -ным доверительным интервалом является 78,25 < А < 78,73.

18.1. Метод Монте-Карло

Рассмотренный пример ставит два вопроса, характерных для любого экспери­мента, связанного с моделированием.

1. Каким должен быть объем выборки п для достижения необходимого значе­ния доверительных интервалов?

2. Сколько для этого требуется прогонов N?

Ответы зависят от природы эксперимента, связанного с моделированием. Как и в любом статистическом эксперименте, большие значения п и N обеспечивают более надежные результаты. Препятствием может быть стоимость проведения экс­перимента, которая возрастает пропорционально увеличению п uN.

упражнения 18.1

1. В условиях примера 18.1.1 вычислите площадь круга, используя из табл. 18.1 два первых столбца в качестве источника случайных чисел из ин­тервала [0, 1]. (Для удобства выбирайте Д, из первого столбца, a Д₂ — из вто­рого, двигаясь при этом сверху вниз.) Сравните полученный результат с ре­зультатами вычислений в Excel, показанными на рис. 18.2.

2. Пусть уравнение окружности имеет вид (х - З)² + (у + 2)² = 16.

a) Найдите соответствующие плотности вероятностей f(x) и /((/). Покажите, как с помощью пары случайных чисел (Д,, Д₂) из интервала [0, 1] можно получить выборочную точку (х, у).

b) С помощью шаблона Excel chl8Circle.xls оцените площадь круга при п= 100 000 и N= 10. Постройте 95%-ный доверительный интервал для оценки площади круга.

3. Примените метод Монте-Карло для вычисления площади озера, показанного на рис. 18.3. Для получения значений случайных чисел из интервала [0, 1] используйте два первых столбца табл. 18.1.

4 3

is

§ 2 S

О 1 2 3 4 5 6 1 Мили

Рис. 18.3. План озера для упражнения 3

4. Рассмотрим игру, в которой два игрока А и Б поочередно подбрасывают пра­вильную (симметричную) монету. Если выпадает лицевая сторона монеты, игрок А получает 10 долл. от игрока Б, иначе игрок Б выигрывает у игрока А10 долл.

a) Как смоделировать эту игру в виде эксперимента Монте-Карло?

b) Проведите эксперимент в 5 прогонов с 10 подбрасываниями монеты в ка­ждом прогоне. Используйте пять первых столбцов табл. 18.1 для получе­ния значений случайных чисел из интервала [0, 1], при этом каждый столбец будет соответствовать одному прогону.

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

c) Вычислите 95% -ный доверительный интервал для выигрышей игрока А.

d) Сравните доверительный интервал, полученный в предыдущем пункте, с ожидаемым теоретическим выигрышем игрока А.

a) Оцените значение этого интеграла с помощью метода Монте-Карло.

b) Используйте четыре первых столбца табл. 18.1 для получения оценки значения интеграла, основанной на 4 прогонах объемом 10 каждый. Вы­числите 95%-ный доверительный интервал и сравните его с точным зна­чением интеграла.

6. Смоделируйте ситуацию с пятью выигрышами или проигрышами в следую­щей игре в кости. Игрок бросает две симметричные игральные кости. Если выпавшая сумма равна 7 или 11, игрок выигрывает 10 долл. Иначе он запо­минает выпавшую сумму (называемую очком) и продолжает бросать кости до тех пор, пока выпавшая сумма не совпадет с очком, после чего игрок получа­ет 10 долл. Но если выпавшая сумма равна 7, игрок проигрывает 10 долл.

7. Цикл исполнения заказа на некую продукцию с равной вероятностью состав­ляет 1 или 2 дня. Предполагается, что ежедневный спрос равен 0, 1 и 2 еди­ницы этой продукции с вероятностями 0,2, 0,5 и 0,3 соответственно. Исполь­зуйте значения случайных чисел из табл. 18.1 (начиная с первого столбца) для оценки совместного распределения спроса и цикла исполнения заказа. Исходя из полученного совместного распределения, оцените плотность веро­ятности спроса в течение цикла исполнения заказа. (Подсказка. Спрос во время исполнения заказа может принимать значения 0, 1, 2, 3 и 4.)

8. Рассмотрим эксперимент Бюффона с иглой. Горизонтальная плоскость раз­делена параллельными прямыми, расположенными на расстоянии D см одна от другой. Игла длиной d см (d < D) случайным образом бросается на плос­кость. Необходимо найти вероятность того, что игла коснется или пересечет одну из прямых. Введем следующие обозначения.

b) Составьте план эксперимента Монте-Карло, обеспечивающий определение оценки искомой вероятности.

c) Используйте первые четыре столбца табл. 18.1 для поиска оценки иско­мой вероятности, основанной на 4 прогонах объемом 10 каждый. Вычис­лите 95% -ный доверительный интервал для оценки.

d) Покажите, что вероятность интересующего нас события равна

Используйте эту формулу вместе с результатом, полученным при решении задачи из п. с), для оценки значения числа к.

5. Рассмотрим определенный интеграл \х^гах.

о

h — расстояние от центра иглы до ближайшей прямой, в— угол, составленный иглой с этой прямой, а) Покажите, что игла коснется или пересечет прямую, если

л< —sinе, o<h<—, о<е<л.

2 2

Id

18.2. Типы имитационных моделей

18.2. ТИПЫ ИМИТАЦИОННЫХ МОДЕЛЕЙ

Использование современных имитационных моделей базируется, в основном, на идее метода Монте-Карло. Отличие состоит в том, что имитационная модель обыч­но связана с изучением реально существующей системы, поведение которой явля­ется функцией времени. Существует два типа имитационных моделей.

1. Непрерывные модели используются для систем, поведение которых изменяется непрерывно во времени. Непрерывные имитационные модели обычно представляют­ся в виде разностно-дифференциальных уравнений, которые описывают взаимодей­ствие между различными элементами системы. Типичным примером непрерывной имитационной модели является изучение динамики народонаселения мира.

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

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

УПРАЖНЕНИЯ 18.2

1. Распределите по категориям приведенные ниже ситуации с точки зрения их принадлежности к дискретному или непрерывному типу (они также могут быть комбинацией обоих типов). В каждом случае укажите цель создания имитационной модели.

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

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

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

2. Объясните, почему вы согласны (или не согласны) со следующим утвержде­нием: "Большинство моделей дискретного моделирования в той или иной

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

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

18.3. ЭЛЕМЕНТЫ ДИСКРЕТНОГО МОДЕЛИРОВАНИЯ

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

18.3.1. Общее определение событий

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

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

Пример 18.3.1

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

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

All: обычная работа поступает в центр 1;

А21: срочная работа поступает в центр 1;

Д11: обычная работа уходит из центра 1;

Д21: срочная работа уходит из центра 1;

А12: обычная работа поступает в центр 2;

А22: срочная работа поступает в центр 2;

Д12: обычная работа уходит из центра 2;

Д22: срочная работа уходит из центра 2.

В действительности мы точно имеем лишь два события: прибытие (новой) работы в цех и выход (выполненной) работы из цеха. Заметим сначала, что события Д11 и А12 совпадают и являются неразличимыми. Это же замечание применимо к со­бытиям Д21 и А22. Далее в дискретной имитационной модели мы можем использовать

18.3. Элементы дискретного моделирования

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