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