Метод Монте-Карло
Метод Монте-Карло – это численный метод решения математических задач при помощи моделирования случайных величин. Метод появился в 1949 году, создателями этого метода считают математиков Дж. Неймана и С. Улама. В Советском Союзе первые статьи о методе Монте-Карло были опубликованы в 1955-1956 годах.
Идея метода состоит в следующем: вместо того, чтобы описывать процесс аналитически, производится «розыгрыш» случайного явления с помощью специально организованной процедуры. В действительности конкретное осуществление случайного процесса складывается каждый раз по-иному. Если таких реализаций получено много, то это множество реализаций можно использовать как некий искусственно полученный статистический материал, который может быть обработан обычными методами математической статистики. После такой обработки могут быть получены любые интересующие нас вероятностные характеристики: вероятности событий, математические ожидания и дисперсии случайных величин и т. д.
Нередко такой прием оказывается проще, чем попытки построить аналитическую модель. Для сложных операций, в которых участвует большое число элементов (машин, людей, организаций, подсобных средств), в которых случайные факторы сложно переплетены, метод Монте-Карло, как правило, оказывается проще аналитического (а нередко бывает и единственно возможным). Метод достаточно эффективен при решении задач, не требующих высокой точности, например, в пределах 5-10%.
В задачах исследования операций метод Монте-Карло применяется в
трех основных ролях:
1) при моделировании сложных, комплексных операций, где
присутствует много взаимодействующих случайных факторов;
2) при проверке применимости более простых, аналитических
методов и выяснении условий их применимости;
3) в целях выработки поправок к аналитическим формулам типа
«эмпирических формул» в технике.
Пример 2. Вычисление числа p методом Монте-Карло.
Попробуем построить метод Монте-Карло для решения задачи о вычислении числа Пи. На рисунке 8 рассмотрим круг радиуса 1 с центром в точке (1,1). Круг вписан в квадрат, площадь которого 
Выбираем внутри квадрата 
случайных точек. Выбрать точку значит задать ее координаты – числа 
и 
. Обозначим 
– число точек, попавших при этом внутрь круга.
Рисунок 8. Круг радиуса 1, вписанный в квадрат
Исходными данными задачи являются длина стороны квадрата, содержащего круг, и количество точек, которые мы будем случайным образом выбирать внутри квадрата. Результатом решения задачи является площадь круга.
Точка принадлежит квадрату, если 
Если 
то точка попадает в круг, иначе она находится вне круга. Это и есть математическое соотношение, позволяющее для каждой точки определить, лежит ли она в круге.
Геометрически очевидно, что 
Отсюда 
Т.е. для круга единичного радиуса 
Но для круга единичного радиуса 
следовательно, получаем 
Эта формула дает оценку числа p. Чем больше , тем больше точность этой оценки. Следует отметить, что данный метод вычисления площади будет справедлив только тогда, когда случайные точки будут не просто случайными, а еще и равномерно разбросанными по всему квадрату .
Для моделирования равномерно распределенных случайных чисел в интервале от 0 до 1 в языке программирования Паскаль используется датчик случайных чисел – функция Random. Таким образом, суть компьютерного эксперимента заключается в обращении к функции Random для получения раз координат точки. Также в программе получим среднее значение случайной величины p.
Листинг программы (Паскаль) для нахождения числа Пи методом Монте-Карло:
Program Monte_Carlo;
var j,k,N:integer; Sr, Pi:real;
Procedure M_C(N:integer; var Pi:real);
var i,N1:integer; x,y:real;
begin
for i:=1 to N do
begin
x:=2*Random; y:=2*Random;
if sqr(x-1)+sqr(y-1)<=1 then inc(N1);
end;
Pi:=4*N1/N;
end;
begin
randomize;
for k:=1 to 2 do
begin
write ('N=');
readln(N);
write (k,' ');
Sr:=0;
for j:=1 to 10 do
begin
M_C(N,Pi);
write(Pi:0:4,' ');
Sr:=Sr+Pi/10;
end;
writeln; writeln(' Srednee Pi=',Sr:0:4);
end;
readln
end.
Итак, с помощью этой программы была проверена верность формулы Более точный ответ можно получить при очень большом количестве проведенных опытов, при испытании большего количества точек и при использовании качественного генератора псевдослучайных чисел.