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

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