Упражнения

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

	С_з, тг	r, кг/мес	K, кг/мес	Q, м³		U, кг/м³
0,05					0,03
1,5					1,2

Глава 8. ПОНЯТИЕ О СТАТИСТИЧЕСКОМ МОДЕЛИРОВАНИИ

Примеры моделирования случайных процессов методом Монте-Карло

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

Основная идея метода состоит в следующем: вместо аналитического решения задачи либо проводят эксперименты, испытания, непосредственно рассматриваемые в задаче, либо эти испытания заменяют другими, имеющими одинаковую с исходными вероятностную структуру, т.е. рассматриваемые в задаче случайные явления имитируют, моделируют другими случайными явлениями. Одним из возможных способов имитации случайных явлений является рулетка. Игрой в рулетку знаменит город Монте-Карло. Именно этим объясняется другое часто встречающееся название метода статистических испытаний — метод Монте-Карло.

Метод Монте-Карло представляет собой применение процедуры «неограниченной случайной выборки», т.е. выборки отдельных элементов из множества таким образом, чтобы вероятность выбора каждого элемента была одинакова. Вариант этой процедуры заключается в использовании случайной выборки для имитации игры с природой или искусственной системой. Эта игра моделирует эксперимент. По существу метод Монте-Карло представляет собой моделирование эксперимента для определения некоторых вероятностных свойств множества объектов или событий.

Открытие метода Монте-Карло приписывают легендарному наблюдению математика за блужданием пьяного. Предполагается, что каждый шаг пьяного может быть с равной вероятностью совершен в любом направлении. Математика интересует вопрос, сколько шагов в среднем должен сделать пьяный, чтобы пройти определенное расстояние от исходной точки. Эта задача была названа задачей о «случайном блуждании».

Задача о «случайном блуждании». Предположим, что пьяный начинает свои блуждания от фонаря, расположенного в центре большой городской площади. Он решает идти, но без определенного направления. Если наблюдать за ним, то можно заметить, что он может сделать несколько шагов в одном направлении, затем несколько шагов в другом направлении и т.д. непредвиденным, или случайным, образом. Задача заключается в том, чтобы определить, как далеко он будет от фонаря после n беспорядочных зигзагов. То есть каково наиболее вероятное расстояние от фонаря после n шагов?

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

Для примера покажем, как можно применить метод Монте-Карло к задаче о «случайном блуждании». Для этого оценим наиболее вероятное расстояние, пройденное после пяти одинаковых шагов (т.е. n=5). Обратимся к табл. 28, в которой приведены двузначные случайные числа. Кроме того, используем следующую символику:

1. Будем считать, что фонарь расположен в начале координат X, Y (рис. 30).

2. Примем, что первая цифра двузначного числа, выбранного из таблицы, означает положительную единицу на оси X, если получаем 0 или четное число, и отрицательную, если число нечетное.

Таблицы 28. Случайные числа

09 73 25 33 54 20 48 05 42 26 89 53 01 90 25 29 80 79 99 70	76 53 01 35 86 64 89 47 42 96 19 64 50 93 03 09 37 67 07 15 80 15 73 61 47	34 67 35 48 76 24 80 52 40 37 23 20 90 25 60 38 31 13 11 65 64 03 23 66 53	80 95 90 90 17 20 63 61 04 02 15 95 33 47 64 S8 67 67 43 97 98 95 11 68 77	39 29 27 49 00 82 29 16 35 08 03 36 04 43 62 76 12 17 17 68
06 57 47 17 06 01 08 05 26 97 76 02 57 33 21 35 79 64 57 53	34 07 27 68 50 45 57 18 24 06 02 05 16 56 92 05 32 54 70 48 03 52 96 47 78	36 69 73 61 70 35 30 34 26 14 68 66 57 48 18 90 55 35 75 48 35 80 83 42 82	65 81 33 98 85 86 79 90 74 39 73 05 38 52 47 28 46 82 87 09 60 93 52 03 44	11 19 92 91 23 40 30 97 18 62 38 85 82 49 12 56 35 27 38 84
52 01 77 67 80 50 54 31 45 29 96 34 68 34 02 00 59 46 73 48	14 90 56 86 07 39 80 82 77 32 06 28 89 80 83 86 50 75 84 01 87 51 76 49 69	22 10 94 05 58 50 72 56 82 48 13 74 67 00 78 36 76 66 79 51 91 82 60 89 28	60 97 09 34 33 29 40 52 42 01 18 47 54 06 10 90 36 47 64 93 93 78 56 13 68	50 50 07 39 52 77 56 78 68 71 17 78 29 60 91 01 23 47 83 41
48 1 1 76 74 12 43 56 35 35 09 98 17 91 62 68 03 89 32 05 05	17 46 85 09 50 17 72 70 80 15 77 40 27 72 14 66 25 22 91 48 14 22 56 85 14	58 04 77 69 74 45 31 82 23 74 43 23 60 02 10 36 93 68 72 03 46 42 75 67 88	73 03 95 71 86 21 11 57 82 53 45 52 16 42 37 76 62 11 39 90 96 29 77 68 22	40 21 81 65 14 38 55 37 96 28 60 26 94 40 05 64 54 38 21 45
49 91 45 23 33 69 45 98 10 48 19 49 55 07 37 42 60 64 93 29	68 47 92 76 86 26 94 03 68 58 85 15 74 79 54 11 10 00 20 40 16 50 53 44 84	46 16 28 35 54 70 29 73 41 35 32 97 92 65 75 12 86 07 46 97 40 21 95 25 63	94 75 08 99 23 53 14 03 33 40 57 60 04 08 81 96 64 48 94 39 43 65 17 70 82	37 08 92 00 42 05 08 23 22 22 20 64 28 70 72 58 07 20 73 17
19 69 04 46 47 44 52 66 55 72 85 73 48 11 62 13 52 37 83 17	26 45 74 77 74 95 27 07 99 53 67 89 75 43 87 97 34 40 87 21 73 20 88 98 37	51 92 43 37 29 59 36 78 38 48 54 62 24 44 31 16 86 84 87 67 68 93 59 14 16	65 39 45 95 93 82 39 61 01 18 91 19 04 25 92 02 07 11 20 59 26 25 22 96 63	42 58 26 05 33 21 15 94 92 92 74 59 25 70 14 66 05 52 28 25
49 35 24 94 54 99 76 54 96 31 53 07 80 80 83 91 05 88 52 36	75 24 63 38 24 64 05 18 81 59 26 89 80 93 54 45 42 72 68 42 01 39 09 22 86	45 86 25 10 25 96 11 96 38 96 33 35 13 54 62 83 60 94 97 00 77 28 14 40 77	61 96 27 93 35 54 69 28 23 91 77 97 45 00 24 13 02 12 48 92 93 91 08 36 47	65 33 71 24 23 28 72 95 90 10 33 93 78 56 52 01 70 61 74 29
17 90 02 97 23 46 14 06 56 54 14 30 15 51 49 38 86 43 19 94	87 37 92 52 41 20 11 74 52 04 01 75 87 53 79 19 47 60 72 46 36 16 81 08 51	05 56 70 70 07 15 95 66 00 00 40 41 92 15 85 43 66 79 45 43 34 88 88 15 53	86 74 31 71 57 18 74 39 24 23 66 67 43 68 06 59 04 79 00 33 01 54 03 54 56	85 39 41 18 97 11 89 63 84 96 28 52 20 82 66 85 05 01 45 11
08 62 48 26 18 51 62 32 95 10 04 06	45 24 02 84 04 41 94 15 09 49 96 38 27 07 74	44 99 90 88 96 89 43 54 85 81 20 15 12 33 87	39 09 47 34 07 88 69 54 19 94 25 01 62 52 98	35 44 13 18 37 54 87 30 94 62 46 1 1

Рис. 30. Траектория "случайного блуждания"

3. Будем считать, что вторая цифра этого числа соответствует единице по оси Y, знак которой определяется так же, как в п. 2.

4. Точка (х_n,у_n) определяет положение пьяного после n шагов.

5. Расстояние пьяного от фонаря после п шагов определяется выражением

Если мы начнем со случайной точки и выберем двузначное число, например, в 10-м столбце и в 6-й строке табл. 29, а затем начнем выбирать числа сверху вниз, то получим следующие пять чисел: 36, 35, 68, 90 и 35. С помощью этих чисел получим координаты движения пьяного, показанные в таблице 29. Кривая движения показана на рис. 27.

Таблица 29

Шаг	Первая цифра	Вторая цифра	Расположение точки (x_n, y_n)
			(–1,1)
			(–2,0)
			(–1,1)
			(–2,2)
			(–3,1)

Таким образом, в этом примере получена одна оценка расстояния от фонаря после пяти шагов. Расстояние равно 3, 16 единиц и получено следующим образом:

d₅²=x₅²+y₅²=9 + l = 10, d₅ = =3,16.

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

Чтобы читатель мог сравнить свое собственное решение этой задачи методом Монте-Карло с правильным решением, отметим, что здесь можно получить аналитическое решение в виде d_n =a , т.е. наиболее вероятное расстояние пьяного от фонаря после большого числа беспорядочных шагов равно средней длине шага а,умноженной на корень квадратный из числа п его шагов.

Метод Монте-Карло широко применяется для решения задач массового обслуживания. В применении к задачам массового обслуживания метод может быть определен следующим образом: метод статистического моделирования (метод Монте-Карло) — метод, идея которого состоит в том, что вместо аналитического описания СМО многократно производится "розыгрыш" случайного процесса. Множество реализаций используется как статистический материал для получения характеристик СМО.

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

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

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

Рассмотрим для примера задачу об оптимальном размере автопарка. Вначале определяется средняя скорость поступления тюков на погрузочный пункт. Она может быть постоянной, но может и варьироваться в широких пределах. В последнем случае надо установить причину этих колебаний. Далее, анализируя записи предыдущих операций, можно определить, как изменялось ежедневное количество тюков, например, за последний год, и выразить изучаемое колебание в величинах стандартных отклонений для времени поступления заказов. Число тюков, прибывающих для доставки, может подчиняться любому из многочисленных законов распределения, Примем, однако, что это распределение нормальное, со средним значением 1000 тюков в день и стандартным отклонением в 100 тюков. Это означает, что средняя скорость поступления заказов l — 1000 тюков в день.

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

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

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

Берем пять первых следующих друг за другом значений из таблицы нормальных случайных чисел (табл. 28) и переписываем их в третий столбец таблицы 30. Отрицательные числа относятся к объему заказов меньшему, чем средний уровень, положительные — соответствуют объему выше среднего. Для того, чтобы преобразовать эти стандартные единицы в истинное число заказов, надо умножить число этих единиц на 100 (получив, таким образом, отклонение от среднего значения) и прибавить к 1000 (средней величине). Полученные значения приведены в столбце (4) таблицы 30. Аналогичным образом составляются столбцы (6) и (7), но только здесь стандартное отклонение принято равным 10. В столбце (8) приведено число неотправленных пакетов. На их доставку и требуется сверхурочное время. В столбце (10) приведена стоимость сверхурочной доставки в предположении, что скорость обслуживания остается неизменной.

Теперь можно найти суммарные еженедельные затраты по каждому автопарку. Так как ежедневные затраты на эксплуатацию одного грузовика равны 25дол., то за 5 дней издержки составят 125дол. Умножая эту величину на число автомобилей в парке, и складывая полученный результат со стоимостью сверхурочной работы, получаем следующие результаты:

(а) 10 грузовиков: (10´$125) + $296 = $1546,

(б) 12 грузовиков: (12´$125) + $56 = $1556,

(в) 15 грузовиков: (15´$125) =$1875.

Следовательно, в данном случае наиболее экономичным оказался парк из 10 грузовиков.

Таблица 30

Число пакетов, подлежащих доставке	Число пакетов, которое может быть доставлено	Издержки на сверхурочное время
(1)	(2)	(3)	(4)	(5)	(6)	(7)	(8)	(9)	(10)
Число грузовиков в парке	Дни	Таблич-ное значение	Число поступив-ших пакетов = 1000+ +100×(3)*	Общее число пакетов, подлежащих доставке: (4)+ +остаток от предыдущего дня	Таблич-ное значение+ +число пакетов, которое может быть доставлено на одном грузовике	Общее количество пакетов, которое может быть доставлено в течение рабочего дня 100+ +10×(6)	Число пакетов, оставшихся для обработки при отсутст-вии сверхурочного времени (5)—(7)	Число пакетов, подлежащих отправке в сверхурочное время (4)—(7)	(9) / __(7)__ ×$ 8,0 (1) (8)
		2,455			–0,323				$184
		–0,531			–1,940				$112
		–0,634			0,697
		1,279			3,521
		0,046			0,321
Итого	$296
		2,455			–0,323				$56
		–0,531			–1,940
		–0,634			0,687
		1,279			3,521
		0,046			0,321
Итого	$56
		2,455			–0,323
		–0,531			–1,940
		–0,634			0,697
		1,279			3,521
		0,046			0,321
Итого	$0
* Цифры, стоящие в скобках, обозначают номер соответствующего столбца