Matlab PPT 第七章最優(yōu)化計算方法

1、第七章第七章 最優(yōu)化計算方法最優(yōu)化計算方法一、實驗目的：一、實驗目的：第一節(jié)第一節(jié) 線性方程組的應用線性方程組的應用1、了解線性規(guī)劃問題及可行解、最優(yōu)解的概念、了解線性規(guī)劃問題及可行解、最優(yōu)解的概念 ； 2、掌握、掌握Matlab軟件關于求解線性規(guī)劃的語句和方法。軟件關于求解線性規(guī)劃的語句和方法。二、實驗原理和方法：二、實驗原理和方法：在生活實踐中，很多重要的實際問題都是線性的（至少能在生活實踐中，很多重要的實際問題都是線性的（至少能夠用線性函數(shù)很好的近似表示），所以我們一般把這些問夠用線性函數(shù)很好的近似表示），所以我們一般把這些問題化為線性的目標函數(shù)和約束條件進行分析，通常將目標題化為線性的

2、目標函數(shù)和約束條件進行分析，通常將目標函數(shù)和約束都是線性表達式的規(guī)劃問題稱為線性規(guī)劃函數(shù)和約束都是線性表達式的規(guī)劃問題稱為線性規(guī)劃 。它的一般形式是：它的一般形式是： )n, 2 , 1i (0 xbxaxaxabxaxaxabxaxaxa. t . sxcxcxcfminimnmn22m11m2nn22221211nn1212111nn2211也可以用矩陣形式來表示：也可以用矩陣形式來表示：0 x,bAx. t . sxcfminT線性規(guī)劃的可行解是滿足約束條件的解；線性規(guī)劃線性規(guī)劃的可行解是滿足約束條件的解；線性規(guī)劃的最優(yōu)解是使目標函數(shù)達到最優(yōu)的可行解。的最優(yōu)解是使目標函數(shù)達到最優(yōu)的可行解

3、。線性規(guī)劃關于解的情況可以是：線性規(guī)劃關于解的情況可以是：1、無可行解，即不存在滿足約束條件的解；、無可行解，即不存在滿足約束條件的解；2、有唯一最優(yōu)解，即在可行解中有唯一的最有解；、有唯一最優(yōu)解，即在可行解中有唯一的最有解；4、有可行解，但由于目標函數(shù)值無界而無最優(yōu)解。、有可行解，但由于目標函數(shù)值無界而無最優(yōu)解。3、有無窮最優(yōu)解，即在可行解中有無窮個解都可使目、有無窮最優(yōu)解，即在可行解中有無窮個解都可使目 標函數(shù)達到最優(yōu)；標函數(shù)達到最優(yōu)； 一般求解線性規(guī)劃的常用方法是單純形法和改進一般求解線性規(guī)劃的常用方法是單純形法和改進的單純形法，這類方法的基本思路是先求得一個可行的單純形法，這類方法的基

4、本思路是先求得一個可行解，檢驗是否為最優(yōu)解；若不是，可用迭代的方法找解，檢驗是否為最優(yōu)解；若不是，可用迭代的方法找到另一個更優(yōu)的可行解，經過有限次迭代后，可以找到另一個更優(yōu)的可行解，經過有限次迭代后，可以找到可行解中的最優(yōu)解或者判定無最優(yōu)解。到可行解中的最優(yōu)解或者判定無最優(yōu)解。 三、內容與步驟：三、內容與步驟：在在Matlab優(yōu)化工具箱中，優(yōu)化工具箱中，linprog函數(shù)是使用單純形法求解函數(shù)是使用單純形法求解下述線性規(guī)劃問題的函數(shù)。下述線性規(guī)劃問題的函數(shù)。vubxvlbbeqaeqxbAxtsxcfT;,.min它的命令格式為：它的命令格式為：)0,(,),(,xvubvlbbeqaeqbA

5、clinprogfvalxvubvlbbeqaeqbAclinprogfvalx其中：其中：A為約束條件矩陣，為約束條件矩陣，b,c分別為目標函數(shù)的系數(shù)向量和分別為目標函數(shù)的系數(shù)向量和約束條件中最右邊的數(shù)值向量；也可設置解向量的上界約束條件中最右邊的數(shù)值向量；也可設置解向量的上界vlb和和下界下界vub，即解向量必須滿足，即解向量必須滿足vlb=x=vub；還可預先設置；還可預先設置初始解向量初始解向量x0。如沒有不等式，而只有等式時，如沒有不等式，而只有等式時，A= ,b= ;輸出的結果：輸出的結果：x表示最優(yōu)解向量；表示最優(yōu)解向量；fval表示最優(yōu)值。表示最優(yōu)值。【例【例 1】 求解線性規(guī)

6、劃問題：求解線性規(guī)劃問題： 3 , 2 , 1i , 0 x1xx23x2xx411xx2x. t . sxxx3fmaxi31321321321解：考慮到解：考慮到linprog函數(shù)只解決形如函數(shù)只解決形如的線性規(guī)劃。所以先要將線性規(guī)劃的線性規(guī)劃。所以先要將線性規(guī)劃變?yōu)槿缦滦问剑鹤優(yōu)槿缦滦问剑?;,. .minxbeqaeqxbAxtsxcfT3 ,2, 1i ,0 x3x2xx411xx2x1xx2. t . sxxx3fmini32132131321然后建立然后建立M文件如下：文件如下：c=-3;1;1;A=1 -2 1;4 -1 -2;b=11;-3;aeq=2 0 -1;beq=-1

7、;vlb=0;0;0;x,fval=linprog(c,A,b,aeq,beq,vlb) Matlab程序：程序： ch701.m以以ch701作為文件名保存此作為文件名保存此M文件后，在命令窗口文件后，在命令窗口輸入輸入ch701后即可得到結果：后即可得到結果：x = 4.0000 1.0000 9.0000同時返回同時返回fval=-2對應到原來的線性規(guī)劃中即知目標函數(shù)的最大值為對應到原來的線性規(guī)劃中即知目標函數(shù)的最大值為2，此時，此時x1=4,x2=1,x3=9。 第二節(jié)第二節(jié) 無約束規(guī)劃計算方法無約束規(guī)劃計算方法一、實驗目的一、實驗目的1、了解無約束規(guī)劃問題的求解原理與方法、了解無約束

8、規(guī)劃問題的求解原理與方法 ； 2、會用、會用Matlab軟件求解無約束規(guī)劃問題。軟件求解無約束規(guī)劃問題。 二、實驗原理和方法二、實驗原理和方法無約束規(guī)劃問題的解法一般按目標函數(shù)的形式分為兩大類：無約束規(guī)劃問題的解法一般按目標函數(shù)的形式分為兩大類：一類是一元函數(shù)的一維搜索法，如黃金分割法、插值法等；一類是一元函數(shù)的一維搜索法，如黃金分割法、插值法等；另一類是求解多元函數(shù)的下降迭代法。另一類是求解多元函數(shù)的下降迭代法。迭代的基本思想和步驟大致可分為以下四步：迭代的基本思想和步驟大致可分為以下四步：繼續(xù)迭代返回否則，令如果是，則結束運算；優(yōu)解。是否滿足精度要求的最檢驗新得到的點由此得到下一個點使得方

9、向選取適當?shù)牟介L出發(fā)，沿由）的值時下降的；目標函數(shù)使得沿著這個方向的后，選取一個搜索方向得到并令選取初始點)2(, 1)4)()(,3)(,)2; 0,) 1110kkxPxxxfPxfPxxfPxkxkkkkkkkkkkkkkk三、實驗內容與步驟三、實驗內容與步驟在在Matlab軟件中，求解無約束規(guī)劃的常用命令是：軟件中，求解無約束規(guī)劃的常用命令是： x=fminunc(fun,x0) 其中，其中，fun函數(shù)應預先定義到函數(shù)應預先定義到M文件中，并設置初始文件中，并設置初始解向量為解向量為x0。 【例【例 2】求解求解1212221x2xxx21x23)x(fmin取取T)0()4 , 2(

10、x解：首先建立函數(shù)文件解：首先建立函數(shù)文件fun702.m) 1 (2)2() 1 (2)2(2/12)1 (2/3)(702xxxxxfxfunffunction 以以fun702為文件名保存此函數(shù)文件。為文件名保存此函數(shù)文件。 在命令窗口輸入：在命令窗口輸入： x0=-2;4;x=fminunc(fun702,x0)結果顯示：結果顯示： f = -1.0000 x = 1.0000 1.0000即極小值為即極小值為-1，是，是x1=1,x2=1時取得。時取得。Matlab程序：程序： ch702.m【例【例 3】 解非線性方程組解非線性方程組01)5 . 0()2(012221221xxx

11、x解：解此非線性方程組等價于求解無約束非線性規(guī)劃問題：解：解此非線性方程組等價于求解無約束非線性規(guī)劃問題： 222212221) 1)5 . 0()2() 1(minxxxx然后建立函數(shù)文件然后建立函數(shù)文件fun703.m 2)12)5 . 0)2(2)2) 1 (2)1)2(2)1 ()(703xxxxfxfunffunction在命令窗口輸入：在命令窗口輸入： x0=0;0;x=fminunc(fun703,x0)結果顯示：結果顯示： f =5.2979e-011 x =1.0673 0.1392則非線性方程組的解為則非線性方程組的解為x1=1.0673,x2=0.1392。 Matlab

12、程序：程序： ch703.m第三節(jié)第三節(jié) 約束非線性規(guī)劃計算方法約束非線性規(guī)劃計算方法 一、實驗目的一、實驗目的1、了解約束非線性規(guī)劃問題的求解原理與方法；、了解約束非線性規(guī)劃問題的求解原理與方法； 2、會用、會用Matlab軟件求解約束非線性規(guī)劃問題。軟件求解約束非線性規(guī)劃問題。 二、實驗原理和方法二、實驗原理和方法對于約束非線性規(guī)劃，隨著目標函數(shù)和約束條件的不同，對于約束非線性規(guī)劃，隨著目標函數(shù)和約束條件的不同，解法也不同，一般來說，有兩類方法：解法也不同，一般來說，有兩類方法：（1）、將約束問題化為無約束問題的求解方法；）、將約束問題化為無約束問題的求解方法；（2）、用線性規(guī)劃來逼近非線

13、性規(guī)劃；）、用線性規(guī)劃來逼近非線性規(guī)劃； 三、實驗內容與步驟三、實驗內容與步驟 約束非線性規(guī)劃的一般形式為：約束非線性規(guī)劃的一般形式為： )(minxfxubxlbxceqxgbeqxaeqbAxt s）（非線性約束線性約束0)(, 0)()(*,.其中，其中，f(x)為多元實值函數(shù)為多元實值函數(shù);g(x)為向量函數(shù)為向量函數(shù),并且并且f(x),g(x)中至中至少有一個函數(shù)是非線性函數(shù)的（否則成為線性規(guī)劃問題）。少有一個函數(shù)是非線性函數(shù)的（否則成為線性規(guī)劃問題）。x=fmincon(fun,x0,A,b)x=fmincon(fun,x0,A,b,Aeq,beq)x=fmincon(fun,x0

14、,A,b,Aeq,beq,lb,ub)x=fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon)在在Matlab優(yōu)化工具箱中，優(yōu)化工具箱中，fmincon函數(shù)是用函數(shù)是用SQP算法來算法來解決一般的約束非線性規(guī)劃的函數(shù)，它的命令格式為：解決一般的約束非線性規(guī)劃的函數(shù)，它的命令格式為：【例【例 4】 求解約束非線性規(guī)劃：求解約束非線性規(guī)劃： 3. .)3(max222222111xetsxexexxx(初值為初值為1;1)解解: :首先建立一個首先建立一個m文件文件fun7041.mfunctiony=fun7041(x)y=-exp(x(1)*x(2)2*(3-ex

15、p(x(1)-x(2)2);存儲為存儲為fun7041.m首先將問題轉化為首先將問題轉化為matlab要求的格式要求的格式;即求出即求出fun,A,b,Aeq,Beq,X0,Lb,Ub然后建立一個然后建立一個m文件文件fun7042.mfunctionc,cep=fun7042(x)c=;%c為非線性不等式為非線性不等式,且為且為c=0cep=exp(x(1)+x(2)2-3;%cep為非線性等式為非線性等式然后存儲為然后存儲為fun7042.m最后在命令窗口中輸入：A=;b=;Aeq=;Beq=;Lb=;Ub=;x,f=fmincon(fun7041,1;1,fun7042)-f因題目中有非

16、線性約束條件，所以建立非線性約束因題目中有非線性約束條件，所以建立非線性約束m-文件。文件。Matlab程序：程序： ch704.m結果為:x = 0.8852 0.7592f = 6.2043e-016ans= - 6.2043e-016最后的結果為: - 6.2043e-016【例【例 5】 求解約束非線性規(guī)劃：求解約束非線性規(guī)劃： 1 ; 1 ; 1 ; 1 0102335. .)4()3()2() 1(min4321432124232221初值為ixxxxxxxxxtsxxxx解：首先建立一個解：首先建立一個m文件文件fun705.mfunctiony=fun705(x)y=(x(1)

17、-1)2+(x(2)-2)2+(x(3)-3)2+(x(4)-4)2;存儲為存儲為fun705.m文件文件.x0=1;1;1;1;A=1 1 1 1;3 3 2 1;B=5;10;Aeq=;Beq=;Lb=0;0;0;0;x,g=fmincon(fun705,x0,A,B,Aeq,Beq,Lb)答案為:x = 0.0000 0.6667 1.6665 2.6668g = 6.3333Matlab程序：程序： ch705.m非現(xiàn)性規(guī)劃的基本概念非現(xiàn)性規(guī)劃的基本概念定義定義 如果目標函數(shù)或約束條件中至少有一個是非線性函數(shù)時的最優(yōu)化問題就叫做非線性規(guī)劃問題非線性規(guī)劃問題 一般形式一般形式: （1）

18、其中 ， 是定義在 En 上的實值函數(shù)，簡記: Xfmin .,.,2 , 1 0 m;1,2,., 0. . ljXhiXgtsjinTnExxxX,21jihgf,1nj1ni1nE :h ,E :g ,E :EEEf 其它情況其它情況: 求目標函數(shù)的最大值或約束條件為小于等于零的情況，都可通過取其相反數(shù)化為上述一般形式用MATLAB軟件求解,其輸入格式輸入格式如下: 1. x=quadprog(H,C,A,b); 2. x=quadprog(H,C,A,b,Aeq,beq); 3. x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB); 4. x=quadprog(H,

19、C,A,b, Aeq,beq ,VLB,VUB,X0); 5. x=quadprog(H,C,A,b, Aeq,beq ,VLB,VUB,X0,options); 6. x,fval=quaprog(.); 7. x,fval,exitflag=quaprog(.); 8. x,fval,exitflag,output=quaprog(.);1、二次規(guī)劃、二次規(guī)劃標準型為： Min Z= 21XTHX+cTX s.t. AX=b beqXAeq VLBXVUB 例例1 1 min f(x1,x2)=-2x1-6x2+x12-2x1x2+2x22 s.t. x1+x22 -x1+2x22 x10

20、, x20 1、寫成標準形式寫成標準形式： 2、 輸入命令輸入命令： H=1 -1; -1 2; c=-2 ;-6;A=1 1; -1 2;b=2;2; Aeq=;beq=; VLB=0;0;VUB=; x,z=quadprog(H,c,A,b,Aeq,beq,VLB,VUB)3、運算結果運算結果為： x =0.6667 1.3333 z = -8.2222212121622 11- 1 ),(minxxxxxxzT212100222 11 1 xxxxs.t. 1. 首先建立M文件fun.m,定義目標函數(shù)F（X）:function f=fun(X);f=F(X);2、一般非線性規(guī)劃、一般非線

21、性規(guī)劃標準型為： min F(X) s.t AX=b beqXAeq G(X)0 Ceq(X)=0 VLBXVUB 其中X為n維變元向量，G(X)與Ceq(X)均為非線性函數(shù)組成的向量，其它變量的含義與線性規(guī)劃、二次規(guī)劃中相同.用Matlab求解上述問題，基本步驟分三步：2. 若約束條件中有非線性約束:G(X)0或Ceq(X)=0,則建立M文件nonlcon.m定義函數(shù)G(X)與Ceq(X): function G,Ceq=nonlcon(X) G=. Ceq=. 3. 建立主程序.非線性規(guī)劃求解的函數(shù)是fmincon,命令的基本格式如下： (1) x=fmincon(fun,X0,A,b)

22、(2) x=fmincon(fun,X0,A,b,Aeq,beq) (3) x=fmincon(fun,X0,A,b, Aeq,beq,VLB,VUB) (4) x=fmincon(fun,X0,A,b,Aeq,beq,VLB,VUB,nonlcon)(5)x=fmincon(fun,X0,A,b,Aeq,beq,VLB,VUB,nonlcon,options) (6) x,fval= fmincon(.) (7) x,fval,exitflag= fmincon(.) (8)x,fval,exitflag,output= fmincon(.)輸出極值點M文件迭代的初值參數(shù)說明變量上下限注意：

23、注意：1 fmincon函數(shù)提供了大型優(yōu)化算法和中型優(yōu)化算法。默認時，若在fun函數(shù)中提供了梯度（options參數(shù)的GradObj設置為on），并且只有上下界存在或只有等式約束，fmincon函數(shù)將選擇大型算法。當既有等式約束又有梯度約束時，使用中型算法。2 fmincon函數(shù)的中型算法使用的是序列二次規(guī)劃法。在每一步迭代中求解二次規(guī)劃子問題，并用BFGS法更新拉格朗日Hessian矩陣。3 fmincon函數(shù)可能會給出局部最優(yōu)解，這與初值X0的選取有關。1、寫成標準形式寫成標準形式： s.t. 00546322121xxxx2100 xx22212121212minxxxxf2221212

24、1212minxxxxf 2x1+3x2 6 s.t x1+4x2 5 x1,x2 0例例22、先建立先建立M-文件文件 fun3.m: function f=fun3(x); f=-x(1)-2*x(2)+(1/2)*x(1)2+(1/2)*x(2)23、再建立主程序youh2.m： x0=1;1; A=2 3 ;1 4; b=6;5; Aeq=;beq=; VLB=0;0; VUB=; x,fval=fmincon(fun3,x0,A,b,Aeq,beq,VLB,VUB)4、運算結果為：運算結果為： x = 0.7647 1.0588 fval = -2.02941先建立先建立M文件文件

25、fun4.m,定義目標函數(shù)定義目標函數(shù): function f=fun4(x); f=exp(x(1) *(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1);) 12424()(22122211xxxxxexfx x1+x2=0 s.t. 1.5+x1x2 - x1 - x2 0 -x1x2 10 0例例32再建立再建立M文件文件mycon.m定義非線性約束：定義非線性約束： function g,ceq=mycon(x) g=x(1)+x(2);1.5+x(1)*x(2)-x(1)-x(2);-x(1)*x(2)-10;3主程序主程序youh3.m為為:x0=-1;

26、1;A=;b=;Aeq=1 1;beq=0;vlb=;vub=;x,fval=fmincon(fun4,x0,A,b,Aeq,beq,vlb,vub,mycon)3. 運算結果為運算結果為： x=-1.22501.2250fval=1.8951 例4 100 , 50 07 025 . .2min 21222122221121xxxxXgxxXgtsxxXf1先建立先建立M-文件文件fun.m定義目標函數(shù)定義目標函數(shù): function f=fun(x); f=-2*x(1)-x(2);2再建立再建立M文件文件mycon2.m定義非線性約束：定義非線性約束：functiong,ceq=myco

27、n2(x)g=x(1)2+x(2)2-25;x(1)2-x(2)2-7;3.主程序主程序fxx.m為為:x0=3;2.5;VLB=00;VUB=510;x,fval,exitflag,output=fmincon(fun,x0,VLB,VUB,mycon2)4.運算結果為運算結果為:x=4.00003.0000fval=-11.0000exitflag=1output=iterations:4funcCount:17stepsize:1algorithm:1x44charfirstorderopt:cgiterations:應用實例：應用實例：供應與選址供應與選址 某公司有6個建筑工地要開工，

28、每個工地的位置（用平面坐標系a，b表示，距離單位：千米 ）及水泥日用量d(噸)由下表給出。目前有兩個臨時料場位于A(5,1)，B(2,7)，日儲量各有20噸。假設從料場到工地之間均有直線道路相連。 （1）試制定每天的供應計劃，即從A，B兩料場分別向各工地運送多少噸水泥，使總的噸千米數(shù)最小。 （2）為了進一步減少噸千米數(shù)，打算舍棄兩個臨時料場，改建兩個新的，日儲量各為20噸，問應建在何處，節(jié)省的噸千米數(shù)有多大？工地位置（a，b）及水泥日用量 d 1 2 3 4 5 6 a 1.25 8.75 0.5 5.75 3 7.25 b 1.25 0.75 4.75 5 6.5 7.25 d 3 5 4

29、7 6 11 （一）、建立模型（一）、建立模型 記工地的位置為記工地的位置為(ai，bi)，水泥日用量為，水泥日用量為di，i=1,6;料場位置為料場位置為(xj，yj)，日儲量為，日儲量為ej，j=1,2；從料場；從料場j向工地向工地i的運送量為的運送量為Xij。目標函數(shù)為：216122)()(minjiijijijbyaxXf 約束條件為：2 , 1 ,6 , 2 , 1 ,6121jeXidXjiijijij 當用臨時料場時決策變量為：Xij，當不用臨時料場時決策變量為：Xij，xj，yj。（二）使用臨時料場的情形（二）使用臨時料場的情形 使用兩個臨時料場A(5,1)，B(2,7).求從

30、料場j向工地i的運送量為Xij，在各工地用量必須滿足和各料場運送量不超過日儲量的條件下，使總的噸千米數(shù)最小，這是線性規(guī)劃問題. 線性規(guī)劃模型為：2161),(minjiijXjiaaf2 , 1 , 6 , 2 , 1 , s.t.6121jeXidXjiijijij其中 22)()(),(ijijbyaxjiaa，i=1,2,6,j=1,2,為常數(shù)。 設X11=X1, X21= X 2, X31= X 3, X41= X 4, X51= X 5, X61= X 6X12= X 7, X22= X 8, X32= X 9, X42= X 10, X52= X 11, X62= X 12 編寫程

31、序gying1.m計算結果為：計算結果為：x = 3.0000 5.0000 0.0000 7.0000 0.0000 1.0000 0.0000 0.0000 4.0000 0.0000 6.0000 10.0000fval = 136.2275即由料場 A、B 向 6 個工地運料方案為： 1 2 3 4 5 6 料場 A 3 5 0 7 0 1 料場 B 0 0 4 0 6 10 總的噸千米數(shù)為136.2275。 （三）改建兩個新料場的情形（三）改建兩個新料場的情形 改建兩個新料場，要同時確定料場的位置(xj,yj)和運送量Xij，在同樣條件下使總噸千米數(shù)最小。這是非線性規(guī)劃問題。非線性規(guī)

32、劃模型為：216122)()(minjiijijijbyaxXf2 , 1 , 6 , 2 , 1 , . .6121jeXidXtsjiijijij設 X11=X1, X21= X 2, X31= X 3, X41= X 4, X51= X 5, X61= X 6 X12= X 7, X22= X 8, X32= X 9, X42= X 10, X52= X 11, X62= X 12 x1=X13, y1=X14, x2=X15, y2=X16 （1）先編寫M文件liaoch.m定義目標函數(shù)。(2) 取初值為線性規(guī)劃的計算結果及臨時料場的坐標: x0=3 5 0 7 0 1 0 0 4 0 6 10 5 1 2 7;編寫主程序gying2.m.(3) 計算結果為：x= 3.0000 5.0000 0.0707 7.0000 0 0.9293 0 0 3.9293 0 6.0000 10.0707 6.3875 4.3943 5.7511 7.1867fval = 105.4626exitf