【正文】 結(jié)果 ：x =[。決策理論與方法 優(yōu)化決策理論與方法優(yōu)化決策理論與方法線性規(guī)劃非線性規(guī)劃（約束和非約束）多目標(biāo)規(guī)劃組合優(yōu)化與整數(shù)規(guī)劃決策理論與方法 優(yōu)化決策理論與方法多目標(biāo)規(guī)劃 — 管理實例v (物資調(diào)度 )假設(shè)物資調(diào)度部門計劃將某種物資從若干個存儲倉庫調(diào)運(yùn)到若干個銷售網(wǎng)點銷售。試建立描述物資調(diào)運(yùn)過程的數(shù)學(xué)模型。第 i個倉庫到第 j個銷售網(wǎng)點的距離為 dij，單位物資的運(yùn)費(fèi)為 cij。決策理論與方法 優(yōu)化決策理論與方法多目標(biāo)規(guī)劃 — 管理實例v 決策目標(biāo)：? 運(yùn)輸速度最快，可用噸公里數(shù)（ 可觀測變量 ）最小描述?？傔\(yùn)輸費(fèi)用為 ?i?jcijxij；v 約束條件? 每個倉庫的運(yùn)出量不超過倉庫的庫存量： ?jxij?ai；? 運(yùn)到每個銷售網(wǎng)點的量與其銷售能力相匹配： ?ixij=bj；? 每個倉庫的運(yùn)出量非負(fù)： xij?0。決策理論與方法 優(yōu)化決策理論與方法多目標(biāo)規(guī)劃 — 標(biāo)準(zhǔn)型v 多目標(biāo)規(guī)劃 (multiObjective Programming,MOP)就是指在決策變量滿足給定約束的條件下研究多個可數(shù)值化的目標(biāo)函數(shù)同時極小化 (或極大化 )的問題。i?I hj(x)=0。決策理論與方法 優(yōu)化決策理論與方法多目標(biāo)規(guī)劃 — Pareto最優(yōu)解v 設(shè) x*是可行域 S上的一個點，對于 ?x?S，均有：fi(x*)?fi(x)(i=1,…, p)，稱 x*為 MOP問題的絕對最優(yōu)解；若不存在 x?S，使得 fi(x)?fi(x*)(或 fi(x)fi(x*)) (i=1,…, p)，則稱 x*為 MOP問題的有效解 (或弱有效解 )。Sx1x2f(S) f(S)f2f2f1 f1絕對最優(yōu)解有效解弱有效解決策理論與方法 優(yōu)化決策理論與方法多目標(biāo)規(guī)劃 — Pareto解的存在條件v (必要條件 )假設(shè)向量值函數(shù) f=[f1(x),…, fp(x)]T, g=[g1(x),…, g|I|(x)]T, h=[h1(x),…, h|?|(x)]T在 x*?S處可微，若 x*是 MOP問題的有效解或弱有效解，則存在向量 ??R+p， ??R+|I|， ??R+|?|，使得 (?,?,?)≠0，且?f(x*)?=?g(x*)?+?h(x*)??Tg(x*)=0。下面介紹多目標(biāo)規(guī)劃問題的間接解法，基本思路都是將多目標(biāo)規(guī)劃問題轉(zhuǎn)化為一個或多個單目標(biāo)優(yōu)化問題。 關(guān)鍵問題在于 ：保證所構(gòu)造的單目標(biāo)問題的最優(yōu)解是 MOP問題的有效解或弱有效解。i?I hj(x)=0。v 主要目標(biāo)法：Min f(x)=f1(x)， (不妨設(shè) f1(x)為主要目標(biāo) ). gi(x)?0。j?? fk(x)?uk, k=2,…, p? uk為專家經(jīng)驗值。? ?為范數(shù)的階，可取 1， 2， ∞。 關(guān)鍵問題在于 ：保證最后一個單目標(biāo)優(yōu)化問題的最優(yōu)解是 MOP問題的有效解或弱有效解。決策理論與方法 優(yōu)化決策理論與方法多目標(biāo)規(guī)劃 — 求解方法1. min f1(x)， x?S（不妨設(shè) f1(x)為第一層目標(biāo)），得到最優(yōu)解集 S1。決策理論與方法 優(yōu)化決策理論與方法多目標(biāo)規(guī)劃 — Matlab函數(shù)應(yīng)用v Optimization ToolBoxMin max {fi(x)}. c(x)?0 ceq(x)=0 Ax=beq lb?x?ubv [x,fval] = fminimax(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon)v Fun定義目標(biāo)函數(shù)； x0定義初始可行解； nonlcon定義 c(x)和 ceq(x)。f(2)=f2(x)。f(p)=f p(x)? 創(chuàng)建另一個 matlab文件，如 function [c, ceq] = confun(x)c = c(x)。? 調(diào)用 fminimax并指定初始搜索點以及其他向量、矩陣。A。Aeq。lb。[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)weightx?b Aeq weight為各目標(biāo)的權(quán)重向量。f(2)=f2(x)。f(p)=f p(x)? 創(chuàng)建另一個 matlab文件，如 function [c, ceq] = confun(x)c = c(x)。? 調(diào)用 fgoalattain并設(shè)定理想點、權(quán)重向量，指定初始搜索點以及其他向量、矩陣。A。Aeq。lb。goal。 f(2)= x(1)^2 3*x(2)^2。f(4)= x(1) x(2)。? 無約束。? 定義 ? 指定初始搜索點： x0=[。minimax SQP, QuasiNewton, line_search‘決策理論與方法 優(yōu)化決策理論與方法多目標(biāo)規(guī)劃 — Matlab函數(shù)應(yīng)用v 解 (2)：用 fgoalattain求解。 ]? 指定理想點： 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。決策理論與方法 優(yōu)化決策理論與方法優(yōu)化決策理論與方法線性規(guī)劃非線性規(guī)劃（約束和非約束）多目標(biāo)規(guī)劃組合優(yōu)化與整數(shù)規(guī)劃決策理論與方法 優(yōu)化決策理論與方法組合優(yōu)化 — 基本概念v 組合優(yōu)化問題 是指從一個有限的可行解集中尋找使某個性能函數(shù)取極值的最優(yōu)解。記N的某些子集的集合為 F，則組合優(yōu)化問題就是從 F中找到一個具有最小權(quán)重的子集。設(shè)計各類 貪婪算法 是求解組合優(yōu)化問題常用的思路。 (TSP問題 )? 最大流問題 ：在一個有容量限制的網(wǎng)絡(luò)中，如何使得從一個頂點到另一個頂點的流量達(dá)到最大？? 裝箱問題 ：如何將一定規(guī)格的物品裝到箱子中，使得占用箱子的個數(shù)最少？? 背包問題 ：如何挑選一些價值不同、尺寸有別的物品放到一個有限大的背包中，使得背包內(nèi)的物品價值總量最大？決策理論與方法 優(yōu)化決策理論與方法組合優(yōu)化 — 最短路問題v 給定一個網(wǎng)絡(luò) N=(V, E, w)，其中 w為權(quán)函數(shù)，最短路問題是指對于兩個不同的頂點 s,t?V，尋找一條從 s到 t的路，使得路上所有弧的權(quán)和最小 (權(quán)可看作弧長 )。 aij=1(vi為 ej的起點 )； aij=1(vi為 ej的終點 )； aij=0(其他情形 )。則最短路徑問題可表示成如下的 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。v 解 ： as=(1 1 0 0 0)T； at=(0 0 0 1 1)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點最短。線性 (混合 )整數(shù)規(guī)劃問題 是指在等式或不等式的線性約束下，極大化 (或極小化 )某個線性函數(shù)，其中要求某些變量必須取整數(shù)。決策理論與方法 優(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ī)劃 — 解的特點v 從整數(shù)規(guī)劃的可行域分析可知，整數(shù)規(guī)劃的解與其松弛問題 (整數(shù)規(guī)劃問題的所有變量取值不受整數(shù)限制時的線性規(guī)劃問題 )既有密切的聯(lián)系，又有本質(zhì)的區(qū)別。所以整數(shù)規(guī)劃問題的最優(yōu)解不會優(yōu)于其松弛問題的最優(yōu)解。決策理論與方法 優(yōu)化決策理論與方法整數(shù)規(guī)劃 — Matlab函數(shù)應(yīng)用v Optimization ToolBoxMin f’x?b Aeq采用基于線性規(guī)劃的分支定界算法。b=[]。0 0 0 1 1。0 1 1 0 1]。 fval=3決策理論與方法 優(yōu)化決策理論與方法演講完畢，謝謝觀看！