Метод случайного поиска.

Метод случайного поиска применяется для нахождения минимума (максимума) произвольной функции y=F(x), что задана в любой допустимой области D.

В программе рассматривается реализация данного метода для функции одной переменной.

Произвольная функция F(x) задана на промежутке [A,B]. С помощью датчика случайных чисел, равномерно распределенных на промежутке [0,1], строится последовательность случайных чисел x{k}, k=1...,N, равномерно распределенных на промежутке [A,B]. Вычисляются и сравниваются между собой значения функции F(x) в точках x{k}. Минимальное из них принимается за оценку минимума функции F(x) на промежутке [A,B].

Если N стремится к бесконечности, полученная оценка за вероятностью совпадает к глобальному минимуму функции, что рассматривается.

При решении задачи максимизации функции F(x) необходимо заменить ее на функцию – F(x).


Метод Фибоначчи.

Метод Фибоначчи (МФ) применяется для поиска минимума унимодальной функции одной переменной y=F(x), что задана на промежутке [A,B].

Алгоритм метода реализуется в виде последовательности шагов, на каждом из которых осуществляется сужение интервала, что содержит точку минимума.

В начале вычислений возлагают А{0}= А, B{0}= B.

На s-у шаге определяют величины

L{s}= B{s} G{s}(B{s} А{s})

R{s}= А{s}+ G{s}(B{s} А{s})

где G{s}=Fi(Ns1)/Fi(Ns), s=0...,N3, G{N2}=(1+e)/2 или (1e)/2, N — заданное число итераций e>0, Fi(j) — числа Фибоначчи, что задаются рекуррентным соотношением

Fi(j)= Fi(j1) + Fi(j2), j ³ 2, Fi(0)= Fi(1)= 1.

Возлагают

А{s+1}= А{s}, B{s+1}= R{s}, если F(L{s}) £ F(R{s})

А{s+1}= L{s}, B{s+1}= B{s}, если F(L{s})> F(R{s}).

За приближенное решение задачи принимают

x* = (А{N}+ B{N})/2, y* = F(x*).

Для МФ в случае предварительно фиксированного числа итераций длина конечного интервала поиска минимальная.

При решении задачи максимизации функции F(x) необходимо заменить ее на функцию – F(x).