【正文】 ceq(x)。? 調(diào)用 fminimax并指定初始搜索點(diǎn)以及其他向量、矩陣。x0=[x1,x2,…,xn]。A。b。Aeq。beq。lb。ub。[x,fval]=fminimax(myfun,x0,A,b,Aeq,beq,lb,ub,confun)決策理論與方法 優(yōu)化決策理論與方法多目標(biāo)規(guī)劃 — Matlab函數(shù)應(yīng)用v Optimization ToolBoxMinx,? ?. F(x)weight??goal c(x)?0 ceq(x)=0 Ax?b Aeqx=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)。 weight為各目標(biāo)的權(quán)重向量。決策理論與方法 優(yōu)化決策理論與方法多目標(biāo)規(guī)劃 — Matlab函數(shù)應(yīng)用v 用法? 創(chuàng)建一個 matlab文件，如 function f = myfun(x)f(1) = f1(x)。f(2)=f2(x)?！?。f(p)=f p(x)? 創(chuàng)建另一個 matlab文件，如 function [c, ceq] = confun(x)c = c(x)。 ceq = ceq(x)。? 調(diào)用 fgoalattain并設(shè)定理想點(diǎn)、權(quán)重向量，指定初始搜索點(diǎn)以及其他向量、矩陣。x0=[x1,x2,…,xn]。A。b。Aeq。beq。lb。ub。goal。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。 f(2)= x(1)^2 3*x(2)^2。f(3)= x(1) + 3*x(2) 18。f(4)= x(1) x(2)。f(5)= x(1) + x(2) 8。? 無約束。決策理論與方法 優(yōu)化決策理論與方法多目標(biāo)規(guī)劃 — Matlab函數(shù)應(yīng)用v 解 (1)：用 fminimax求解。? 定義 ? 指定初始搜索點(diǎn)： x0=[。 ]? 調(diào)用 [x,fval]=fminimax(myfun,x0)? 結(jié)果：x =[ ]fval = [ ]iterations: 7algorithm: 39。minimax SQP, QuasiNewton, line_search‘決策理論與方法 優(yōu)化決策理論與方法多目標(biāo)規(guī)劃 — Matlab函數(shù)應(yīng)用v 解 (2)：用 fgoalattain求解。? 定義 ? 指定初始搜索點(diǎn)： x0=[。 ]? 指定理想點(diǎn)： goal=[1 60 5 10 1]? 指定權(quán)重： weight=abs(goal)? 調(diào)用 [x,fval]=fgoalattain(myfun,x0,goal,weight)? 結(jié)果：x =[ ]fval =[ ]iterations: 7algorithm: 39。goal attainment SQP, QuasiNewton, line_search39。決策理論與方法 優(yōu)化決策理論與方法優(yōu)化決策理論與方法線性規(guī)劃非線性規(guī)劃（約束和非約束）多目標(biāo)規(guī)劃組合優(yōu)化與整數(shù)規(guī)劃決策理論與方法 優(yōu)化決策理論與方法組合優(yōu)化 — 基本概念v 組合優(yōu)化問題 是指從一個有限的可行解集中尋找使某個性能函數(shù)取極值的最優(yōu)解。v 給定一個有限集 N={1,2,…,n} 和權(quán)函數(shù) c:N→R 。記N的某些子集的集合為 F，則組合優(yōu)化問題就是從 F中找到一個具有最小權(quán)重的子集。v 已經(jīng)證明：求解組合優(yōu)化問題的最優(yōu)解是 NP難的。設(shè)計各類 貪婪算法 是求解組合優(yōu)化問題常用的思路。決策理論與方法 優(yōu)化決策理論與方法組合優(yōu)化 — 基本概念v 常見的組合優(yōu)化問題：? 最短路問題 ：給定一定的路長分布，確定從某個地點(diǎn)到另一個地點(diǎn)使路長最短的路徑。 (TSP問題 )? 最大流問題 ：在一個有容量限制的網(wǎng)絡(luò)中，如何使得從一個頂點(diǎn)到另一個頂點(diǎn)的流量達(dá)到最大？? 裝箱問題 ：如何將一定規(guī)格的物品裝到箱子中，使得占用箱子的個數(shù)最少？? 背包問題 ：如何挑選一些價值不同、尺寸有別的物品放到一個有限大的背包中，使得背包內(nèi)的物品價值總量最大？決策理論與方法 優(yōu)化決策理論與方法組合優(yōu)化 — 最短路問題v 給定一個網(wǎng)絡(luò) N=(V, E, w)，其中 w為權(quán)函數(shù)，最短路問題是指對于兩個不同的頂點(diǎn) s,t?V，尋找一條從 s到 t的路，使得路上所有弧的權(quán)和最小 (權(quán)可看作弧長 )。v 關(guān)聯(lián)矩陣： A=(aij)|V||E|。 aij=1(vi為 ej的起點(diǎn) )； aij=1(vi為 ej的終點(diǎn) )； aij=0(其他情形 )。引入 01整型變量 xj(ej?E)，記x=(x1,x2,...,x|E|)T。則最短路徑問題可表示成如下的 01整數(shù)規(guī)劃問題：min wTx. asTx=1 atTx=1 aiTx=0, i≠s,t x?0決策理論與方法 優(yōu)化決策理論與方法組合優(yōu)化 — 最短路問題v 例 ：考慮如圖所示的網(wǎng)絡(luò)，定義權(quán)函數(shù) w=(1,2,2,3,1)T。試確定從 s到 t點(diǎn)的最短路徑。v 解 ： as=(1 1 0 0 0)T； at=(0 0 0 1 1)T。aa=(1 0 1 1 0)T。 ab=(0 1 1 0 1)T，得到以下規(guī)劃方程：min x1+2x2+2x3+3x4+x5. x1+x2=1 x4x5=1 x1+x3+x4=0 x2x3+x5=0 x1,x2,x3,x4,x5?0? 調(diào)用函數(shù) linprog(w,[],[],Aeq,beq,lb)得 x=[0 1 0 0 1]T? 表明從 s出發(fā)經(jīng)過第 5條邊到達(dá) t點(diǎn)最短。s tabe1e2e3e5e4決策理論與方法 優(yōu)化決策理論與方法整數(shù)規(guī)劃 — 標(biāo)準(zhǔn)型v 整數(shù)規(guī)劃是一類特殊的組合優(yōu)化問題。線性 (混合 )整數(shù)規(guī)劃問題 是指在等式或不等式的線性約束下，極大化 (或極小化 )某個線性函數(shù)，其中要求某些變量必須取整數(shù)。v 線性混合整數(shù)規(guī)劃 (MILP)：max {cTx+hTy|Ax+Gy?b, x?Z+n, y?R+p}? x,y為決策變量向量，其中 x包含 n個整數(shù)變量， y包含 p個實(shí)數(shù)變量； c為 n維向量； h為 p維向量； A為 mn階矩陣，G為 mp階矩陣。決策理論與方法 優(yōu)化決策理論與方法整數(shù)規(guī)劃 — 標(biāo)準(zhǔn)型v 整數(shù)規(guī)劃的可行域 ：S={(x,y)|Ax+Gy?b, x?Z+n, y?R+p}v 例： P={x?Z1R1|x1+x2?1/2, 3x1+4x2?3, x2?0}x1x2決策理論與方法 優(yōu)化決策理論與方法整數(shù)規(guī)劃 — 解的特點(diǎn)v 從整數(shù)規(guī)劃的可行域分析可知，整數(shù)規(guī)劃的解與其松弛問題 (整數(shù)規(guī)劃問題的所有變量取值不受整數(shù)限制時的線性規(guī)劃問題 )既有密切的聯(lián)系，又有本質(zhì)的區(qū)別。v 整數(shù)規(guī)劃問題的可行解一定是松弛問題的可行解，但反之不一定。所以整數(shù)規(guī)劃問題的最優(yōu)解不會優(yōu)于其松弛問題的最優(yōu)解。v 求解方法： Gomory割平面法、分支定界法、分解算法。決策理論與方法 優(yōu)化決策理論與方法整數(shù)規(guī)劃 — Matlab函數(shù)應(yīng)用v Optimization ToolBoxMin f’x. Ax?b Aeqx=beq x： 01v[x,fval] =bintprog(f, A, b, Aeq, beq, x0)vx0定義初始可行解 (可選 )； bintprog僅適合求解 01整數(shù)規(guī)劃問題。采用基于線性規(guī)劃的分支定界算法。決策理論與方法 優(yōu)化決策理論與方法整數(shù)規(guī)劃 — Matlab函數(shù)應(yīng)用v 用法 （最短路徑問題）? f=[1 2 2 3 1]T? A=[]。b=[]。? Aeq=[1 1 0 0 0。0 0 0 1 1。1 0 1 1 0。0 1 1 0 1]。? beq=[1 1 0 0]T? [x,fval] =bintprog(f, [], [], Aeq, beq)? x=[0 1 0 0 1]T。 fval=3決策理論與方法 優(yōu)化決策理論與方法演講完畢，謝謝觀看！