UNIVERSIDAD NACIONAL DE TRUJILLO
ESCUELA DE POSTGRADO
CURSO: Métodos y Modelos de Optimización
TEMA: Optimización de una función no restringida
de una variable
PROFESOR: Dr. Joaquín Lombira Echevarría
ALUMNO:
Ing. Walter Moreno Eustaquio
FECHA: 10 de Marzo de 2007
TRUJILLO - PERU
OPTIMIZACIÓN DE UNA FUNCIÓN DE UNA SOLA VARIBLE
La razón de crecimiento de una levadura que produce un antibiótico es una función de la concentración del alimento c,
g = __________2c__________
4 + 0.8 c + c2 + 0.2 c3
Como se ilustra en la siguiente figura 1, el crecimiento parte de cero a muy baja concentraciones debido a la alimentación de la comida. También parte de cero en altas concentraciones debido a los efectos de toxicidad. Encuentre el valor de c para cual el crecimiento es un máximo.
Figura 1.
2.- Solución:
Para la solución de este problema se emplearon los diferentes métodos desarrollados en clase, tanto de tipo indirecto (Newton Raphson), como de tipo directo (Eliminación de regiones) usando Matlab como lenguaje de programación.
Se presenta su ejecución de cada uno de ellos con sus respectivos resultados y conclusiones. Según el problema la optimización consiste en una maximización.
function y=f(x)
y = 2*x / (4+0.8*x+x^2+0.2*x^3);
function y=df(x)
y = (8-2*x^2-0.8*x^3) / (4+0.8*x+x^2+0.2*x^3);
function y=d2f(x)
y = (-12.8-36*x-8.8*x^2+9.28*x^3+5.6*x^4+0.96*x^5)/(4+0.8*x+x^2+0.2*x^3);
clear
error =0.0001;
exito =0;
x0 =input('valor inicial : ');
iter =0;
fprintf('-----------------------------------------------------\n');
fprintf('Iteraccion x0 df(x0) d2f(x0) x \n');
fprintf('-----------------------------------------------------\n');
while exito==0
iter = iter+1;
x= x0 - df(x0)/d2f(x0);
fprintf('%6.0f%15.6f %10.6f%10.6f%10.6f\n',iter,x0,df(x0),d2f(x0),x);
if abs(df(x0))<=error
fprintf('-----------------------------------------------------\n');
fprintf('El c optimo es : %10.6f\n',x);
fprintf('El valor optimo de g es : %10.6f\n',f(x));
exito=1;
else
x0=x;
end
end
>> opt_raphson
Valor inicial: 0
--------------------------------------------------------------
Iteración x0 df (x0) d2f(x0) x
--------------------------------------------------------------
1 0.000000 2.000000 -3.200000 0.625000
2 0.625000 1.421906 -7.192260 0.822699
3 0.822699 1.138534 -7.395533 0.976648
4 0.976648 0.902995 -7.052333 1.104690
5 1.104690 0.703019 -6.413603 1.214304
6 1.214304 0.531814 -5.609028 1.309118
7 1.309118 0.385251 -4.722829 1.390690
8 1.390690 0.261094 -3.821537 1.459012
9 1.459012 0.158886 -2.969798 1.512512
10 1.512512 0.080159 -2.242420 1.548259
11 1.548259 0.028255 -1.727355 1.564616
12 1.564616 0.004699 -1.484000 1.567782
13 1.567782 0.000153 -1.436339 1.567889
14 1.567889 0.000000 -1.434727 1.567889
--------------------------------------------------------------
El c óptimo es: 1.567889
El valor óptimo de g es: 0.369635
2.2.- Método de los dos puntos igualmente espaciados
clear
error=0.0001;
a=input('valor inicial a : ');
b=input('valor inicial b : ');
x1=a+(b-a)/3;
x2=b-(b-a)/3;
exito=0;
iter=0;
fprintf('---------------------------------------------------------------------------\n');
fprintf('Interaction a b x1 x2 f(x1) f(x2) \n');
fprintf('---------------------------------------------------------------------------\n');
while exito==0
iter=iter+1;
fprintf('%6.0f%15.6f %10.6f%10.6f%10.6f%10.6f%10.6f\n',iter,a,b,x1,x2,f(x1),f(x2));
if(f(x1)<f(x2))
a=x1;
x1=a+(b-a)/3;
x2=b-(b-a)/3;
else
if(f(x1)>f(x2))
b=x2;
x1=a+(b-a)/3;
x2=b-(b-a)/3;
end
end
if abs(a-b)<=error
fprintf('---------------------------------------------------------------------------\n');
fprintf('el c optimo es : %10.6f\n',x1);
fprintf('El g optimo es : %10.6f\n',f(x1));
exito=1;
end
end
>> opt_eli
valor inicial a : 0
valor inicial b : 5
------------------------------------------------------------------------------------------
Iteration a b x1 x2 f(x1) f(x2)
-----------------------------------------------------------------------------------------
1 0.000000 5.000000 1.666667 3.333333 0.368852 0.264706
2 0.000000 3.333333 1.111111 2.222222 0.347341 0.344241
3 0.000000 2.222222 0.740741 1.481481 0.283669 0.368974
4 0.740741 2.222222 1.234568 1.728395 0.358462 0.367637
5 1.234568 2.222222 1.563786 1.893004 0.369633 0.362139
6 1.234568 1.893004 1.454047 1.673525 0.368471 0.368743
7 1.454047 1.893004 1.600366 1.746685 0.369547 0.367180
8 1.454047 1.746685 1.551593 1.649139 0.369612 0.369100
9 1.454047 1.649139 1.519077 1.584108 0.369428 0.369613
10 1.519077 1.649139 1.562431 1.605785 0.369632 0.369516
11 1.519077 1.605785 1.547980 1.576882 0.369601 0.369628
12 1.547980 1.605785 1.567248 1.586517 0.369635 0.369606
13 1.547980 1.586517 1.560826 1.573671 0.369631 0.369632
14 1.560826 1.586517 1.569389 1.577953 0.369635 0.369626
15 1.560826 1.577953 1.566535 1.572244 0.369635 0.369633
16 1.560826 1.572244 1.564632 1.568438 0.369634 0.369635
17 1.564632 1.572244 1.567169 1.569706 0.369635 0.369635
18 1.564632 1.569706 1.566323 1.568015 0.369635 0.369635
19 1.566323 1.569706 1.567451 1.568579 0.369635 0.369635
20 1.566323 1.568579 1.567075 1.567827 0.369635 0.369635
21 1.567075 1.568579 1.567576 1.568077 0.369635 0.369635
22 1.567576 1.568579 1.567910 1.568245 0.369635 0.369635
23 1.567576 1.568245 1.567799 1.568022 0.369635 0.369635
24 1.567576 1.568022 1.567725 1.567873 0.369635 0.369635
25 1.567725 1.568022 1.567824 1.567923 0.369635 0.369635
26 1.567824 1.568022 1.567890 1.567956 0.369635 0.369635
27 1.567824 1.567956 1.567868 1.567912 0.369635 0.369635
----------------------------------------------------------------------------------------
el x optimo es : 1.567853
El y optimo es : 0.369635
2.3.- Método de la bisección
% Método de la Bisección o Búsqueda dicotomica para optimizar funciones
% de una sola Variable:
clear
error=0.0001;
delta=0.00001;
a=input('valor inicial a : ');
b=input('valor inicial b : ');
x1=(a+b-delta)/2;
x2=(a+b+delta)/2;
exito=0;
iter=0;
fprintf(' ERROR DELTA\n');
fprintf('%10.6f%10.6f\n',error,delta);
fprintf('---------------------------------------------------------------------------\n');
fprintf('Iteraccion a b x1 x2 f(x1) f(x2) \n');
fprintf('---------------------------------------------------------------------------\n');
while exito==0
iter=iter+1;
fprintf('%6.0f%15.6f %10.6f%10.6f%10.6f%10.6f%10.6f\n',iter,a,b,x1,x2,f(x1),f(x2));
if(f(x1)<f(x2))
a=x1;
x1=(a+b-delta)/2;
x2=(a+b+delta)/2;
else
if(f(x1)>f(x2))
b=x2;
x1=(a+b-delta)/2;
x2=(a+b+delta)/2;
end
end
if abs(b-a)<=error
fprintf('---------------------------------------------------------------------------\n');
fprintf('el c optimo es : %10.6f\n',x1);
fprintf('El g optimo es : %10.6f\n',f(x1));
exito=1;
end
end
>> dico
valor inicial a : 0
valor inicial b : 5
ERROR DELTA
0.000100 0.000010
----------------------------------------------------------------------------------------
Iteración a b x1 x2 f(x1) f(x2)
----------------------------------------------------------------------------------------
1 0.000000 5.000000 2.499995 2.500005 0.325204 0.325203
2 0.000000 2.500005 1.249997 1.250007 0.359550 0.359551
3 1.249997 2.500005 1.874996 1.875006 0.362881 0.362880
4 1.249997 1.875006 1.562497 1.562507 0.369632 0.369632
5 1.562497 1.875006 1.718747 1.718757 0.367861 0.367860
6 1.562497 1.718757 1.640622 1.640632 0.369205 0.369205
7 1.562497 1.640632 1.601559 1.601569 0.369541 0.369541
8 1.562497 1.601569 1.582028 1.582038 0.369618 0.369618
9 1.562497 1.582038 1.572262 1.572272 0.369633 0.369633
10 1.562497 1.572272 1.567380 1.567390 0.369635 0.369635
11 1.567380 1.572272 1.569821 1.569831 0.369635 0.369635
12 1.567380 1.569831 1.568600 1.568610 0.369635 0.369635
13 1.567380 1.568610 1.567990 1.568000 0.369635 0.369635
14 1.567380 1.568000 1.567685 1.567695 0.369635 0.369635
15 1.567685 1.568000 1.567837 1.567847 0.369635 0.369635
16 1.567837 1.568000 1.567914 1.567924 0.369635 0.369635
----------------------------------------------------------------------------------------
El c óptimo es: 1.567876
El g óptimo es: 0.369635
2.4.- Método de la Sección Áurea o Método de la Regla de Oro
% Método de la Sección dorada para optimizar funciones de una
% sola Variable:
clear
error=0.0001;
a=input('valor inicial a : ');
b=input('valor inicial b : ');
x1=a+0.382*(b-a);
x2=a+0.618*(b-a);
exito=0;
iter=0;
fprintf('---------------------------------------------------------------------------\n');
fprintf('Iteraccion a b x1 x2 f(x1) f(x2) \n');
fprintf('---------------------------------------------------------------------------\n');
while exito==0
iter=iter+1;
fprintf('%6.0f%15.6f%10.6f%10.6f%10.6f%10.6f%10.6f\n',iter,a,b,x1,x2,f(x1),f(x2));
if(f(x1)<f(x2))
a=x1;
x1=a+0.382*(b-a);
x2=a+0.618*(b-a);
else
if(f(x1)>f(x2))
b=x2;
x1=a+0.382*(b-a);
x2=a+0.618*(b-a);
end
end
if abs(b-a)<=error
fprintf('---------------------------------------------------------------------------\n');
fprintf('el c optimo es : %10.6f\n',x1);
fprintf('El g optimo es : %10.6f\n',f(x1));
exito=1;
end
end
>> dorada
valor inicial a : 0
valor inicial b : 5
---------------------------------------------------------------------------------------
Iteración a b x1 x2 f(x1) f(x2)
---------------------------------------------------------------------------------------
1 0.000000 5.000000 1.910000 3.090000 0.361411 0.281924
2 0.000000 3.090000 1.180380 1.909620 0.354122 0.361428
3 1.180380 3.090000 1.909855 2.360525 0.361418 0.335038
4 1.180380 2.360525 1.631195 1.909710 0.369307 0.361424
5 1.180380 1.909710 1.458984 1.631106 0.368572 0.369308
6 1.458984 1.909710 1.631161 1.737532 0.369308 0.367414
7 1.458984 1.737532 1.565389 1.631127 0.369634 0.369308
8 1.458984 1.631127 1.524743 1.565368 0.369474 0.369634
9 1.524743 1.631127 1.565381 1.590488 0.369634 0.369592
10 1.524743 1.590488 1.549857 1.565373 0.369607 0.369634
11 1.549857 1.590488 1.565378 1.574967 0.369634 0.369631
12 1.549857 1.574967 1.559449 1.565375 0.369629 0.369634
13 1.559449 1.574967 1.565377 1.569039 0.369634 0.369635
14 1.565377 1.574967 1.569041 1.571304 0.369635 0.369634
15 1.565377 1.571304 1.567641 1.569040 0.369635 0.369635
16 1.565377 1.569040 1.566776 1.567641 0.369635 0.369635
17 1.566776 1.569040 1.567641 1.568175 0.369635 0.369635
18 1.566776 1.568175 1.567311 1.567641 0.369635 0.369635
19 1.567311 1.568175 1.567641 1.567845 0.369635 0.369635
20 1.567641 1.568175 1.567845 1.567971 0.369635 0.369635
21 1.567641 1.567971 1.567767 1.567845 0.369635 0.369635
22 1.567767 1.567971 1.567845 1.567893 0.369635 0.369635
23 1.567845 1.567971 1.567893 1.567923 0.369635 0.369635
----------------------------------------------------------------------------------------
El c óptimo es: 1.567875
El g óptimo es: 0.369635
2.5.- Método de Fibonacci
clear
a=input('valor inicial a : ');
b=input('valor inicial b : ');
while a>=b
if a>=b
frintf('a debe ser menor que b\n');
end
a=input('valor inicial a : ');
b=input('valor inicial b : ');
end
error=input('Valor del error : ');
while error<=0
error=input('Valor del error : ');
end
Fi(1)=1;
Fi(2)=1;
FIB =(b-a)/error;
I=3;
Fi(I)=Fi(I-2)+Fi(I-1);
while Fi(I)<FIB
I= I+1;
Fi(I)=Fi(I-2)+Fi(I-1);
end
n=I;
Fi(n+1)=Fi(n)+Fi(n-1);
x1=(Fi(n-1)/Fi(n+1))*(b-a) +a;
x2=(Fi(n)/Fi(n+1))*(b-a) +a;
iter=0;
fprintf('---------------------------------------------------------------------------\n');
fprintf('Iteraccion a b x1 x2 f(x1) f(x2) \n');
fprintf('---------------------------------------------------------------------------\n');
for k=1:n-1
iter=iter+1;
fprintf('%6.0f%15.6f %10.6f%10.6f%10.6f%10.6f%10.6f\n',iter,a,b,x1,x2,f(x1),f(x2));
if(f(x1)<f(x2))
a=x1;
x1=(Fi(n-(k+1))/Fi(n-(k-1)))*(b-a) +a;
x2=(Fi(n-k)/Fi(n-(k-1)))*(b-a) +a;
else
if(f(x1)>f(x2))
b=x2;
x1=(Fi(n-(k+1))/Fi(n-(k-1)))*(b-a) +a;
x2=(Fi(n-k)/Fi(n-(k-1)))*(b-a) +a;
end
end
end
fprintf('---------------------------------------------------------------------------\n');
fprintf('el c optimo es : %10.6f\n',x1);
fprintf('El g optimo es : %10.6f\n',f(x1));
>> fibonacci4
valor inicial a : 0
valor inicial b : 5
Valor del error : 0.0001
----------------------------------------------------------------------------------------
Iteración a b x1 x2 f(x1) f(x2)
----------------------------------------------------------------------------------------
1 0.000000 5.000000 1.909830 3.090170 0.361419 0.281911
2 0.000000 3.090170 1.180340 1.909830 0.354118 0.361419
3 1.180340 3.090170 1.909830 2.360680 0.361419 0.335027
4 1.180340 2.360680 1.631190 1.909830 0.369307 0.361419
5 1.180340 1.909830 1.458980 1.631190 0.368572 0.369307
6 1.458980 1.909830 1.631190 1.737621 0.369307 0.367412
7 1.458980 1.737621 1.565412 1.631190 0.369634 0.369307
8 1.458980 1.631190 1.524758 1.565412 0.369474 0.369634
9 1.524758 1.631190 1.565412 1.590537 0.369634 0.369592
10 1.524758 1.590537 1.549883 1.565412 0.369607 0.369634
11 1.549883 1.590537 1.565412 1.575008 0.369634 0.369631
12 1.549883 1.575008 1.559480 1.565412 0.369629 0.369634
13 1.559480 1.575008 1.565412 1.569077 0.369634 0.369635
14 1.565412 1.575008 1.569077 1.571343 0.369635 0.369634
15 1.565412 1.571343 1.567677 1.569077 0.369635 0.369635
16 1.565412 1.569077 1.566812 1.567677 0.369635 0.369635
17 1.566812 1.569077 1.567677 1.568212 0.369635 0.369635
18 1.566812 1.568212 1.567347 1.567677 0.369635 0.369635
19 1.567347 1.568212 1.567677 1.567883 0.369635 0.369635
20 1.567677 1.568212 1.567883 1.568006 0.369635 0.369635
21 1.567677 1.568006 1.567800 1.567883 0.369635 0.369635
22 1.567800 1.568006 1.567883 1.567924 0.369635 0.369635
23 1.567800 1.567924 1.567842 1.567883 0.369635 0.369635
24 1.567842 1.567924 1.567883 1.567883 0.369635 0.369635
-----------------------------------------------------------------------------------------
El c óptimo es: 1.567883
El g óptimo es: 0.369635
3.- Resultados y Conclusiones:
Método |
c óptimo |
g óptimo |
Iteración |
1.- Newton-Raphson |
1.567889 |
0.369635 |
14 |
2.- Dos puntos igualmente espaciados |
1.567853 |
0.369635 |
27 |
3.- Método de la bisección |
1.567876 |
0.369635 |
16 |
4.- Método de la Sección Áurea |
1.567875 |
0.369635 |
23 |
5.- Método de Fibonacci |
1.567883 |
0.369635 |
24 |
La aplicación de los diferentes métodos dan el mismo resultado de optimización para maximizar en este caso el valor de la función g. Los métodos 1 y 3 según nuestra tabla anterior tienen menos iteraciones, la diferencia entre estos dos métodos es que el método de Newton Raspón (Método indirecto), parte de un punto, para encontrar el valor óptimo, por lo que es necesario derivar dos veces la función objetivo, este método es bondadoso cuando la primera y segunda derivada de la función que se desea optimizar son relativamente fácil solución, cuando derivar sea mas complejo muy bien se puede emplear los métodos de eliminaciones de región (métodos directos).
Según el resultado en lo métodos directos el numero de iteraciones esta en relación al criterio empleado en definir los dos puntos en el intervalo donde se encuentra el valor de x optimo, de la función objetivo de una variable, por ejemplo el método de bisección es el que presenta el menor número de iteraciones, por que en cada iteración se elimina casi la mitad del intervalo, mayor que el resto de métodos se puede verificar según la siguiente tabla:
Métodos Indirectos |
Intervalo |
% eliminado |
Iteración |
|
|
|
|
2.- Dos puntos igualmente espaciados |
LK=(2/3)Lº |
33.33 |
27 |
3.- Método de la bisección |
LK=(1/2)Lº |
50.00 |
16 |
4.- Método de la Sección Áurea |
LK=(0.618)Lº |
38.20 |
23 |
5.- Método de Fibonacci |
dk=0.3820LK |
38.00 |
24 |
El método de la bisección es un método es mas eficiente que el resto de los métodos directos para la solución de maximización de nuestra función objetivo:
g = __________2c__________
4 + 0.8 c + c2 + 0.2 c3
