8. МОДЕЛИРОВАНИЕ ОПЕРАЦИЙ МЕТОДОМ СТАТИСТИЧЕСКИХ ИСПЫТАНИЙ

1. МЕТОД СТАТИСТИЧЕСКИХ ИСПЫТАНИИ (МОНТЕ-КАРЛО)

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

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

В тех случаях, когда построение аналитической модели явления по той или другой причине трудно осуществимо, применяется другой метод моделирования, известный под названием метода статистических испытаний или, иначе, метода Монте-Карло,

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

Однако в принципе метод Монте-Карло может применяться и без помощи ЭЦВМ. В данном параграфе мы изложим существо метода, безотносительно к способу его осуществления.

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

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

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

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

Поставленную вероятностную задачу можно решить двумя способами: а) аналитически и б) «розыгрышем».

Сначала решим задачу аналитически. Вероятность поражения цели W вычислим через вероятность противоположного события — непоражения цели. Вероятность непоражения цели равна сумме вероятностей ни одного попадания и ровно одного попадания; вероятность ни одного попадания равна 0,54; вероятность ровно одного попадания равна следовательно,

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

Повторим такой «опыт», состоящий в бросании четырех монет, очень много раз подряд. Тогда, согласно теореме Бернулли, частота «поражения» цели почти наверняка будет мало отличаться от вероятности этого события W; значит, если мы бросим четыре монеты большое число раз N и разделим число «поражений» цели на N, мы почти наверняка получим число, близкое к W, т. е. к 0,688.

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

Рис. 8.1

Рассмотрим пример такой задачи. Пусть производится бомбометание по некоторой цели Ц (рис. 8.1); зона разрушительного действия бомбы имеет вид круга радиуса . Сбрасывается бомб.

Для поражения цели (вывода ее из строя) нужно покрыть разрушениями не менее площади цели. Требуется найти вероятность поражения цели

Несмотря на видимую простоту постановки задачи, ее аналитическое решение чрезвычайно сложно. Гораздо проще будет решить задачу «розыгрышем». Для этого надо будет «разыграть» координаты точек попадания (как это сделать — будет рассказано в дальнейшем); вокруг каждой точки попадания описать круг радиуса и подсчитать общую пораженную площадь цели (на рис. 8.1 она заштрихована). Если эта площадь оказалась больше площади цели, считать, что цель «поражена», если меньше — «не поражена». Такой «опыт», состоящий в «бросании» бомб, нужно повторить очень много раз, отмечая каждый раз условным знаком (например, ) опыт, в котором цель была «поражена». При большом числе «опытов» N вероятность поражения цели W может быть приближенно оценена как частота «поражения» цели:

где М — число «опытов», отмеченных плюсом.

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

Заметим, что методом статистических испытаний (Монте-Карло) можно находить не только вероятности событий, но и средние значения (математические ожидания) случайных величин. При этом мы будем пользоваться уже не теоремой Бернулли, а законом больших чисел (теоремой Чебышева). Согласно этой теореме при большом числе независимых опытов среднее арифметическое наблюденных значений случайной величины почти наверняка мало отличается от ее математического ожидания.

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

то его можно определить приближенно как среднее арифметическое площадей разрушений в большом числе N разыгранных «опытов».

где — значение площади разрушений в «опыте».

Аналогичным способом могут быть найдены не только математические ожидания, но и дисперсии интересующих нас случайных величин. Не забудем, что дисперсия случайной величины есть не что иное, как математическое ожидание квадрата центрированной случайной величины; оно может быть приближенно найдено как среднее арифметическое этих квадратов в отдельных «опытах». Так, в нашем примере дисперсия площади разрушений может быть приближение найдена по формуле

или, что проще, через второй начальный момент:

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

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

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

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

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