【正文】 matlab文件，如 function f = myfun(x) f =exp(x(1))*(4*x(1)^2+2*x(2)^2+4*x(1)*x(2)+2*x(2)+1)。 2021年 6月 15日 1時(shí) 47分 決策理論與方法 優(yōu)化決策理論與方法 無(wú)約束非線性規(guī)劃 — 準(zhǔn)牛頓法 ?牛頓法算法的優(yōu)點(diǎn)是收斂速度快 (利用了 Hesse矩陣 )。 2021年 6月 15日 1時(shí) 47分 決策理論與方法 優(yōu)化決策理論與方法 無(wú)約束非線性規(guī)劃 — 復(fù)習(xí) ? 梯度矩陣 ????????????????????????????nxfxfxfxf?21)(??????????????????????????????????????????????22221222222122122122122)(nnnnnxfxxfxxfxxfxfxxfxxfxxfxfxf??????? Hesse矩陣 ? Taylor展開(kāi) ),(||||))(()(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)。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)。 [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。在給定初始可行解后，沿著什么樣的路徑到達(dá)最優(yōu)解呢？ ? 單純形法是從某個(gè)基可行解開(kāi)始，沿著多面體的邊移動(dòng)最終找到最優(yōu)解。為技術(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è)超平面。 ?決策的已知變量 ： ? 決策變量及其取值范圍 ?解決問(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)的極小化或極大化。 ?動(dòng)態(tài)規(guī)劃 與 多層規(guī)劃 ：若決策是分成多個(gè)階段完成的，前后階段之間相互影響，則稱為動(dòng)態(tài)規(guī)劃；若決策是分成多個(gè)層次完成的，不同層次之間相互影響，則稱為多層規(guī)劃。 ?單純形算法的基本思想 ? 從某個(gè)極點(diǎn)開(kāi)始獲得一個(gè)可行解； ? 判斷該可行解是不是目標(biāo)解。 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)置于變換后的可行域的中心。 b=[40。設(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。則 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。具體內(nèi)容請(qǐng)參考相關(guān)書(shū)籍。LargeScale39。NelderMead simplex direct search39。記 J={j|gj(x0)=0?hj(x0)=0}，稱為積極約束指標(biāo)集。 ? 可行下降方向 。對(duì)于 x*?S，若 函數(shù) f(x), gi(x)在 x*處可微，且KKT條件成立，則 x*為 COP問(wèn)題的全局最小點(diǎn)。因此有 ?2=?3=0，所以x1=x2=?1/2，得 x1=x2=2， x*=[2,2]T為該問(wèn)題的唯一 KKT點(diǎn)。 2021年 6月 15日 1時(shí) 47分 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 — 可行方向法 ? Zoutendijk可行方向法：其核心思想是通過(guò)求解下列線性規(guī)劃問(wèn)題，在可行方向的某個(gè)范圍內(nèi)獲得目標(biāo)函數(shù)的最速下降方向。 ? 該方法的適用性： COP問(wèn)題僅包含不等式約束函數(shù)，且可行域存在內(nèi)點(diǎn)。 2021年 6月 15日 1時(shí) 47分 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 — SQP法 ?對(duì)于非線性約束優(yōu)化 (COP)問(wèn)題， ?若 x*是 COP問(wèn)題的一個(gè)局部最優(yōu)解，則它對(duì)應(yīng)一個(gè)純等式約束優(yōu)化問(wèn)題 ??????jxhIixgtsxfjiRx n,0)(,0)(..)(m i n????????jxhxgIixIxgtsxfjixIRx n,0)(}0)(|{)(,0)(..)(m i n***)( *2021年 6月 15日 1時(shí) 47分 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 — SQP法 ?因此如果事先知道積極約束指標(biāo)集，那么帶有不等式約束優(yōu)化問(wèn)題就可以轉(zhuǎn)化為純等式約束優(yōu)化問(wèn)題，并可用準(zhǔn)牛頓法求解，這就是逐次二次規(guī)劃(Sequential Quadratic Programming， SQP)法。 ? 創(chuàng)建另一個(gè) matlab文件，如 function [c, ceq] = confun(x) c = c(x)。lb。LargeScale39。x=beq lb?x?ub ? [x,fval] = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0) ? x0定義初始可行解 (可選 ) 2021年 6月 15日 1時(shí) 47分 決策理論與方法 優(yōu)化決策理論與方法 二次規(guī)劃 — Matlab函數(shù)應(yīng)用 ? 用法 ? 首先要將目標(biāo)函數(shù)轉(zhuǎn)換成二次規(guī)劃標(biāo)準(zhǔn)型，從而得到 H和f兩個(gè)矩陣。ub。 b=[2。不指派初始解。設(shè)從第 i個(gè)倉(cāng)庫(kù)運(yùn)到第 j個(gè)銷售網(wǎng)點(diǎn)的物資量為 xij。i?I hj(x)=0。 關(guān)鍵問(wèn)題在于 ：保證所構(gòu)造的單目標(biāo)問(wèn)題的最優(yōu)解是 MOP問(wèn)題的有效解或弱有效解。 ? ?為范數(shù)的階，可取 1， 2， ∞。x=beq lb?x?ub ? [x,fval] = fminimax(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon) ? Fun定義目標(biāo)函數(shù)； x0定義初始可行解； nonlcon定義 c(x)和 ceq(x)。A。x?b Aeq ? 調(diào)用 fgoalattain并設(shè)定理想點(diǎn)、權(quán)重向量，指定初始搜索點(diǎn)以及其他向量、矩陣。goal。 ? 定義 ? 指定初始搜索點(diǎn)： x0=[。記 N的某些子集的集合為 F，則組合優(yōu)化問(wèn)題就是從 F中找到一個(gè)具有最小權(quán)重的子集。則最短路徑問(wèn)題可表示成如下的 01整數(shù)規(guī)劃問(wèn)題： min wTx . asTx=1 atTx=1 aiTx=0, i≠s,t x?0 2021年 6月 15日 1時(shí) 47分 決策理論與方法 優(yōu)化決策理論與方法 組合優(yōu)化 — 最短路問(wèn)題 ? 例 ：考慮如圖所示的網(wǎng)絡(luò)，定義權(quán)函數(shù) w=(1,2,2,3,1)T。 2021年 6月 15日 1時(shí) 47分 決策理論與方法 優(yōu)化決策理論與方法 整數(shù)規(guī)劃 — 標(biāo)準(zhǔn)型 ?整數(shù)規(guī)劃的可行域 ： S={(x,y)|Ax+Gy?b, x?Z+n, y?R+p} ?例： P={x?Z1 R1|x1+x2?1/2, 3x1+4x2?3, x2?0} x1 x2 2021年 6月 15日 1時(shí) 47分 決策理論與方法 優(yōu)化決策理論與方法 整數(shù)規(guī)劃 — 解的特點(diǎn) ?從整數(shù)規(guī)劃的可行域分析可知，整數(shù)規(guī)劃的解與其松弛問(wèn)題 (整數(shù)規(guī)劃問(wèn)題的所有變量取值不受整數(shù)限制時(shí)的線性規(guī)劃問(wèn)題 )既有密切的聯(lián)系，又有本質(zhì)的區(qū)別。