運(yùn)籌學(xué)第一次實驗

1、熟練利用0.618法，共軛梯度法以及非二次函數(shù)的共軛梯度法求解相關(guān)問題。（一） 問題描述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：對區(qū)間a,b= a1,b1中取兩點：1=a1+0.382（b1-a1），1=a1+0.618（b1-a1）Step2：若bk-ak<,停止運(yùn)算，輸出結(jié)果，否則計算并比較。若(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元正定二次函數(shù)f(x)=1/2xTQx+bT+c,給定任一初始點x0,計算d0=-g0，置k：=0step1：tk=gkTgk/dkTQdk,xk+1=xk+tkdkstep2：判斷|gk+1|<，若成立則終止，輸出。否則轉(zhuǎn)step3step3：計算下一次的搜索方向dk+1=-gk+1+kdk，其中k=gk+1TQdk/dkTQdks

3、tep4：置k:=k+1,轉(zhuǎn)step1進(jìn)行下一次迭代。(3)CG算法的推廣：對tk：改用直接的e.l.s，求得步長因子。對k：k=gk+1Tgk+1/gkTgk（四）程序代碼及運(yùn)行結(jié)果：（1）0.618法源程序代碼a=-1;%區(qū)間端點b=1; %區(qū)間端點fprintf('初始區(qū)間為');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('得到新區(qū)間為'); interval=a,b else a=u1; u1=u2; u2=a+0.618*(b-a); fprintf('得到新區(qū)間為'); 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法 運(yùn)行結(jié)果： 初始區(qū)間為：interval

5、= -1 1得到的新區(qū)間為：得到的新區(qū)間為：interval = -0.2360 0.5278得到的新區(qū)間為：得到的新區(qū)間為：interval = 0.0558 0.3475得到的新區(qū)間為：得到的新區(qū)間為：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('最優(yōu)解為：'

7、);xfprintf('共迭代了n步');n（4）CG法 運(yùn)行結(jié)果：在matlab對話框中輸入Untitled3(0;0,0.2) 得到結(jié)果：最優(yōu)解為：x = 0 2共迭代了n步：n = 2在matlab對話框中輸入Untitled3(-1;1,0.2) 得到結(jié)果：最優(yōu)解為：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('最優(yōu)解為：');xfprintf('最小值為：');f=subs(f,x1,x2,x)fprintf('共迭代了n步：');n （6）CG法推廣 運(yùn)行結(jié)果：在matlab對話框中輸入num3(0;0,0.001) 得到結(jié)果：最優(yōu)解為： x = 1 1最小值為：f = 0共迭代了n步n = 2（六）結(jié)果分析針對0.618法：在本題手工計算時我們采用了借助圖像簡化計算，matlab運(yùn)算的結(jié)果與手工計算結(jié)果基本完全吻合，兩種方法的正確性互相得到了驗證。針對CG法:本題我們分別選擇了兩個初始點進(jìn)行迭代，對這兩個初始點進(jìn)行比較可以看出使用（-1,1）這個初始點迭代步數(shù)更少，同時使用該點作為初始點進(jìn)行手工計算時計算量也相對小于（0,0）作為初始點，因此我們要根據(jù)實際情況選擇初始點。針對CG推廣法：是在CG法基礎(chǔ)上進(jìn)行修改，用