【正文】 x=beq x： 01 ? [x,fval] =bintprog(f, A, b, Aeq, beq, x0) ? x0定義初始可行解 (可選 )； bintprog僅適合求解 01整數(shù)規(guī)劃問題。x . A ?求解方法： Gomory割平面法、分支定界法、分解算法。 ?整數(shù)規(guī)劃問題的可行解一定是松弛問題的可行解，但反之不一定。 ?線性混合整數(shù)規(guī)劃 (MILP)： max {cTx+hTy|Ax+Gy?b, x?Z+n, y?R+p} ? x,y為決策變量向量，其中 x包含 n個整數(shù)變量， y包含 p個實數(shù)變量； c為 n維向量； h為 p維向量； A為 m n階矩陣，G為 m p階矩陣。 s t a b e1 e2 e3 e5 e4 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 整數(shù)規(guī)劃 — 標準型 ?整數(shù)規(guī)劃是一類特殊的組合優(yōu)化問題。aa=(1 0 1 1 0)T。試確定從 s到 t點的最短路徑。引入 01整型變量 xj(ej?E)，記x=(x1,x2,...,x|E|)T。 ? 關(guān)聯(lián)矩陣： A=(aij)|V| |E|。 ???SjjFS cm i n2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 組合優(yōu)化 — 基本概念 ?常見的組合優(yōu)化問題： ? 最短路問題 ：給定一定的路長分布，確定從某個地點到另一個地點使路長最短的路徑。 ? 已經(jīng)證明：求解組合優(yōu)化問題的最優(yōu)解是 NP難的。 ? 給定一個有限集 N={1,2,…,n} 和權(quán)函數(shù) c:N→R 。goal attainment SQP, QuasiNewton, line_search39。 ? 定義 ? 指定初始搜索點： x0=[。 ] ? 調(diào)用 [x,fval]=fminimax(myfun,x0) ? 結(jié)果： x =[ ] fval = [ ] iterations: 7 algorithm: 39。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 多目標規(guī)劃 — Matlab函數(shù)應(yīng)用 ?解 (1)：用 fminimax求解。 f(5)= x(1) + x(2) 8。 f(3)= x(1) + 3*x(2) 18。weight [x,fval]=fgoalattain(myfun,x0,goal,weight,A,b,Aeq,beq,lb,ub,confun) 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 多目標規(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。ub。beq。b。 x0=[x1,x2,…,xn]。 ceq = ceq(x)?！?。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 多目標規(guī)劃 — Matlab函數(shù)應(yīng)用 ? 用法 ? 創(chuàng)建一個 matlab文件，如 function f = myfun(x) f(1) = f1(x)。x=beq lb?x?ub ? [x,fval]=fgoalattain(fun,x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon) ? Fun定義目標函數(shù)； goal為理想點； x0定義初始可行解；nonlcon定義 c(x)和 ceq(x)。??goal c(x)?0 ceq(x)=0 Aub。beq。b。 x0=[x1,x2,…,xn]。 ceq = ceq(x)。…。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 多目標規(guī)劃 — Matlab函數(shù)應(yīng)用 ? 用法 ? 創(chuàng)建一個 matlab文件，如 function f = myfun(x) f(1) = f1(x)。x?b Aeq 2. 第 j層： min fj(x),x?Sj1， j=2,…, p 3. 最后將 Sp中的點作為多目標問題的最優(yōu)解。 ?分層排序法 ：將目標函數(shù)按重要度依次排序，然后在前一個目標函數(shù)的最優(yōu)解集中尋找下一個目標的最優(yōu)解集，并把最后一個目標的最優(yōu)解作為 MOP問題的最優(yōu)解。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 多目標規(guī)劃 — 求解方法 ?基于多個單目標問題的方法 ：將原來的多目標規(guī)劃問題轉(zhuǎn)化成具有一定次序的多個單目標優(yōu)化問題，然后依次求解這些單目標優(yōu)化問題，并把最后一個單目標優(yōu)化問題的解作為 MOP問題的最優(yōu)解。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 多目標規(guī)劃 — 求解方法 ?極小化極大法 ：在目標函數(shù) f(x)的 p個分量中，極小化 f(x)的最大分量，即 minx?Smax1?j?pfj(x) ?理想點法 ：分別求出 f(x)中每個分量 fj(x)的極小點 fj0，得到理想點 f0=(f10,…, fp0)T；然后求解單目標優(yōu)化問題： minx?S||f(x)f0||?。i?I hj(x)=0。j?? ? 權(quán)重設(shè)置 要求 ： ?k?k=1, ?k?0(k=1,2,…, p)。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 多目標規(guī)劃 — 求解方法 ?線性加權(quán)和法 ： Min ?Tf(x)=?k?kfk(x)， . gi(x)?0。 ?基于一個單目標問題的方法 ：將原來的多目標規(guī)劃問題轉(zhuǎn)化成一個單目標優(yōu)化問題，然后利用非線性優(yōu)化算法求解該單目標問題，所得解作為 MOP問題的最優(yōu)解。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 多目標規(guī)劃 — 求解方法 ?直接求解多目標規(guī)劃問題的有效解集是 NP難問題。有效解通常也稱為 Pareto最優(yōu)解。j??。其一般形式如下： Min f(x)=(f1(x),f2(x),…, fp(x))T， . gi(x)?0。 ),1?？傔\輸費用為 ?i?jcijxij； ?約束條件 ? 每個倉庫的運出量不超過倉庫的庫存量： ?jxij?ai； ? 運到每個銷售網(wǎng)點的量與其銷售能力相匹配： ?ixij=bj； ? 每個倉庫的運出量非負： xij?0。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 多目標規(guī)劃 — 管理實例 ?決策目標： ? 運輸速度最快，可用噸公里數(shù)（ 可觀測變量 ）最小描述。第 i個倉庫到第 j個銷售網(wǎng)點的距離為 dij，單位物資的運費為 cij。試建立描述物資調(diào)運過程的數(shù)學模型。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 優(yōu)化決策理論與方法 線性規(guī)劃 非線性規(guī)劃（約束和非約束） 多目標規(guī)劃 組合優(yōu)化與整數(shù)規(guī)劃 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 多目標規(guī)劃 — 管理實例 ? (物資調(diào)度 )假設(shè)物資調(diào)度部門計劃將某種物資從若干個存儲倉庫調(diào)運到若干個銷售網(wǎng)點銷售。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 二次規(guī)劃 — Matlab函數(shù)應(yīng)用 ? 調(diào)用二次規(guī)劃函數(shù) [x,fval]=quadprog(H,f,A,b,[],[],lb) ? 運行結(jié)果 ： x =[。ub=[]。Aeq=[]。 lb=[0。2。2 1]。 ? 表示其它矩陣或向量 A=[1 1。6], x=[x1。 [x,fval]=quadprog(H,f,A,b,Aeq,beq,lb,ub,x0) 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 二次規(guī)劃 — Matlab函數(shù)應(yīng)用 ? 例 ： min f(x)=1/2x12+x22x1x22x16x2) . x1+x2?2 x1+2x2?2 2x1+x2?3 x1, x2?0 ? 解 ： ? 改寫 f(x)=1/2(x12+2x22x1x2x1x2)2x16x2 得： H=[1 1。lb。Aeq。A。 ? 調(diào)用 quadprog并根據(jù)需要指定初始搜索點以及其他向量、矩陣。x?b Aeqmediumscale: SQP, QuasiNewton, linesearch39。)。,39。 % Starting guess options = optimset(39。 ceq = []。 ? 創(chuàng)建另一個 matlab文件，如 function [c, ceq] = confun(x) c = [ + x(1)*x(2) x(1) x(2)。ub。beq。b。 x0=[x1,x2,…,xn]。 ceq = ceq(x)。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 — Matlab函數(shù)應(yīng)用 ? 用法 ? 創(chuàng)建一個 matlab文件，如 function f = myfun(x) f = f(x)。x?b Aeq ? 設(shè) (xk,?k)是第 k次迭代結(jié)果，根據(jù)牛頓法，有： ???????? ????????????????????????????????????????????????????)()()(0)()(),()),(()),((121211kkkkTkkkkxxkkkkkkkkkkxhxhxfxhxhxLxxLxLxx???????2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 — SQP法 ? 上述迭代過程等價于如下的二次規(guī)劃的迭代。 ?基本思想 ：在迭代點處構(gòu)造一個二次規(guī)劃子問題，近似原來的約束優(yōu)化問題；然后通過求解該二次規(guī)劃子問題獲得約束優(yōu)化問題的一個改進迭代點；不斷重