【正文】 0 0 0 1 1。決策理論與方法 優(yōu)化決策理論與方法整數(shù)規(guī)劃 — Matlab函數(shù)應(yīng)用v Optimization ToolBoxMin 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)過(guò)第 5條邊到達(dá) t點(diǎn)最短。 (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à)值總量最大？決策理論與方法 優(yōu)化決策理論與方法組合優(yōu)化 — 最短路問(wèn)題v 給定一個(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) )。 ]? 指定理想點(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: 7algorithm: 39。f(4)= x(1) x(2)。Aeq。f(2)=f2(x)。lb。f(p)=f p(x)? 創(chuàng)建另一個(gè) matlab文件，如 function [c, ceq] = confun(x)c = c(x)。決策理論與方法 優(yōu)化決策理論與方法多目標(biāo)規(guī)劃 — 求解方法1. min f1(x)， x?S（不妨設(shè) f1(x)為第一層目標(biāo)），得到最優(yōu)解集 S1。v 主要目標(biāo)法：Min f(x)=f1(x)， (不妨設(shè) f1(x)為主要目標(biāo) ). gi(x)?0。Sx1x2f(S) f(S)f2f2f1 f1絕對(duì)最優(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問(wèn)題的有效解或弱有效解，則存在向量 ??R+p， ??R+|I|， ??R+|?|，使得 (?,?,?)≠0，且?f(x*)?=?g(x*)?+?h(x*)??Tg(x*)=0?？傔\(yùn)輸費(fèi)用為 ?i?jcijxij；v 約束條件? 每個(gè)倉(cāng)庫(kù)的運(yùn)出量不超過(guò)倉(cāng)庫(kù)的庫(kù)存量： ?jxij?ai；? 運(yùn)到每個(gè)銷售網(wǎng)點(diǎn)的量與其銷售能力相匹配： ?ixij=bj；? 每個(gè)倉(cāng)庫(kù)的運(yùn)出量非負(fù)： xij?0。決策理論與方法 優(yōu)化決策理論與方法優(yōu)化決策理論與方法線性規(guī)劃非線性規(guī)劃（約束和非約束）多目標(biāo)規(guī)劃組合優(yōu)化與整數(shù)規(guī)劃決策理論與方法 優(yōu)化決策理論與方法多目標(biāo)規(guī)劃 — 管理實(shí)例v (物資調(diào)度 )假設(shè)物資調(diào)度部門計(jì)劃將某種物資從若干個(gè)存儲(chǔ)倉(cāng)庫(kù)調(diào)運(yùn)到若干個(gè)銷售網(wǎng)點(diǎn)銷售。 lb=[0。6], x=[x1。A。)。? 創(chuàng)建另一個(gè) matlab文件，如 function [c, ceq] = confun(x)c = [ + x(1)*x(2) x(1) x(2)。x0=[x1,x2,…,xn]。v 設(shè) (xk,?k)是第 k次迭代結(jié)果，根據(jù)牛頓法，有：決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — SQP法v 上述迭代過(guò)程等價(jià)于如下的二次規(guī)劃的迭代。若目標(biāo)函數(shù)的 Hesse矩陣 Q是半正定 (或正定 )的，則 QP問(wèn)題為 (嚴(yán)格 )凸二次規(guī)劃 (CQP)。v 基本思想： 將約束條件通過(guò)某種轉(zhuǎn)換與目標(biāo)函數(shù)合并形成一個(gè)無(wú)約束優(yōu)化問(wèn)題。下面介紹幾種約束優(yōu)化的求解方法：可行方向法、序列無(wú)約束化法和 SQP法。v 二階充分條件? 設(shè) x*是 COP問(wèn)題的 KKT點(diǎn)。x1x2決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — 極小值存在條件v 一階必要條件? 幾何特征 ：若 x*是 COP問(wèn)題的局部極小點(diǎn)且函數(shù) f(x), gi(x), hj(x)在 x*處可微，則 dT?f(x*)?0。顯然若 d滿足 dT?gi(x)?0， dT?hj(x)=0，則 d一定是可行方向。v 有約束非線性規(guī)劃問(wèn)題 (COP)是指 f(x),gi(x),hj(x)至少有一個(gè)是非線性的，且 I或 ??至少有一個(gè)為非空。)。決策理論與方法 優(yōu)化決策理論與方法無(wú)約束非線性規(guī)劃 — Matlab函數(shù)應(yīng)用v 用法? 創(chuàng)建一個(gè) matlab文件，如 function f = myfun(x)f = f(x)。k+1→ k。v 充要條件 。 A=[1 1。x≤bAeq那么是否存在求解線性規(guī)劃問(wèn)題的多項(xiàng)式時(shí)間算法？v1984年， N. Karmarkar提出了一種 投影尺度算法 ，其計(jì)算效果能夠同單純形法相比較，掀起了線性規(guī)劃 內(nèi)點(diǎn)算法 的熱潮。人體正常活動(dòng)過(guò)程中需要 m種基本的營(yíng)養(yǎng)成分，且每人每天至少需要攝入第 i種營(yíng)養(yǎng)成分 bi個(gè)單位。決策理論與方法 (2) —— 優(yōu)化決策理論與方法合肥工業(yè)大學(xué)管理學(xué)院Wednesday, April 07, 2023確定性決策v 確定性決策 ：指未來(lái)狀態(tài)是確定的（即只有一種狀態(tài)）一類決策問(wèn)題，每一個(gè)行動(dòng)方案對(duì)應(yīng)著一個(gè)確定的結(jié)果值，此時(shí)決策函數(shù)僅依賴于決策變量。已知第 j種食物中包含第 i種營(yíng)養(yǎng)成分的量為 aij個(gè)單位。決策理論與方法 優(yōu)化決策理論與方法線性規(guī)劃 — 內(nèi)點(diǎn)算法v 內(nèi)點(diǎn)算法的思想? 已知線性規(guī)劃問(wèn)題的可行域是一個(gè)多面體，最優(yōu)點(diǎn)在多面體的某個(gè)極點(diǎn)取到。x=beqlb≤x≤ub? 其中： f, x, b, beq, lb和 ub均為向量； A和 Aeq為矩陣。2 1] [x, fval] = linprog(f,A,b,[],[],lb) x=[0。設(shè) f(x)是可微凸函數(shù)，則 x*是 f(x)的全局最小點(diǎn)，當(dāng)且僅當(dāng)梯度 ?f(x*)=0。返回收斂性檢驗(yàn)。? 然后調(diào)用 fminunc或 fminsearch并指定初始搜索點(diǎn)。 [x,fval] = fminunc(myfun,x0,options)。決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — 幾個(gè)概念v 積極 (active)約束 ：設(shè) x0是 COP問(wèn)題的一個(gè)可行解，則它必須滿足所有約束條件。（可用一階 Taylor公式分析）。 d為 x*的任意可行方向。 ?*,?*分別為對(duì)應(yīng)于 g(x)和 h(x)的拉格朗日乘子向量，且 函數(shù) f(x), gi(x), hj(x)在 x*處二階可微，若 dT?xx2L(x*,?*,?*)d0,則 x*為 COP問(wèn)題的一個(gè)嚴(yán)格局部極小點(diǎn)。v 可行方向法的應(yīng)用條件 ：要求所有約束均為線性約束（稱為線性約束的優(yōu)化問(wèn)題， LCO）。這種轉(zhuǎn)換隱含著某種懲罰，即 x偏離約束條件越遠(yuǎn)，受到的懲罰越大。我們僅討論凸二次規(guī)劃問(wèn)題，因?yàn)榉峭苟我?guī)劃的 Q存在負(fù)特征根，求解很困難。設(shè)給定迭代點(diǎn)(xk,?k)，則決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — Matlab函數(shù)應(yīng)用v Optimization ToolBoxMin f(x). c(x)?0 ceq(x)=0 AA。 x(1)*x(2) 10]。[x,fval]=fmincon(objfun,x0,[],[],[],[],[],[],confun,options)? 運(yùn)行結(jié)果 ：x =[ ]fval =iterations: 8algorithm: 39。b。x2]。0]?？紤]到物資的時(shí)效性和銷售效益，調(diào)度部門希望物資在運(yùn)輸過(guò)程中盡可能快地到達(dá)目的地；同時(shí)，考慮到運(yùn)輸成本，調(diào)度部門還希望物資的總運(yùn)輸費(fèi)用最小。決策理論與方法 優(yōu)化決策理論與方法多目標(biāo)規(guī)劃 — 管理實(shí)例v 最后得到模型：v 模型包含 2個(gè)目標(biāo)；vmn個(gè)決策變量；vmn+m+n個(gè)約束。決策理論與方法 優(yōu)化決策理論與方法多目標(biāo)規(guī)劃 — 求解方法v 直接求解多目標(biāo)規(guī)劃問(wèn)題的有效解集是 NP難問(wèn)題。i?I hj(x)=0。2. 第 j層： min fj(x),x?Sj1， j=2,…, p3. 最后將 Sp中的點(diǎn)作為多目標(biāo)問(wèn)題的最優(yōu)解