Метод Монте-Карло получил распространение с появлением ЭВМ. Его преимущество в том, что он очень легко программируется и для сложных задач зачастую является единственным приемлемом решения. Суть метода: составляется некоторая целевая функция и затем отыскивается её минимум или максимум. Параметры функции задаются при датчика случайных чисел.
Пример. Найти минимум функции P(x,y,z) при заданных ограничениях. Как видно из условия, имеется пять ограничений. Конечно, в данном случае можно решить задачу методом простого перебора параметров с каким-то шагом, сначала найти примерное положение минимума (или минимумов, если их несколько), а потом уменьшить шаг и повторить поиск, но методом Монте-Карло задача решается намного изящнее.
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
Введите число проб: 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 секунд, так что быстродействие метода прекрасное
Анализ результатов показывает, что наша целевая функция имеет значительное количество экстремумов, что связано с наличием в ней трех периодических функций. Значение аргумента х практически определено (оно меняется незначительно), его можно зафиксировать и продолжить поиск уже для функции двух переменных, границы которых также следует сузить в районе полученных значений.
Посмотрим, как будут отыскиваться экстремумы с теми же ограничениями на те же параметры, если целевую функцию заменить на непериодическую:
В программе при этом надо будет только изменить формулу целевой функции: 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
Введите число проб: 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], или также зафиксировать найденное значение функции и решить полученное уравнение относительно х.
Пример. Найти минимум функции P(x,y,z) при заданных ограничениях.
Как видно из условия, имеется пять ограничений.
Конечно, в данном случае можно решить задачу методом простого перебора параметров с каким-то шагом, сначала найти примерное положение минимума (или минимумов, если их несколько), а потом уменьшить шаг и повторить поиск, но методом Монте-Карло задача решается намного изящнее.
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 секунд, так что быстродействие метода прекрасное
Анализ результатов показывает, что наша целевая функция имеет значительное количество экстремумов, что связано с наличием в ней трех периодических функций. Значение аргумента х практически определено (оно меняется незначительно), его можно зафиксировать и продолжить поиск уже для функции двух переменных, границы которых также следует сузить в районе полученных значений.
Посмотрим, как будут отыскиваться экстремумы с теми же ограничениями на те же параметры, если целевую функцию заменить на непериодическую:
В программе при этом надо будет только изменить формулу целевой функции:
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], или также зафиксировать найденное значение функции и решить полученное уравнение относительно х.