第02講優化決策理論與方法-資料下載頁

　　

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