运筹学第一次实验

1、熟练利用0.618法，共轭梯度法以及非二次函数的共轭梯度法求解相关问题。（一） 问题描述0.618法：min f(x)=2x2-x-1，a1,b1=-1,1,精度L0.16共轭梯度法(CG算法)： min f(x)=x12-x1x2+x22+2x1-4x2 非二次的共轭梯度法（CG算法推广）：min f(x)=(1-x1)2+2(x2-x12)2 (三) 算法介绍(1)0.618法Step1：对区间a,b= a1,b1中取两点：1=a1+0.382（b1-a1），1=a1+0.618（b1-a1）Step2：若bk-ak<,停止运算，输出结果，否则计算并比较。若(k)(k)，则ak+1=

2、ak，bk+1=k，k+1=k，k+1=ak+1+0.382*(bk-ak+1)若(k)(k)，则ak+1=k，bk+1=bk，k+1=k，k+1=ak+1+0.618*(bk-ak+1)Step3:置k：=k+1，返回Step2(2)CG算法原理及步骤：n元正定二次函数f(x)=1/2xTQx+bT+c,给定任一初始点x0,计算d0=-g0，置k：=0step1：tk=gkTgk/dkTQdk,xk+1=xk+tkdkstep2：判断|gk+1|<，若成立则终止，输出。否则转step3step3：计算下一次的搜索方向dk+1=-gk+1+kdk，其中k=gk+1TQdk/dkTQdks

3、tep4：置k:=k+1,转step1进行下一次迭代。(3)CG算法的推广：对tk：改用直接的e.l.s，求得步长因子。对k：k=gk+1Tgk+1/gkTgk（四）程序代码及运行结果：（1）0.618法源程序代码a=-1;%区间端点b=1; %区间端点fprintf('初始区间为');interval=a,be=0.16;%误差q=b-a;u1=a+0.382*(b-a);u2=a+0.618*(b-a);n=0;while q>e n=n+1; f1=2*u12-u1-1; f2=2*u22-u2-1; if f1<f2 b=u2; u2=u1; u1=a+0.

4、382*(b-a); fprintf('得到新区间为'); interval=a,b else a=u1; u1=u2; u2=a+0.618*(b-a); fprintf('得到新区间为'); interval=a,b end q=b-a;end interval=a,bfprintf('使f=2*x2-x-1去的最小值的x为： ');x=(b+a)/2fprintf('f的最小值为：');f=2*x2-x-1fprintf('共计迭代了n步：');n（2）0.618法 运行结果： 初始区间为：interval

5、= -1 1得到的新区间为：得到的新区间为：interval = -0.2360 0.5278得到的新区间为：得到的新区间为：interval = 0.0558 0.3475得到的新区间为：得到的新区间为：interval = 0.1672 0.2787使f=2*x2-x-1取得最小值的x为：x = 0.2229f的最小值为：f = -1.1235共计迭代了n步：n = 6（3）CG法源程序代码function f=Untitled3(x0,e)syms x1 x2f=x12-x1*x2+x22+2*x1-4*x2;a=diff(f,x1);b=diff(f,x2);a=subs(a,x1,x

6、2,x0);b=subs(b,x1,x2,x0);g=a;bQ=2 -1;-1 2;d=-g;x=x0;n=0;while double(sqrt(a2+b2)>0.2 t=(g.'*g)/(d.'*Q*d); x=x+t*d; f=x12-x1*x2+x22+2*x1-4*x2; a=diff(f,x1); b=diff(f,x2); a=subs(a,x1,x2,x); b=subs(b,x1,x2,x); g=a;b; p=(g.'*Q*d)/(d.'*Q*d); d=-g+p*d; n=n+1; endfprintf('最优解为：'

7、);xfprintf('共迭代了n步');n（4）CG法 运行结果：在matlab对话框中输入Untitled3(0;0,0.2) 得到结果：最优解为：x = 0 2共迭代了n步：n = 2在matlab对话框中输入Untitled3(-1;1,0.2) 得到结果：最优解为：x = 0 2共迭代了n步：n = 1（5）CG推广法源程序代码：function f=num3(x0,e)syms x1 x2 tx=x0;f=(1-x1)2+2*(x2-x12)2;a=diff(f,x1);b=diff(f,x2);a=subs(a,x1,x2,x0);b=subs(b,x1,x2,x

8、0);g=a;b;d=-g; n=0;while double(sqrt(a2+b2)>e x=x+t*d; f=subs(f,x1,x2,x); f1=diff(f); f1=solve(f1); if f1=0 ti=double(f1); else break end x=subs(x,t,ti(1,1); m=g.'*g; f=(1-x1)2+2*(x2-x12)2; a1=diff(f,x1); b1=diff(f,x2); a1=subs(a1,x1,x2,x); b1=subs(b1,x1,x2,x); g1=a1;b1; p=(g1.'*g1)/m; d=

9、-g1+p*d; a-a1; b=b1; n=n+1;endfprintf('最优解为：');xfprintf('最小值为：');f=subs(f,x1,x2,x)fprintf('共迭代了n步：');n （6）CG法推广 运行结果：在matlab对话框中输入num3(0;0,0.001) 得到结果：最优解为： x = 1 1最小值为：f = 0共迭代了n步n = 2（六）结果分析针对0.618法：在本题手工计算时我们采用了借助图像简化计算，matlab运算的结果与手工计算结果基本完全吻合，两种方法的正确性互相得到了验证。针对CG法:本题我们分别选择了两个初始点进行迭代，对这两个初始点进行比较可以看出使用（-1,1）这个初始点迭代步数更少，同时使用该点作为初始点进行手工计算时计算量也相对小于（0,0）作为初始点，因此我们要根据实际情况选择初始点。针对CG推广法：是在CG法基础上进行修改，用