最優(yōu)化方法課程設(shè)計(jì)

1、最優(yōu)化方法課程設(shè)計(jì)報(bào)告2016年 6月 14日摘要最優(yōu)化理論和方法日益受到重視，已經(jīng)滲透到生產(chǎn)、管理、商業(yè)、軍事、決 策等各個(gè)領(lǐng)域，而最優(yōu)化模型與方法廣泛應(yīng)用于工業(yè)、農(nóng)業(yè)、交通運(yùn)輸、商業(yè)、 國(guó)防、建筑、通信、政府機(jī)關(guān)等各個(gè)部門及各個(gè)領(lǐng)域。伴隨著計(jì)算機(jī)技術(shù)的高速 發(fā)展，最優(yōu)化理論與方法的迅速進(jìn)步為解決實(shí)際最優(yōu)化問題的軟件也在飛速發(fā)展。 其中，MATLAB軟件已經(jīng)成為最優(yōu)化領(lǐng)域應(yīng)用最廣的軟件之一。有了 MATLAB這個(gè) 強(qiáng)大的計(jì)算平臺(tái)，既可以利用MATLAB優(yōu)化工具箱(OptimizationToolbox)中的 函數(shù)，又可以通過算法變成實(shí)現(xiàn)相應(yīng)的最優(yōu)化計(jì)算。關(guān)鍵詞：優(yōu)化、線性規(guī)劃，黃金分割法、最

2、速下降法、MATLAB、算法AbstractOptimization theory and methods and more attention, have penetrated into the production, management, business, military, decision-making and other fields, and optimization models and methods widely used in industry, agriculture, transportation, commerce, defense, construction,

3、students, government various departments and agencies and other fields. With the rapid development of computer technology, optimization theory and methods for the rapid progress of the optimization problem to solve practical software is also developing rapidly. Which, MATLAB software has become the

4、most optimization software is one of the most widely used. With this powerful computing platform MATLAB, either using MATLAB optimization toolbox (OptimizationToolbox) in the function, but also can achieve the appropriate algorithm to optimize into the calculation.Key words: Optimization、Golden sect

5、ion method、steepest descent method、 MATLAB、algorithm第一章單純形算法的基本思想與原理1.1單純形算法的基本思路單純形法的基本思想是：先找出一個(gè)基本可行解，對(duì)它進(jìn)行鑒別，看是否是最優(yōu) 解；若不是，則按照一定法則轉(zhuǎn)換到另一改進(jìn)的基本可行解，再鑒別；若仍不是， 則再轉(zhuǎn)換,按此重復(fù)進(jìn)行。因基本可行解的個(gè)數(shù)有限，故經(jīng)有限次轉(zhuǎn)換必能得出 問題的最優(yōu)解。如果問題無最優(yōu)解也可用此法判別。求解步驟：（1）確定初始基可行解從線性規(guī)劃標(biāo)準(zhǔn)形的系數(shù)矩陣中能直接找出m個(gè)線性獨(dú)立的單位向量；對(duì)約束條件全為“二”連接的LP，化為標(biāo)準(zhǔn)形，左端添加松弛變量后即形成 一個(gè)單位子

6、矩陣；約束條件中含有“二”或仁”連接的方程，在插入剩余變量后找不到單位矩 陣，則必須采用“人造基”法，也稱“人工變量”法。（2）最優(yōu)性檢驗(yàn)及解的判別準(zhǔn)則最優(yōu)性判定準(zhǔn)則多重最優(yōu)解判定準(zhǔn)則無界最優(yōu)解判定準(zhǔn)則（3）換基迭代確定換入變量確定換出變量樞運(yùn)算（旋轉(zhuǎn)運(yùn)算）1.2算 法 流 程 圖求出一個(gè)初始基本可行解I字?jǐn)嗟玫交?可行解是否乒無結(jié)束 否求H4便目標(biāo)得到改善的基本可行解1.3用matlab編寫源程序Functionx,f=zuiyouhua(A,b,c)Size(A) = m,n;i=n+1:n+m;N=1:n;B=eye(m,m);xb=b ;xn=zeros(m,1);f1=0;w=zer

7、os(1,m);z=-c;flag=1;while(1)a,k=max(z);If a=0flag=0;breakelsey=inv(B)*A(:,k)if y0);a,rl=min(bl(t)/y(t)r=t(rl);i(:,k)=kB(:,k)=A(:,k);cb=C(:,i);xb=inv(B)*b;b0=xb;x=zeros(1,n+m)x(:,i)=xbf=cb*xbz=cb*inv(B)*A-C;endend1.4單純形算法應(yīng)用舉例線性規(guī)劃問題：min f (X = 0.1x + 0.3x + 0.9 x + 0 x + 1.1x + 0.2 x + 0.8 x +1.4 x123

8、456782x + x + x + x 10012342x + x + 3x + 2x + x 100s.t 23567x + x + 3 x + 2 x + 3 x + 4 x 100 x , x , x , x , x , x , x , x 012345678在matlab的命令窗口輸入：A=2,1,1,1,0,0,0,0;0,2,1,0,3,2,1,0;1,0,1,3,0,2,3,4;b=100,100,100c=0.1,0.3,0.9,0,1.1,0.2,0.8,1.4;x,f=zuiyouhua(A,b,c)Matlab輸出內(nèi)容：x=10 50 0 30 0 0 0 0f=-16第

9、二章黃金分割法的基本思想與原理2.1黃金分割法的基本思路黃金分割法適用于b,a 區(qū)間上的任何單股函數(shù)求極小值問題,對(duì)函數(shù)除要求“單 峰”外不做其他要求，甚至可以不連續(xù)。因此，這種方法的適應(yīng)面非常廣。黃金 分割法也是建立在區(qū)間消去法原理基礎(chǔ)上的試探方法，即在搜索區(qū)間a,b內(nèi)適當(dāng) 插入兩點(diǎn)a1,a2,并計(jì)算其函數(shù)值a1,a2,將區(qū)間分成三段，應(yīng)用函數(shù)的單峰性質(zhì)， 通過函數(shù)值大小的比較，刪去其中一段，是搜索區(qū)間得以縮小。然后再在保留下 來的區(qū)間上作同樣的處理，如此迭代下去，是搜索區(qū)間無限縮小，從而得到極小 點(diǎn)的數(shù)值近似解。2.2算法流程圖2.3用matlab編寫源程序a=input（請(qǐng)輸入初始區(qū)間下

10、端點(diǎn):na=）;b=input（請(qǐng)輸入初始區(qū)間上端點(diǎn):nb=）;e=input（請(qǐng)輸入計(jì)算精度:ne=）;t=b-a;while tea1=a+0.382*(b-a);a2=a+0.618*(b-a);f1=question2(a1);f2=question2(a2);if f1 0,令k ：= 0 ；第2步 計(jì)算w (xk)，若IIW (xk)IMg，停止迭代.輸出xk .否則進(jìn)行第三步；第 3 步取pk =-Vf (xk)；=min f (xk + tpk)t 0第4步 進(jìn)行一維搜索，求tk，使得f (Xk + t pk )令 Xk+1 = Xk + k，k := k +1，轉(zhuǎn)第 2 步。

11、由以上計(jì)算步驟可知，最速下降法迭代終止時(shí)，求得的是目標(biāo)函數(shù)駐點(diǎn)的一個(gè)近似點(diǎn)。3.2算法流程圖開始求人使其滿足3.3用matlab編寫源程序function R,n=steel(x0,y0,eps) syms x;syms y;f=(x-2)A2+(y-4)A2;v=x,y;j=jacobian(f,v);T=subs(j(1),x,x0),subs(j(2),y,y0);temp=sqrt(T(1)A2+(T(2)A2);x1=x0;y1=y0;n=0;syms kk;while (tempeps)d=-T;f1=x1+kk*d(1);f2=y1+kk*d(2);fT=subs(j(1),x,

12、f1),subs(j(2),y,f2);fun=sqrt(fT (1)八2+(仃(2)八2);Mini=Gold(fun,0,1,0.00001);x0=x1+Mini*d(1);y0=y1+Mini*d(2);T=subs(j(1),x,x0),subs(j(2),y,y0);temp=sqrt(T(1)A2+(T(2)A2);x1=x0;y1=y0;n=n+1;endR=x0,y0%調(diào)用黃金分割法：function Mini=Gold(f,a0,b0,eps)syms x;format long;syms kk;u=a0+0.382*(b0-a0);v=a0+0.618*(b0-a0);k

13、=0;a=a0;b=b0;array(k+1,1)=a;array(k+1,2)=b;while(b-a)/(b0-a0)=eps)Fu=subs(f,kk,u);Fv=subs(f,kk,v);if(FuFv)a=u;u=v;v=a+0.618*(b-a);k=k+1;endarray(k+1,1)=a;array(k+1,2)=b;endMini=(a+b)/2;3.4最速下降法應(yīng)用舉例函數(shù) f=(x-2)A2+(y-4)A2;在命令窗口輸入R,n=steel(0,1,0.00001) 運(yùn)行結(jié)果如下：R =1.9999999999828113.999999999974216R = 1.99

14、99999999828113.999999999974216第四章懲罰函數(shù)法的基本思想與原理4.1懲罰函數(shù)法的基本思路罰函數(shù)法求解帶約束的非線形規(guī)劃問題的基本思想是：利用問題的目標(biāo)函數(shù)和約 束函數(shù)構(gòu)造出帶參數(shù)的所謂增廣目標(biāo)函數(shù)，把約束非線形規(guī)劃問題轉(zhuǎn)化為一系列 無約束非線形規(guī)劃問題來求解。增廣目標(biāo)函數(shù)由兩個(gè)部分構(gòu)成，一部分是原問題 的目標(biāo)函數(shù)，另一部分是由約束函數(shù)構(gòu)造出的“懲罰”項(xiàng)，“懲罰”項(xiàng)的作用是 對(duì)“違規(guī)”的點(diǎn)進(jìn)行“懲罰”。罰函數(shù)法主要有兩種形式。一種稱為外部罰函數(shù) 法，或稱外點(diǎn)法，這種方法的迭代點(diǎn)一般在可行域的外部移動(dòng)，隨著迭代次數(shù)的 增加，“懲罰”的力度也越來越大，從而迫使迭代點(diǎn)向可

15、行域靠近；另一種成為 內(nèi)部罰函數(shù)法，或稱內(nèi)點(diǎn)法，它從滿足約束條件的可行域的內(nèi)點(diǎn)開始迭代，并對(duì) 企圖穿越可行域邊界的點(diǎn)予以“懲罰”，當(dāng)?shù)c(diǎn)越接近邊界，“懲罰”就越大， 從而保證迭代點(diǎn)的可行性。4.2算法流程圖給定X（。）、?。ā＃?、c、Y4.3用mat lab編寫源程序global lamada %主程序main2.m，懲罰數(shù)方法 x0 = 1 1;lamada = 2;c = 10;e = 1e-5;k = 1;while lamada*q4_fun2p(x0) = ex0 = fminsearch(q4_fun2min,x0);lamada = c*lamada;k = k+1;enddisp(最優(yōu)解),disp(x0)Kfunction r = q4_fun2p(x)%罰項(xiàng)函數(shù)r = (x(1)-1)A3-x(2)*x(2)A2;function r = q4_fun2min(x)%輔助函數(shù)global lamadar = x(1)A2+x(2)A2+lamada*q4_fun2p(x);4.4懲罰函數(shù)法應(yīng)用舉例求解非線性規(guī)劃問題：min (x1八2+x2八2)S.t. (x1-1)八3-x2八2=0運(yùn)行結(jié)果如下：最優(yōu)解1.00012815099