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