Автор работы: Пользователь скрыл имя, 13 Сентября 2012 в 21:14, лабораторная работа
Цель работы: знакомство с оптимизационными задачами, изучение различных методов одномерной оптимизации и сравнение эффективности их применения для конкретных целевых функций.
Условие задачи:
№
Целевая функция
Отрезок [a,b]
Точность или число экспериментов N
7
[0,2]
=5*10-3
1. Цель работы………………………………………………………………………………….3
2. Условие задачи………………………………………………………………………………3
3. График функции……………………………………………………………………………..3
4.1. Пассивный оптимальный алгоритм………………………………………………………..4
4.2. Алгоритм блочного равномерного поиска………………………………………………...7
4.3. Алгоритм деления интервала пополам…………………………………………………...11
4.4. Метод дихотомии…………………………………………………………………………..13
4.5. Метод золотого сечения…………………………………………………………………...15
4.6. Метод Фибоначчи………………………………………………………………………….17
4.7. Метод касательных………………………………………………………………………...20
4.8. Метод парабол……………………………………………………………………………...22
4.9. Таблица результатов сравнения рассмотренных методов………………………………26
4.10. Вывод……………………………………………………………………………………...26
Лабораторная работа по методам оптимизации №1:
«Безусловная одномерная оптимизация»
Содержание:
1. Цель работы………………………………………………………………
2. Условие задачи………………………………………………………………
3. График функции……………………………………………………………
4.1. Пассивный оптимальный алгоритм……………………………………………………….
4.2. Алгоритм блочного равномерного поиска………………………………………………...7
4.3. Алгоритм деления интервала пополам…………………………………………………...
4.4. Метод дихотомии………………………………………………………
4.5. Метод золотого сечения……………………………………………………………
4.6. Метод Фибоначчи………………………………………………………
4.7. Метод касательных…………………………………………………
4.8. Метод парабол……………………………………………………………
4.9. Таблица результатов сравнения рассмотренных методов………………………………26
4.10. Вывод…………………………………………………………………
Цель работы: знакомство с оптимизационными задачами, изучение различных методов одномерной оптимизации и сравнение эффективности их применения для конкретных целевых функций.
Условие задачи:
№ | Целевая функция | Отрезок [a,b] | Точность или число экспериментов N |
7 | [0,2] | =5*10-3 |
График функции:
x y
0 | 7,389056 |
0,1 | 6,825894 |
0,2 | 6,329647 |
0,3 | 5,893947 |
0,4 | 5,513032 |
0,5 | 5,181689 |
0,6 | 4,8952 |
0,7 | 4,649297 |
0,8 | 4,440117 |
0,9 | 4,264166 |
1 | 4,118282 |
1,1 | 3,999603 |
1,2 | 3,905541 |
1,3 | 3,833753 |
1,4 | 3,782119 |
1,5 | 3,748721 |
1,6 | 3,731825 |
1,7 | 3,729859 |
1,8 | 3,741403 |
1,9 | 3,765171 |
2 | 3,8 |
Пассивный оптимальный алгоритм
Листинг функции:
void PasMet(double a,double b,double E)
{
int N;
N=ceil((b-a)/E-1);
if(N%2==0)
N++;
double *x=new double[N];
double *y=new double[N];
for(int i=0; i<N; i++)
{
x[i]=a+(b-a)/(N+1)*(i+1);
y[i]=F(x[i]);
}
double min=y[0];
int l=0;
for(int i=1;i<N;i++)
{
if(min>y[i])
{
min=y[i];
l=i;
}
}
cout<<"Optimalnii passivnii metod:\nx'="<<x[l]<<"\ny'="<<
N=floor((b-a)/E-2+1);
if(N%2==1)
N++;
x=new double[N+2];
y=new double[N+2];
double d=E/100;
for(int i=1; i<=N/2; i++)
{
x[2*i]=a+(b-a)/(N/2+1)*i;
x[2*i-1]=x[2*i]-d;
}
x[0]=a;
x[N+1]=b;
for(int i=1;i<=N;i++)
{
y[i]=F(x[i]);
}
min=y[1];
l=1;
for(int i=2;i<=N;i++)
{
if(min>y[i])
{
min=y[i];
l=i;
}
}
double xw=(x[l-1]+x[l+1])/2;
double yw=F(xw);
cout<<"x'="<<xw<<"\ny'="<<yw<<
delete x;
delete y;
getch();
}
Блок-схема:
Алгоритм блочного равномерного поиска
Листинг функций:
void BlochMet(double a,double b,double E)
{
for(int i=1; i<6; i++)
{
BlochCh(a,b,E,i*2);
}
for(int i=1; i<6; i++)
{
BlochNech(a,b,E,i*2+1);
}
getch();
}
Для нечетного N:
void BlochNech(double a,double b,double E,int n)
{
int k=(n+1)/2;
double *x,*y;
x= new double[n+2];
y= new double[n+2];
x[k]=(a+b)/2;
y[k]=F(x[k]);
int N=1;
int l;
double min;
do
{
for(int i=1;i<=n;i++)
{
if(i!=k)
{
}
}
x[0]=a;
x[n+1]=b;
N=N+n-1;
l=1;
min=y[1];
for(int i=2;i<=n;i++)
{
if(min>y[i])
{
}
}
a=x[l-1];
b=x[l+1];
x[k]=x[l];
y[k]=y[l];
}
while(b-a>2*E);
double xw=x[k];
double yw=y[k];
cout<<"Razmer bloka: "<<n<<" x'="<<xw<<" y'= "<<yw<<" N= "<<N<<"\n";
}
Для четного N:
void BlochCh(double a,double b,double E,int n)
{
double *x,*y;
x= new double[n+2];
y= new double[n+2];
double d=E/100;
int l;
double min;
int N=0;
do
{
for(int i=1; i<=n/2; i++)
{
x[2*i]=a+(b-a)/(n/2+1)*i;
x[2*i-1]=x[2*i]-d;
}
for(int i=1; i<=n; i++)
{
y[i]=F(x[i]);
}
N+=n;
x[0]=a;
x[n+1]=b;
l=1;
min=y[1];
for(int i=2; i<=n; i++)
{
if(min>y[i])
{
}
}
a=x[l-1];
b=x[l+1];
}
while(b-a>2*E);
double xw=(a+b)/2;
double yw=F(xw);
cout<<"Razmer bloka: "<<n<<" x'= "<<xw<<" y'= "<<yw<<" N= "<<N<<"\n";
}
Блок-схема:
Для нечетного N:
Для четного N:
Алгоритм деления интервала пополам
Листинг функции:
void PopolamMet(double a,double b,double E)
{
double x[5],y[5];
x[2]=(a+b)/2;
y[2]=F(x[2]);
int N=1;
int l;
double min,yw,xw;
do
{
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+=2;
l=1;
min=y[1];
for(int i=2;i<4;i++)
{
if(min>y[i])
{
min=y[i];
l=i;
}
}
a=x[l-1];
b=x[l+1];
x[2]=x[l];
y[2]=y[l];
}
while(b-a>2*E);
xw=x[2];
yw=y[2];
cout<<"Metod deleniya otrezka popolam:\nx'="<<xw<<"\ny'="<<
getch();
}
Блок-схема:
Метод дихотомии
Листинг функции:
void DihMet(double a,double b,double E)
{
int N=0;
double y[2],x;
double xw,yw;
double d;
d=E/100;
do
{
x=(a+b)/2;
y[0]=F(x-d);
y[1]=F(x+d);
if(y[0]<y[1])
b=x+d;
else
a=x-d;
N+=2;
}
while(b-a>2*E);
xw=(a+b)/2;
yw=F(xw);
cout<<"Metod dihotomii:\nx'="<<xw<<"\ny'="<
getch();
}
Блок-схема:
Метод золотого сечения
Листинг функции:
void ZolMet(double a,double b,double E)
{
double tau=(1+sqrt(5))/2;
double x[2], y[2],xw,yw;
x[0]=a+(b+a)/pow(tau,2);
y[0]=F(x[0]);
x[1]=a+(b+a)/tau;
y[1]=F(x[1]);
int N=2;
do
{
if(y[0]<y[1])
{
b=x[1];
x[1]=x[0];
y[1]=y[0];
x[0]=a+b-x[1];
y[0]=F(x[0]);
}
else
{
a=x[0];
x[0]=x[1];
y[0]=y[1];
x[1]=a+b-x[0];
y[1]=F(x[1]);
}
N++;
}
while((b-a)/tau>2*E);
if(y[0]<y[1])
xw=(a+x[1])/2;
else
xw=(x[0]+b)/2;
yw=F(xw);
cout<<"Metod zolotogo secheniya:\nx'="<<xw<<"\ny'="<