【正文】 法 多目標(biāo)規(guī)劃 — 求解方法 1. min f1(x)， x?S（不妨設(shè) f1(x)為第一層目標(biāo)），得到最優(yōu)解集 S1。 2. 第 j層： min fj(x),x?Sj1， j=2,…, p 3. 最后將 Sp中的點(diǎn)作為多目標(biāo)問(wèn)題的最優(yōu)解。 2021年 6月 15日 1時(shí) 47分 決策理論與方法 優(yōu)化決策理論與方法 多目標(biāo)規(guī)劃 — Matlab函數(shù)應(yīng)用 ? Optimization ToolBox Min max {fi(x)} . c(x)?0 ceq(x)=0 Ax?b Aeqx=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)。 2021年 6月 15日 1時(shí) 47分 決策理論與方法 優(yōu)化決策理論與方法 多目標(biāo)規(guī)劃 — Matlab函數(shù)應(yīng)用 ? 用法 ? 創(chuàng)建一個(gè) matlab文件，如 function f = myfun(x) f(1) = f1(x)。f(2)=f2(x)?！(p)=f p(x) ? 創(chuàng)建另一個(gè) matlab文件，如 function [c, ceq] = confun(x) c = c(x)。 ceq = 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) 2021年 6月 15日 1時(shí) 47分 決策理論與方法 優(yōu)化決策理論與方法 多目標(biāo)規(guī)劃 — Matlab函數(shù)應(yīng)用 ? Optimization ToolBox Minx,? ? . F(x)weight??goal c(x)?0 ceq(x)=0 Ax?b Aeqx=beq lb?x?ub ? [x,fval]=fgoalattain(fun,x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon) ? Fun定義目標(biāo)函數(shù)； goal為理想點(diǎn)； x0定義初始可行解；nonlcon定義 c(x)和 ceq(x)。 weight為各目標(biāo)的權(quán)重向量。 2021年 6月 15日 1時(shí) 47分 決策理論與方法 優(yōu)化決策理論與方法 多目標(biāo)規(guī)劃 — Matlab函數(shù)應(yīng)用 ? 用法 ? 創(chuàng)建一個(gè) matlab文件，如 function f = myfun(x) f(1) = f1(x)。f(2)=f2(x)?！?。f(p)=f p(x) ? 創(chuàng)建另一個(gè) 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) 2021年 6月 15日 1時(shí) 47分 決策理論與方法 優(yōu)化決策理論與方法 多目標(biāo)規(guī)劃 — Matlab函數(shù)應(yīng)用 ?例： 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。 ? 無(wú)約束。 2021年 6月 15日 1時(shí) 47分 決策理論與方法 優(yōu)化決策理論與方法 多目標(biāo)規(guī)劃 — Matlab函數(shù)應(yīng)用 ?解 (1)：用 fminimax求解。 ? 定義 ? 指定初始搜索點(diǎn)： x0=[。 ] ? 調(diào)用 [x,fval]=fminimax(@myfun,x0) ? 結(jié)果： x =[ ] fval = [ ] iterations: 7 algorithm: 39。minimax SQP, QuasiNewton, line_search‘ 2021年 6月 15日 1時(shí) 47分 決策理論與方法 優(yōu)化決策理論與方法 多目標(biāo)規(guī)劃 — Matlab函數(shù)應(yīng)用 ? 解 (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: 7 algorithm: 39。goal attainment SQP, QuasiNewton, line_search39。 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)化決策理論與方法 組合優(yōu)化 — 基本概念 ? 組合優(yōu)化問(wèn)題 是指從一個(gè)有限的可行解集中尋找使某個(gè)性能函數(shù)取極值的最優(yōu)解。 ? 給定一個(gè)有限集 N={1,2,…,n} 和權(quán)函數(shù) c:N→R 。記 N的某些子集的集合為 F，則組合優(yōu)化問(wèn)題就是從 F中找到一個(gè)具有最小權(quán)重的子集。 ? 已經(jīng)證明：求解組合優(yōu)化問(wèn)題的最優(yōu)解是 NP難的。設(shè)計(jì)各類 貪婪算法 是求解組合優(yōu)化問(wèn)題常用的思路。 ???SjjFS cm i n2021年 6月 15日 1時(shí) 47分 決策理論與方法 優(yōu)化決策理論與方法 組合優(yōu)化 — 基本概念 ?常見(jiàn)的組合優(yōu)化問(wèn)題： ? 最短路問(wèn)題 ：給定一定的路長(zhǎng)分布，確定從某個(gè)地點(diǎn)到另一個(gè)地點(diǎn)使路長(zhǎng)最短的路徑。 (TSP問(wèn)題 ) ? 最大流問(wèn)題 ：在一個(gè)有容量限制的網(wǎng)絡(luò)中，如何使得從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的流量達(dá)到最大？ ? 裝箱問(wèn)題 ：如何將一定規(guī)格的物品裝到箱子中，使得占用箱子的個(gè)數(shù)最少？ ? 背包問(wèn)題 ：如何挑選一些價(jià)值不同、尺寸有別的物品放到一個(gè)有限大的背包中，使得背包內(nèi)的物品價(jià)值總量最大？ 2021年 6月 15日 1時(shí) 47分 決策理論與方法 優(yōu)化決策理論與方法 組合優(yōu)化 — 最短路問(wèn)題 ? 給定一個(gè)網(wǎng)絡(luò) N=(V, E, w)，其中 w為權(quán)函數(shù)，最短路問(wèn)題是指對(duì)于兩個(gè)不同的頂點(diǎn) s,t?V，尋找一條從 s到 t的路，使得路上所有弧的權(quán)和最小 (權(quán)可看作弧長(zhǎng) )。 ? 關(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。則最短路徑問(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。試確定從 s到 t點(diǎn)的最短路徑。 ? 解 ： 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)過(guò)第 5條邊到達(dá) t點(diǎn)最短。 s t a b e1 e2 e3 e5 e4 2021年 6月 15日 1時(shí) 47分 決策理論與方法 優(yōu)化決策理論與方法 整數(shù)規(guī)劃 — 標(biāo)準(zhǔn)型 ?整數(shù)規(guī)劃是一類特殊的組合優(yōu)化問(wèn)題。線性 (混合 )整數(shù)規(guī)劃問(wèn)題 是指在等式或不等式的線性約束下，極大化 (或極小化 )某個(gè)線性函數(shù)，其中要求某些變量必須取整數(shù)。 ?線性混合整數(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為 m n階矩陣，G為 m p階矩陣。 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ū)別。 ?整數(shù)規(guī)劃問(wèn)題的可行解一定是松弛問(wèn)題的可行解，但反之不一定。所以整數(shù)規(guī)劃問(wèn)題的最優(yōu)解不會(huì)優(yōu)于其松弛問(wèn)題的最優(yōu)解。 ?求解方法： Gomory割平面法、分支定界法、分解算法。 2021年 6月 15日 1時(shí) 47分 決策理論與方法 優(yōu)化決策理論與方法 整數(shù)規(guī)劃 — Matlab函數(shù)應(yīng)用 ? Optimization ToolBox Min f’x . Ax?b Aeqx=beq x： 01 ? [x,fval] =bintprog(f, A, b, Aeq, beq, x0) ? x0定義初始可行解 (可選 )； bintprog僅適合求解 01整數(shù)規(guī)劃問(wèn)題。