Главная > Математика > Исследование операций: задачи, принципы, методология
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

§ 23. Единичный жребий и формы его организации

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

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

Поясним понятие «жребия». Пусть в ходе процесса наступил момент, когда его дальнейшее развитие (а значит и результат) зависит от того, произошло или нет какое-то событие А?

Например, попал ли в цель снаряд? Исправна ли аппаратура? Обнаружен ли объект? Устранена ли неисправность? Тогда нужно «бросанием жребия» решить вопрос: произошло событие или нет. Как можно осуществить этот жребий? Нужно привести в действие какой-то механизм случайного выбора (например, бросание монеты или игральной кости, или же вынимание жетона с цифрой из вращающегося барабана, или выбор наугад какого-то числа из таблицы). Нам хорошо знакомы некоторые механизмы случайного выбора (например, «пляска шариков» перед объявлением выигравших номеров «Спортлото»). Если жребий бросается для того, чтобы узнать, произошло ли событие А, его нужно организовать так, чтобы условный результат розыгрыша имел ту же вероятность, что и событие А. Как это делается — мы увидим ниже. Кроме случайных событий, на ход и исход операции могут влиять различные случайные величины, например: время до первого отказа технического устройства; время обслуживания заявки каналом СМО; размер детали; вес поезда, прибывающего на участок пути; координаты точки попадания снаряда и т. п. С помощью жребия можно разыграть и значение любой случайной величины, и совокупность значений нескольких.

Условимся называть «единичным жребием» любой опыт со случайным исходом, который отвечает на один из следующих вопросов:

1. Произошло или нет событие А?

2. Какое из событий произошло?

3. Какое значение приняла случайная величина X?

4. Какую совокупность значений приняла система случайных величин

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

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

Условимся кратко называть величину R — «случайное число от 0 до 1». Покажем, что с помощью такого числа можно разыграть любой из четырех видов единичного жребия.

1. Произошло или нет событие А? Чтобы ответить на этот вопрос, надо знать вероятность события А. Разыграем случайное число от 0 до 1, и если оно оказалось меньше как показано на рис. 23.1, будем считать, что событие произошло, а если больше — не произошло.

Рис. 23.1.

А как быть, — спросит читатель, — если число R оказалось в точности равным ? Вероятностью такого совпадения можно пренебречь. А уж если оно случилось, можно поступать как угодно: или всякое «равно» считать за «больше», или за «меньше», или попеременно за то и другое — от этого результат моделирования практически не зависит.

2. Какое из нескольких событий появилось?

Пусть события несовместны и образуют полную группу. Тогда сумма их вероятностей равна единице. Разделим интервал (0, 1) на к участков длиной (рис. 23.2). На какой из участков попало число — то событие и появилось.

Рис. 23.2.

3. Какое значение приняла случайная величина X?

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

Чтобы разыграть ее значение, достаточно осуществить следующую процедуру: перейти от плотности вероятности к функции распределения по формуле

затем найти для функции F обратную ей функцию . Затем разыграть случайное число и от 0 до 1 и взять от него эту обратную функцию:

Можно доказать (мы этого делать не будем), что полученное значение X имеет как раз нужное нам распределение

Графически процедура розыгрыша значения X показана на рис. 23.3. Разыгрывается число от 0 до 1 и для него ищется такое значение X, при котором (это показано стрелками на рис. 23.3).

Рис. 23.3.

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

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

Это и будет нужная нам нормально распределенная случайная величина.

4. Какую совокупность значений приняли случайные величины X1, X2,...,Xk?

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

Таким образом, мы рассмотрели все четыре вариант та единичного жребия и убедились, что все они сводятся к розыгрышу (одно- или многократному) случайного числа Д от 0 до 1.

Возникает вопрос: а как же разыгрывается это число Ю Существует целый ряд разновидностей так называемых «датчиков случайных чисел», решающих эту задачу. Остановимся вкратце на некоторых из них.

Самый простой из датчиков случайных чисел — это вращающийся барабан, в котором перемешиваются перенумерованные шарики (или жетоны). Пусть, например, нам надо разыграть случайное число R от 0 до 1 с точностью до 0,001. Заложим в барабан 1000 перенумерованных шариков, приведем его во вращение и после остановки выберем первый попавшийся шарик, прочтем его номер и разделим на 1000.

Можно поступить и немного иначе: вместо 1000 шариков заложить в барабан только 10, с цифрами Вынув один шарик, прочтем первый десятичный знак дроби. Вернем его обратно, снова покрутим барабан и возьмем второй шарик — это будет второй десятичный знак и т. д. Легко доказать (мы этого делать не будем), что полученная таким образом десятичная дробь будет иметь равномерное распределение от 0 до 1. Преимущество этого способа в том, что он никак не связан с числом знаков, с которым мы хотим знать

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

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

При ручном применении метода Монте-Карло таблицы случайных чисел — наилучший способ розыгрыша случайного числа от 0 до 1. Если же моделирование осуществляется не вручную, а на ЭВМ, то пользование таблицами случайных чисел (как и вообще таблицами) нерационально — они слишком загрузили бы память. Для розыгрыша Д на ЭВМ применяются специальные датчики, которыми оснащены многие вычислительные машины. Это могут быть как «физические датчики», основанные на преобразовании случайных шумов, так и вычислительные алгоритмы, по которым сама машина вычисляет так называемые «псевдослучайные числа». Приставка «псевдо» означает «как бы», «якобы». И в самом деле, числа, вычисляемые с помощью таких алгоритмов, фактически случайными не являются, но практически ведут себя как случайные; все значения от 0 до 1 встречаются в среднем одинаково часто и, кроме того, связь между последовательными значениями получаемых чисел практически отсутствует. Существует ряд алгоритмов вычисления псевдослучайных чисел, различающихся между собой по простоте, равномерности и другим признакам (см. [22]). Один из самых простых алгоритмов вычисления псевдослучайных чисел состоит в следующем. Берут два произвольных -значных двоичных числа , перемножают их и в полученном произведении берут средних знаков; это будет число Затем перемножают в произведении снова берут передних знаков и т. д. Полученные таким образом числа рассматривают как последовательность двоичных дробей с знаками после запятой. Такая последовательность дробей ведет себя практически как ряд значений случайного числа от 0 до 1.

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

<< Предыдущий параграф Следующий параграф >>
Оглавление