Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Методичка по методам оптимизации.doc
Скачиваний:
179
Добавлен:
02.05.2014
Размер:
1.18 Mб
Скачать

Лабораторная работа 17. Методы одномерной оптимiзации

Метод золотого сечения.

Метод золотого сечения (МЗС) применяется для поиска минимума унимодальной функции одной переменной y=F(x), что задана на промежутке [A,B]. Алгоритм метода реализуется в виде последовательности шагов, на каждом из которых осуществляется сужение интервала, что содержит точку минимума.

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

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

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

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

где константа G = (51)/20.618. Подставим

А{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}).

Итерации продолжают до тех пор, пока не будет выполняться неравенство

B{s} А{s} ,

где > 0 — заданное число, которое определяет погрешность решения задачи.

На каждом шагу МЗП, начиная с 1-го, вычисляется лишь одно значение функции F(x), потому что одна из точек золотого перерезу на предыдущем шаге осуществляет золотой перерез промежутка на следующем шаге.

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

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

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

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

Метод случайного поиска применяется для нахождения минимума (максимума) произвольной функции 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+)2 или (1)2, N — заданное число итераций >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).

Метод дихотомии (половинного деления).

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

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

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

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

L{s} = (А{s}+ B{s} )2

R{s}= (А{s}+ B{s}+ )2

где  > 0 — достаточно малое число. Возлагают

А{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}).

Итерации продолжают до тех пор, пока не будет выполняться неравенство

B{s} А{s} ,

где >0 — заданное число, которое определяет погрешность решения задачи.

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

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

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

Программное обеспечение.

Обучающий модуль, с помощью которого задачи одномерной оптимизации Решаются в диалоге с пользователем за выложенными алгоритмами, вызывается из раздела «НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ» главного меню пакета ПОМО.

Задание.

Решить методами золотого пересечения, случайного поиска, Фибоначчи и дихотомии задачи одномерной оптимизации, условия которых задаются модулем с помощью команды «Данные» главного меню, а также найти наибольшее и наименьшее значение следующих функций на указанных промежутках:

1) F(x)= |||x21|1|1| x  [2, 2];

2) F(x)= 2x33x212x+1++ x  [2, 2];

3) F(x)= (x+1)2 ln(x+1)+x exp(x) x  [0, e];

4) F(x)= sin(x) sin(2x)+ arccos(x2) x  [0.75, 0.75];

5) F(x)= arctg(x) ln(x) /2 x  [0.65, 1.75];

6) F(x)= x+ + ехp(x) x2 x  [0, 4];

7) F(x)= 4 x(x2 + 4)[x2 (x 2)](2/5) x  [2, 2].