Автор работы: Пользователь скрыл имя, 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
getch();
}
Блок-схема:
Метод Фибоначчи
Листинг функции:
void FibMet(double a,double b,double E)
{
double d=E/100;
double fib[3];
double x[2],y[2],xw,yw;
fib[0]=1;
fib[1]=1;
fib[2]=2;
int N=2;
do
{
fib[0]=fib[1];
fib[1]=fib[2];
fib[2]=fib[0]+fib[1];
N++;
}
while(fib[2]<=(b-a)/(2*E));
x[0]=a+((b-a)/fib[2])*fib[0];
x[1]=a+((b-a)/fib[2])*fib[1];
y[0]=F(x[0]);
y[1]=F(x[1]);
for(int i=3;i<N;i++)
{
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]);
}
}
if(y[0]<y[1])
{
b=x[1];
x[1]=x[0];
y[1]=y[0];
}
else
a=x[0];
x[0]=x[1]-d;
y[0]=F(x[0]);
if(y[0]<y[1])
b=x[1];
else
a=x[0];
xw=(a+b)/2;
yw=F(xw);
cout<<"Metod chisel Fibbonachi:\nx'="<<xw<<"\ny'="
getch();
}
Блок-схема:
Метод касательных
Листинг функции:
void KasMet(double a,double b,double E)
{
double z[2],y[2],s,yr,zr,xw,yw;
cout<<"funkciya vipuklaya na vsem intervale, => metod primenim\n";
y[0]=F(a);
z[0]=Fp(a);
y[1]=F(b);
z[1]=Fp(b);
int N=4;
do
{
s=((z[1]*b-z[0]*a)-(y[1]-y[0])
yr=F(s);
zr=Fp(s);
if(zr==0)
{
xw=s;
yw=yr;
break;
}
if(zr>0)
{
b=s;
y[1]=yr;
z[1]=zr;
}
else
{
a=s;
y[0]=yr;
z[0]=zr;
}
N+=2;
}
while(b-a>2*E);
if(zr!=0)
{
xw=(a+b)/2;
yw=F(xw);
}
cout<<"Metod kasatelnih:\nx'="<<xw<<"\ny'="
getch();
}
Блок-схема:
Метод парабол
Листинг функции:
void ParMet(double a,double b,double E)
{
int N;
double c=1.361;
double ya,yb,yc,xw,yw,s,t,yt;
ya=F(a);
yb=F(b);
yc=F(c);
N=3;
do
{
s=c+0.5*(pow((b-c),2)*(ya-yc)-
if(s!=c)
t=s;
else
t=(a+c)/2;
yt=F(t);
N++;
if(t<c)
{
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++;
}
}
}
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;
yb=yt;
c=(a+b)/2;
yc=F(c);
N++;
}
}
}
}
while(b-a>2*E);
xw=(a+b)/2;
yw=F(xw);
cout<<"Metod parabol:\nx'="<<xw<<"\ny'="<<
getch();
}
Блок-схема:
Таблица результатов сравнения рассмотренных методов:
Название метода | x’ | y' | N | |
пассивный оптимальный алгоритм (N нечетное) | 1.665 | 3.72894 | 399 | |
пассивный оптимальный алгоритм (N четное) | 1.66662 | 3.72895 | 400 | |
алгоритм блочного равномерного поиска | Размер блока |
|
|
|
2 | 1,66003 | 3,7895 | 16 | |
4 | 1,66644 | 3,7894 | 20 | |
6 | 1,66002 | 3,7895 | 24 | |
8 | 1,66233 | 3,7894 | 32 | |
10 | 1,66201 | 3,7894 | 30 | |
3 | 1,66406 | 3,7895 | 17 | |
5 | 1,66189 | 3,7897 | 21 | |
7 | 1,66406 | 3,7895 | 25 | |
9 | 1,6656 | 3,7894 | 33 | |
11 | 1,6713 | 3,7898 | 31 | |
алгоритм деления интервала пополам | 1.66406 | 3.72894 | 17 | |
метод дихотомии | 1.66012 | 3.72895 | 16 | |
метод золотого сечения | 1.66253 | 3.72894 | 13 | |
метод Фибоначчи | 1.66094 | 3.72894 | 12 | |
метод касательных | 1.66651 | 3.72895 | 22 | |
метод парабол | 1.66353 | 3.72894 | 17 | |
Вывод: как видно из таблицы результатов все методы выдали в итоге почти одинаковые значения и . Следует отметить, что заметно существенное отличие в количестве экспериментов между пассивным оптимальным алгоритмом, алгоритмом блочного равномерного поиска, алгоритм деления интервала пополам, методами дихотомии, золотого сечения, Фибоначчи, касательных, парабол и пассивным методом. В ходе выполнения работы получили, что метод Фибоначчи является самым эффективным среди этих восьми методов. Пассивный метод плох тем, что для достижения того же результата, при той же точности искомого решения, необходимо выполнить намного большее количество экспериментов.
26