【正文】 決策理論與方法 (2) —— 優(yōu)化決策理論與方法合肥工業(yè)大學管理學院Wednesday, April 07, 2023確定性決策v 確定性決策 ：指未來狀態(tài)是確定的（即只有一種狀態(tài)）一類決策問題，每一個行動方案對應著一個確定的結果值，此時決策函數(shù)僅依賴于決策變量。v 特點 ：狀態(tài)是確定的；決策問題變?yōu)閮?yōu)化問題。v 決策的已知變量 ：? 決策變量及其取值范圍v 解決問題的主要理論方法 ：最優(yōu)化理論與方法v 注： 最優(yōu)化理論與方法（數(shù)學規(guī)劃）也可以求解不確定性決策問題、隨機性決策問題決策理論與方法 優(yōu)化決策理論與方法確定性決策v 優(yōu)化決策方法的問題求解過程? 辨識目標 C，確定優(yōu)化的標準，如：利潤、時間、能量等? 確定影響決策目標的決策變量 x，形成目標函數(shù) C=f(x)? 明確決策變量的取值范圍，形成約束函數(shù)? 設計求解算法，尋找決策目標在決策變量所受限制的范圍內(nèi)的極小化或極大化。? 最優(yōu)化問題的一般形式為：決策理論與方法 優(yōu)化決策理論與方法優(yōu)化問題分類v 可行點 與 可行域 ：滿足約束條件的 x稱為可行點，所有可行點的集合稱為可行域，記為 S；v 約束優(yōu)化 與 無約束優(yōu)化 ：當 S?Rn時，稱為約束優(yōu)化；當 S=Rn時，稱為無約束優(yōu)化；v 多目標優(yōu)化 ：若 f是多個目標函數(shù)構成的一個向量值函數(shù)，則稱為多目標規(guī)劃；v 線性規(guī)劃 與 非線性規(guī)劃 ：當 f,g,h均為線性函數(shù)時稱為線性規(guī)劃，否則稱為非線性規(guī)劃。決策理論與方法 優(yōu)化決策理論與方法優(yōu)化問題分類v 整數(shù)規(guī)劃 ：當決策變量的取值均為整數(shù)時稱為整數(shù)規(guī)劃；若某些變量取值為整數(shù)，而另一些變量取值為實數(shù)，則成為混合整數(shù)規(guī)劃。v 動態(tài)規(guī)劃 與 多層規(guī)劃 ：若決策是分成多個階段完成的，前后階段之間相互影響，則稱為動態(tài)規(guī)劃；若決策是分成多個層次完成的，不同層次之間相互影響，則稱為多層規(guī)劃。決策理論與方法 優(yōu)化決策理論與方法優(yōu)化決策理論與方法線性規(guī)劃非線性規(guī)劃（約束和非約束）多目標規(guī)劃組合優(yōu)化與整數(shù)規(guī)劃決策理論與方法 優(yōu)化決策理論與方法線性規(guī)劃 — 管理實例v (食譜問題 )假設市場上有 n種不同的食物，第 j種食物的單價為 cj。人體正?；顒舆^程中需要 m種基本的營養(yǎng)成分，且每人每天至少需要攝入第 i種營養(yǎng)成分 bi個單位。已知第 j種食物中包含第 i種營養(yǎng)成分的量為 aij個單位。問在滿足人體基本營養(yǎng)需求的前提下什么樣的配食方案最經(jīng)濟？v 設食譜中包含第 j種食物的量為 xj，則：決策理論與方法 優(yōu)化決策理論與方法線性規(guī)劃 — 標準型決策理論與方法 優(yōu)化決策理論與方法線性規(guī)劃 — 單純形算法v 解空間分析? 可行域分析 ： n維空間；第一象限； m個超平面。? 最優(yōu)解分析 ：在端點 (或稱為極點。極點向量中，至少有 nm個 0分量 )處取極值。v 單純形算法的基本思想? 從某個極點開始獲得一個可行解；? 判斷該可行解是不是目標解。若是，算法結束；否則尋找下一個極點（確定 入基變量 和 出基變量 ），直至找到目標解。決策理論與方法 優(yōu)化決策理論與方法線性規(guī)劃 — 內(nèi)點算法v1972年， V. Klee和 G. L. Minty指出 Dantzig的單純形算法的迭代次數(shù)為 O(2n)，是一個指數(shù)時間算法，不是優(yōu)良算法。那么是否存在求解線性規(guī)劃問題的多項式時間算法？v1984年， N. Karmarkar提出了一種 投影尺度算法 ，其計算效果能夠同單純形法相比較，掀起了線性規(guī)劃 內(nèi)點算法 的熱潮。決策理論與方法 優(yōu)化決策理論與方法線性規(guī)劃 — 內(nèi)點算法v 內(nèi)點算法的思想? 已知線性規(guī)劃問題的可行域是一個多面體，最優(yōu)點在多面體的某個極點取到。在給定初始可行解后，沿著什么樣的路徑到達最優(yōu)解呢？? 單純形法是從某個基可行解開始，沿著多面體的邊移動最終找到最優(yōu)解。? 內(nèi)點算法的思想是從可行域內(nèi)的任意一點 (任一可行解 )出發(fā)，穿越可行域的內(nèi)部達到最優(yōu)解。 N. Karmarkar的 投影尺度算法 就是一種典型的內(nèi)點算法。決策理論與方法 優(yōu)化決策理論與方法線性規(guī)劃 — 內(nèi)點算法可行域內(nèi)點初始基可行解基可行解目標函數(shù)目標函數(shù)最速下降方向決策理論與方法 優(yōu)化決策理論與方法線性規(guī)劃 — 內(nèi)點算法v 投影尺度算法? 如何穿過可行域的內(nèi)部快速達到最優(yōu)解呢？ Karmarkar發(fā)現(xiàn)： (1)如果一個內(nèi)點位于可行域 (多胞形、多面體 )的中心，那么目標函數(shù)的最速下降方向是比較好的方向；(2)存在一個適當?shù)淖儞Q，能夠將可行域中給定的內(nèi)點置于變換后的可行域的中心。基于這兩點， Karmarkar構造了一種稱為 投影尺度算法 的內(nèi)點算法。決策理論與方法 優(yōu)化決策理論與方法線性規(guī)劃 — 內(nèi)點算法X空間內(nèi)點目標函數(shù)目標函數(shù)最速下降方向Y1空間中心點投影尺度變換 1目標函數(shù)最速下降方向Y2空間中心點投影尺度變換2決策理論與方法 優(yōu)化決策理論與方法線性規(guī)劃 — Matlab函數(shù)應用v Optimization ToolBoxMin fTx. Ax≤bAeqx=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函數(shù)應用v 例： max z=x1+2x2. ? x1+x2≤40? 2x1+x2≤60? x1≥0。 x2≥0解 ：將 max變?yōu)?min， min –z=x12x2則： f=[1。2]。 b=[40。60]。 lb=zeros(2,1)。 A=[1 1。2 1] [x, fval] = linprog(f,A,b,[],[],lb) x=[0。40], fval= 80x1x2x1+x2=402x1+x2=60Z=x1+2x2決策理論與方法 優(yōu)化決策理論與方法優(yōu)化決策理論與方法線性規(guī)劃非線性規(guī)劃（約束和非約束）多目標規(guī)劃組合優(yōu)化與整數(shù)規(guī)劃決策理論與方法 優(yōu)化決策理論與方法無約束非線性規(guī)劃 — 標準型v Min f(x)。 x?Rnv 其中 f： Rn→R 是一個非線性連續(xù)函數(shù)。對于任意點x*?Rn, 它是函數(shù) f的最小點 (或局部極小點 )嗎？v 例如： min f(x)=ex1(4x12+2x22+4x1x2+2x2+1)決策理論與方法 優(yōu)化決策理論與方法無約束非線性規(guī)劃 — 復習v 梯度向量 vHesse矩陣vTaylor展開決策理論與方法 優(yōu)化決策理論與方法無約束非線性規(guī)劃 — 極小值存在條件v 必要條件 。設 x*是 f(x)的局部極小點，則? 當 f(x)在 x*點可微時，梯度 ?f(x*)=0；? 當 f(x)在 x*點二階可微時， Hesse矩陣 ▽ 2f(x*)是半正定 的，即 ??d?Rn，有 dT?2f(x*)d?0。v 充分條件 。 設 f(x)在 x*點二階可微，若梯度 ?f(x*)=0且 Hesse矩陣 ?2f(x*)是正定 的，則 x*是 f(x)的一個嚴格局部極小點。v 充要條件 。設 f(x)是可微凸函數(shù)，則 x*是 f(x)的全局最小點，當且僅當梯度 ?f(x*)=0。決策理論與方法 優(yōu)化決策理論與方法無約束非線性規(guī)劃 — 牛頓法v 基本思想 ：在一個點附近，用目標函數(shù) f(x)的二階Taylor多項式近似 f(x)，并用該 Taylor多項式的最小點近似 f(x)的最小點。如果近似誤差比較大，那么可在近似最小點附近重新構造 f(x)的二階 Taylor多項式(迭代 )，據(jù)此尋找新的近似最小點，重復以上過程直到求得滿足一定精度要求的迭代點。決策理論與方法 優(yōu)化決策理論與方法無約束非線性規(guī)劃 — 牛頓法v 設 xk是第 k次迭代結果，記 gk=g(xk)=?f(xk)；Gk=G(xk)=?2f(xk)。則f(x)=f(xk+p)≈f(xk)+g(xk)Tp+1/2pTG(xk)p=?k(p)v 由于 ?k(p)的最小點滿足 g(xk)+G(xk)p=0，得p=xxk=G1(xk)g(xk)v 因此，可近似得到迭代關系：xk+1=xkG1(xk)g(xk)決策理論與方法 優(yōu)化決策理論與方法無約束非線性規(guī)劃 — 牛頓法v 牛頓迭代法步驟? 初始化 ：給定一個初始點 x0以及參數(shù) e0；記 k=0。? 收斂性檢驗 ：計算 g(xk)，若 ||g(xk)||≤e，則算法終止；否則計算 G(xk)。? 迭代改進 ：計算新的迭代點 xk+1，即 xk+1=xkG1(xk)g(xk)。k+1