misle.ru страница 1
скачать файл
Красноярский государственный университет цветных металлов и золота

Кафедра автоматизации производственных процессов


ЦМ





Дисциплина “Методы оптимизации”

Красноярск 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().

1iN

Найденная точка принимается за приближенное решение задачи . Исходный отрезок неопределенности (a,b) после экспериментов в N точках сужается до (xj-1,xj+1), длина которого равна:

.

Точность найденного решения равна половине отрезка неопределенности, т.е. , где и x* - точное решение, - точность решения.



Алгоритм деления интервала пополам
Схема алгоритма.

Шаг 1. Задаются a,b,. Производим эксперимент в точке , т.е. вычисляем 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, а длина получившегося отрезка неопределенности будет .

Следовательно, достигнутая точность будет , =1/2LN.

Метод дихотомии

Схема алгоритма.

Шаг 1. Задаются a,b, и - малое положительное число, значительно меньшее чем .

Шаг 2. Определяется середина отрезка x=(a+b)/2. Производятся эксперименты в двух точках близких середине: y1=f(x-), y2=f(x+).

Шаг 3. Определяется следующий отрезок локализации, т.е. определяется какой из отрезков (a,x+) или (x-,b) содержит точное решение x*. Если y1y2, то это отрезок (a,x+) и b=x+, иначе это отрезок (x-,b) и a=x-, т.е. выбранный отрезок локализации мы снова обозначили как (a,b).

Шаг 4. Если b-a2, то x=(a+b)/2, и поиск заканчивается. Иначе перейти к шагу 2.

После к итераций общее число экспериментов будет N=2к, а длина получившегося отрезка неопределенности . Следовательно, .

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

Схема алгоритма

Шаг1. Задаются и .

Вычисляют .

Шаг2. а) Если , то полагают и вычисляют .

б) Если , то полагают и вычисляют .

Шаг3. Если , то переходят к шагу 2. Иначе если , то полагают и если , то полагают и

Закончить поиск.

После каждой итерации длина отрезка неопределённости уменьшается в раз. Так как первая итерация начинается после двух экспериментов, то после экспериментов длина отрезка неопределённости будет .

Метод чисел Фибоначчи

Схема алгоритма

Шаг 1. Задаются Вычисляются числа Фибоначчи . Определяется:

Шаг 2. а) Если , то полагают и вычисляют .

б) Если , то полагают и вычисляют .

Повторить шаг 2 раза.

Шаг 3. Если , то полагают и . Если , то полагают и .

Закончить поиск.

Длина отрезка неопределённости в методе Фибоначчи .

Метод касательных
Схема алгоритма

Шаг 1. Заданы . Вычислить .

Шаг 2. Если , то полагаем . Поиск окончен. Если , то вычислить . Если, то полагаем и поиск окончен. Если , то следующий отрезок . Если , то . Повторить шаг 2.

Метод парабол
Схема алгоритма

Шаг 1. Задаются a,c,b и . Вычислить f(a), f(c), f(b).

Шаг 2. Вычислить , y=f(x), где

Шаг 3. А) При x

Если 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.

Если 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, то закончить поиск, положив , иначе перейти к шагу 2.


Отчет о работе

Отчет должен содержать подробный ход решения для всех задач. Каждая задача должна сопровождаться графиком, по которому было бы видно, что функция действительно имеет минимум в найденной точке. Отчет необходимо иметь в РАСПЕЧАТАННОМ (написанном от руки) виде.
скачать файл



Смотрите также: