Красноярский государственный университет цветных металлов и золота
Кафедра автоматизации производственных процессов
 
|
Красноярск 2005 г. |
Лабораторная работа № 3
“ Одномерная безусловная оптимизация”
ЦЕЛЬ РАБОТЫ
1. Изучить предлагаемые методы одномерной безусловной оптимизации.
2. В соответствии с вариантом задания, определенным преподавателем, составить программы, реализующие методы поиска, и найти точку минимума функции f(x) на отрезке (a,b).
3. Оформить отчет о выполнении задания с приведением условия задачи, алгоритмов и программ указанных методов поиска.
ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ
Алгоритм пассивного поиска минимума
Отрезок (a,b) исходный отрезок неопределенности. Пусть N - число точек, в которых необходимо провести вычисления целевой функции f(x), т. е. N экспериментов. Точки, в которых необходимо провести эксперименты, определяются следующим образом:
Среди вычисленных значений {f(xi)} (i=1,N), ищется точка xj , в которой достигается минимум:
f(xj)= min f( ).
1£i£N
Найденная точка принимается за приближенное решение задачи 
. Исходный отрезок неопределенности (a,b) после экспериментов в N точках сужается до (xj-1,xj+1), длина которого равна:
.
Точность найденного решения 
равна половине отрезка неопределенности, т. е. 
, где 
и x* - точное решение, e - точность решения.
Алгоритм деления интервала пополам
Схема алгоритма.
Шаг 1. Задаются a,b,e. Производим эксперимент в точке 
, т. е. вычисляем y2=f(x2).
Шаг 2. Проводим эксперименты в остальных точках блока: 
, y1=f(x1), 
, y3=f(x3).
Находим 
такую, что f(xj)=min {f(xi)}.
Тогда точное решение x* содержится на отрезке 
. Предполагается 
.
Шаг 3. Полагаем a=xj-1, b=xj+1, x2=xj, y2=yj. Если 
, то 
и поиск заканчивается. Иначе перейти к шагу 2.
После к итераций общее число проведенных экспериментов равно N=2к+1, а длина получившегося отрезка неопределенности будет 
.
Следовательно, достигнутая точность будет 
, e=1/2LN.
Метод дихотомии
Схема алгоритма.
Шаг 1. Задаются a,b,e и d - малое положительное число, значительно меньшее чем e.
Шаг 2. Определяется середина отрезка x=(a+b)/2. Производятся эксперименты в двух точках близких середине: y1=f(x-d), y2=f(x+d).
Шаг 3. Определяется следующий отрезок локализации, т. е. определяется какой из отрезков (a,x+d) или (x-d,b) содержит точное решение x*. Если y1£y2, то это отрезок (a,x+d) и b=x+d, иначе это отрезок (x-d,b) и a=x-d, т. е. выбранный отрезок локализации мы снова обозначили как (a,b).
Шаг 4. Если b-a£2e, то x=(a+b)/2, 
и поиск заканчивается. Иначе перейти к шагу 2.
После к итераций общее число экспериментов будет N=2к, а длина получившегося отрезка неопределенности 
. Следовательно, 
.
Метод золотого сечения
Схема алгоритма
Шаг1. Задаются 
и 
.
Вычисляют 
.
Шаг2. а) Если 
, то полагают 
и вычисляют 
.
б) Если 
, то полагают 
и вычисляют 
.
Шаг3. Если 
, то переходят к шагу 2. Иначе если 
, то полагают 
и 
если 
, то полагают 
и 
Закончить поиск.
После каждой итерации длина отрезка неопределённости уменьшается в 
раз. Так как первая итерация начинается после двух экспериментов, то после 
экспериментов длина отрезка неопределённости будет 
.
Метод чисел Фибоначчи
Схема алгоритма
Шаг 1. Задаются 
Вычисляются числа Фибоначчи 
. Определяется:
Шаг 2. а) Если 
, то полагают 
и вычисляют 
.
б) Если 
, то полагают 
и вычисляют 
.
Повторить шаг 2 
раза.
Шаг 3. Если 
, то полагают 
и 
. Если 
, то полагают 
и 
.
Закончить поиск.
Длина отрезка неопределённости в методе Фибоначчи 
.
Метод касательных
Схема алгоритма
Шаг 1. Заданы 
. Вычислить 
.
Шаг 2. Если 
, то полагаем 
. Поиск окончен. Если 
, то вычислить 
. Если
, то полагаем 
и поиск окончен. Если 
, то следующий отрезок 
. Если 
, то 
. Повторить шаг 2.
Метод парабол
Схема алгоритма
Шаг 1. Задаются a, c,b и e. Вычислить f(a), f(c), f(b).
Шаг 2. Вычислить 
, y=f(x), где
Шаг 3. А) При x<c.
Если y<yc, то b=c, c=x, yb=yc, yc=y.
Если y>yc, то a=x, ya=y.
Если y=yc, то a=x, b=c, c=(x+c)/2, ya=y, yb=yc, yc=f(c).
Б) При x>c.
Если y<yc, то a=c, c=x, ya=yc, yc=y.
Если y>yc, то b=x, yb=y.
Если y=yc, то a=c, b=x, c=(x+c)/2, ya=yc, yb=y, yc=f(c).
Шаг 4. Если b-a£e, то закончить поиск, положив 
, иначе перейти к шагу 2.
Отчет о работе
Отчет должен содержать подробный ход решения для всех задач. Каждая задача должна сопровождаться графиком, по которому было бы видно, что функция действительно имеет минимум в найденной точке. Отчет необходимо иметь в РАСПЕЧАТАННОМ (написанном от руки) виде.
