【正文】 0 1 1 0 1]。b=[]。x?b Aeq所以整數(shù)規(guī)劃問題的最優(yōu)解不會優(yōu)于其松弛問題的最優(yōu)解。線性 (混合 )整數(shù)規(guī)劃問題 是指在等式或不等式的線性約束下，極大化 (或極小化 )某個線性函數(shù)，其中要求某些變量必須取整數(shù)。v 解 ： as=(1 1 0 0 0)T； at=(0 0 0 1 1)T。 aij=1(vi為 ej的起點 )； aij=1(vi為 ej的終點 )； aij=0(其他情形 )。設(shè)計各類 貪婪算法 是求解組合優(yōu)化問題常用的思路。決策理論與方法 優(yōu)化決策理論與方法優(yōu)化決策理論與方法線性規(guī)劃非線性規(guī)劃（約束和非約束）多目標(biāo)規(guī)劃組合優(yōu)化與整數(shù)規(guī)劃決策理論與方法 優(yōu)化決策理論與方法組合優(yōu)化 — 基本概念v 組合優(yōu)化問題 是指從一個有限的可行解集中尋找使某個性能函數(shù)取極值的最優(yōu)解。minimax SQP, QuasiNewton, line_search‘決策理論與方法 優(yōu)化決策理論與方法多目標(biāo)規(guī)劃 — Matlab函數(shù)應(yīng)用v 解 (2)：用 fgoalattain求解。? 無約束。 f(2)= x(1)^2 3*x(2)^2。lb。A。f(p)=f p(x)? 創(chuàng)建另一個 matlab文件，如 function [c, ceq] = confun(x)c = c(x)。 weight為各目標(biāo)的權(quán)重向量。[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)weightAeq。? 調(diào)用 fminimax并指定初始搜索點以及其他向量、矩陣。f(2)=f2(x)。決策理論與方法 優(yōu)化決策理論與方法多目標(biāo)規(guī)劃 — Matlab函數(shù)應(yīng)用v Optimization ToolBoxMin max {fi(x)}. c(x)?0 ceq(x)=0 A 關(guān)鍵問題在于 ：保證最后一個單目標(biāo)優(yōu)化問題的最優(yōu)解是 MOP問題的有效解或弱有效解。j?? fk(x)?uk, k=2,…, p? uk為專家經(jīng)驗值。i?I hj(x)=0。下面介紹多目標(biāo)規(guī)劃問題的間接解法，基本思路都是將多目標(biāo)規(guī)劃問題轉(zhuǎn)化為一個或多個單目標(biāo)優(yōu)化問題。決策理論與方法 優(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問題的有效解 (或弱有效解 )。決策理論與方法 優(yōu)化決策理論與方法多目標(biāo)規(guī)劃 — 標(biāo)準(zhǔn)型v 多目標(biāo)規(guī)劃 (multiObjective Programming,MOP)就是指在決策變量滿足給定約束的條件下研究多個可數(shù)值化的目標(biāo)函數(shù)同時極小化 (或極大化 )的問題。決策理論與方法 優(yōu)化決策理論與方法多目標(biāo)規(guī)劃 — 管理實例v 決策目標(biāo)：? 運輸速度最快，可用噸公里數(shù)（ 可觀測變量 ）最小描述。試建立描述物資調(diào)運過程的數(shù)學(xué)模型。決策理論與方法 優(yōu)化決策理論與方法二次規(guī)劃 — Matlab函數(shù)應(yīng)用? 調(diào)用二次規(guī)劃函數(shù)[x,fval]=quadprog(H,f,A,b,[],[],lb)? 運行結(jié)果 ：x =[。Aeq=[]。2。? 表示其它矩陣或向量A=[1 1。[x,fval]=quadprog(H,f,A,b,Aeq,beq,lb,ub,x0)決策理論與方法 優(yōu)化決策理論與方法二次規(guī)劃 — Matlab函數(shù)應(yīng)用v 例 ： min f(x)=1/2x12+x22x1x22x16x2 . x1+x2?2 x1+2x2?2 2x1+x2?3 x1, x2?0v 解 ：? 改寫 f(x)=1/2(x12+2x22x1x2x1x2)2x16x2得： H=[1 1。Aeq。? 調(diào)用 quadprog并根據(jù)需要指定初始搜索點以及其他向量、矩陣。mediumscale: SQP, QuasiNewton, linesearch39。,39。ceq = []。ub。b。 ceq = ceq(x)。x?b Aeqv 基本思想 ：在迭代點處構(gòu)造一個二次規(guī)劃子問題，近似原來的約束優(yōu)化問題；然后通過求解該二次規(guī)劃子問題獲得約束優(yōu)化問題的一個改進迭代點；不斷重復(fù)此過程，直到求出滿足一定要求的迭代點。決策理論與方法 優(yōu)化決策理論與方法二次規(guī)劃 — 極小點存在條件v 充要條件? 可行點 x*是 QP問題的局部極小點當(dāng)且僅當(dāng) x*為一個 KKT點且對于任意非零可行方向 d，有 dTQd?0。即 S0={x|g(x)0}≠?決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — 序列無約束化法v 例 ： min{f=x/2|x?1}v 解：構(gòu)造對數(shù)障礙函數(shù) P(x,?)=x/2?ln(x1)? P’x=1/2?/(x1)=0，得 x?*=1+2?， P*=1/2+??ln2?? 當(dāng) ?→0 時得 x*=1， f*=1/2決策理論與方法 優(yōu)化決策理論與方法二次規(guī)劃 — 標(biāo)準(zhǔn)型v 若有約束非線性規(guī)劃的目標(biāo)函數(shù)是決策變量 x的二次函數(shù)且所有約束均為線性約束，稱此類非線性規(guī)劃問題為二次規(guī)劃 (Quadratic Programming, QP)問題。因此也將此類方法稱為 罰函數(shù)法 ，所形成的無約束優(yōu)化函數(shù)成為 罰函數(shù) 。Min dT?f(x0). AI(x0)d?0, I(x0)={i|aiTx0=bi,i?I} A?d=0 ||d||∞?1v 可以證明：當(dāng) x0取得 KKT點時當(dāng)且僅當(dāng) dT?f(x0)的最優(yōu)值為零。v 可行方向法的基本思想 ：當(dāng)某個可行方向同時也是目標(biāo)函數(shù)的下降方向時，沿此方向移動一定會在滿足可行性的情況下改進迭代點的目標(biāo)函數(shù)值。v 根據(jù)凸規(guī)劃充分條件知 x*為全局最小點。決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — 極小值存在條件v 例： min f(x)=x12+x22 . x1+x2?4 x1,x2?0v 解： g1(x)=x1+x24?0。決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — 極小值存在條件v 二階必要條件? 設(shè) x*是 COP問題的局部極小點且滿足 KKT條件。f(x*+?d)=f(x*)+?(?f(x*))Td+o(?)? 代數(shù)特征 (KKT定理 )： 若 x*是 COP問題的局部極小點且函數(shù) f(x), gi(x), hj(x)在 x*處可微，則存在實數(shù) ?i?0(i?I), ?j?R(j??)，使得：?f(x*)=?i?gi(x*)?i+?j?hj(x*)?j；gi(x*)?i=0； ?i?0， ?i?I? 若 x*滿足 KKT條件，則稱 x*為 COP問題的一個 KKT點，?i, ?j稱為 x*處的拉格朗日乘子。若 x0的某一方向 d既是可行方向又是下降方向則稱其為可行下降方向。v 下降方向 。決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — 幾個概念v 可行方向 。對于 gi(x0)?0，或者等號成立，或者大于號成立。決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — 標(biāo)準(zhǔn)型v 其中 f(x)是目標(biāo)函數(shù)， gi(x)和 hj(x)為約束函數(shù) (約束條件 )?；蛘?[x,fval] = fminsearch(myfun,x0,options)。,39。 x0=[x1,x2,…,xn] [x,fval] = fminunc(myfun,x0) 或 [x,fval] = fminsearch(myfun,x0)決策理論與方法 優(yōu)化決策理論與方法無約束非線性規(guī)劃 — Matlab函數(shù)應(yīng)用v 例 ： min f(x)=ex1(4x12+2x22+4x1x2+2x2+1)v 解 ：? 創(chuàng)建一個 matlab文件，如 function f = myfun(x)f =exp(x(1))*(4*x(1)^2+2*x(2)^2+4*x(1)*x(2)+2*x(2)+1)。決策理論與方法 優(yōu)化決策理論與方法無約束非線性規(guī)劃 — Matlab函數(shù)應(yīng)用v Optimization ToolBoxMin f(x)v Matlab提供了兩個求解無