【數(shù)學(xué)建?！康?講_非線性規(guī)劃模型

1、數(shù)學(xué)建模數(shù)學(xué)建模非線性規(guī)劃模型非線性規(guī)劃模型 1 1非線性規(guī)劃的基本理論非線性規(guī)劃的基本理論4 4實(shí)驗(yàn)作業(yè)實(shí)驗(yàn)作業(yè)2 用數(shù)學(xué)軟件求解非線性規(guī)劃用數(shù)學(xué)軟件求解非線性規(guī)劃3 鋼管訂購(gòu)及運(yùn)輸優(yōu)化模型鋼管訂購(gòu)及運(yùn)輸優(yōu)化模型非線性規(guī)劃非線性規(guī)劃 返回返回 定義定義 如果目標(biāo)函數(shù)或約束條件中至少有一個(gè)是非線性函數(shù),則最優(yōu)化問(wèn)題就叫做非線性規(guī)劃問(wèn)題非線性規(guī)劃問(wèn)題非現(xiàn)性規(guī)劃的基本概念非現(xiàn)性規(guī)劃的基本概念 一般形式一般形式: （1） 其中 ， 是定義在 R Rn 上的實(shí)值函數(shù)，簡(jiǎn)記: Xfmin jihgf, 其它情況其它情況: 求目標(biāo)函數(shù)的最大值，或約束條件小于等于零兩種情況，都可通過(guò)取其相反數(shù)化為上述一般形

2、式1nj1ni1nR :h ,R :g ,R :RRRfnTnRxxxX=,21L =.,.,2 , 1 0 m;1,2,., 0. . ljXhiXgtsji 定義定義1 1 把滿足問(wèn)題（1）中條件的解 稱為可行解可行解（或可行（或可行點(diǎn)點(diǎn)），），所有可行點(diǎn)的集合稱為可行集可行集（或（或可行域可行域）記為D即 問(wèn)題(1)可簡(jiǎn)記為 XfDXmin定義定義2 2 對(duì)于問(wèn)題(1),設(shè) ,若存在 ,使得對(duì)一切 ,且 ,都有 ,則稱X*是f(X)在D上的局部極小值點(diǎn)局部極小值點(diǎn)（局部最優(yōu)解局部最優(yōu)解）特別地,當(dāng) 時(shí)，若 ,則稱X*是f(X)在D上的嚴(yán)格局部極小值點(diǎn)嚴(yán)格局部極小值點(diǎn)（嚴(yán)格局部最嚴(yán)格局部最

3、優(yōu)解優(yōu)解）DX *0DX *XX*XX XfXf* XfXf*定義定義3 3 對(duì)于問(wèn)題(1),設(shè) ,若對(duì)任意的 ,都有則稱X*是f(X)在D上的全局極小值點(diǎn)全局極小值點(diǎn)（全局最優(yōu)解全局最優(yōu)解）特別地,當(dāng) 時(shí)，若 ,則稱X*是f(X)在D上的嚴(yán)格全局極小值嚴(yán)格全局極小值點(diǎn)點(diǎn)（嚴(yán)格全局最優(yōu)解嚴(yán)格全局最優(yōu)解）DX *DX *XX XfXf* 返回返回)(nRX njiRXXhXg XD = =, 0, 0| ,Xf Xf *非線性規(guī)劃的基本解法非線性規(guī)劃的基本解法 返回返回 罰函數(shù)法罰函數(shù)法 罰函數(shù)法罰函數(shù)法基本思想是通過(guò)構(gòu)造罰函數(shù)把約束問(wèn)題轉(zhuǎn)化為一系列無(wú)約束最優(yōu)化問(wèn)題，進(jìn)而用無(wú)約束最優(yōu)化方法去求解

4、這類方法稱為序列無(wú)約束最小化方法序列無(wú)約束最小化方法簡(jiǎn)稱為SUMTSUMT法法 其一為SUMTSUMT外點(diǎn)法外點(diǎn)法，其二為SUMTSUMT內(nèi)點(diǎn)內(nèi)點(diǎn)法法 )2( , 0min,1212=ljjmiiXhMXgMXfMXT可設(shè)：R1 min, (3)nXT X M將問(wèn)題（）轉(zhuǎn)化為無(wú)約束問(wèn)題： 其中T(X,M)稱為罰函數(shù)罰函數(shù)，M稱為罰因子罰因子，帶M的項(xiàng)稱為罰項(xiàng)罰項(xiàng)，這里的罰函數(shù)只對(duì)不滿足約束條件的點(diǎn)實(shí)行懲罰:當(dāng) 時(shí)，滿足各 ，故罰項(xiàng)為0，不受懲罰當(dāng) 時(shí),必有約束條件 ，故罰項(xiàng)大于0，要受懲罰DX 0, 0=XhXgiiDX 00XhXgii或SUTMSUTM外點(diǎn)法外點(diǎn)法 min0 1,2,.,

5、; s.t. (1)0 1,2,., .ijfXgXimhXjl=對(duì)一般的非線性規(guī)劃： 罰函數(shù)法的缺點(diǎn)缺點(diǎn)：每個(gè)近似最優(yōu)解Xk往往不是容許解，而只能近似滿足約束，在實(shí)際問(wèn)題中這種結(jié)果可能不能使用；在解一系列無(wú)約束問(wèn)題中，計(jì)算量太大，特別是隨著Mk的增大，可能導(dǎo)致錯(cuò)誤1任意給定初始點(diǎn) X0，取M11，給定允許誤差 ，令k=1；2求無(wú)約束極值問(wèn)題 的最優(yōu)解，設(shè)Xk=X(Mk)，即 ；3若存在 ，使 ,則取MkM( ),令k=k+1返回（2），否則，停止迭代得最優(yōu)解 計(jì)算時(shí)也可將收斂性判別準(zhǔn)則 改為 0Rmin,nXT X MRmin,(,)nkkXT X MT XM=mii1kiXg10, 1=M

6、Mk 0, 0min12=miiXgMkXX*kiXg SUTM SUTM外點(diǎn)法外點(diǎn)法(罰函數(shù)法)的迭代步驟迭代步驟min (1)s.t. 0 1,2,.,ifXgXim=考慮問(wèn)題：00|0,1,2, iDXgXimD=L設(shè)集合，是可行域中所有嚴(yán)格內(nèi)點(diǎn)的集合.0 1min, kkkXDIX rXr這樣問(wèn)題（）就轉(zhuǎn)化為求一系列極值問(wèn)題：得（ ）.SUTMSUTM內(nèi)點(diǎn)法（內(nèi)點(diǎn)法（障礙函數(shù)法） 為障礙因子.為障礙項(xiàng)，或其中稱或 ：構(gòu)造障礙函數(shù)rXgrXgrXgrXfrXIXgrXfrXIrXImiimiimiimii=11111 ln1)(),( ln, 內(nèi)點(diǎn)法的迭代步驟內(nèi)點(diǎn)法的迭代步驟(1) 給定

7、允許誤差0，取10 , 01r； 近似規(guī)劃法的基本思想近似規(guī)劃法的基本思想：將問(wèn)題(3)中的目標(biāo)函數(shù) 和約束條件 近似為線性函數(shù)，并對(duì)變量的取值范圍加以限制，從而得到一個(gè)近似線性規(guī)劃問(wèn)題，再用單純形法求解之，把其符合原始條件的最優(yōu)解作為(3)的解的近似Xf0 (1,., ); 0 (1, )ijgXimhXjl=L近似規(guī)劃法近似規(guī)劃法每得到一個(gè)近似解，都從這點(diǎn)出發(fā)，重復(fù)以上步驟 這樣，通過(guò)求解一系列線性規(guī)劃問(wèn)題，產(chǎn)生一個(gè)由線性規(guī)劃最優(yōu)解組成的序列，經(jīng)驗(yàn)表明，這樣的序列往往收斂于非線性規(guī)劃問(wèn)題的解 近似規(guī)劃法的算法步驟如下：算法步驟如下：(3)在上述近似線性規(guī)劃問(wèn)題的基礎(chǔ)上增加一組限制步長(zhǎng)的線性

8、約束條件因?yàn)榫€性近似通常只在展開(kāi)點(diǎn)附近近似程度較高，故需要對(duì)變量的取值范圍加以限制， 所增加的約束條件是： njxxkjkjj, 1 L= 求解該線性規(guī)劃問(wèn)題，得到最優(yōu)解1kX； 返回返回 用MATLAB軟件求解,其輸入格式輸入格式如下: 1x=quadprog(H,C,A,b); 2x=quadprog(H,C,A,b,Aeq,beq); 3x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB); 4x=quadprog(H,C,A,b, Aeq,beq ,VLB,VUB,X0); 5x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB,X0,options)

9、; 6x,fval=quaprog(); 7x,fval,exitflag=quaprog(); 8x,fval,exitflag,output=quaprog();1二次規(guī)劃二次規(guī)劃例例1 1 min f(x1,x2)=-2x1-6x2+x12-2x1x2+2x22 s.t. x1+x22 -x1+2x22 x10, x20 1寫成標(biāo)準(zhǔn)形式寫成標(biāo)準(zhǔn)形式： 2輸入命令輸入命令： H=2 -2; -2 4; 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運(yùn)算結(jié)果

10、運(yùn)算結(jié)果為： x =08 1.2， z = -7.2T111222 2 -221min( , )2 462xxzx xxx = 1212 1 121 2200 xxxxs.t. 1 首先建立M文件fun.m,用來(lái)定義目標(biāo)函數(shù)F（X）:function f=fun(X);f=F(X);2一般非線性規(guī)劃一般非線性規(guī)劃 其中X為n維變?cè)蛄?，G(X)與Ceq(X)均為非線性函數(shù)組成的向量，其他變量的含義與線性規(guī)劃、二次規(guī)劃中相同用MATLAB求解上述問(wèn)題，基本步驟分三步：3 建立主程序.求解非線性規(guī)劃的函數(shù)是fmincon,命令的基本格式如下： (1) x=fmincon(fun,X0,A,b) (

11、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()輸出極值點(diǎn)M文件迭代的初值參數(shù)說(shuō)明變量上下限1寫成標(biāo)準(zhǔn)形式

12、寫成標(biāo)準(zhǔn)形式： s.t. 00546322121xxxx2100 xx22212121212minxxxxf=22212121212minxxxxf= 2x1+3x2 6 s.t. x1+4x2 5 x1,x2 0例例22先建立先建立M-文件文件 fun3m: function f=fun3(x); f=-x(1)-2*x(2)+(1/2)*x(1)2+(1/2)*x(2)23再建立主程序youh2m： 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)

13、4運(yùn)算結(jié)果為：運(yùn)算結(jié)果為： x = 07647 10588 fval = -202941 1先建立先建立M文件文件fun4m定義目標(biāo)函數(shù)定義目標(biāo)函數(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);12212122( )e (42421)xf xxxx xx= x1+x2=0 s.t. 1.5+x1x2 - x1 - x2 0 -x1x2 10 0例例3 2再建立再建立M文件文件myconm定義非線性約束：定義非線性約束： function g,ceq=mycon(x) g=15+x(1)*x(2)

14、-x(1)-x(2);-x(1)*x(2)-10; ceq=;3主程序主程序youh3m為為:x0=-1;1;A=;b=;Aeq=1 1;beq=0;vlb=;vub=;x,fval=fmincon(fun4,x0,A,b,Aeq,beq,vlb, vub,mycon)4 運(yùn)算結(jié)果為運(yùn)算結(jié)果為： x = -12250 12250 fval = 18951 例4 12221122221212 min2s.t. 250 70 05, 010fXxxgXxxgXxxxx= =1先建立先建立M文件文件funm定義目標(biāo)函數(shù)定義目標(biāo)函數(shù): function f=fun(x); f=-2*x(1)-x(2)

15、;2再建立再建立M文件文件mycon2m定義非線性約束：定義非線性約束：function g,ceq=mycon2(x) g=x(1)2+x(2)2-25;x(1)2-x(2)2-7; ceq=;3 主程序主程序fxxm為為: x0=3;25; VLB=0 0;VUB=5 10; x,fval,exitflag,output =fmincon(fun,x0, VLB,VUB,mycon2)4 運(yùn)算結(jié)果為運(yùn)算結(jié)果為: x = 40000 30000fval =-110000exitflag = 1output = iterations: 4 funcCount: 17 stepsize: 1 a

16、lgorithm: 1x44 char firstorderopt: cgiterations: 返回返回應(yīng)用實(shí)例：應(yīng)用實(shí)例： 供應(yīng)與選址供應(yīng)與選址 某公司有6個(gè)建筑工地要開(kāi)工，每個(gè)工地的位置（用平面坐標(biāo)系a，b表示，距離單位：km）及水泥日用量d(t)由下表給出目前有兩個(gè)臨時(shí)料場(chǎng)位于A(5,1)，B(2,7)，日儲(chǔ)量各有20t假設(shè)從料場(chǎng)到工地之間均有直線道路相連 （1）試制定每天的供應(yīng)計(jì)劃，即從A，B兩料場(chǎng)分別向各工地運(yùn)送多少水泥，可使總的噸千米數(shù)最小 （2）為了進(jìn)一步減少噸千米數(shù)，打算舍棄兩個(gè)臨時(shí)料場(chǎng)，改建兩個(gè)新的，日儲(chǔ)量各為20t，問(wèn)應(yīng)建在何處，節(jié)省的噸千米數(shù)有多大？（一）建立模型（一）

17、建立模型 記工地的位置為(ai，bi)，水泥日用量為di，i=1,6;料場(chǎng)位置為(xj，yj)，日儲(chǔ)量為ej，j=1,2；料場(chǎng)j向工地i的運(yùn)送量為Xij當(dāng)用臨時(shí)料場(chǎng)時(shí)決策變量為：Xij，當(dāng)不用臨時(shí)料場(chǎng)時(shí)決策變量為：Xij，xj，yj（二）使用臨時(shí)料場(chǎng)的情形（二）使用臨時(shí)料場(chǎng)的情形 使用兩個(gè)臨時(shí)料場(chǎng)A(5,1)，B(2,7)求從料場(chǎng)j向工地i的運(yùn)送量Xij . 在各工地用量必須滿足和各料場(chǎng)運(yùn)送量不超過(guò)日儲(chǔ)量的條件下，使總的噸千米數(shù)最小，這是線性規(guī)劃問(wèn)題 線性規(guī)劃模型為：=2161),(minjiijXjiaaf2 , 1 , 6 , 2 , 1 , s.t.6121=jeXidXjiijijij

18、L設(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 編寫程序gying1m計(jì)算結(jié)果為：計(jì)算結(jié)果為：x = 30000 50000 00000 70000 00000 10000 00000 00000 40000 00000 60000 100000fval = 1362275（三）改建兩個(gè)新料場(chǎng)的情形（三）改建兩個(gè)新料場(chǎng)的情形 改建兩個(gè)新料場(chǎng)，要同時(shí)確定料場(chǎng)的位置(xj,yj)和運(yùn)送量Xij，在同樣條件下

19、使總噸千米數(shù)最小這是非線性規(guī)劃問(wèn)題非線性規(guī)劃模型為：設(shè) 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文件liaochm定義目標(biāo)函數(shù)MATLAB（liaoch）(2) 取初值為線性規(guī)劃的計(jì)算結(jié)果及臨時(shí)料場(chǎng)的坐標(biāo): x0=3 5 0 7 0 1 0 0 4 0 6 10 5 1 2 7;編寫主程序gying2mMATLAB（gyin

20、g2）(3) 計(jì)算結(jié)果為：x= 30000 50000 00707 70000 0 09293 0 0 39293 0 60000 100707 63875 43943 57511 71867fval = 1054626exitflag = 1(4) 若修改主程序gying2m, 取初值為上面的計(jì)算結(jié)果:x0= 30000 50000 00707 70000 0 09293 0 0 39293 0 60000 100707 63875 43943 57511 71867 則得結(jié)果為:x=30000 50000 03094 70000 00108 06798 0 0 36906 0 59892 103202 55369 49194 58291 72852fval =1034760exitf