Безусловная одномерная оптимизация

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

Уфимский Государственный Авиационный Технический Университет

Лабораторная работа

«Безусловная одномерная оптимизация»

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

Задание:

1. Изучить предлагаемые методы одномерной безусловной оптимизации.

2. В соответствии с вариантом задания, определенным преподавателем, составить программы, реализующие методы поиска, и найти точку минимума функции f(x) на отрезке [a,b], указано число экспериментов N, то сравнить заданные в варианте методы по получаемой длине отрезка неопределенности.

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

Методы одномерной безусловной оптимизации:

а) пассивный оптимальный алгоритм;

б) метод перебора.

в) алгоритм деления интервала пополам;

г) метод дихотомии;

д) метод золотого сечения;

е) метод Фибоначчи;

ж) метод касательных;

з) метод парабол.

№	Целевая функция	Отрезок [a,b]
14	x2 + e-0.25*x	[0,1]

оптимизация безусловный одномерный



Постановка задачи:

Найти точку минимума функции f(x)= x² + e-^0.25*x на отрезке [0,1] с заданной точностью.

График функции x² + e-^0.25*x на отрезке [0,1]:

X=0.44712; Y = 3,77688

Текст программы на С++

#include<iostream>

#include<math.h>

#include<conio.h>

#include<stdio.h>

using namespace std;

const double e=0.0001,

t1=0, t2=1, d=e/10;

doube f(double x)

{double f;

f=x*x+4*exp(-0.25*x);

return f;

}

double df(double x)

{double f;

f=2*x-exp(-0.25*x);

return f;

}

void blochnimetod(){

double a=t1, b=t2, x[1000], y[1000], xl, yl;

long i, j, n, N, k, l;

cout<<"Алгоритм блочного равномерного поиска."<<endl;

cout<<"Введите размер блока: ";

cin>>n;

N=0;

if (n%2==0){

k=n/2;

while (b-a> 2*e)

{for (j=1; j<k+1; j++){

x[2*j]=a+j*(b-a)/(k+1);

x[2*j-1]=x[2*j]-d;}

for (i=1; i<n+1; i++){

y[i]=f(x[i]);}

x[0]=a;

x[n+1]=b;

N=n+N;

yl=y[1]; l=1; xl=x[1];

for (i=2; i<n+1; i++){

if (y[i]<yl) {yl=y[i]; xl=x[i]; l=i;}}

a=x[l-1];

b=x[l+1];}

xl=(a+b)/2;

yl=f(xl);}

else{

k=(n+1)/2;

x[k]=(a+b)/2;

y[k]=f(x[k]);

N=1;

while (b-a>2*e){

for (i=1; i<n+1; i++){

x[i]=a+i*(b-a)/(n+1);

y[i]=f(x[i]);}

x[0]=a;

x[n+1]=b;

N=N+n-1;

yl=y[1]; xl=x[1]; l=1;

for (i=2; i<n+1; i++){

if (y[i]<yl) {yl=y[i]; xl=x[i]; l=i;}}

a=x[l-1];

b=x[l+1];

x[k]=xl; y[k]=yl;}}

cout<<"x = "<< xl<<endl;

cout<<"y = "<< yl<<endl;

cout<<"Число эксперементов: N = "<<N<<endl;

_getch();

}

void fibonachi(){

int F1, F0, F, N;

double x1,x2,y1,y2,x,y,a=t1,b=t2,Fn;

F0=1; F1=1;

F=0; N=0;

Fn=(b-a)/2/e;

cout<<"Метод Фибоначи."<<endl;

while (F<Fn){

F=F1+F0;

if (F<Fn){

F0=F1;

F1=F; }}

x1=a+F0*(b-a)/F;

x2=a+F1*(b-a)/F;

y1=f(x1);

y2=f(x2);

N=0;

do{ if (y1<=y2){

b=x2; x2=x1; y2=y1; x1=a+b-x2; y1=f(x1);}

else{a=x1; x1=x2; y1=y2; x2=a+b-x1; y2=f(x2);}

N++;}

while (b-a>2*e);

if (y1<=y2){

b=x2, x2=x1, y2=y1;}

else {a=x1;}

x1=x2-d;

y1=f(x1);

x=(a+b)/2;

y=f(x);

cout<<"x = "<< x<<endl;

cout<<"y = "<< y<<endl;

cout<<"Число эксперементов: N = "<<N<<endl;

_getch();

}

void perebor(){

long double x, y, yl, xl, a=t1, b=t2, i, N;

N=(a+b)/e;

cout<<"Метод перебора."<<endl;

cout<<"Количество точек (эксперементов) N = "<<N<<" для точности e = "<<e<<endl;

for (i=1; i<N+1; i++){

x=a+i*(b-a)/(N+1);

y=f(x);

if ((i==1) || (yl>y)) {xl=x; yl=y;}}

cout<<"x = "<< xl<<endl;

cout<<"y = "<< yl<<endl;

_getch();

}

void seredinaotr(){

double a=t1, b=t2, x[5], y[4], yl, xl;

int i, N, l;

cout<<"Алгоритм деления интервала пополам."<<endl;

x[2]=(a+b)/2;

y[2]=f(x[2]);

N=1;

while (b-a > 2*e){

x[0]=a;

x[4]=b;

x[1]=(a+x[2])/2;

y[1]=f(x[1]);

x[3]=(x[2]+b)/2;

y[3]=f(x[3]);

N=N+2;

yl=y[1]; xl=x[1]; l=1;

for (i=2; i<4; i++){

if (yl>y[i]) {yl=y[i]; xl=x[i]; l=i;}}

a=x[l-1];

b=x[l+1];

x[2]=xl;

y[2]=yl;}

cout<<"x = "<< x[2]<<endl;

cout<<"y = "<< y[2]<<endl;

cout<<"Число эксперементов: N = "<<N<<endl;

_getch();

}

void dixotomii(){

double x,y,y1,y2,a=t1,b=t2;

int N;

cout<<"Метод дихотомии."<<endl;

x=(a+b)/2;

N=0;

while ((b-a)>2*e){

y1=f(x-d);

y2=f(x+d);

N=N+2;

if (y1<=y2){b=x+d;}

else{a=x-d;}

x=(a+b)/2;}

y=f(x);

cout<<"x = "<< x<<endl;

cout<<"y = "<< y<<endl;

cout<<"Число эксперементов: N = "<<N<<endl;

_getch();

}

void zolotoesech(){

const double t=0.5*(1+sqrt(5));

double a=t1, b=t2, x1,x2, y1, y2, x;

int N=0;

cout<<"Метод золотого сечения."<<endl;

x1=a+(b-a)/(t*t);

y1=f(x1);

x2=a+(b-a)/t;

y2=f(x2);

N+=2;

while ((b-a)/t > 2*e){

if (y1<=y2) {b=x2;

x2=x1;

y2=y1;

x1=a+b-x2;

y1=f(x1); N++;}

else {a=x1;

x1=x2;

y1=y2;

x2=a+b-x1;

y2=f(x2); N++;}}

if (y1<y2){x=(a+x2)/2;}

else {x=(x1+b)/2;}

y1=f(x);

cout<<"x = "<< x<<endl;

cout<<"y = "<< y1<<endl;

cout<<"Число эксперементов: N = "<<N<<endl;

_getch();

}

void metodkasateln(){

double a=t1, b=t2, y1, y2, z1, z2, s, z, x, y;

int N;

cout<<"Метод касательных."<<endl;

y1=f(a);

y2=f(b);

z1=df(a);

z2=df(b);

N=2;

do{ s=((b*z2 - a*z1)-(y2-y1))/(z2-z1);

y=f(s);

z=df(s);

N=N+2;

if (z==0) {x=s; break;}

if (z>0) {b=s; y2=y; z2=z;}

else {a=s; y1=y; z1=z;}}

while (b-a>2*e);

x=(a+b)/2; y=f(x);

cout<<"x = "<< x<<endl;

cout<<"y = "<< y1<<endl;

cout<<"Число эксперементов: N = "<<N<<endl;

_getch();

}

void metodparobol(){

double a=t1, b=t2, ya, yb, yc, c=-3.5, t, s, yt, x, y;

int N;

cout<<"Метод парабол."<<endl;

if ((a>=c) || (b<=c) || (f(a)>=f(c)) || f(b)<=f(c)){ya=f(a);}

yb=f(b);

yc=f(c);

N=3;

while (b-a>2*e){

s=c+0.5*( (b-c)*(b-c)*(ya-yc) - (c-a)*(c-a)*(yb-yc) )/( (b-c)*(ya-yc) + (c-a)*(yb-yc) );

if (s==c){t=(a+c)/2;}

else {t=s;}

yt=f(t);

N++;

if (t>c){

if (yt<yc) {a=c; ya=yc; c=t; yc=yt;}

else if (yt>yc) {b=t; yb=yt;}

else {a=c; ya=yc; b=t; yt=yc; c=(a+b)/2; yc=f(c); N++;}}

else {

if (yt<yc) {b=c; yb=yc; c=t; yc=yt;}

else if (yt>yc) {a=t; ya=yt;}

else {a=t; ya=yt; b=c; yb=yc; c=(a+b)/2; yc=f(c); N++;}}}

x=(a+b)/2; y=f(x);

cout<<"x = "<< x<<endl;

cout<<"y = "<< y<<endl;

cout<<"Число эксперементов: N = "<<N<<endl;

_getch();

}

int main(){

setlocale(LC_ALL, "Russian");

int j;

while (1){

cout <<endl<< "1. Алгоритм блочного равномерного поиска.\n";

cout << "2. Метод Фибоначчи.\n";

cout << "3. Метод перебора.\n";

cout << "4. Алгоритм деления интервала пополам.\n";

cout << "5. Метод дихотомии.\n";

cout << "6. Метод золотого сечения.\n";

cout << "7. Метод касательных.\n";

cout << "8. Метод парабол.\n";

cout << "9. Выход.\n";

cout <<endl<< "Ваш выбор (1-9): "; cin >> j; cout<<"\n";

switch(j){

case 1: blochnimetod(); break;

case 2: fibonachi(); break;

case 3: perebor(); break;

case 4: seredinaotr(); break;

case 5: dixotomii(); break;

case 6: zolotoesech(); break;

case 7: metodkasateln(); break;

case 8: metodparobol(); break;

case 9: cout << "Конец работы.\n"; return(0);

default: cout << "Нет пункта под номером " << j << ". Повторите.\n";}}

return(0);

}



Блок-схемы алгоритмов

Метод перебора

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

Пассивный оптимальный метод

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



Метод деления интервала пополам

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

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

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



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

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

Метод парабол

Метод касательных



Блочный метод



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



Расчётные формулы для N

Пассивный оптимальный:

Блочного равномерного поиска чётн:

Блочного равномерного поиска не чётн:

Деления интервала пополам:

Дихотомии:

Золотого сечения:

Фибоначчи:

Результирующая таблица

Для e=0.00001

Метод	Результат	N	N расч.
Метод перебора	X=0.447116; Y = 3.77688	100000
Блочного равномерного поиска n=2	X=0.447121; Y = 3.77688	32
Блочного равномерного поиска n=3	X=0.447121; Y = 3.77688	33
Деления интервала пополам	X=0.447121; Y = 3.77688	33
Дихотомии	X=0.44712; Y = 3.77688	32
Золотого сечения	X=0.44712; Y = 3.77688	24
Фибоначчи	X=0.447121; Y = 3.77688	23
Касательных	X=0.447123; Y = 3.77688	34
Парабол	X=0.44712; Y = 3.77688	14

Для e=0.0001

Метод	Результат	N	N расч.
Метод перебора	X=0.447155; Y = 3.77688	10000
Блочного равномерного поиска n=2	X=0.447173; Y = 3.77688	26
Блочного равномерного поиска n=3	X=0.447144; Y = 3.77688	27
Деления интервала пополам	X=0.447144; Y = 3.77688	27
Дихотомии	X=0.447084; Y = 3.77688	26
Золотого сечения	X=0.447097; Y = 3.77688	19
Фибоначчи	X=0.447081; Y = 3.77688	18
Касательных	X=0.4471; Y = 3.77688	28
Парабол	X=0.44712; Y = 3.77688	14



Для e=0.001

Метод	Результат	N	N расч.
Метод перебора	X=0.447552; Y = 3.77688	1000
Блочного равномерного поиска n=2	X=0.447464; Y = 3.77688	20
Блочного равномерного поиска n=3	X=0.447266; Y = 3.77688	19
Деления интервала пополам	X=0.447266; Y = 3.77688	19
Дихотомии	X=0.446788; Y = 3.77688	20
Золотого сечения	X=0.446784; Y = 3.77688	14
Фибоначчи	X=0.446721; Y = 3.77688	13
Касательных	X=0.446185; Y = 3.77688	20
Парабол	X=0.44712; Y = 3.77688	14

Для e=0.01

Метод	Результат	N	N расч.
Метод перебора	X=0.445545; Y = 3.77688	100
Блочного равномерного поиска (n=2)	X=0.443781; Y = 3.77689	12
Блочного равномерного поиска (n=3)	X=0.45313; Y = 3.77688	13
Деления интервала пополам	X=0.445313; Y = 3.77688	13
Дихотомии	X=0.445422; Y = 3.77688	12
Золотого сечения	X=0.444272; Y = 3.77689	10
Фибоначчи	X=0.445455; Y = 3.7768	8
Касательных	X=0.443258; Y = 3.77703	14
Парабол	X=0.44712; Y = 3.77688	14

Для e=0.1

Метод	Результат	N	N расч.
Метод перебора	X=1.22222; Y = -0.656042	10
Блочного равномерного поиска (n=2)	X=0.43; Y = 3.77721	6
Блочного равномерного поиска (n=3)	X=0.4357; Y = 3.77698	7
Деления интервала пополам	X=0.4357; Y = 3.77698	7
Дихотомии	X=0.43875; Y = 3.77696	6
Золотого сечения	X=0.454915; Y = 3.77695	7
Фибоначчи	X=0.3; Y = 3.80097	3
Касательных	X=0.435484; Y = 3.78299	8
Парабол	X=0.44712; Y = 3.77688	14



Графики

Основной

Для перебора

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

...