第02講 優(yōu)化決策理論與方法

決策理論與方法(2)優(yōu)化決策理論與方法,合肥工業(yè)大學管理學院2020年4月26日,.,確定性決策,確定性決策：指未來狀態(tài)是確定的（即只有一種狀態(tài)）一類決策問題，每一個行動方案對應著一個確定的結果值，此時決策函數(shù)僅依賴于決策變量。特點：狀態(tài)是確定的；決策問題變?yōu)閮?yōu)化問題。決策的已知變量：決策變量及其取值范圍解決問題的主要理論方法：最優(yōu)化理論與方法注：最優(yōu)化理論與方法（數(shù)學規(guī)劃）也可以求解不確定性決策問題、隨機性決策問題,.,確定性決策,優(yōu)化決策方法的問題求解過程辨識目標C，確定優(yōu)化的標準，如：利潤、時間、能量等確定影響決策目標的決策變量x，形成目標函數(shù)C=f(x)明確決策變量的取值范圍，形成約束函數(shù)設計求解算法，尋找決策目標在決策變量所受限制的范圍內的極小化或極大化。最優(yōu)化問題的一般形式為：,.,優(yōu)化問題分類,可行點與可行域：滿足約束條件的x稱為可行點，所有可行點的集合稱為可行域，記為S；約束優(yōu)化與無約束優(yōu)化：當SRn時，稱為約束優(yōu)化；當S=Rn時，稱為無約束優(yōu)化；多目標優(yōu)化：若f是多個目標函數(shù)構成的一個向量值函數(shù)，則稱為多目標規(guī)劃；線性規(guī)劃與非線性規(guī)劃：當f,g,h均為線性函數(shù)時稱為線性規(guī)劃，否則稱為非線性規(guī)劃。,.,優(yōu)化問題分類,整數(shù)規(guī)劃：當決策變量的取值均為整數(shù)時稱為整數(shù)規(guī)劃；若某些變量取值為整數(shù)，而另一些變量取值為實數(shù)，則成為混合整數(shù)規(guī)劃。動態(tài)規(guī)劃與多層規(guī)劃：若決策是分成多個階段完成的，前后階段之間相互影響，則稱為動態(tài)規(guī)劃；若決策是分成多個層次完成的，不同層次之間相互影響，則稱為多層規(guī)劃。,.,優(yōu)化決策理論與方法,1、線性規(guī)劃2、非線性規(guī)劃（約束和非約束）3、多目標規(guī)劃4、組合優(yōu)化與整數(shù)規(guī)劃,.,線性規(guī)劃管理實例,(食譜問題)假設市場上有n種不同的食物，第j種食物的單價為cj。人體正?；顒舆^程中需要m種基本的營養(yǎng)成分，且每人每天至少需要攝入第i種營養(yǎng)成分bi個單位。已知第j種食物中包含第i種營養(yǎng)成分的量為aij個單位。問在滿足人體基本營養(yǎng)需求的前提下什么樣的配食方案最經濟？設食譜中包含第j種食物的量為xj，則：,.,線性規(guī)劃標準型,.,線性規(guī)劃單純形算法,解空間分析可行域分析：n維空間；第一象限；m個超平面。最優(yōu)解分析：在端點(或稱為極點。極點向量中，至少有n-m個0分量)處取極值。單純形算法的基本思想從某個極點開始獲得一個可行解；判斷該可行解是不是目標解。若是，算法結束；否則尋找下一個極點（確定入基變量和出基變量），直至找到目標解。,.,線性規(guī)劃內點算法,1972年，V.Klee和G.L.Minty指出Dantzig的單純形算法的迭代次數(shù)為O(2n)，是一個指數(shù)時間算法，不是優(yōu)良算法。那么是否存在求解線性規(guī)劃問題的多項式時間算法？1984年，N.Karmarkar提出了一種投影尺度算法，其計算效果能夠同單純形法相比較，掀起了線性規(guī)劃內點算法的熱潮。,.,線性規(guī)劃內點算法,內點算法的思想已知線性規(guī)劃問題的可行域是一個多面體，最優(yōu)點在多面體的某個極點取到。在給定初始可行解后，沿著什么樣的路徑到達最優(yōu)解呢？單純形法是從某個基可行解開始，沿著多面體的邊移動最終找到最優(yōu)解。內點算法的思想是從可行域內的任意一點(任一可行解)出發(fā)，穿越可行域的內部達到最優(yōu)解。N.Karmarkar的投影尺度算法就是一種典型的內點算法。,.,線性規(guī)劃內點算法,可行域,內點,初始基可行解,基可行解,目標函數(shù),目標函數(shù)最速下降方向,.,線性規(guī)劃內點算法,投影尺度算法如何穿過可行域的內部快速達到最優(yōu)解呢？Karmarkar發(fā)現(xiàn)：(1)如果一個內點位于可行域(多胞形、多面體)的中心，那么目標函數(shù)的最速下降方向是比較好的方向；(2)存在一個適當?shù)淖儞Q，能夠將可行域中給定的內點置于變換后的可行域的中心?；谶@兩點，Karmarkar構造了一種稱為投影尺度算法的內點算法。,.,線性規(guī)劃內點算法,X空間,內點,目標函數(shù),目標函數(shù)最速下降方向,Y1空間,中心點,投影尺度變換1,目標函數(shù)最速下降方向,Y2空間,中心點,投影尺度變換2,.,線性規(guī)劃Matlab函數(shù)應用,OptimizationToolBoxMinfTxS.t.AxbAeqx=beqlbxub其中：f,x,b,beq,lb和ub均為向量；A和Aeq為矩陣。x,fval=linprog(f,A,b,Aeq,beq,lb,ub),.,線性規(guī)劃Matlab函數(shù)應用,例：maxz=x1+2x2S.t.x1+x2402x1+x260 x10;x20解：將max變?yōu)閙in，minz=-x1-2x2則：f=-1;-2;b=40;60;lb=zeros(2,1);A=11;21x,fval=linprog(f,A,b,lb)x=0;40,fval=-80,x1,x2,x1+x2=40,2x1+x2=60,Z=x1+2x2,.,優(yōu)化決策理論與方法,1、線性規(guī)劃2、非線性規(guī)劃（約束和非約束）3、多目標規(guī)劃4、組合優(yōu)化與整數(shù)規(guī)劃,.,無約束非線性規(guī)劃標準型,Minf(x);xRn其中f：RnR是一個非線性連續(xù)函數(shù)。對于任意點x*Rn,它是函數(shù)f的最小點(或局部極小點)嗎？例如：minf(x)=ex1(4x12+2x22+4x1x2+2x2+1),.,無約束非線性規(guī)劃極小值存在條件,必要條件。設x*是f(x)的局部極小點，則當f(x)在x*點可微時，梯度f(x*)=0；當f(x)在x*點二階可微時，Hesse矩陣2f(x*)是半正定的，即dRn，有dT2f(x*)d0。充分條件。設f(x)在x*點二階可微，若梯度f(x*)=0且Hesse矩陣2f(x*)是正定的，則x*是f(x)的一個嚴格局部極小點。充要條件。設f(x)是可微凸函數(shù)，則x*是f(x)的全局最小點，當且僅當梯度f(x*)=0。,.,無約束非線性規(guī)劃復習,梯度矩陣,Hesse矩陣,Taylor展開,.,無約束非線性規(guī)劃牛頓法,基本思想：在一個點附近，用目標函數(shù)f(x)的二階Taylor多項式近似f(x)，并用該Taylor多項式的最小點近似f(x)的最小點。如果近似誤差比較大，那么可在近似最小點附近重新構造f(x)的二階Taylor多項式(迭代)，據(jù)此尋找新的近似最小點，重復以上過程直到求得滿足一定精度要求的迭代點。,.,無約束非線性規(guī)劃牛頓法,設xk是第k次迭代結果，記gk=g(xk)=f(xk)；Gk=G(xk)=2f(xk)。則f(x)=f(xk+p)k(p)=f(xk)+g(xk)Tp+1/2pTG(xk)p由于k(p)的最小點滿足g(xk)+G(xk)p=0，得p=x-xk=-G-1(xk)g(xk)因此，可近似得到迭代關系：xk+1=xk-G-1(xk)g(xk),.,無約束非線性規(guī)劃牛頓法,牛頓迭代法步驟初始化：給定一個初始點x0以及參數(shù)e0；記k=0。收斂性檢驗：計算g(xk)，若|g(xk)|e，則算法終止；否則計算G(xk)。迭代改進：計算新的迭代點xk+1，即xk+1=xk-G-1(xk)g(xk)。k+1k。返回收斂性檢驗。,.,無約束非線性規(guī)劃準牛頓法,牛頓法算法的優(yōu)點是收斂速度快(利用了Hesse矩陣)。但使用Hesse矩陣的不足之處是計算量大，Hesse矩陣可能非正定等，準牛頓法(Quasi-Newtonmethod)是對牛頓法的改進，目前被公認為是比較有效的無約束優(yōu)化方法?；舅枷耄涸诘^程中只利用目標函數(shù)f(x)和梯度g(x)的信息，構造Hesse矩陣的近似矩陣，由此獲得一個搜索方向，生產新的迭代點。具體內容請參考相關書籍。,.,無約束非線性規(guī)劃Matlab函數(shù)應用,OptimizationToolBoxMinf(x)Matlab提供了兩個求解無約束非線性規(guī)劃的函數(shù)x,fval=fminunc(fun,x0)x,fval=fminsearch(fun,x0)用法相似，算法內部的搜索策略不同。fun為f(x)的函數(shù)形式，x0為初始解向量。,.,無約束非線性規(guī)劃Matlab函數(shù)應用,用法創(chuàng)建一個matlab文件，如myfun.mfunctionf=myfun(x)f=f(x);然后調用fminunc或fminsearch并指定初始搜索點。x0=x1,x2,xnx,fval=fminunc(myfun,x0)或x,fval=fminsearch(myfun,x0),.,無約束非線性規(guī)劃Matlab函數(shù)應用,例：minf(x)=ex1(4x12+2x22+4x1x2+2x2+1)解：創(chuàng)建一個matlab文件，如myfun.mfunctionf=myfun(x)f=exp(x(1)*(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1);調用無約束非線性規(guī)劃函數(shù)x0=-1,1;%Startingguessoptions=optimset(LargeScale,off);x,fval=fminunc(myfun,x0,options);或者x,fval=fminsearch(myfun,x0,options);,.,無約束非線性規(guī)劃Matlab函數(shù)應用,fminunc結果：x=0.5000-1.0000fval=1.0983e-015iterations:8algorithm:medium-scale:Quasi-Newtonlinesearchfminsearch結果：x=0.5000-1.0000fval=5.1425e-010iterations:46algorithm:Nelder-Meadsimplexdirectsearch,.,約束非線性規(guī)劃標準型,其中f(x)是目標函數(shù)，gi(x)和hj(x)為約束函數(shù)(約束條件)。S=x|gi(x)0hj(x)=0為可行域。有約束非線性規(guī)劃問題(COP)是指f(x),gi(x),hj(x)至少有一個是非線性的，且I或至少有一個為非空。,.,約束非線性規(guī)劃幾個概念,積極(active)約束：設x0是COP問題的一個可行解，則它必須滿足所有約束條件。對于gi(x0)0，或者等號成立，或者大于號成立。稱等號成立的約束為積極約束(有效約束)，此時，x0處于該約束條件形成的可行域邊界上；稱大于號成立的約束為非積極(inactive)約束(無效約束)，此時，x0不在該約束條件形成的可行域邊界上。顯然所有hj(x0)約束均是積極約束。記J=j|gj(x0)=0hj(x0)=0，稱為積極約束指標集。,.,約束非線性規(guī)劃幾個概念,可行方向。設x0為COP問題的任一可行解，對某一方向d來說，若00使得對于任意0,0，均有x0+dS，稱d為x0的一個可行方向。顯然若d滿足dTgi(x)0，dThj(x)=0，則d一定是可行方向。（可用一階Taylor公式分析）。下降方向。設x0S，對某一方向d來說，若00使得對于任意0,0，均有f(x0+d)f(x0)，則稱d為x0點的一個下降方向。由f(x0+d)=f(x0)+(f(x0)Td+o()可知：若d滿足dTf(x0)0,則x*為COP問題的一個嚴格局部極小點。,.,約束非線性規(guī)劃極小值存在條件,例：minf(x)=x12+x22S.t.x1+x24x1,x20解：g1(x)=x1+x2-40;g2(x)=x10;g3(x)=x20f(x)=2x1,2x2T,g1(x)=1,1T,g2(x)=1,0T,g3(x)=0,1T,得到：2x1=1+22x2=1+3又(x1+x2-4)1=0；x12=0；x23=0；i0若1=0，則x1=x2=0，與題意不符；若10，則x1+x2-4=0，x10,x20。因此有2=3=0，所以x1=x2=1/2，得x1=x2=2，x*=2,2T為該問題的唯一KKT點。根據(jù)凸規(guī)劃充分條件知x*為全局最小點。,.,約束非線性規(guī)劃可行方向法,上面例題介紹了通過求解KKT方程獲得問題解的方法，但KKT方程并不總是很好求解。下面介紹幾種約束優(yōu)化的求解方法：可行方向法、序列無約束化法和SQP法?？尚蟹较蚍ǖ膽脳l件：要求所有約束均為線性約束（稱為線性約束的優(yōu)化問題，LCO）?？尚蟹较蚍ǖ幕舅枷耄寒斈硞€可行方向同時也是目標函數(shù)的下降方向時，沿此方向移動一定會在滿足可行性的情況下改進迭代點的目標函數(shù)值。,.,約束非線性規(guī)劃可行方向法,x1,x2,.,約束非線性規(guī)劃可行方向法,LCO問題：Minf(x)S.t.aiTxbi,iIajTx=bj,j設x0是LCO的一個可行解，若d是可行域在x0點的可行方向，則d滿足AI(x0)d0(I(x0)=i|aiTx0=bi,iI)，Ad=0。設x0是LCO的一個可行解，若d是可行域在x0點的下降方向，則d滿足dTf(x0)0，定義二次罰函數(shù)MinQ(x,)=x1+x2+(2)-1(x1-x22)2Qx1=1+(x1-x22)/=0Qx2=1-2x2(x1-x22)/=0解得：x*=(1/4-,-1/2)T,Q*=-1/4-/2當0時得，x*=(1/4,-1/2)T,f*=-1/4,.,約束非線性規(guī)劃序列無約束化法,對數(shù)障礙函數(shù)法：障礙函數(shù)：其中稱為障礙參數(shù)，且當0時，P(x,)的極小值趨于f(x)的極小值。該方法的適用性：COP問題僅包含不等式約束函數(shù)，且可行域存在內點。即S0=x|g(x)0,.,約束非線性規(guī)劃序列無約束化法,例：minf=x/2|x1解：構造對數(shù)障礙函數(shù)P(x,)=x/2-ln(x-1)Px=1/2-/(x-1)=0，得x*=1+2，P*=1/2+-ln2當0時得x*=1，f*=1/2,.,二次規(guī)劃標準型,若有約束非線性規(guī)劃的目標函數(shù)是決策變量x的二次函數(shù)且所有約束均為線性約束，稱此類非線性規(guī)劃問題為二次規(guī)劃(QuadraticProgramming,QP)問題。其標準型為：,.,二次規(guī)劃標準型,其中Q=QTRnn（n階對稱方陣）；以aiT(iI)為行向量的矩陣記為AIRIn；以ajT(j)為行向量的矩陣記為ARn；對應的向量記為bI,b。若目標函數(shù)的Hesse矩陣Q是半正定(或正定)的，則QP問題為(嚴格)凸二次規(guī)劃(CQP)。我們僅討論凸二次規(guī)劃問題，因為非凸二次規(guī)劃的Q存在負特征根，求解很困難。,.,二次規(guī)劃極小點存在條件,充要條件可行點x*是QP問題的局部極小點當且僅當x*為一個KKT點且對于任意非零可行方向d，有dTQd0。對于凸二次規(guī)劃，x*為全局極小點當且僅當x*為局部極小點，當且僅當x*為KKT點。二次規(guī)劃的KKT定理形式為：Qx*+c=AIT*+AT*(AIx*-bI)*=0二次規(guī)劃的求解本質上就是求解上述KKT方程。,.,約束非線性規(guī)劃SQP法,對于非線性約束優(yōu)化(COP)問題，若x*是COP問題的一個局部最優(yōu)解，則它對應一個純等式約束優(yōu)化問題,.,約束非線性規(guī)劃SQP法,因此如果事先知道積極約束指標集，那么帶有不等式約束優(yōu)化問題就可以轉化為純等式約束優(yōu)化問題，并可用準牛頓法求解，這就是逐次二次規(guī)劃(SequentialQuadraticProgramming，SQP)法?；舅枷耄涸诘c處構造一個二次規(guī)劃子問題，近似原來的約束優(yōu)化問題；然后通過求解該二次規(guī)劃子問題獲得約束優(yōu)化問題的一個改進迭代點；不斷重復此過程，直到求出滿足一定要求的迭代點。,.,約束非線性規(guī)劃SQP法,對于等式約束優(yōu)化問題Minf(x)S.t.h(x)=0拉格朗日函數(shù)記為L(x,)=f(x)-Th(x)則L(x,)=(f(x)-h(x),-h(x)T=0，顯然問題的最優(yōu)解(x*,*)滿足此式。設(xk,k)是第k次迭代結果，根據(jù)牛頓法，有：,.,約束非線性規(guī)劃SQP法,上述迭代過程等價于如下的二次規(guī)劃的迭代。設給定迭代點(xk,k)，則,.,約束非線性規(guī)劃Matlab函數(shù)應用,OptimizationToolBoxMinf(x)s.t.c(x)0ceq(x)=0AxbAeqx=beqlbxubx,fval=fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon)fun定義目標函數(shù),x0定義初始可行解，nonlcon定義c(x)和ceq(x)。,.,約束非線性規(guī)劃Matlab函數(shù)應用,用法創(chuàng)建一個matlab文件，如myfun.mfunctionf=myfun(x)f=f(x);創(chuàng)建另一個matlab文件，如confun.mfunctionc,ceq=confun(x)c=c(x);ceq=ceq(x);調用fmincon并指定初始搜索點以及其他向量、矩陣。x0=x1,x2,xn;A;b;Aeq;beq;lb;ub;x,fval=fmincon(myfun,x0,A,b,Aeq,beq,lb,ub,confun),.,約束非線性規(guī)劃Matlab函數(shù)應用,例：minf(x)=ex1(4x12+2x22+4x1x2+2x2+1)S.t.x1x2-x1-x2-1.5x1x2-10解：創(chuàng)建一個matlab文件，如myfun.mfunctionf=myfun(x)f=exp(x(1)*(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1);創(chuàng)建另一個matlab文件，如confun.mfunctionc,ceq=confun(x)c=1.5+x(1)*x(2)-x(1)-x(2);-x(1)*x(2)-10;ceq=;,.,約束非線性規(guī)劃Matlab函數(shù)應用,調用有約束非線性規(guī)劃函數(shù)x0=-1,1;%Startingguessoptions=optimset(LargeScale,off);x,fval=fmincon(objfun,x0,confun,options)運行結果：x=-9.54741.0474fval=0.0236iterations:8algorithm:medium-scale:SQP,Quasi-Newton,line-search,.,二次規(guī)劃Matlab函數(shù)應用,OptimizationToolBoxMin0.5xTHx+fTxs.t.AxbAeqx=beqlbxubx,fval=quadprog(H,f,A,b,Aeq,beq,lb,ub,x0)x0定義初始可行解(可選),.,二次規(guī)劃Matlab函數(shù)應用,用法首先要將目標函數(shù)轉換成二次規(guī)劃標準型，從而得到H和f兩個矩陣。調用quadprog并根據(jù)需要指定初始搜索點以及其他向量、矩陣。x0=x1,x2,xn;A;b;Aeq;beq;lb;ub;x,fval=quadprog(H,f,A,b,Aeq,beq,lb,ub,x0),.,二次規(guī)劃Matlab函數(shù)應用,例：minf(x)=1/2x12+x22-x1x2-2x1-6x2)S.t.x1+x22-x1+2x222x1+x23x1,x20解：改寫f(x)=1/2(x12+2x22-x1x2-x1x2)-2x1-6x2得：H=1-1;-12,f=-2;-6,x=x1;x2;表示其它矩陣或向量A=11;-12;21;b=2;2;3;lb=0;0;Aeq=;beq=;ub=。不指派初始解。,.,二次規(guī)劃Matlab函數(shù)應用,調用二次規(guī)劃函數(shù)x,fval=quadprog(H,f,A,b,lb)運行結果：x=0.6667;1.3333fval=-8.2222iterations:3algorithm:medium-scale:active-set(積極約束集方法),.,優(yōu)化決策理論與方法,1、線性規(guī)劃2、非線性規(guī)劃（約束和非約束）3、多目標規(guī)劃4、組合優(yōu)化與整數(shù)規(guī)劃,.,多目標規(guī)劃管理實例,(物資調度)假設物資調度部門計劃將某種物資從若干個存儲倉庫調運到若干個銷售網(wǎng)點銷售?？紤]到物資的時效性和銷售效益，調度部門希望物資在運輸過程中盡可能快地到達目的地；同時，考慮到運輸成本，調度部門還希望物資的總運輸費用最小。試建立描述物資調運過程的數(shù)學模型。解：設共有m個倉庫，第i個倉庫的物資庫存量為ai噸；有n個銷售網(wǎng)點，第j個銷售網(wǎng)點的銷售量為bj噸。第i個倉庫到第j個銷售網(wǎng)點的距離為dij，單位物資的運費為cij。設從第i個倉庫運到第j個銷售網(wǎng)點的物資量為xij。,.,多目標規(guī)劃管理實例,決策目標：運輸速度最快，可用噸公里數(shù)（可觀測變量）最小描述?？倗嵐飻?shù)為ijdijxij；運輸費用最小?？傔\輸費用為ijcijxij；約束條件每個倉庫的運出量不超過倉庫的庫存量：jxijai；運到每個銷售網(wǎng)點的量與其銷售能力相匹配：ixij=bj；每個倉庫的運出量非負：xij0。,.,多目標規(guī)劃管理實例,最后得到模型：模型包含2個目標；mn個決策變量；mn+m+n個約束。,.,多目標規(guī)劃標準型,多目標規(guī)劃(multi-ObjectiveProgramming,MOP)就是指在決策變量滿足給定約束的條件下研究多個可數(shù)值化的目標函數(shù)同時極小化(或極大化)的問題。其一般形式如下：Minf(x)=(f1(x),f2(x),fp(x)T，S.t.gi(x)0;iIhj(x)=0;j。,.,多目標規(guī)劃Pareto最優(yōu)解,設x*是可行域S上的一個點，對于xS，均有：fi(x*)fi(x)(i=1,p)，稱x*為MOP問題的絕對最優(yōu)解；若不存在xS，使得fi(x)fi(x*)(或fi(x)fi(x*)(i=1,p)，則稱x*為MOP問題的有效解(或弱有效解)。有效解通常也稱為Pareto最優(yōu)解。,S,x1,x2,f(S),f(S),f2,f2,f1,f1,絕對最優(yōu)解,有效解,弱有效解,.,多目標規(guī)劃Pareto最優(yōu)解存在條件,(必要條件)假設向量值函數(shù)f=f1(x),fp(x)T,g=g1(x),g|I|(x)T,h=h1(x),h|(x)T在x*S處可微，若x*是MOP問題的有效解或弱有效解，則存在向量R+p，R+|I|，R+|，使得(,)0，且f(x*)=g(x*)+h(x*)Tg(x*)=0。,.,多目標規(guī)劃求解方法,直接求解多目標規(guī)劃問題的有效解集是NP-難問題。下面介紹多目標規(guī)劃問題的間接解法，基本思路都是將多目標規(guī)劃問題轉化為一個或多個單目標優(yōu)化問題?；谝粋€單目標問題的方法：將原來的多目標規(guī)劃問題轉化成一個單目標優(yōu)化問題，然后利用非線性優(yōu)化算法求解該單目標問題，所得解作為MOP問題的最優(yōu)解。關鍵問題在于：保證所構造的單目標問題的最優(yōu)解是MOP問題的有效解或弱有效解。,.,多目標規(guī)劃求解方法,線性加權和法：MinTf(x)=kkfk(x)，S.t.gi(x)0;iIhj(x)=0;j權重設置要求：kk=1,k0(k=1,2,p)。主要目標法：Minf(x)=f1(x)，(不妨設f1(x)為主要目標)S.t.gi(x)0;iIhj(x)=0;jfk(x)uk,k=2,puk為專家經驗值。,.,多目標規(guī)劃求解方法,極小化極大法：在目標函數(shù)f(x)的p個分量中，極小化f(x)的最大分量，即minxSmax1jpfj(x)理想點法：分別求出f(x)中每個分量fj(x)的極小點fj0，得到理想點f0=(f10,fp0)T；然后求解單目標優(yōu)化問題：minxS|f(x)-f0|。為范數(shù)的階，可取1，2，。,.,多目標規(guī)劃求解方法,基于多個單目標問題的方法：將原來的多目標規(guī)劃問題轉化成具有一定次序的多個單目標優(yōu)化問題，然后依次求解這些單目標優(yōu)化問題，并把最后一個單目標優(yōu)化問題的解作為MOP問題的最優(yōu)解。關鍵問題在于：保證最后一個單目標優(yōu)化問題的最優(yōu)解是MOP問題的有效解或弱有效解。分層排序法：將目標函數(shù)按重要度依次排序，然后在前一個目標函數(shù)的最優(yōu)解集中尋找下一個目標的最優(yōu)解集，并把最后一個目標的最優(yōu)解作為MOP問題的最優(yōu)解。,.,多目標規(guī)劃求解方法,minf1(x)，xS（不妨設f1(x)為第一層目標），得到最優(yōu)解集S1;第j層：minfj(x),xSj-1，j=2,p最后將Sp中的點作為多目標問題的最優(yōu)解。,.,多目標規(guī)劃Matlab函數(shù)應用,OptimizationToolBoxMinmaxfi(x)s.t.c(x)0ceq(x)=0AxbAeqx=beqlbxubx,fval=fminimax(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon)Fun定義目標函數(shù)；x0定義初始可行解；nonlcon定義c(x)和ceq(x)。,.,多目標規(guī)劃Matlab函數(shù)應用,用法創(chuàng)建一個matlab文件，如myfun.mfunctionf=myfun(x)f(1)=f1(x);f(2)=f2(x);f(p)=fp(x)創(chuàng)建另一個matlab文件，如confun.mfunctionc,ceq=confun(x)c=c(x);ceq=ceq(x);調用fminimax并指定初始搜索點以及其他向量、矩陣。x0=x1,x2,xn;A;b;Aeq;beq;lb;ub;x,fval=fminimax(myfun,x0,A,b,Aeq,beq,lb,ub,confun),.,多目標規(guī)劃Matlab函數(shù)應用,OptimizationToolBoxMinx,s.t.F(x)-weightgoalc(x)0ceq(x)=0AxbAeqx=beqlbxubx,fval=fgoalattain(fun,x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon)Fun定義目標函數(shù)；goal為理想點；x0定義初始可行解；nonlcon定義c(x)和ceq(x)。weight為各目標的權重向量。,.,多目標規(guī)劃Matlab函數(shù)應用,用法創(chuàng)建一個matlab文件，如myfun.mfunctionf=myfun(x)f(1)=f1(x);f(2)=f2(x);f(p)=fp(x)創(chuàng)建另一個matlab文件，如confun.mfunctionc,ceq=confun(x)c=c(x);ceq=ceq(x);調用fgoalattain并設定理想點、權重向量，指定初始搜索點以及其他向量、矩陣。x0=x1,x2,xn;A;b;Aeq;beq;lb;ub;goal;weightx,fval=fgoalattain(myfun,x0,goal,weight,A,b,Aeq,beq,lb,ub,confun),.,多目標規(guī)劃Matlab函數(shù)應用,例：minf1,f2,f3,f4,f5f(1)=2*x(1)2+x(2)2-48*x(1)-40*x(2)+304;f(2)=-x(1)2-3*x(2)2;f(3)=x(1)+3*x(2)-18;f(4)=-x(1)-x(2);f(5)=x(1)+x(2)-8;無約束。,.,多目標規(guī)劃Matlab函數(shù)應用,解(1)：用fminimax求解。定義myfun.m指定初始搜索點：x0=0.1;0.1調用x,fval=fminimax(myfun,x0)結果：x=4.00004.0000fval=0.0000-64.0000-2.0000-8.0000-0.0000iterations:7algorithm:minimaxSQP,Quasi-Newton,line_search,.,多目標規(guī)劃Matlab函數(shù)應用,解(2)：用fgoalattain求解。定義myfun.m指定初始搜索點：x0=0.1;0.1指定理想點：goal=1-60-5-10-1指定權重：weight=abs(goal)調用x,fval=fgoalattain(myfun,x0,goal,weight)結果：x=3.97983.9596fval=1.9395-62.8754-2.1412-7.9395-0.0605iterations:7algorithm:goalattainmentSQP,Quasi-Newton,line_search,.,優(yōu)化決策理論與方法,1、線性規(guī)劃2、非線性規(guī)劃（約束和非約束）3、多目標規(guī)劃4、組合優(yōu)化與整數(shù)規(guī)劃,.,組合優(yōu)化基本概念,組合優(yōu)化問題是指從一個有限的可行解集中尋找使某個性能函數(shù)取極值的最優(yōu)解。給定一個有限集N=1,2,n和權函數(shù)c:NR。記N的某些子集的集合為F，則組合優(yōu)化問題就是從F中找到一個具有最小權重的子集。已經證明：求解組合優(yōu)化問題的最優(yōu)解是NP-難的。設計各類貪婪算法是求解組合優(yōu)化問題常