Question

Метод монте-карло. написать программу в pascal.

Answer 1

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

Пример. Найти минимум функции P(x,y,z) при заданных ограничениях.
$P(x,y,z)=sin2x+cos3y+sin^2(4z+1); \\ x \in [-2;2], \ y \in [-1.5;1.5], \ z \in [-5;5], \ xy, \ x*z \geq 0$
Как видно из условия, имеется пять ограничений.
Конечно, в данном случае можно решить задачу методом простого перебора параметров с каким-то шагом, сначала найти примерное положение минимума (или минимумов, если их несколько), а потом уменьшить шаг и повторить поиск, но методом Монте-Карло задача решается намного изящнее.

function f(x, y, z: real): real;
begin
  f := sin(2 * x) + cos(3 * y) + sqr(sin(4 * z + 1))
end;

var
  x, y, z, p, x1, y1, z1, p1: real;
  i, n: longint;

begin
  Write('Введите число проб: ');
  Readln(n);
  Randomize;
  p1 := 1e20;
  for i := 1 to n do
  begin
    repeat
      x := 4 * Random - 2;
      y := 3 * Random - 1.5;
      z := 10 * Random - 5
    until (x>0) and (x*z>=0);
    p := f(x, y, z);
    if p1 > p then begin
      x1 := x; y1 := y; z1 := z; p1 := p
    end;
  end;
  Writeln('n=', n:8, ' ', x1:0:4, ' ', y1:0:4, ' ', z1:0:4, ' Минимум=', p1)
end.

Тестовое решение (при разных количествах проб):

Введите число проб: 1000
n=    1000 1.9111 -1.0660 0.5749 Минимум=-1.6029403376222

n=   10000 1.9931 -1.0176 2.0465 Минимум=-1.68773775014315

Введите число проб: 100000
n=  100000 1.9985 -1.0401 0.5191 Минимум=-1.75037309941284

Введите число проб: 1000000
n= 1000000 1.9997 1.0378 3.6868 Минимум=-1.7544874244815

Введите число проб: 10000000
n=10000000 1.9995 1.0471 2.1027 Минимум=-1.75595433108399

Вычисление даже для 10 миллионов проб выполняется около 5 секунд, так что быстродействие метода прекрасное

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

Посмотрим, как будут отыскиваться экстремумы с теми же ограничениями на те же параметры, если целевую функцию заменить на непериодическую:
$P(x,y,z)=3.5x^2+2.4(y-1)^2-6.18yz$

В программе при этом надо будет только изменить формулу целевой функции:
f := 3.5*sqr(x)+2.4*sqr(y-1)-6.18*y*z

Тестовое решение:

Введите число проб: 1000
n=    1000 0.4468 1.3516 4.9403 Минимум=-40.2712691657245

n=   10000 0.1716 1.4677 4.8246 Минимум=-43.1319690531051

Введите число проб: 100000
n=  100000 0.0283 1.4920 4.9365 Минимум=-44.9334596263254

Введите число проб: 1000000
n= 1000000 0.0320 1.4891 4.9963 Минимум=-45.3999805516411

Введите число проб: 10000000
n=10000000 0.1106 1.4998 4.9993 Минимум=-45.6964653852599

Хорошо видно, что параметры y и z уже после 10 тысяч проб практически не меняются, а параметр х меняется в значительных пределах. Дальнейший путь решения - зафиксировать с некоторой точностью найденные значения параметров и продолжить поиск значения уже одной переменной в области [0;0.15], или также зафиксировать найденное значение функции и решить полученное уравнение относительно х.