【正文】 ? 明確決策變量的取值范圍，形成約束函數(shù)? 設(shè)計(jì)求解算法，尋找決策目標(biāo)在決策變量所受限制的范圍內(nèi)的極小化或極大化。? 最優(yōu)解分析 ：在端點(diǎn) (或稱為極點(diǎn)。? 內(nèi)點(diǎn)算法的思想是從可行域內(nèi)的任意一點(diǎn) (任一可行解 )出發(fā)，穿越可行域的內(nèi)部達(dá)到最優(yōu)解。 x2≥0解 ：將 max變?yōu)?min， min –z=x12x2則： f=[1。 x?Rnv 其中 f： Rn→R 是一個(gè)非線性連續(xù)函數(shù)。如果近似誤差比較大，那么可在近似最小點(diǎn)附近重新構(gòu)造 f(x)的二階 Taylor多項(xiàng)式(迭代 )，據(jù)此尋找新的近似最小點(diǎn)，重復(fù)以上過(guò)程直到求得滿足一定精度要求的迭代點(diǎn)。但使用 Hesse矩陣的不足之處是計(jì)算量大，Hesse矩陣可能非正定等，準(zhǔn)牛頓法 (QuasiNewton method)是對(duì)牛頓法的改進(jìn)，目前被公認(rèn)為是比較有效的無(wú)約束優(yōu)化方法。? 調(diào)用無(wú)約束非線性規(guī)劃函數(shù) x0 = [1,1]。決策理論與方法 優(yōu)化決策理論與方法無(wú)約束非線性規(guī)劃 — Matlab函數(shù)應(yīng)用v fminunc結(jié)果：? x =[ ]? fval = ? iterations: 8? algorithm: 39。稱等號(hào)成立的約束為積極約束 (有效約束 )，此時(shí)， x0處于該約束條件形成的可行域邊界上；稱大于號(hào)成立的約束為非積極(inactive)約束 (無(wú)效約束 )，此時(shí)， x0不在該約束條件形成的可行域邊界上。 設(shè) x0?S，對(duì)某一方向 d來(lái)說(shuō)，若 ???00使得對(duì)于任意 ??[0,?0]，均有 f(x0+?d)f(x0)，則稱 d為 x0點(diǎn)的一個(gè)下降方向。決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — 極小值存在條件v 一階充分條件? 設(shè) x*?S，若 函數(shù) f(x), gi(x), hj(x)在 x*處可微，且對(duì)于 x*的任意可行方向 d，有 dT?f(x*)0，則 x*為 COP問題的一個(gè)嚴(yán)格局部極小點(diǎn)。g2(x)=x1?0。決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — 可行方向法x1x2決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — 可行方向法v LCO問題： Min f(x) . aiTx?bi, i?I ajTx=bj, j??v 設(shè) x0是 LCO的一個(gè)可行解，若 d是可行域在 x0點(diǎn)的 可行方向 ，則 d滿足 AI(x0)d?0(I(x0)={i|aiTx0=bi,i?I})，A?d=0。決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — 序列無(wú)約束化法v 二次罰函數(shù)法 ：? 罰函數(shù)：? 其中 (gi)=max{0,gi}， ?稱為罰參數(shù)，且當(dāng) ?→0 時(shí)， Q(x,?)的極小值趨于 f(x)的極小值。? 對(duì)于凸二次規(guī)劃， x*為全局極小點(diǎn)當(dāng)且僅當(dāng) x*為局部極小點(diǎn)，當(dāng)且僅當(dāng) x*為 KKT點(diǎn)。x=beq lb?x?ubv [x,fval] = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon)v fun定義目標(biāo)函數(shù) ,x0定義初始可行解， nonlcon定義 c(x)和ceq(x)。Aeq。決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — Matlab函數(shù)應(yīng)用? 調(diào)用有約束非線性規(guī)劃函數(shù)x0 = [1,1]。決策理論與方法 優(yōu)化決策理論與方法二次規(guī)劃 — Matlab函數(shù)應(yīng)用v Optimization ToolBoxMin +fTx. Abeq。1 2。beq=[]。v 解 ：設(shè)共有 m個(gè)倉(cāng)庫(kù)，第 i個(gè)倉(cāng)庫(kù)的物資庫(kù)存量為 ai噸；有 n個(gè)銷售網(wǎng)點(diǎn)，第 j個(gè)銷售網(wǎng)點(diǎn)的銷售量為 bj噸。其一般形式如下：Min f(x)=(f1(x),f2(x),…, fp(x))T，. gi(x)?0。v 基于一個(gè)單目標(biāo)問題的方法 ：將原來(lái)的多目標(biāo)規(guī)劃問題轉(zhuǎn)化成一個(gè)單目標(biāo)優(yōu)化問題，然后利用非線性優(yōu)化算法求解該單目標(biāo)問題，所得解作為 MOP問題的最優(yōu)解。決策理論與方法 優(yōu)化決策理論與方法多目標(biāo)規(guī)劃 — 求解方法v 極小化極大法： 在目標(biāo)函數(shù) f(x)的 p個(gè)分量中，極小化 f(x)的最大分量，即minx?Smax1?j?pfj(x)v 理想點(diǎn)法： 分別求出 f(x)中每個(gè)分量 fj(x)的極小點(diǎn) fj0，得到理想點(diǎn) f0=(f10,…, fp0)T；然后求解單目標(biāo)優(yōu)化問題：minx?S||f(x)f0||?。x?b Aeqx0=[x1,x2,…,xn]。??goal c(x)?0 ceq(x)=0 A ceq = ceq(x)。ub。決策理論與方法 優(yōu)化決策理論與方法多目標(biāo)規(guī)劃 — Matlab函數(shù)應(yīng)用v 解 (1)：用 fminimax求解。v 給定一個(gè)有限集 N={1,2,…,n} 和權(quán)函數(shù) c:N→R 。引入 01整型變量 xj(ej?E)，記x=(x1,x2,...,x|E|)T。v 線性混合整數(shù)規(guī)劃 (MILP)：max {cTx+hTy|Ax+Gy?b, x?Z+n, y?R+p}? x,y為決策變量向量，其中 x包含 n個(gè)整數(shù)變量， y包含 p個(gè)實(shí)數(shù)變量； c為 n維向量； h為 p維向量； A為 mn階矩陣，G為 mp階矩陣。x=beq x： 01v[x,fval] =bintprog(f, A, b, Aeq, beq, x0)vx0定義初始可行解 (可選 )； bintprog僅適合求解 01整數(shù)規(guī)劃問題。? beq=[1 1 0 0]T? [x,fval] =bintprog(f, [], [], Aeq, beq)? x=[0 1 0 0 1]T。決策理論與方法 優(yōu)化決策理論與方法整數(shù)規(guī)劃 — Matlab函數(shù)應(yīng)用v 用法 （最短路徑問題）? f=[1 2 2 3 1]T? A=[]。v 整數(shù)規(guī)劃問題的可行解一定是松弛問題的可行解，但反之不一定。試確定從 s到 t點(diǎn)的最短路徑。v 已經(jīng)證明：求解組合優(yōu)化問題的最優(yōu)解是 NP難的。 ]? 調(diào)用 [x,fval]=fminimax(myfun,x0)? 結(jié)果：x =[ ]fval = [ ]iterations: 7algorithm: 39。weight[x,fval]=fgoalattain(myfun,x0,goal,weight,A,b,Aeq,beq,lb,ub,confun)決策理論與方法 優(yōu)化決策理論與方法多目標(biāo)規(guī)劃 — Matlab函數(shù)應(yīng)用v 例： min {f1,f2,f3,f4,f5}f(1)= 2*x(1)^2+x(2)^248*x(1)40*x(2)+304。x0=[x1,x2,…,xn]。x=beq lb?x?ubv [x,fval]=fgoalattain(fun,x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon)v Fun定義目標(biāo)函數(shù)； goal為理想點(diǎn)； x0定義初始可行解；nonlcon定義 c(x)和 ceq(x)。b。決策理論與方法 優(yōu)化決策理論與方法多目標(biāo)規(guī)劃 — Matlab函數(shù)應(yīng)用v 用法? 創(chuàng)建一個(gè) matlab文件，如 function f = myfun(x)f(1) = f1(x)。決策理論與方法 優(yōu)化決策理論與方法多目標(biāo)規(guī)劃 — 求解方法v 基于多個(gè)單目標(biāo)問題的方法 ：將原來(lái)的多目標(biāo)規(guī)劃問題轉(zhuǎn)化成具有一定次序的多個(gè)單目標(biāo)優(yōu)化問題，然后依次求解這些單目標(biāo)優(yōu)化問題，并把最后一個(gè)單目標(biāo)優(yōu)化問題的解作為 MOP問題的最優(yōu)解。決策理論與方法 優(yōu)化決策理論與方法多目標(biāo)規(guī)劃 — 求解方法v 線性加權(quán)和法 ：Min ?Tf(x)=?k?kfk(x)，. gi(x)?0。j??。設(shè)從第 i個(gè)倉(cāng)庫(kù)運(yùn)到第 j個(gè)銷售網(wǎng)點(diǎn)的物資量為 xij。不指派初始解。 b=[2。ub。x=beq lb?x?ubv[x,fval] = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0)vx0定義初始可行解 (可選 )決策理論與方法 優(yōu)化決策理論與方法二次規(guī)劃 — Matlab函數(shù)應(yīng)用v 用法? 首先要將目標(biāo)函數(shù)轉(zhuǎn)換成二次規(guī)劃標(biāo)準(zhǔn)型，從而得到 H和f兩個(gè)矩陣。LargeScale39。lb。? 創(chuàng)建另一個(gè) matlab文件，如 function [c, ceq] = confun(x)c = c(x)。決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — SQP法v 對(duì)于非線性約束優(yōu)化 (COP)問題，v 若 x*是 COP問題的一個(gè)局部最優(yōu)解，則它對(duì)應(yīng)一個(gè)純等式約束優(yōu)化問題決策理論與方法 優(yōu)化決策理論與方法約