版第三講Matlab優(yōu)化工具

1、第三講Matlab優(yōu)化工具一、簡(jiǎn)介在建模過程中，好多問題都可概括為“最優(yōu)化（optimization）”問題，如最大利潤(rùn)、最小成本、最短路徑等，最優(yōu)化問題也稱數(shù)學(xué)規(guī)劃。要描述一個(gè)最優(yōu)化問題，應(yīng)明確三個(gè)基本要素：決策變量（decisionvariables）：它們是決策者所控制的變量，它們?nèi)∈裁粗敌枰獩Q策者來決策，最優(yōu)化問題的求解就是找出決策變量的最優(yōu)取值。拘束條件（constraints）：它們是決策變量在現(xiàn)實(shí)世界中所碰到的限制，也許說決策變量在這些限制范圍之內(nèi)取值才有實(shí)質(zhì)意義。目標(biāo)函數(shù)（objectivefunction）：它代表決策者希望對(duì)其進(jìn)行優(yōu)化的那個(gè)指標(biāo)，目標(biāo)函數(shù)是決策變量的函數(shù)。最

2、優(yōu)化問題的分類，按決策變量是否是時(shí)間的函數(shù)分為動(dòng)向優(yōu)化和靜態(tài)優(yōu)化。按目標(biāo)函數(shù)與拘束條件是否是決策變量的線性函數(shù)分為線性規(guī)劃和非線性規(guī)劃，按決策變量可否為整數(shù)分為整數(shù)規(guī)劃和非整數(shù)規(guī)劃，其他還有0-1規(guī)劃、二次規(guī)劃、多目標(biāo)優(yōu)化、最小最大優(yōu)化問題等。可行解（feasiblesolution）:滿足全部拘束條件的決策向量?？尚杏颍喝靠尚薪鈽?gòu)成的會(huì)集。最優(yōu)解：使目標(biāo)函數(shù)達(dá)到最優(yōu)值（最大或最小值，并且有界）的可行解。無界解：若求極大化則目標(biāo)函數(shù)在可行域中無上界，若求極小化則目標(biāo)函數(shù)在可行域中無下界。二、線性規(guī)劃（Linearprogramming）Matlab中，線性規(guī)劃問題的標(biāo)準(zhǔn)形式為mincTxAx

3、bst.Aeqxbeqlbxub其中c(c1,c2,Lcn)T,x(x1,x2,Lxn)T思慮：最大值問題maxcTx和不等式拘束Axb怎樣轉(zhuǎn)變成上述標(biāo)準(zhǔn)形式？（加負(fù)號(hào)；兩邊同乘-1）Matlab中解上述線性規(guī)劃問題的指令：x=linprog(c,A,b,Aeq,beq,lb,ub)x,fval=linprog(c,A,b,Aeq,beq,lb,ub)說明：當(dāng)上述指令中某個(gè)輸入?yún)?shù)缺省時(shí)應(yīng)在相應(yīng)地址填上空矩陣，若從某項(xiàng)輸入?yún)?shù)開始此后各項(xiàng)參數(shù)都缺省，則可以將其全部省略而不用補(bǔ)上。比方線性規(guī)劃問題mincxstAxb，可以表示T,.為x=linprog(c,A,b)；而問題mincTx,st.A

4、xb則必定表示為lbxubx=linprog(c,A,b,lb,ub)例：解以下線性規(guī)劃問題minz5x14x26x3maxz400 x11000 x2300 x3200 x42x2x3x40 x1x2x3202x13x2161、3x12x24x3422、4x224st.2x230s.t3x13x10 x35xi0,i1,2,3x10,x20,x40解：1、c=-5-4-6;A=1-11;324;320;b=204230;lb=zeros(3,1);x,fval=linprog(c,A,b,lb)2、c=4001000300-200;c=-c;A=2300;3400;b=1624;Aeq=0-

5、211;beq=0;lb=zeros(4,1);ub=infinf5inf;x,fval=linprog(c,A,b,Aeq,beq,lb,ub)三、非線性規(guī)劃（Nonlinearprogramming）當(dāng)目標(biāo)函數(shù)、拘束條件中最少有一個(gè)表達(dá)式是非線性函數(shù)時(shí)稱為非線性規(guī)劃，一般形式：minf(x)Axb,Aeqxbeq線性拘束s.tc(x)0,ceq(x)0非線性拘束lbxub其中c(x),ceq(x)都是函數(shù)向量。Matlab中求解非線性規(guī)劃的指令：x=fmincon(fun,x0,A,b,Aeq,beq,lb,ub，nonlcon)調(diào)用格式與linprog函數(shù)的調(diào)用格式相同。其中x0是最優(yōu)值

6、x的初始值（估計(jì)值），fun和nonlcon是目標(biāo)函數(shù)和非線性拘束函數(shù)文件的函數(shù)句柄。例：求解非線性規(guī)劃問題1、minf(x)x1x2x3取初值x010,10,10st.0 x12x22x372obj=inline(-x(1)*x(2)*x(3),x)x0=101010;A=-1-2-2;122;b=072;x,fval=fmincon(obj,x0,A,b)minzx12x222、x1x24s.t(x14)2x222先建立目標(biāo)函數(shù)文件obj1.m和非線性拘束條件函數(shù)文件nonlcon1.m爾后在命令窗口輸入：Aeq=11;beq=4;x0=11;xfval=fmincon(obj1,x0,A

7、eq,beq,nonlcon1)；四、整數(shù)線性規(guī)劃（IntegerLinearprogramming）目標(biāo)函數(shù)和拘束條件都是線性函數(shù)，且決策變量都取整數(shù)值的數(shù)學(xué)規(guī)劃，稱為整數(shù)線性規(guī)劃，簡(jiǎn)記為ILP，解整數(shù)線性規(guī)劃問題的主要方法是分支定界法。Matlab中沒有現(xiàn)成的解整數(shù)規(guī)劃的庫函數(shù)，可以參照外編程序intprog.m。基本語法為x=intprog(c,A,b,Aeq,beq,lb,ub,x0,id,options)其用法與相關(guān)參數(shù)說明同linprog.m，該程序不但可以解純整數(shù)規(guī)劃，還可以解混雜規(guī)劃問題（即只有部分變量取整數(shù)的情況），輸入?yún)?shù)id是標(biāo)記整數(shù)變量索引號(hào)的列向量，1表示整數(shù)，0表示

8、實(shí)數(shù)，默認(rèn)情況是全1向量即純整數(shù)規(guī)劃。例：求解以下整數(shù)規(guī)劃問題maxfx1x24x3x1x22x39x1x2x32s.tx1x2x34xj0,j1,2,3x1,x2,x3取整數(shù)c=-1*11-4;A=112;11-1;-111;b=924;lb=000;x,fval=intprog(c,A,b,lb)五、0-1型整數(shù)線性規(guī)劃（Binaryintegerprogramming）作為整數(shù)線性規(guī)劃的一種特別情況，0-1型整數(shù)線性規(guī)劃要求決策變量的值只取0也許1。Matlab中解0-1規(guī)劃問題的函數(shù)是bintprog，其用法與linprog相似。x=bintprog(c,A,b,Aeq,beq)例：求

9、解以下0-1型整數(shù)線性規(guī)劃maxf3x12x25x3x12x2x32x14x2x34s.tx1x234x2x36x1,x2,x3為0或1c=-1*-32-5;A=12-1;141;110;041;b=2436;x,fval=bintprog(c,A,b)六、二次規(guī)劃問題（Quadraticprogramming）非線性規(guī)劃問題的一種特別情況，二次規(guī)劃要求目標(biāo)函數(shù)是決策變量的二次函數(shù)，而拘束條件是線性的。其一般形式為：1TTminxHxfxAxbs.tAeqxbeqlbxubMatlab中解二次規(guī)劃問題的語法為x=quadprog(H,f,A,b,Aeq,beq,lb,ub)其用法同linpro

10、g函數(shù)。例：求解以下二次規(guī)劃問題minzx122x1x22x222x16x2x1x22st.x12x22x10,x20H=2-2;-24;f=-2-6;A=11;-12;b=22;lb=00;x,fval=quadprog(H,f,A,b,lb)七、無拘束優(yōu)化問題（Unconstrainednonlinearprogramming）近似于高等數(shù)學(xué)中的極值問題，即求函數(shù)的極小值或極大值。Matlab中與此相關(guān)的主若是兩個(gè)函數(shù)：fminbnd和fminsearch。x,fmin=fminbnd(fun,a,b)求一元函數(shù)fun在a,b區(qū)間上的局部極小值點(diǎn)及極小值。x,fmin=fminsearch

11、(fun,x0)求多元函數(shù)fun在初值x0周邊的局部極小值點(diǎn)及極小值。這里x,x0均為向量。例1、求函數(shù)y2exsinx在0,5上的最大值和最小值。xmin,fmin=fminbnd(2*exp(-x)*sin(x),0,5)xmax,fmax=fminbnd(-2*exp(-x)*sin(x),0,5)%fmax=-fmax例2、求函數(shù)f(x,y)(4x22y24xy2y1)ex在點(diǎn)(-1,1)周邊的極小值。f=inline(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1)*exp(x(1)x0=-1,1;xmin,fmin=fminsearch(f,x0)注意：1

12、、多元函數(shù)要寫成向量函數(shù)的形式。2、上面的函數(shù)找到的都是局部最優(yōu)解，不用然是全局最優(yōu)，若是要求全局最優(yōu)解，在精度要求不是很高的情況下可以試一試使用min和max函數(shù)。其他還有多目標(biāo)優(yōu)化問題、最小最大值問題等，可參照相關(guān)資料。上機(jī)練習(xí)1、求解以下數(shù)學(xué)規(guī)劃問題：minf3x14x22x35x44x1x22x3x42x1x23x3x414st.3x2x32x422x1x1,x2,x30,x4無拘束minf(x)x1x2x3x12x22x30 x12x22x372st.x22010 x1x210minf4x13x22x3minf5x14x28x3x12x2x362x1x24st.5x13x215xj0,j1,2,3maxf3x1x23x12x23st.5x14x2102x1x25x1,x20,x1,x2為整數(shù)minf(x)1x12x22x1x22x16x22st.2x15x2