優(yōu)化決策理論與方法課件

決策理論與方法(2)

——優(yōu)化決策理論與方法合肥工業(yè)大學管理學院Saturday,December17,2022決策理論與方法(2)

——確定性決策確定性決策：指未來狀態(tài)是確定的（即只有一種狀態(tài)）一類決策問題，每一個行動方案對應著一個確定的結果值，此時決策函數僅依賴于決策變量。特點：狀態(tài)是確定的；決策問題變?yōu)閮?yōu)化問題。決策的已知變量：決策變量及其取值范圍解決問題的主要理論方法：最優(yōu)化理論與方法注：最優(yōu)化理論與方法（數學規(guī)劃）也可以求解不確定性決策問題、隨機性決策問題決策理論與方法-優(yōu)化決策理論與方法確定性決策確定性決策：指未來狀態(tài)是確定的（即只有一種狀態(tài)）一2確定性決策優(yōu)化決策方法的問題求解過程辨識目標C，確定優(yōu)化的標準，如：利潤、時間、能量等確定影響決策目標的決策變量x，形成目標函數C=f(x)明確決策變量的取值范圍，形成約束函數設計求解算法，尋找決策目標在決策變量所受限制的范圍內的極小化或極大化。最優(yōu)化問題的一般形式為：決策理論與方法-優(yōu)化決策理論與方法確定性決策優(yōu)化決策方法的問題求解過程決策理論與方法-優(yōu)化決策3優(yōu)化問題分類可行點與可行域：滿足約束條件的x稱為可行點，所有可行點的集合稱為可行域，記為S；約束優(yōu)化與無約束優(yōu)化：當SRn時，稱為約束優(yōu)化；當S=Rn時，稱為無約束優(yōu)化；多目標優(yōu)化：若f是多個目標函數構成的一個向量值函數，則稱為多目標規(guī)劃；線性規(guī)劃與非線性規(guī)劃：當f,g,h均為線性函數時稱為線性規(guī)劃，否則稱為非線性規(guī)劃。決策理論與方法-優(yōu)化決策理論與方法優(yōu)化問題分類可行點與可行域：滿足約束條件的x稱為可行點，所有4優(yōu)化問題分類整數規(guī)劃：當決策變量的取值均為整數時稱為整數規(guī)劃；若某些變量取值為整數，而另一些變量取值為實數，則成為混合整數規(guī)劃。動態(tài)規(guī)劃與多層規(guī)劃：若決策是分成多個階段完成的，前后階段之間相互影響，則稱為動態(tài)規(guī)劃；若決策是分成多個層次完成的，不同層次之間相互影響，則稱為多層規(guī)劃。決策理論與方法-優(yōu)化決策理論與方法優(yōu)化問題分類整數規(guī)劃：當決策變量的取值均為整數時稱為整數規(guī)劃5優(yōu)化決策理論與方法1、線性規(guī)劃2、非線性規(guī)劃（約束和非約束）3、多目標規(guī)劃4、組合優(yōu)化與整數規(guī)劃決策理論與方法-優(yōu)化決策理論與方法優(yōu)化決策理論與方法1、線性規(guī)劃決策理論與方法-優(yōu)化決策理論與6線性規(guī)劃—管理實例(食譜問題)假設市場上有n種不同的食物，第j種食物的單價為cj。人體正常活動過程中需要m種基本的營養(yǎng)成分，且每人每天至少需要攝入第i種營養(yǎng)成分bi個單位。已知第j種食物中包含第i種營養(yǎng)成分的量為aij個單位。問在滿足人體基本營養(yǎng)需求的前提下什么樣的配食方案最經濟？設食譜中包含第j種食物的量為xj，則：決策理論與方法-優(yōu)化決策理論與方法線性規(guī)劃—管理實例(食譜問題)假設市場上有n種不同的食物，第7線性規(guī)劃—標準型決策理論與方法-優(yōu)化決策理論與方法線性規(guī)劃—標準型決策理論與方法-優(yōu)化決策理論與方法8線性規(guī)劃—單純形算法解空間分析可行域分析：n維空間；第一象限；m個超平面。最優(yōu)解分析：在端點(或稱為極點。極點向量中，至少有n-m個0分量)處取極值。單純形算法的基本思想從某個極點開始獲得一個可行解；判斷該可行解是不是目標解。若是，算法結束；否則尋找下一個極點（確定入基變量和出基變量），直至找到目標解。決策理論與方法-優(yōu)化決策理論與方法線性規(guī)劃—單純形算法解空間分析決策理論與方法-優(yōu)化決策理論與9線性規(guī)劃—內點算法1972年，V.Klee和G.L.Minty指出Dantzig的單純形算法的迭代次數為O(2n)，是一個指數時間算法，不是優(yōu)良算法。那么是否存在求解線性規(guī)劃問題的多項式時間算法？1984年，N.Karmarkar提出了一種投影尺度算法，其計算效果能夠同單純形法相比較，掀起了線性規(guī)劃內點算法的熱潮。決策理論與方法-優(yōu)化決策理論與方法線性規(guī)劃—內點算法1972年，V.Klee和G.L.M10線性規(guī)劃—內點算法內點算法的思想已知線性規(guī)劃問題的可行域是一個多面體，最優(yōu)點在多面體的某個極點取到。在給定初始可行解后，沿著什么樣的路徑到達最優(yōu)解呢？單純形法是從某個基可行解開始，沿著多面體的邊移動最終找到最優(yōu)解。內點算法的思想是從可行域內的任意一點(任一可行解)出發(fā)，穿越可行域的內部達到最優(yōu)解。N.Karmarkar的投影尺度算法就是一種典型的內點算法。決策理論與方法-優(yōu)化決策理論與方法線性規(guī)劃—內點算法內點算法的思想決策理論與方法-優(yōu)化決策理論11線性規(guī)劃—內點算法可行域內點初始基可行解基可行解目標函數目標函數最速下降方向決策理論與方法-優(yōu)化決策理論與方法線性規(guī)劃—內點算法可行域內點初始基可行解基可行解目標函數目標12線性規(guī)劃—內點算法投影尺度算法如何穿過可行域的內部快速達到最優(yōu)解呢？Karmarkar發(fā)現：(1)如果一個內點位于可行域(多胞形、多面體)的中心，那么目標函數的最速下降方向是比較好的方向；(2)存在一個適當的變換，能夠將可行域中給定的內點置于變換后的可行域的中心?；谶@兩點，Karmarkar構造了一種稱為投影尺度算法的內點算法。決策理論與方法-優(yōu)化決策理論與方法線性規(guī)劃—內點算法投影尺度算法決策理論與方法-優(yōu)化決策理論與13線性規(guī)劃—內點算法X空間內點目標函數目標函數最速下降方向Y1空間中心點投影尺度變換1目標函數最速下降方向Y2空間中心點投影尺度變換2決策理論與方法-優(yōu)化決策理論與方法線性規(guī)劃—內點算法X空間內點目標函數目標函數最速下降方向Y114線性規(guī)劃—Matlab函數應用OptimizationToolBoxMinfTxS.t.A·x≤bAeq·x=beqlb≤x≤ub其中：f,x,b,beq,lb和ub均為向量；A和Aeq為矩陣。[x,fval]=linprog(f,A,b,Aeq,beq,lb,ub)決策理論與方法-優(yōu)化決策理論與方法線性規(guī)劃—Matlab函數應用OptimizationTo15線性規(guī)劃—Matlab函數應用例：maxz=x1+2x2S.t.x1+x2≤402x1+x2≤60x1≥0;x2≥0解：將max變?yōu)閙in，min–z=-x1-2x2則：f=[-1;-2];b=[40;60];lb=zeros(2,1);A=[11;21][x,fval]=linprog(f,A,b,[],[],lb)x=[0;40],fval=-80x1x2x1+x2=402x1+x2=60Z=x1+2x2決策理論與方法-優(yōu)化決策理論與方法線性規(guī)劃—Matlab函數應用例：maxz=x1+2x2x16優(yōu)化決策理論與方法1、線性規(guī)劃2、非線性規(guī)劃（約束和非約束）3、多目標規(guī)劃4、組合優(yōu)化與整數規(guī)劃決策理論與方法-優(yōu)化決策理論與方法優(yōu)化決策理論與方法1、線性規(guī)劃決策理論與方法-優(yōu)化決策理論與17無約束非線性規(guī)劃—標準型Minf(x);xRn其中f：Rn→R是一個非線性連續(xù)函數。對于任意點x*Rn,它是函數f的最小點(或局部極小點)嗎？例如：minf(x)=ex1(4x12+2x22+4x1x2+2x2+1)決策理論與方法-優(yōu)化決策理論與方法無約束非線性規(guī)劃—標準型Minf(x);xRn決策理論18無約束非線性規(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)是可微凸函數，則x*是f(x)的全局最小點，當且僅當梯度f(x*)=0。決策理論與方法-優(yōu)化決策理論與方法無約束非線性規(guī)劃—極小值存在條件必要條件。設x*是f(x)的19無約束非線性規(guī)劃—復習梯度矩陣Hesse矩陣Taylor展開決策理論與方法-優(yōu)化決策理論與方法無約束非線性規(guī)劃—復習梯度矩陣Hesse矩陣Taylor展開20無約束非線性規(guī)劃—牛頓法基本思想：在一個點附近，用目標函數f(x)的二階Taylor多項式近似f(x)，并用該Taylor多項式的最小點近似f(x)的最小點。如果近似誤差比較大，那么可在近似最小點附近重新構造f(x)的二階Taylor多項式(迭代)，據此尋找新的近似最小點，重復以上過程直到求得滿足一定精度要求的迭代點。決策理論與方法-優(yōu)化決策理論與方法無約束非線性規(guī)劃—牛頓法基本思想：在一個點附近，用目標函數f21無約束非線性規(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)決策理論與方法-優(yōu)化決策理論與方法無約束非線性規(guī)劃—牛頓法設xk是第k次迭代結果，記gk=g(22無約束非線性規(guī)劃—牛頓法牛頓迭代法步驟初始化：給定一個初始點x0以及參數e>0；記k=0。收斂性檢驗：計算g(xk)，若||g(xk)||≤e，則算法終止；否則計算G(xk)。迭代改進：計算新的迭代點xk+1，即xk+1=xk-G-1(xk)g(xk)。k+1→k。返回收斂性檢驗。決策理論與方法-優(yōu)化決策理論與方法無約束非線性規(guī)劃—牛頓法牛頓迭代法步驟決策理論與方法-優(yōu)化決23無約束非線性規(guī)劃—準牛頓法牛頓法算法的優(yōu)點是收斂速度快(利用了Hesse矩陣)。但使用Hesse矩陣的不足之處是計算量大，Hesse矩陣可能非正定等，準牛頓法(Quasi-Newtonmethod)是對牛頓法的改進，目前被公認為是比較有效的無約束優(yōu)化方法。基本思想：在迭代過程中只利用目標函數f(x)和梯度g(x)的信息，構造Hesse矩陣的近似矩陣，由此獲得一個搜索方向，生產新的迭代點。具體內容請參考相關書籍。決策理論與方法-優(yōu)化決策理論與方法無約束非線性規(guī)劃—準牛頓法牛頓法算法的優(yōu)點是收斂速度快(利用24無約束非線性規(guī)劃—Matlab函數應用OptimizationToolBoxMinf(x)Matlab提供了兩個求解無約束非線性規(guī)劃的函數[x,fval]=fminunc(fun,x0)[x,fval]=fminsearch(fun,x0)用法相似，算法內部的搜索策略不同。fun為f(x)的函數形式，x0為初始解向量。決策理論與方法-優(yōu)化決策理論與方法無約束非線性規(guī)劃—Matlab函數應用Optimizatio25無約束非線性規(guī)劃—Matlab函數應用用法創(chuàng)建一個matlab文件，如myfun.mfunctionf=myfun(x)f=f(x);然后調用fminunc或fminsearch并指定初始搜索點。x0=[x1,x2,…,xn][x,fval]=fminunc(@myfun,x0)或[x,fval]=fminsearch(@myfun,x0)決策理論與方法-優(yōu)化決策理論與方法無約束非線性規(guī)劃—Matlab函數應用用法決策理論與方法-優(yōu)26無約束非線性規(guī)劃—Matlab函數應用例：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ī)劃函數x0=[-1,1];%Startingguessoptions=optimset('LargeScale','off');[x,fval]=fminunc(@myfun,x0,options);或者[x,fval]=

fminsearch(@myfun,x0,options);決策理論與方法-優(yōu)化決策理論與方法無約束非線性規(guī)劃—Matlab函數應用例：minf(x)=27無約束非線性規(guī)劃—Matlab函數應用fminunc結果：x=[0.5000-1.0000]fval=1.0983e-015iterations:8algorithm:'medium-scale:Quasi-Newtonlinesearch‘

fminsearch結果：x=[0.5000-1.0000]fval=5.1425e-010iterations:46algorithm:'Nelder-Meadsimplexdirectsearch'決策理論與方法-優(yōu)化決策理論與方法無約束非線性規(guī)劃—Matlab函數應用fminunc結果：28約束非線性規(guī)劃—標準型其中f(x)是目標函數，gi(x)和hj(x)為約束函數(約束條件)。S={x|gi(x)0hj(x)=0}為可行域。有約束非線性規(guī)劃問題(COP)是指f(x),gi(x),hj(x)至少有一個是非線性的，且I或至少有一個為非空。決策理論與方法-優(yōu)化決策理論與方法約束非線性規(guī)劃—標準型決策理論與方法-優(yōu)化決策理論與方法29約束非線性規(guī)劃—幾個概念積極(active)約束：設x0是COP問題的一個可行解，則它必須滿足所有約束條件。對于gi(x0)0，或者等號成立，或者大于號成立。稱等號成立的約束為積極約束(有效約束)，此時，x0處于該約束條件形成的可行域邊界上；稱大于號成立的約束為非積極(inactive)約束(無效約束)，此時，x0不在該約束條件形成的可行域邊界上。顯然所有hj(x0)約束均是積極約束。記J={j|gj(x0)=0hj(x0)=0}，稱為積極約束指標集。決策理論與方法-優(yōu)化決策理論與方法約束非線性規(guī)劃—幾個概念積極(active)約束：設x0是C30約束非線性規(guī)劃—幾個概念可行方向。設x0為COP問題的任一可行解，對某一方向d來說，若0>0使得對于任意[0,0]，均有x0+dS，稱d為x0的一個可行方向。顯然若d滿足dTgi(x)0，dThj(x)=0，則d一定是可行方向。（可用一階Taylor公式分析）。下降方向。設x0S，對某一方向d來說，若0>0使得對于任意[0,0]，均有f(x0+d)<f(x0)，則稱d為x0點的一個下降方向。由f(x0+d)=f(x0)+(f(x0))Td+o()可知：若d滿足dTf(x0)<0，有f(x0+d)<f(x0)，則d一定是下降方向?？尚邢陆捣较?。若x0的某一方向d既是可行方向又是下降方向則稱其為可行下降方向。這個方向就是我們從x0出發(fā)尋求最優(yōu)解的搜索方向！決策理論與方法-優(yōu)化決策理論與方法約束非線性規(guī)劃—幾個概念可行方向。設x0為COP問題的任一可31約束非線性規(guī)劃—幾個概念例：minf(x)=x1+x2S.t.g(x)=1-x12-x220圖描述了該問題的相關概念。x1x2決策理論與方法-優(yōu)化決策理論與方法約束非線性規(guī)劃—幾個概念例：minf(x)=x1+x2x132約束非線性規(guī)劃—極小值存在條件一階必要條件幾何特征：若x*是COP問題的局部極小點且函數f(x),gi(x),hj(x)在x*處可微，則dTf(x*)0。d為x*的任意可行方向。f(x*+d)=f(x*)+(f(x*))Td+o()代數特征(KKT定理)：若x*是COP問題的局部極小點且函數f(x),gi(x),hj(x)在x*處可微，則存在實數i0(iI),jR(j)，使得：f(x*)=igi(x*)i+jhj(x*)j；gi(x*)i=0；i0，iI若x*滿足KKT條件，則稱x*為COP問題的一個KKT點，i,j稱為x*處的拉格朗日乘子。決策理論與方法-優(yōu)化決策理論與方法約束非線性規(guī)劃—極小值存在條件一階必要條件決策理論與方法-優(yōu)33約束非線性規(guī)劃—極小值存在條件一階充分條件設x*S，若函數f(x),gi(x),hj(x)在x*處可微，且對于x*的任意可行方向d，有dTf(x*)>0，則x*為COP問題的一個嚴格局部極小點。(凸規(guī)劃問題)設f(x)為凸函數，gi(x)為凹函數，hj(x)為線性函數。對于x*S，若函數f(x),gi(x)在x*處可微，且KKT條件成立，則x*為COP問題的全局最小點。決策理論與方法-優(yōu)化決策理論與方法約束非線性規(guī)劃—極小值存在條件一階充分條件決策理論與方法-優(yōu)34約束非線性規(guī)劃—極小值存在條件二階必要條件設x*是COP問題的局部極小點且滿足KKT條件。若函數f(x),gi(x),hj(x)在x*處二階可微，則必有：dTxx2L(x*,*,*)d0其中，L(x,,)=f(x)-g(x)T-h(x)T,g(x),h(x)分別為由gi(x)和hj(x)構成的向量值函數，,分別為對應于g(x)和h(x)的拉格朗日乘子向量。二階充分條件設x*是COP問題的KKT點。*,*分別為對應于g(x)和h(x)的拉格朗日乘子向量，且函數f(x),gi(x),hj(x)在x*處二階可微，若dTxx2L(x*,*,*)d>0,則x*為COP問題的一個嚴格局部極小點。決策理論與方法-優(yōu)化決策理論與方法約束非線性規(guī)劃—極小值存在條件二階必要條件決策理論與方法-優(yōu)35約束非線性規(guī)劃—極小值存在條件例：minf(x)=x12+x22S.t.x1+x24x1,x20解：g1(x)=x1+x2-40;g2(x)=x10;g3(x)=x20f(x)=[2x1,2x2]T,g1(x)=[1,1]T,g2(x)=[1,0]T,g3(x)=[0,1]T,得到：2x1=1+22x2=1+3又(x1+x2-4)1=0；x12=0；x23=0；i0若1=0，則x1=x2=0，與題意不符；若1>0，則x1+x2-4=0，x1>0,x2>0。因此有2=3=0，所以x1=x2=1/2，得x1=x2=2，x*=[2,2]T為該問題的唯一KKT點。根據凸規(guī)劃充分條件知x*為全局最小點。決策理論與方法-優(yōu)化決策理論與方法約束非線性規(guī)劃—極小值存在條件例：minf(x)=x12+36約束非線性規(guī)劃—可行方向法上面例題介紹了通過求解KKT方程獲得問題解的方法，但KKT方程并不總是很好求解。下面介紹幾種約束優(yōu)化的求解方法：可行方向法、序列無約束化法和SQP法。可行方向法的應用條件：要求所有約束均為線性約束（稱為線性約束的優(yōu)化問題，LCO）。可行方向法的基本思想：當某個可行方向同時也是目標函數的下降方向時，沿此方向移動一定會在滿足可行性的情況下改進迭代點的目標函數值。決策理論與方法-優(yōu)化決策理論與方法約束非線性規(guī)劃—可行方向法上面例題介紹了通過求解KKT方程獲37約束非線性規(guī)劃—可行方向法x1x2決策理論與方法-優(yōu)化決策理論與方法約束非線性規(guī)劃—可行方向法x1x2決策理論與方法-優(yōu)化決策理38約束非線性規(guī)劃—可行方向法LCO問題：Minf(x)S.t.aiTxbi,iI

ajTx=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。決策理論與方法-優(yōu)化決策理論與方法約束非線性規(guī)劃—可行方向法LCO問題：決策理論與方法-優(yōu)化決39約束非線性規(guī)劃—可行方向法Zoutendijk可行方向法：其核心思想是通過求解下列線性規(guī)劃問題，在可行方向的某個范圍內獲得目標函數的最速下降方向。MindTf(x0)S.t.AI(x0)d0,I(x0)={i|aiTx0=bi,iI}Ad=0||d||∞1可以證明：當x0取得KKT點時當且僅當dTf(x0)的最優(yōu)值為零。決策理論與方法-優(yōu)化決策理論與方法約束非線性規(guī)劃—可行方向法Zoutendijk可行方向法：其40約束非線性規(guī)劃—序列無約束化法求解約束優(yōu)化的一類重要方法是用一個無約束優(yōu)化問題的序列逼近約束優(yōu)化問題，通過無約束優(yōu)化問題的最優(yōu)解序列逼近約束優(yōu)化問題的最優(yōu)解。基本思想：將約束條件通過某種轉換與目標函數合并形成一個無約束優(yōu)化問題。這種轉換隱含著某種懲罰，即x偏離約束條件越遠，受到的懲罰越大。因此也將此類方法稱為罰函數法，所形成的無約束優(yōu)化函數成為罰函數。決策理論與方法-優(yōu)化決策理論與方法約束非線性規(guī)劃—序列無約束化法求解約束優(yōu)化的一類重要方法是用41約束非線性規(guī)劃—序列無約束化法二次罰函數法：罰函數：其中(gi)-=max{0,-gi}，稱為罰參數，且當→0時，Q(x,)的極小值趨于f(x)的極小值。決策理論與方法-優(yōu)化決策理論與方法約束非線性規(guī)劃—序列無約束化法二次罰函數法：決策理論與方法-42約束非線性規(guī)劃—序列無約束化法例：minf=x1+x2S.t.x1-x22=0解：對于>0，定義二次罰函數MinQ(x,)=x1+x2+(2)-1(x1-x22)2Q’x1=1+(x1-x22)/=0Q’x2=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決策理論與方法-優(yōu)化決策理論與方法約束非線性規(guī)劃—序列無約束化法例：minf=x1+x2決策43約束非線性規(guī)劃—序列無約束化法對數障礙函數法：障礙函數：其中稱為障礙參數，且當→0時，P(x,)的極小值趨于f(x)的極小值。該方法的適用性：COP問題僅包含不等式約束函數，且可行域存在內點。即S0={x|g(x)>0}≠決策理論與方法-優(yōu)化決策理論與方法約束非線性規(guī)劃—序列無約束化法對數障礙函數法：決策理論與方法44約束非線性規(guī)劃—序列無約束化法例：min{f=x/2|x1}解：構造對數障礙函數P(x,)=x/2-ln(x-1)P’x=1/2-/(x-1)=0，得x*=1+2，P*=1/2+-ln2當→0時得x*=1，f*=1/2決策理論與方法-優(yōu)化決策理論與方法約束非線性規(guī)劃—序列無約束化法例：min{f=x/2|x145二次規(guī)劃—標準型若有約束非線性規(guī)劃的目標函數是決策變量x的二次函數且所有約束均為線性約束，稱此類非線性規(guī)劃問題為二次規(guī)劃(QuadraticProgramming,QP)問題。其標準型為：決策理論與方法-優(yōu)化決策理論與方法二次規(guī)劃—標準型若有約束非線性規(guī)劃的目標函數是決策變量x的二46二次規(guī)劃—標準型其中Q=QTRn×n（n階對稱方陣）；以aiT(iI)為行向量的矩陣記為AIRI×n；以ajT(j)為行向量的矩陣記為AR×n；對應的向量記為bI,b。若目標函數的Hesse矩陣Q是半正定(或正定)的，則QP問題為(嚴格)凸二次規(guī)劃(CQP)。我們僅討論凸二次規(guī)劃問題，因為非凸二次規(guī)劃的Q存在負特征根，求解很困難。決策理論與方法-優(yōu)化決策理論與方法二次規(guī)劃—標準型其中Q=QTRn×n（n階對稱方陣）；以a47二次規(guī)劃—極小點存在條件充要條件可行點x*是QP問題的局部極小點當且僅當x*為一個KKT點且對于任意非零可行方向d，有dTQd0。對于凸二次規(guī)劃，x*為全局極小點當且僅當x*為局部極小點，當且僅當x*為KKT點。二次規(guī)劃的KKT定理形式為：Qx*+c=AIT*+AT*(AIx*-bI)*=0二次規(guī)劃的求解本質上就是求解上述KKT方程。決策理論與方法-優(yōu)化決策理論與方法二次規(guī)劃—極小點存在條件充要條件決策理論與方法-優(yōu)化決策理論48約束非線性規(guī)劃—SQP法對于非線性約束優(yōu)化(COP)問題，若x*是COP問題的一個局部最優(yōu)解，則它對應一個純等式約束優(yōu)化問題決策理論與方法-優(yōu)化決策理論與方法約束非線性規(guī)劃—SQP法對于非線性約束優(yōu)化(COP)問題，決49約束非線性規(guī)劃—SQP法因此如果事先知道積極約束指標集，那么帶有不等式約束優(yōu)化問題就可以轉化為純等式約束優(yōu)化問題，并可用準牛頓法求解，這就是逐次二次規(guī)劃(SequentialQuadraticProgramming，SQP)法?；舅枷耄涸诘c處構造一個二次規(guī)劃子問題，近似原來的約束優(yōu)化問題；然后通過求解該二次規(guī)劃子問題獲得約束優(yōu)化問題的一個改進迭代點；不斷重復此過程，直到求出滿足一定要求的迭代點。決策理論與方法-優(yōu)化決策理論與方法約束非線性規(guī)劃—SQP法因此如果事先知道積極約束指標集，那么50約束非線性規(guī)劃—SQP法對于等式約束優(yōu)化問題Minf(x)S.t.h(x)=0拉格朗日函數記為L(x,)=f(x)-Th(x)則L(x,)=(f(x)-h(x),-h(x))T=0，顯然問題的最優(yōu)解(x*,*)滿足此式。設(xk,k)是第k次迭代結果，根據牛頓法，有：決策理論與方法-優(yōu)化決策理論與方法約束非線性規(guī)劃—SQP法對于等式約束優(yōu)化問題決策理論與方法-51約束非線性規(guī)劃—SQP法上述迭代過程等價于如下的二次規(guī)劃的迭代。設給定迭代點(xk,k)，則決策理論與方法-優(yōu)化決策理論與方法約束非線性規(guī)劃—SQP法上述迭代過程等價于如下的二次規(guī)劃的迭52約束非線性規(guī)劃—Matlab函數應用OptimizationToolBoxMinf(x)s.t.c(x)0ceq(x)=0A·xbAeq·x=beqlbxub[x,fval]=fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon)fun定義目標函數,x0定義初始可行解，nonlcon定義c(x)和ceq(x)。決策理論與方法-優(yōu)化決策理論與方法約束非線性規(guī)劃—Matlab函數應用Optimization53約束非線性規(guī)劃—Matlab函數應用用法創(chuàng)建一個matlab文件，如myfun.mfunctionf=myfun(x)f=f(x);創(chuàng)建另一個matlab文件，如confun.mfunction[c,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)決策理論與方法-優(yōu)化決策理論與方法約束非線性規(guī)劃—Matlab函數應用用法決策理論與方法-優(yōu)化54約束非線性規(guī)劃—Matlab函數應用例：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.mfunction[c,ceq]=confun(x)c=[1.5+x(1)*x(2)-x(1)-x(2);-x(1)*x(2)-10];ceq=[];決策理論與方法-優(yōu)化決策理論與方法約束非線性規(guī)劃—Matlab函數應用例：minf(x)=e55約束非線性規(guī)劃—Matlab函數應用調用有約束非線性規(guī)劃函數x0=[-1,1];%Startingguessoptions=optimset('LargeScale','off');[x,fval]=fmincon(@objfun,x0,[],[],[],[],[],[],@confun,options)運行結果：x=[-9.54741.0474]fval=0.0236iterations:8algorithm:'medium-scale:SQP,Quasi-Newton,line-search'決策理論與方法-優(yōu)化決策理論與方法約束非線性規(guī)劃—Matlab函數應用調用有約束非線性規(guī)劃函數56二次規(guī)劃—Matlab函數應用OptimizationToolBoxMin0.5xTHx+fTxs.t.A·xbAeq·x=beqlbxub[x,fval]=quadprog(H,f,A,b,Aeq,beq,lb,ub,x0)x0定義初始可行解(可選)決策理論與方法-優(yōu)化決策理論與方法二次規(guī)劃—Matlab函數應用OptimizationTo57二次規(guī)劃—Matlab函數應用用法首先要將目標函數轉換成二次規(guī)劃標準型，從而得到H和f兩個矩陣。調用quadprog并根據需要指定初始搜索點以及其他向量、矩陣。x0=[x1,x2,…,xn];A;b;Aeq;beq;lb;ub;[x,fval]=quadprog(H,f,A,b,Aeq,beq,lb,ub,x0)決策理論與方法-優(yōu)化決策理論與方法二次規(guī)劃—Matlab函數應用用法決策理論與方法-優(yōu)化決策理58二次規(guī)劃—Matlab函數應用例：minf(x)=1/2x12+x22-x1x2-2x1-6x2)S.t.x1+x22

-x1+2x22

2x1+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=[]。不指派初始解。決策理論與方法-優(yōu)化決策理論與方法二次規(guī)劃—Matlab函數應用例：minf(x)=1/2x59二次規(guī)劃—Matlab函數應用調用二次規(guī)劃函數[x,fval]=quadprog(H,f,A,b,[],[],lb)運行結果：x=[0.6667;1.3333]fval=-8.2222iterations:3algorithm:‘medium-scale:active-set(積極約束集方法)'決策理論與方法-優(yōu)化決策理論與方法二次規(guī)劃—Matlab函數應用調用二次規(guī)劃函數決策理論與方法60優(yōu)化決策理論與方法1、線性規(guī)劃2、非線性規(guī)劃（約束和非約束）3、多目標規(guī)劃4、組合優(yōu)化與整數規(guī)劃決策理論與方法-優(yōu)化決策理論與方法優(yōu)化決策理論與方法1、線性規(guī)劃決策理論與方法-優(yōu)化決策理論與61多目標規(guī)劃—管理實例(物資調度)假設物資調度部門計劃將某種物資從若干個存儲倉庫調運到若干個銷售網點銷售?？紤]到物資的時效性和銷售效益，調度部門希望物資在運輸過程中盡可能快地到達目的地；同時，考慮到運輸成本，調度部門還希望物資的總運輸費用最小。試建立描述物資調運過程的數學模型。解：設共有m個倉庫，第i個倉庫的物資庫存量為ai噸；有n個銷售網點，第j個銷售網點的銷售量為bj噸。第i個倉庫到第j個銷售網點的距離為dij，單位物資的運費為cij。設從第i個倉庫運到第j個銷售網點的物資量為xij。決策理論與方法-優(yōu)化決策理論與方法多目標規(guī)劃—管理實例(物資調度)假設物資調度部門計劃將某種物62多目標規(guī)劃—管理實例決策目標：運輸速度最快，可用噸公里數（可觀測變量）最小描述?？倗嵐飻禐閕jdijxij；運輸費用最小?？傔\輸費用為ijcijxij；約束條件每個倉庫的運出量不超過倉庫的庫存量：jxijai；運到每個銷售網點的量與其銷售能力相匹配：ixij=bj；每個倉庫的運出量非負：xij0。決策理論與方法-優(yōu)化決策理論與方法多目標規(guī)劃—管理實例決策目標：決策理論與方法-優(yōu)化決策理論與63多目標規(guī)劃—管理實例最后得到模型：模型包含2個目標；mn個決策變量；mn+m+n個約束。決策理論與方法-優(yōu)化決策理論與方法多目標規(guī)劃—管理實例最后得到模型：決策理論與方法-優(yōu)化決策理64多目標規(guī)劃—標準型多目標規(guī)劃(multi-ObjectiveProgramming,MOP)就是指在決策變量滿足給定約束的條件下研究多個可數值化的目標函數同時極小化(或極大化)的問題。其一般形式如下：Minf(x)=(f1(x),f2(x),…,fp(x))T，S.t.gi(x)0;iIhj(x)=0;j。決策理論與方法-優(yōu)化決策理論與方法多目標規(guī)劃—標準型多目標規(guī)劃(multi-Objective65多目標規(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)解。Sx1x2f(S)f(S)f2f2f1f1絕對最優(yōu)解有效解弱有效解決策理論與方法-優(yōu)化決策理論與方法多目標規(guī)劃—Pareto最優(yōu)解設x*是可行域S上的一個點，對66多目標規(guī)劃—Pareto最優(yōu)解存在條件(必要條件)假設向量值函數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。決策理論與方法-優(yōu)化決策理論與方法多目標規(guī)劃—Pareto最優(yōu)解存在條件(必要條件)假設向量值67多目標規(guī)劃—求解方法直接求解多目標規(guī)劃問題的有效解集是NP-難問題。下面介紹多目標規(guī)劃問題的間接解法，基本思路都是將多目標規(guī)劃問題轉化為一個或多個單目標優(yōu)化問題?；谝粋€單目標問題的方法：將原來的多目標規(guī)劃問題轉化成一個單目標優(yōu)化問題，然后利用非線性優(yōu)化算法求解該單目標問題，所得解作為MOP問題的最優(yōu)解。關鍵問題在于：保證所構造的單目標問題的最優(yōu)解是MOP問題的有效解或弱有效解。決策理論與方法-優(yōu)化決策理論與方法多目標規(guī)劃—求解方法直接求解多目標規(guī)劃問題的有效解集是NP-68多目標規(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為專家經驗值。決策理論與方法-優(yōu)化決策理論與方法多目標規(guī)劃—求解方法線性加權和法：決策理論與方法-優(yōu)化決策理69多目標規(guī)劃—求解方法極小化極大法：在目標函數f(x)的p個分量中，極小化f(x)的最大分量，即minxSmax1jpfj(x)理想點法：分別求出f(x)中每個分量fj(x)的極小點fj0，得到理想點f0=(f10,…,fp0)T；然后求解單目標優(yōu)化問題：minxS||f(x)-f0||。為范數的階，可取1，2，∞。決策理論與方法-優(yōu)化決策理論與方法多目標規(guī)劃—求解方法極小化極大法：在目標函數f(x)的p個分70多目標規(guī)劃—求解方法基于多個單目標問題的方法：將原來的多目標規(guī)劃問題轉化成具有一定次序的多個單目標優(yōu)化問題，然后依次求解這些單目標優(yōu)化問題，并把最后一個單目標優(yōu)化問題的解作為MOP問題的最優(yōu)解。關鍵問題在于：保證最后一個單目標優(yōu)化問題的最優(yōu)解是MOP問題的有效解或弱有效解。分層排序法：將目標函數按重要度依次排序，然后在前一個目標函數的最優(yōu)解集中尋找下一個目標的最優(yōu)解集，并把最后一個目標的最優(yōu)解作為MOP問題的最優(yōu)解。決策理論與方法-優(yōu)化決策理論與方法多目標規(guī)劃—求解方法基于多個單目標問題的方法：將原來的多目標71多目標規(guī)劃—求解方法minf1(x)，xS（不妨設f1(x)為第一層目標），得到最優(yōu)解集S1;第j層：minfj(x),xSj-1，j=2,…,p最后將Sp中的點作為多目標問題的最優(yōu)解。決策理論與方法-優(yōu)化決策理論與方法多目標規(guī)劃—求解方法minf1(x)，xS（不妨設f1(72多目標規(guī)劃—Matlab函數應用OptimizationToolBoxMinmax{fi(x)}s.t.c(x)0ceq(x)=0A·xbAeq·x=beqlbxub[x,fval]=fminimax(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon)Fun定義目標函數；x0定義初始可行解；nonlcon定義c(x)和ceq(x)。決策理論與方法-優(yōu)化決策理論與方法多目標規(guī)劃—Matlab函數應用OptimizationT73多目標規(guī)劃—Matlab函數應用用法創(chuàng)建一個matlab文件，如myfun.mfunctionf=myfun(x)f(1)=f1(x);f(2)=f2(x);…;f(p)=fp(x)創(chuàng)建另一個matlab文件，如confun.mfunction[c,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)決策理論與方法-優(yōu)化決策理論與方法多目標規(guī)劃—Matlab函數應用用法決策理論與方法-優(yōu)化決策74多目標規(guī)劃—Matlab函數應用OptimizationToolBoxMinx,

s.t.F(x)-weight·goalc(x)0ceq(x)=0A·xbAeq·x=beqlbxub[x,fval]=fgoalattain(fun,x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon)Fun定義目標函數；goal為理想點；x0定義初始可行解；nonlcon定義c(x)和ceq(x)。weight為各目標的權重向量。決策理論與方法-優(yōu)化決策理論與方法多目標規(guī)劃—Matlab函數應用OptimizationT75多目標規(guī)劃—Matlab函數應用用法創(chuàng)建一個matlab文件，如myfun.mfunctionf=myfun(x)f(1)=f1(x);f(2)=f2(x);…;f(p)=fp(x)創(chuàng)建另一個matlab文件，如confun.mfunction[c,ceq]=confun(x)c=c(x);ceq=ceq(x);調用fgoalattain并設定理想點、權重向量，指定初始搜索點以及其他向量、矩陣。x0=[x1,x2,…,xn];A;b;Aeq;beq;lb;ub;goal;weight[x,fval]=fgoalattain(@myfun,x0,goal,weight,A,b,Aeq,beq,lb,ub,@confun)決策理論與方法-優(yōu)化決策理論與方法多目標規(guī)劃—Matlab函數應用用法決策理論與方法-優(yōu)化決策76多目標規(guī)劃—Matlab函數應用例：min{f1,f2,f3,f4,f5}f(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;無約束。決策理論與方法-優(yōu)化決策理論與方法多目標規(guī)劃—Matlab函數應用例：min{f1,f2,f77多目標規(guī)劃—Matlab函數應用解(1)：用fminimax求解。定義myfun.m指定初始搜索點：x0=[0.1;0.1]調用[x,fval]=fminimax(@myfun,x0)結果：x=[4.00004.0000]fval=[0.0000-64.0000-2.0000-8.0000-0.0000]iterations:7algorithm:'minimaxSQP,Quasi-Newton,line_search‘決策理論與方法-優(yōu)化決策理論與方法多目標規(guī)劃—Matlab函數應用解(1)：用fminimax78多目標規(guī)劃—Matlab函數應用解(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.9596]fval=[1.9395-62.8754-2.1412-7.9395-0.0605]iterations:7algorithm:'goalattainmentSQP,Quasi-Newton,line_search'決策理論與方法-優(yōu)化決策理論與方法多目標規(guī)劃—Matlab函數應用解(2)：用fgoalatt79優(yōu)化決策理論與方法1、線性規(guī)劃2、非線性規(guī)劃（約束和非約束）3、多目標規(guī)劃4、組合優(yōu)化與整數規(guī)劃決策理論與方法-優(yōu)化決策理論與方法優(yōu)化決策理論與方法1、線性規(guī)劃決策理論與方法-優(yōu)化決策理論與80組合優(yōu)化—基本概念組合優(yōu)化問題是指從一個有限的可行解集中尋找使某個性能函數取極值的最優(yōu)解。給定一個有限集N={1,2,…,n}和權函數c:N→R。記N的某些子集的集合為F，則組合優(yōu)化問題就是從F中找到一個具有最小權重的子集。已經證明：求解組合優(yōu)化問題的最優(yōu)解是NP-難的。設計各類貪婪算法是求解組合優(yōu)化問題常用的思路。決策理論與方法-優(yōu)化決策理論與方法組合優(yōu)化—基本概念組合優(yōu)化問題是指從一個有限的可行解集中尋找81組合優(yōu)化—基本概念常見的組合優(yōu)化問題：最短路問題：給定一定的路長分布，確定從某個地點到另一個地點使路長最短的路徑。(TSP問題)最大流問題：在一個有容量限制的網絡中，如何使得從一個頂點到另一個頂點的流量達到最大？裝箱問題：如何將一定規(guī)格的物品裝到箱子中，使得占用箱子的個數最少？背包問題：如何挑選一些價值不同、尺寸有別的物品放到一個有限大的背包中，使得背包內的物品價值總量最大？決策理論與方法-優(yōu)化決策理論與方法組合優(yōu)化—基本概念常見的組合優(yōu)化問題：決策理論與方法-優(yōu)化決82組合優(yōu)化—最短路問題給定一個網絡N=(V,E,w)，其中w為權函數，最短路問題是指對于兩個不同的頂點s,tV，尋找一條從s到t的路，使得路上所有弧的權和最小(權可看作弧長)。關聯矩陣：A=(aij)|V|×|E|。aij=1(vi為ej的起點)；aij=-1(vi為ej的終點)；aij=0(其他情形)。引入0-1整型變量xj(ejE)，記x=(x1,x2,...,x|E|)T。則最短路徑問題可表示成如下的0-1整數規(guī)劃問題：minwTxs.t.asTx=1

atTx=-1

aiTx=0,i≠s,t

x0決策理論與方法-優(yōu)化決策理論與方法組合優(yōu)化—最短路問題給定一個網絡N=(V,E,w)，其中83組合優(yōu)化—最短路問題例：考慮如圖所示的網絡，定義權函數w=(1,2,2,3,1)T。試確定從s到t點的最短路徑。解：as=(11000)T；at=(000-1-1)T;aa=(-10110)T;ab=(0-1-101)T，得到以下規(guī)劃方程：minx1+2x2+2x3+3x4+x5s.t.x1+x2=1-x4-x5=-1-x1+x3+x4=0-x2-x3+x5=0x1,x2,x3,x4,x50調用函數linprog(w,[],[],Aeq,beq,lb)得x=[01001]T表明從s出發(fā)經過第2、5條邊到達t點最短。stabe1e2e3e5e4決策理論與方法-優(yōu)化決策理論與方法組合優(yōu)化—最短路問題例：考慮如圖所示的網絡，定義權函數w=(84整數規(guī)劃—標準型整數規(guī)劃是一類特殊的組合優(yōu)化問題。線性(混合)整數規(guī)劃問題是指在等式或不等式的線性約束下，極大化(或極小化)某個線性函數，其中要求某些變量必須取整數。線性混合整數規(guī)劃(MILP)：max{cTx+hTy|Ax+Gyb,xZ+n,yR+p}x,y為決策變量向量，其中x包含n個整數變量，y包含p個實數變量；c為n維向量；h為p維向量；A為m×n階矩陣，G為m×p階矩陣。決策理論與方法-優(yōu)化決策理論與方法整數規(guī)劃—標準型整數規(guī)劃是一類特殊的組合優(yōu)化問題。線性(混合85整數規(guī)劃—標準型整數規(guī)劃的可行域：S={(x,y)|Ax+Gyb,xZ+n,yR+p}例：P={xZ1×R1|-x1+x21/2,3x1+4x23,x20}x1x2決策理論與方法-優(yōu)化決策理論與方法整數規(guī)劃—標準型整數規(guī)劃的可行域：x1x2決策理論與方法-優(yōu)86整數規(guī)劃—解的特點從整數規(guī)劃的可行域分析可知，整數規(guī)劃的解與其松弛問題(整數規(guī)劃問題的所有變量取值不受整數限制時的線性規(guī)劃問題)既有密切的聯系，又有本質的區(qū)別。整數規(guī)劃問題的可行解一定是松弛問題的可行解，但反之不一定。所以整數規(guī)劃問題的最優(yōu)解不會優(yōu)于其松弛問題的最優(yōu)解。求解方法：Gomory割平面法、分支定界法、分解算法。決策理論與方法-優(yōu)化決策理論與方法整數規(guī)劃—解的特點從整數規(guī)劃的可行域分析可知，整數規(guī)劃的解與87整數規(guī)劃—Matlab函數應用OptimizationToolBoxMinf’·xs.t.A·xbAeq·x=beq

x：0-1[x,fval]=bintprog(f,A,b,Aeq,beq,x0)x0定義初始可行解(可選)；bintprog僅適合求解0-1整數規(guī)劃問題。決策理論與方法-優(yōu)化決策理論與方法整數規(guī)劃—Matlab函數應用OptimizationTo88演講完畢，謝謝觀看！演講完畢，謝謝觀看！89決策理論與方法(2)

——優(yōu)化決策理論與方法合肥工業(yè)大學管理學院Saturday,December17,2022決策理論與方法(2)

——確定性決策確定性決策：指未來狀態(tài)是確定的（即只有一種狀態(tài)）一類決策問題，每一個行動方案對應著一個確定的結果值，此時決策函數僅依賴于決策變量。特點：狀態(tài)是確定的；決策問題變?yōu)閮?yōu)化問題。決策的已知變量：決策變量及其取值范圍解決問題的主要理論方法：最優(yōu)化理論與方法注：最優(yōu)化理論與方法（數學規(guī)劃）也可以求解不確定性決策問題、隨機性決策問題決策理論與方法-優(yōu)化決策理論與方法確定性決策確定性決策：指未來狀態(tài)是確定的（即只有一種狀態(tài)）一91確定性決策優(yōu)化決策方法的問題求解過程辨識目標C，確定優(yōu)化的標準，如：利潤、時間、能量等確定影響決策目標的決策變量x，形成目標函數C=f(x)明確決策變量的取值范圍，形成約束函數設計求解算法，尋找決策目標在決策變量所受限制的范圍內的極小化或極大化。最優(yōu)化問題的一般形式為：決策理論與方法-優(yōu)化決策理論與方法確定性決策優(yōu)化決策方法的問題求解過程決策理論與方法-優(yōu)化決策92優(yōu)化問題分類可行點與可行域：滿足約束條件的x稱為可行點，所有可行點的集合稱為可行域，記為S；約束優(yōu)化與無約束優(yōu)化：當SRn時，稱為約束優(yōu)化；當S=Rn時，稱為無約束優(yōu)化；多目標優(yōu)化：若f是多個目標函數構成的一個向量值函數，則稱為多目標規(guī)劃；線性規(guī)劃與非線性規(guī)劃：當f,g,h均為線性函數時稱為線性規(guī)劃，否則稱為非線性規(guī)劃。決策理論與方法-優(yōu)化決策理論與方法優(yōu)化問題分類可行點與可行域：滿足約束條件的x稱為可行點，所有93優(yōu)化問題分類整數規(guī)劃：當決策變量的取值均為整數時稱為整數規(guī)劃；若某些變量取值為整數，而另一些變量取值為實數，則成為混合整數規(guī)劃。動態(tài)規(guī)劃與多層規(guī)劃：若決策是分成多個階段完成的，前后階段之間相互影響，則稱為動態(tài)規(guī)劃；若決策是分成多個層次完成的，不同層次之間相互影響，則稱為多層規(guī)劃。決策理論與方法-優(yōu)化決策理論與方法優(yōu)化問題分類整數規(guī)劃：當決策變量的取值均為整數時稱為整數規(guī)劃94優(yōu)化決策理論與方法1、線性規(guī)劃2、非線性規(guī)劃（約束和非約束）3、多目標規(guī)劃4、組合優(yōu)化與整數規(guī)劃決策理論與方法-優(yōu)化決策理論與方法優(yōu)化決策理論與方法1、線性規(guī)劃決策理論與方法-優(yōu)化決策理論與95線性規(guī)劃—管理實例(食譜問題)假設市場上有n種不同的食物，第j種食物的單價為cj。人體正?；顒舆^程中需要m種基本的營養(yǎng)成分，且每人每天至少需要攝入第i種營養(yǎng)成分bi個單位。已知第j種食物中包含第i種營養(yǎng)成分的量為aij個單位。問在滿足人體基本營養(yǎng)需求的前提下什么樣的配食方案最經濟？設食譜中包含第j種食物的量為xj，則：決策理論與方法-優(yōu)化決策理論與方法線性規(guī)劃—管理實例(食譜問題)假設市場上有n種不同的食物，第96線性規(guī)劃—標準型決策理論與方法-優(yōu)化決策理論與方法線性規(guī)劃—標準型決策理論與方法-優(yōu)化決策理論與方法97線性規(guī)劃—單純形算法解空間分析可行域分析：n維空間；第一象限；m個超平面。最優(yōu)解分析：在端點(或稱為極點。極點向量中，至少有n-m個0分量)處取極值。單純形算法的基本思想從某個極點開始獲得一個可行解；判斷該可行解是不是目標解。若是，算法結束；否則尋找下一個極點（確定入基變量和出基變量），直至找到目標解。決策理論與方法-優(yōu)化決策理論與方法線性規(guī)劃—單純形算法解空間分析決策理論與方法-優(yōu)化決策理論與98線性規(guī)劃—內點算法1972年，V.Klee和G.L.Minty指出Dantzig的單純形算法的迭代次數為O(2n)，是一個指數時間算法，不是優(yōu)良算法。那么是否存在求解線性規(guī)劃問題的多項式時間算法？1984年，N.Karmarkar提出了一種投影尺度算法，其計算效果能夠同單純形法相比較，掀起了線性規(guī)劃內點算法的熱潮。決策理論與方法-優(yōu)化決策理論與方法線性規(guī)劃—內點算法1972年，V.Klee和G.L.M99線性規(guī)劃—內點算法內點算法的思想已知線性規(guī)劃問題的可行域是一個多面體，最優(yōu)點在多面體的某個極點取到。在給定初始可行解后，沿著什么樣的路徑到達最優(yōu)解呢？單純形法是從某個基可行解開始，沿著多面體的邊移動最終找到最優(yōu)解。內點算法的思想是從可行域內的任意一點(任一可行解)出發(fā)，穿越可行域的內部達到最優(yōu)解。N.Karmarkar的投影尺度算法就是一種典型的內點算法。決策理論與方法-優(yōu)化決策理論與方法線性規(guī)劃—內點算法內點算法的思想決策理論與方法-優(yōu)化決策理論100線性規(guī)劃—內點算法可行域內點初始基可行解基可行解目標函數目標函數最速下降方向決策理論與方法-優(yōu)化決策理論與方法線性規(guī)劃—內點算法可行域內點初始基可行解基可行解目標函數目標101線性規(guī)劃—內點算法投影尺度算法如何穿過可行域的內部快速達到最優(yōu)解呢？Karmarkar發(fā)現：(1)如果一個內點位于可行域(多胞形、多面體)的中心，那么目標函數的最速下降方向是比較好的方向；(2)存在一個適當的變換，能夠將可行域中給定的內點置于變換后的可行域的中心?；谶@兩點，Karmarkar構造了一種稱為投影尺度算法的內點算法。決策理論與方法-優(yōu)化決策理論與方法線性規(guī)劃—內點算法投影尺度算法決策理論與方法-優(yōu)化決策理論與102線性規(guī)劃—內點算法X空間內點目標函數目標函數最速下降方向Y1空間中心點投影尺度變換1目標函數最速下降方向Y2空間中心點投影尺度變換2決策理論與方法-優(yōu)化決策理論與方法線性規(guī)劃—內點算法X空間內點目標函數目標函數最速下降方向Y1103線性規(guī)劃—Matlab函數應用OptimizationToolBoxMinfTxS.t.A·x≤bAeq·x=beqlb≤x≤ub其中：f,x,b,beq,lb和ub均為向量；A和Aeq為矩陣。[x,fval]=linprog(f,A,b,Aeq,beq,lb,ub)決策理論與方法-優(yōu)化決策理論與方法線性規(guī)劃—Matlab函數應用OptimizationTo104線性規(guī)劃—Matlab函數應用例：maxz=x1+2x2S.t.x1+x2≤402x1+x2≤60x1≥0;x2≥0解：將max變?yōu)閙in，min–z=-x1-2x2則：f=[-1;-2];b=[40;60];lb=zeros(2,1);A=[11;21][x,fval]=linprog(f,A,b,[],[],lb)x=[0;40],fval=-80x1x2x1+x2=402x1+x2=60Z=x1+2x2決策理論與方法-優(yōu)化決策理論與方法線性規(guī)劃—Matlab函數應用例：maxz=x1+2x2x105優(yōu)化決策理論與方法1、線性規(guī)劃2、非線性規(guī)劃（約束和非約束）3、多目標規(guī)劃4、組合優(yōu)化與整數規(guī)劃決策理論與方法-優(yōu)化決策理論與方法優(yōu)化決策理論與方法1、線性規(guī)劃決策理論與方法-優(yōu)化決策理論與106無約束非線性規(guī)劃—標準型Minf(x);xRn其中f：Rn→R是一個非線性連續(xù)函數。對于任意點x*Rn,它是函數f的最小點(或局部極小點)嗎？例如：minf(x)=ex1(4x12+2x22+4x1x2+2x2+1)決策理論與方法-優(yōu)化決策理論與方法無約束非線性規(guī)劃—標準型Minf(x);xRn決策理論107無約束非線性規(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)是可微凸函數，則x*是f(x)的全局最小點，當且僅當梯度f(x*)=0。決策理論與方法-優(yōu)化決策理論與方法無約束非線性規(guī)劃—極小值存在條件必要條件。設x*是f(x)的108無約束非線性規(guī)劃—復習梯度矩陣Hesse矩陣Taylor展開決策理論與