【正文】 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 整數(shù)規(guī)劃 — Matlab函數(shù)應(yīng)用 ? Optimization ToolBox Min f’ 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條邊到達 t點最短。 (TSP問題 ) ? 最大流問題 ：在一個有容量限制的網(wǎng)絡(luò)中，如何使得從一個頂點到另一個頂點的流量達到最大？ ? 裝箱問題 ：如何將一定規(guī)格的物品裝到箱子中，使得占用箱子的個數(shù)最少？ ? 背包問題 ：如何挑選一些價值不同、尺寸有別的物品放到一個有限大的背包中，使得背包內(nèi)的物品價值總量最大？ 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 組合優(yōu)化 — 最短路問題 ? 給定一個網(wǎng)絡(luò) N=(V, E, w)，其中 w為權(quán)函數(shù)，最短路問題是指對于兩個不同的頂點 s,t?V，尋找一條從 s到 t的路，使得路上所有弧的權(quán)和最小 (權(quá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。 f(4)= x(1) x(2)。Aeq。f(2)=f2(x)。lb。f(p)=f p(x) ? 創(chuàng)建另一個 matlab文件，如 function [c, ceq] = confun(x) c = c(x)。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 多目標規(guī)劃 — 求解方法 1. min f1(x)， x?S（不妨設(shè) f1(x)為第一層目標），得到最優(yōu)解集 S1。 ?主要目標法： Min f(x)=f1(x)， (不妨設(shè) f1(x)為主要目標 ) . gi(x)?0。 S x1 x2 f(S) f(S) f2 f2 f1 f1 絕對最優(yōu)解 有效解 弱有效解 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 多目標規(guī)劃 — Pareto最優(yōu)解存在條件 ? (必要條件 )假設(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。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 多目標規(guī)劃 — 管理實例 ?最后得到模型： ?模型包含 2個目標； ? mn個決策變量； ? mn+m+n個約束?？紤]到物資的時效性和銷售效益，調(diào)度部門希望物資在運輸過程中盡可能快地到達目的地；同時，考慮到運輸成本，調(diào)度部門還希望物資的總運輸費用最小。0]。x2]。b。 [x,fval]=fmincon(objfun,x0,[],[],[],[],[],[],confun,options) ? 運行結(jié)果 ： x =[ ] fval = iterations: 8 algorithm: 39。 x(1)*x(2) 10]。A。設(shè)給定迭代點(xk,?k)，則 0)()(..,)(),(21m i n 2??????kTkTkkkxxTdxhdxhtsdxfdxLd ?2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 — Matlab函數(shù)應(yīng)用 ? Optimization ToolBox Min f(x) . c(x)?0 ceq(x)=0 A我們僅討論凸二次規(guī)劃問題，因為非凸二次規(guī)劃的 Q存在負特征根，求解很困難。這種轉(zhuǎn)換隱含著某種懲罰，即 x偏離約束條件越遠，受到的懲罰越大。 ?可行方向法的應(yīng)用條件 ：要求所有約束均為線性約束（稱為線性約束的優(yōu)化問題， LCO）。 ?*,?*分別為對應(yīng)于 g(x)和 h(x)的拉格朗日乘子向量，且 函數(shù) f(x), gi(x), hj(x)在 x*處二階可微，若 dT?xx2L(x*,?*,?*)d0,則 x*為 COP問題的一個嚴格局部極小點。 d為 x*的任意可行方向。（可用一階 Taylor公式分析）。 ??????jxhIixgtsxfjiRxn,0)(,0)(..)(m i n2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 — 幾個概念 ?積極 (active)約束 ：設(shè) x0是 COP問題的一個可行解，則它必須滿足所有約束條件。 [x,fval] = fminunc(myfun,x0,options)。 ? 然后調(diào)用 fminunc或 fminsearch并指定初始搜索點。返回收斂性檢驗。設(shè) f(x)是可微凸函數(shù)，則 x*是 f(x)的全局最小點，當且僅當梯度 ?f(x*)=0。2 1] [x, fval] = linprog(f,A,b,[],[],lb) x=[0。x=beq lb≤x≤ub ? 其中： f, x, b, beq, lb和 ub均為向量； A和 Aeq為矩陣。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 線性規(guī)劃 — 內(nèi)點算法 ?內(nèi)點算法的思想 ? 已知線性規(guī)劃問題的可行域是一個多面體，最優(yōu)點在多面體的某個極點取到。問在滿足人體基本營養(yǎng)需求的前提下什么樣的配食方案最經(jīng)濟？ ? 設(shè)食譜中包含第 j種食物的量為 xj，則： njxmibaxtscxjinjijjnjjj,2,10,2,1..m i n11??????????2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 線性規(guī)劃 — 標準型 ? ?為右端項。 ?特點 ：狀態(tài)是確定的；決策問題變?yōu)閮?yōu)化問題。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 優(yōu)化決策理論與方法 線性規(guī)劃 非線性規(guī)劃（約束和非約束） 多目標規(guī)劃 組合優(yōu)化與整數(shù)規(guī)劃 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 線性規(guī)劃 — 管理實例 ? (食譜問題 )假設(shè)市場上有 n種不同的食物，第 j種食物的單價為 cj。若是，算法結(jié)束；否則尋找下一個極點（確定 入基變量 和 出基變量 ），直至找到目標解?；谶@兩點， Karmarkar構(gòu)造了一種稱為 投影尺度算法 的內(nèi)點算法。60]。 ?充分條件 。 ? 收斂性檢驗 ：計算 g(xk)，若 ||g(xk)||≤e，則算法終止；否則計算 G(xk)。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 無約束非線性規(guī)劃 — Matlab函數(shù)應(yīng)用 ? Optimization ToolBox Min f(x) ? Matlab提供了兩個求解無約束非線性規(guī)劃的函數(shù) ? [x,fval] = fminunc(fun,x0) ? [x,fval] = fminsearch(fun,x0) ?用法相似，算法內(nèi)部的搜索策略不同。,39。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 — 標準型 ?其中 f(x)是目標函數(shù)， gi(x)和 hj(x)為約束函數(shù) (約束條件 )。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 — 幾個概念 ? 可行方向 。若 x0的某一方向 d既是可行方向又是下降方向則稱其為可行下降方向。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 — 極小值存在條件 ? 二階必要條件 ? 設(shè) x*是 COP問題的局部極小點且滿足 KKT條件。 ? 根據(jù)凸規(guī)劃充分條件知 x*為全局最小點。 Min dT?f(x0) . AI(x0)d?0, I(x0)={i|aiTx0=bi,i?I} A?d=0 ||d||∞?1 ?可以證明：當 x0取得 KKT點時當且僅當 dT?f(x0)的最優(yōu)值為零。即 S0={x|g(x)0}≠? ????Iii xgxfxP )(ln)(),( ??2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 — 序列無約束化法 ?例 ： min{f=x/2|x?1} ?解：構(gòu)造對數(shù)障礙函數(shù) P(x,?)=x/2?ln(x1) ? P’x=1/2?/(x1)=0，得 x?*=1+2?， P*=1/2+??ln2? ? 當 ?→ 0時得 x*=1， f*=1/2 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 二次規(guī)劃 — 標準型 ?若有約束非線性規(guī)劃的目標函數(shù)是決策變量 x的二次函數(shù)且所有約束均為線性約束，稱此類非線性規(guī)劃問題為二次規(guī)劃 (Quadratic Programming, QP)問題。 ?基本思想 ：在迭代點處構(gòu)造一個二次規(guī)劃子問題，近似原來的約束優(yōu)化問題；然后通過求解該二次規(guī)劃子問題獲得約束優(yōu)化問題的一個改進迭代點；不斷重復(fù)此過程，直到求出滿足一定要求的迭代點。 ceq = ceq(x)。ub。,39。 ? 調(diào)用 quadprog并根據(jù)需要指定初始搜索點以及其他向量、矩陣。 [x,fval]=quadprog(H,f,A,b,Aeq,beq,lb,ub,x0) 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 二次規(guī)劃 — Matlab函數(shù)應(yīng)用