Оптимизация методом дихотомии

Размещено на http://www.allbest.ru

Содержание

• Введение
• Описание метода
• Алгоритм поиска минимума
• Блок-схема алгоритма вычисления экстремума
• Блок-схема подпрограммы для задания функции
• Описание программы
• Листинг
• Результаты выполнения программы
• Достоинства и недостатки метода

Список использованной литературы

Введение

одномерный оптимизация дихотомия унимодальный

В данной курсовой работе требуется решить задачу одномерной оптимизации, найти её минимум или максимум функции. Для этого была использована программа MatLab, которая позволяет оптимизировать поставленную задачу (нахождение минимума и максимума) различными методами с помощью таких операторов как plot, grad и т.д.

В курсовой работе задача оптимизации была решена методом дихотомии.

Описание метода

Метод дихотомии применяется для унимодальных функций. Метод дихотомии заключается в том, что исходный интервал [ а, b] делится средней точкой с = ( b + a) / 2 на два подинтервала [ а, с] и [ с, b] в одном из

которых лежит точка минимума х*.

Для выбора подинтервала, для хорошо дифференцируемой функции вычисляют в точке c производную f 0'( с) и анализируют ее знак. Если

f 0'( с)>0, то х*лежит слева от точки c, т.е. В отрезке [ а, с]; если f 0'( с)<0, то х* лежит справа от точки c, т.е. В отрезке [ с, b], а при f '( c) ? 0 найдена

точка минимума х* = с.

Если f 0( x) не дифференцируемая, то выясняется направление убывания унимодальной функции. С этой целью задается точка с+ h (где h>0 ? малая величина, соизмеримая с е и вычисляется ордината f 0( с+ h).

Если приращение функции Д f ( c) = f ( c) ? f ( c + h) < 0, то точка х* лежит справа от точки c, т.е. х* принадлежит отрезку [ с, b].

Если Д f ( c) = f ( c) ? f ( c + h) > 0, то точка х* лежит сktdf от точки c, т.е. х* принадлежит отрезку [ a, c]

При Д f ( c) ? 0 имеем точку минимума* x ? c .

После выбора подинтервала, в котором находится х*, например

[ с, b], переопределяем левую границу а= с (при выборе [ а, с] следует поменять правую границу b= с).

Проверяем b ? a ? е , если нет, то вновь делим отрезок [ b- a] пополам и опять определяем, в каком подинтервале находится точка минимума.

Алгоритм поиска минимума

1. Вводим границы [ а, b] и е. h = 100?е.

2. Делим отрезок пополам с = ( b + a) / 2 .

3. Вычисляем приращение функции f

Д ( c) = f ( c) ? f ( c + h) . Если

Д f 0( с) < 0, то a = с, иначе если Д f 0( с) ? 0, то b = с.

4. Проверяем условие ( b ? a) ? е ? Если нет, то переходим на п.2,

да - переход на п.5.

5. Печать: "точка минимума х* = ", с, f 0( с), f 0'( c). Конец.

Для контроля правильности полученного решения можно вывести на печать значение f 0'( x*), которое должно быть близко к нулю. Если условие (6.2) не выполняется, то следует искать ошибку в программе. Если интервал, содержащий точку минимума функции определяется на основе вычисления производной f 0'( с), то такая реализации метода дихотомии будет относиться к итерационным процедурам 1 порядка.

Блок-схема алгоритма вычисления экстремума

да

Блок-схема подпрограммы для задания функции

Описание программы

В основном модуле программы вычисляется минимум данной функции методом дихотомии Входными данными являются начало и конец отрезка, точность. Выходными данными является точка х, в которой функция принимает экстремальное значение.

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

Таблица1. Основные подпрограммы

Листинг программы

function popova % функция, реализующая метод дихотомии

x=-2:0.1:2; % диапазон изменения х с шагом для построения графика

y1=f(x); % вызов подпрограммы для построения графика

plot(x,y1); % построение графика

grid on % наложение сетки

xlabel('x') % подпись оси x

ylabel('y') % подпись оси y

a=-2; % левая граница поиска

b=2; % правая граница поиска

eps=1e-5; % точность

h=100*eps;

while abs(b-a)>=eps %начало итерационного цикла

c=(b+a)/2; % функция деления отрезка пополам

y=f(c)-f(c+h); % вычисление приращения функции

if y>0 ;% проверка условия

a=c;

else

b=c;

end

end% конец итерационного цикла

x_opt=c

y=f(x_opt)

function y=f(x) % подпрограмма для вычисления значения функции

y=0.87.*sin(1.4.*x).*exp(-0.89.*x)+0.78.*x.^2-2.06;

end

end

Результаты выполнения программы

По графику функции видно, что при x=-1,2 и y=-3.34, что соответствует результатам расчетов программы.

Результаты расчетов программы:

Достоинства и недостатки метода

Дихотомическое деление привлекательно своей простотой. Действительно, при дихотомии мы всегда имеем дело лишь с двумя классами, которые исчерпывают объём делимого понятия. Таким образом, дихотомичес-кое деление всегда соразмерно; члены деления исключают друг друга, так как каждый объект делимого множества попадает только в один из классов а или не а; деление проводится по одному основа-нию -- наличие или отсутствие некоторого признака. Обозначив делимое понятие буквой, а, и выделив в его объёме некоторый вид, скажем, b, можно разделить объём,a,на две части -- b и не b.

Дихотомическое деление имеет недостаток: при делении объё-ма понятия на два противоречащих понятия каждый раз остаётся крайне неопределённой та его часть, к которой относится частица «не». Если разделить учёных на историков и не историков, то вторая группа оказывается весьма неясной. Кроме того, если в начале дихотомического деления обычно довольно легко устано-вить наличие противоречащего понятия, то по мере удаления от первой пары понятий найти его становится всё труднее.

Список использованной литературы

1. Конспект лекций по курсу « Прикладное программирование для студентов 2-ого курса по направлению 260.100-62 - Технология продуктов питания.

2. Оптимизация технологических процессов В.С. Асламова , И.В. Васильев, О.А. Засухина - Ангарск , АГТА-2005г., 106 с.

3. http://ru.wikipedia.org/wiki/

4. Прикладное нелинейное программирование, Химмельблау Д Москва, Мир, 1975г.,536с.

Размещено на Allbest.ru