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

第三講Matlab優(yōu)化工具一、簡介在建模過程中，許多問題都可歸結(jié)為“最優(yōu)化(optimization)”問題，如最大利潤、最小成本、最短路徑等，最優(yōu)化問題也稱數(shù)學(xué)規(guī)劃。要描述一個最優(yōu)化問題，應(yīng)明確三個基本要素：決策變量(decisionvariables)：它們是決策者所控制的變量，它們?nèi)∈裁粗敌枰獩Q策者來決策，最優(yōu)化問題的求解就是找出決策變量的最優(yōu)取值。約束條件(constraints)：它們是決策變量在現(xiàn)實世界中所受到的限制，或者說決策變量在這些限制范圍之內(nèi)取值才有實際意義。目標(biāo)函數(shù)(objectivefunction)：它代表決策者希望對其進行優(yōu)化的那個指標(biāo)，目標(biāo)函數(shù)是決策變量的函數(shù)。最優(yōu)化問題的分類，按決策變量是否是時間的函數(shù)分為動態(tài)優(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)成的集合。最優(yōu)解：使目標(biāo)函數(shù)達到最優(yōu)值(最大或最小值，并且有界)的可行解。無界解：若求極大化則目標(biāo)函數(shù)在可行域中無上界，若求極小化

則目標(biāo)函數(shù)在可行域中無下界。二、線性規(guī)劃(Linearprogramming)Matlab中，線性規(guī)劃問題的標(biāo)準(zhǔn)形式為mincTxAx<bs.t<Ax=beqeqlb<x<ub其中c=(c,c,Lc)t,x=(x,x,Lx)t12n12n思考：最大值問題maxcTx和不等式約束Ax>b怎樣轉(zhuǎn)化為上述標(biāo)準(zhǔn)形式？(加負(fù)號；兩邊同乘-1)Matlab中解上述線性規(guī)劃問題的指令：x=linprog(c,A,b,Aeq,beq,lb,ub)或[x,fval]=linprog(c,A,b,Aeq,beq,lb,ub)說明：當(dāng)上述指令中某個輸入?yún)?shù)缺省時應(yīng)在相應(yīng)位置填上空矩陣[]，若從某項輸入?yún)?shù)開始往后各項參數(shù)都缺省，則可以將其全部

省略而不用補上[]。例如線性規(guī)劃問題mincTx,s.t.Ax<b，可以表示

為x=linprog(c,A,b)；而問題mincTx,s.t；Ax<b則必須表示為Ilb<x<ubx=linprog(c,A,b,[],[],lb,ub)例：解下列線性規(guī)劃問題minz=-5x-4x-6x123x-xminz=-5x-4x-6x123x-x+x<20

1231、3x+2x+4x<42st\1233x+2x<3012

Ix>0,i=1,2,3i2、12—2x+x+x=02342x+3x<1612s.t<3x+4x<24120<x<53x>0,x>0,x>0124解：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-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ù)、約束條件中至少有一個表達式是非線性函數(shù)時稱為非線性規(guī)劃，一般形式：minf(x)Ax<b,Ax=b線性約束eqeqs.t<c(x)<0,ceq(x)=0非線性約束lb<x<ub其中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)值x的初始值(估計值)，fun和nonIcon是目標(biāo)函數(shù)和非線性約束函數(shù)文件的函數(shù)句柄。例：求解非線性規(guī)劃問題1minf(x)=-xxx的汁/古1、123取初值x=[10,10,10]s.t0<x+2x+2x<720123>>obj=inline('-x(1)*x(2)*x(3)','x')>>x0=[101010];A=[-1-2-2;122];b=[072];>>[x,fval]=fmincon(obj,x0,A,b)minz=x2+x2122、fx+x二4s.t彳12I(x-4)2+x2<212先建立目標(biāo)函數(shù)文件[obj1?m]和非線性約束條件函數(shù)文件[nonlcon1.m]然后在命令窗口輸入：>>Aeq=[11];beq=4;x0=[11];>>[xfval]=fmincon(@obj1,x0,[],[],Aeq,beq,[],[],@nonlcon1)；四、整數(shù)線性規(guī)劃(IntegerLinearprogramming)目標(biāo)函數(shù)和約束條件都是線性函數(shù)，且決策變量都取整數(shù)值的數(shù)學(xué)規(guī)劃，稱為整數(shù)線性規(guī)劃，簡記為ILP,解整數(shù)線性規(guī)劃問題的主要方法是分支定界法。Matlab中沒有現(xiàn)成的解整數(shù)規(guī)劃的庫函數(shù)，可以參考外編程序[intprog?m]?；菊Z法為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ù)變量索引號的列向量，1表示整數(shù)，0表示實數(shù)，默認(rèn)情況是全1向量即純整數(shù)規(guī)劃。例：求解下列整數(shù)規(guī)劃問題

maXf=X1+X2-4X3x+x+2x<9123x+x-x<2s.t.s.t.v—x+x+x<4123x>0,j=1,2,3jx,x,x取整數(shù)I123>>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)例：求解下列0-1型整數(shù)線性規(guī)劃maXf=—3x1+2x2—5x3x+2x—x<2123x+4x+x<4s.t.s.t.vx+x<3124x+x<623x,x,x為0或1I123>>c=-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ù)，而約束條件是線性的。其一般形式為：min2min2xtHx+ftxAx<bs.t<Aeqx=beqlb<x<ubMatlab中解二次規(guī)劃問題的語法為x=quadprog(H,f,A,b,Aeq,beq,lb,ub)其用法同linprog函數(shù)。例：求解下列二次規(guī)劃問題minz=x2一2xx+2x2一2x-6x112212x+x<212st<-x+2x<212x>0,x>012>>H=[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)的主要是兩個函數(shù)：fminbnd和fminsearch。[x,fmin]=fminbnd(fun,a,b)求一元函數(shù)fun在[a,b]區(qū)間上的局部極小值點及極小值。[x,fmin]=fminsearch(fun,x0)求多元函數(shù)fun在初值x0附近的局部極小值點及極小值。這里x,x0均為向量。例1、求函數(shù)y=2e-xsinx在[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)二(4x2+2y2+4xy+2y+1)ex在點(-1,1)附近的極小值。>>f=inline('(4*x(1)A2+2*x(2)A2+4*x(1)*x(2)+2*x(2)+1)*exp(x(1))')>>x0=[-1,1];>>[xmin,fmin]=fminsearch(f,x0)注意：1、多元函數(shù)要寫成向量函數(shù)的形式。2、上面的函數(shù)找到的都是局部最優(yōu)解，不一定是全局最優(yōu)，如果要求全局最優(yōu)解，在精度要求不是很高的情況下可以嘗試使用min和max函數(shù)。其它還有多目標(biāo)優(yōu)化問題、最小最大值問題等，可參考相關(guān)資料。上機練習(xí)1、求解下列數(shù)學(xué)規(guī)劃問題：⑹minf⑹minf（x）=—xx—2x—6x1212（1）minf=一3x+4x-2x+5x12344x—x+2x—x=—2TOC\o"1-5"\h\z1234x+x+3x—x<14S?t<1234—2x+3x—x+2xn21234x,x,x>0,x無約束1234（⑶minf（x）=xxx123—x+2x+2x>0123x+2x+2x<72s.t<12310<x<202x—x=1012⑸）minf=4x+3x+2xTOC\o"1-5"\h\z1232x—5x+3x<41234x+x+3x>3s..<123x+x>123x,x,x為0或1123

（2）minf=5x+4x+8x123x+2x+x=6123—2x+x>—4<125x+3x<1512x>0,j=1,2,3j⑷maxf=3x—x123x—2x<3125x+4x>10s.t<1