【正文】 采用基于線性規(guī)劃的分支定界算法。則最短路徑問題可表示成如下的 01整數規(guī)劃問題：min wTx. asTx=1 atTx=1 aiTx=0, i≠s,t x?0決策理論與方法 優(yōu)化決策理論與方法組合優(yōu)化 — 最短路問題v 例 ：考慮如圖所示的網絡，定義權函數 w=(1,2,2,3,1)T。? 定義 ? 指定初始搜索點： x0=[。? 調用 fgoalattain并設定理想點、權重向量，指定初始搜索點以及其他向量、矩陣。A。? ?為范數的階，可取 1， 2， ∞。i?I hj(x)=0。ub=[]。lb。 % Starting guessoptions = optimset(39。決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — Matlab函數應用v 用法? 創(chuàng)建一個 matlab文件，如 function f = myfun(x)f = f(x)。決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — 序列無約束化法v 例 ： min f=x1+x2 . x1x22=0v 解：對于 ?0，定義二次罰函數Min Q(x,?)=x1+x2+(2?)1(x1x22)2Q’x1=1+(x1x22)/?=0Q’x2=12x2(x1x22)/?=0解得： x?*=(1/4?,1/2)T, Q*=1/4?/2當 ?→0 時得， x*=(1/4,1/2)T, f*=1/4決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — 序列無約束化法v 對數障礙函數法 ：? 障礙函數：? 其中 ?稱為障礙參數，且當 ?→0 時， P(x,?)的極小值趨于f(x)的極小值。g3(x)=x2?0?f(x)=[2x1,2x2]T,?g1(x)=[1,1]T,?g2(x)=[1,0]T,?g3(x)=[0,1]T,得到：? 2x1=?1+?2? 2x2=?1+?3又 (x1+x24)?1=0； x1?2=0； x2?3=0； ?i?0v 若 ?1=0，則 x1=x2=0，與題意不符；v 若 ?10，則 x1+x24=0， x10, x20。由 f(x0+?d)=f(x0)+?(?f(x0))Td+o(?)可知：若 d滿足dT?f(x0)0，有 f(x0+?d)f(x0)，則 d一定是下降方向。mediumscale: QuasiNewton line search‘v fminsearch結果：? x =[ ]? fval =? iterations: 46? algorithm: 39。v 基本思想 ：在迭代過程中只利用目標函數 f(x)和梯度 g(x)的信息，構造 Hesse矩陣的近似矩陣，由此獲得一個搜索方向，生產新的迭代點。對于任意點x*?Rn, 它是函數 f的最小點 (或局部極小點 )嗎？v 例如： min f(x)=ex1(4x12+2x22+4x1x2+2x2+1)決策理論與方法 優(yōu)化決策理論與方法無約束非線性規(guī)劃 — 復習v 梯度向量 vHesse矩陣vTaylor展開決策理論與方法 優(yōu)化決策理論與方法無約束非線性規(guī)劃 — 極小值存在條件v 必要條件 。 N. Karmarkar的 投影尺度算法 就是一種典型的內點算法。? 最優(yōu)化問題的一般形式為：決策理論與方法 優(yōu)化決策理論與方法優(yōu)化問題分類v 可行點 與 可行域 ：滿足約束條件的 x稱為可行點，所有可行點的集合稱為可行域，記為 S；v 約束優(yōu)化 與 無約束優(yōu)化 ：當 S?Rn時，稱為約束優(yōu)化；當 S=Rn時，稱為無約束優(yōu)化；v 多目標優(yōu)化 ：若 f是多個目標函數構成的一個向量值函數，則稱為多目標規(guī)劃；v 線性規(guī)劃 與 非線性規(guī)劃 ：當 f,g,h均為線性函數時稱為線性規(guī)劃，否則稱為非線性規(guī)劃。v 單純形算法的基本思想? 從某個極點開始獲得一個可行解；? 判斷該可行解是不是目標解。 b=[40。則f(x)=f(xk+p)≈f(xk)+g(xk)Tp+1/2pTG(xk)p=?k(p)v 由于 ?k(p)的最小點滿足 g(xk)+G(xk)p=0，得p=xxk=G1(xk)g(xk)v 因此，可近似得到迭代關系：xk+1=xkG1(xk)g(xk)決策理論與方法 優(yōu)化決策理論與方法無約束非線性規(guī)劃 — 牛頓法v 牛頓迭代法步驟? 初始化 ：給定一個初始點 x0以及參數 e0；記 k=0。LargeScale39。記 J={j|gj(x0)=0?hj(x0)=0}，稱為積極約束指標集。對于 x*?S，若 函數 f(x), gi(x)在 x*處可微，且 KKT條件成立，則 x*為 COP問題的全局最小點。決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — 可行方向法vZoutendijk可行方向法：其核心思想是通過求解下列線性規(guī)劃問題，在可行方向的某個范圍內獲得目標函數的最速下降方向。決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — SQP法v 對于非線性約束優(yōu)化 (COP)問題，v 若 x*是 COP問題的一個局部最優(yōu)解，則它對應一個純等式約束優(yōu)化問題決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — SQP法v 因此如果事先知道積極約束指標集，那么帶有不等式約束優(yōu)化問題就可以轉化為純等式約束優(yōu)化問題，并可用準牛頓法求解，這就是逐次二次規(guī)劃(Sequential Quadratic Programming， SQP)法。lb。x=beq lb?x?ubv[x,fval] = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0)vx0定義初始可行解 (可選 )決策理論與方法 優(yōu)化決策理論與方法二次規(guī)劃 — Matlab函數應用v 用法? 首先要將目標函數轉換成二次規(guī)劃標準型，從而得到 H和f兩個矩陣。 b=[2。設從第 i個倉庫運到第 j個銷售網點的物資量為 xij。決策理論與方法 優(yōu)化決策理論與方法多目標規(guī)劃 — 求解方法v 線性加權和法 ：Min ?Tf(x)=?k?kfk(x)，. gi(x)?0。決策理論與方法 優(yōu)化決策理論與方法多目標規(guī)劃 — Matlab函數應用v 用法? 創(chuàng)建一個 matlab文件，如 function f = myfun(x)f(1) = f1(x)。x=beq lb?x?ubv [x,fval]=fgoalattain(fun,x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon)v Fun定義目標函數； goal為理想點； x0定義初始可行解；nonlcon定義 c(x)和 ceq(x)。weight[x,fval]=fgoalattain(myfun,x0,goal,weight,A,b,Aeq,beq,lb,ub,confun)決策理論與方法 優(yōu)化決策理論與方法多目標規(guī)劃 — Matlab函數應用v 例： min {f1,f2,f3,f4,f5}f(1)= 2*x(1)^2+x(2)^248*x(1)40*x(2)+304。v 已經證明：求解組合優(yōu)化問題的最優(yōu)解是 NP難的。v 整數規(guī)劃問題的可行解一定是松弛問題的可行解，但反之不一定。? beq=[1 1 0 0]T? [x,fval] =bintprog(f, [], [], Aeq, beq)? x=[0 1 0 0 1]T。v 線性混合整數規(guī)劃 (MILP)：max {cTx+hTy|Ax+Gy?b, x?Z+n, y?R+p}? x,y為決策變量向量，其中 x包含 n個整數變量， y包含 p個實數變量； c為 n維向量； h為 p維向量； A為 mn階矩陣，G為 mp階矩陣。v 給定一個有限集 N={1,2,…,n} 和權函數 c:N→R 。ub。??goal c(x)?0 ceq(x)=0 Ax?b Aeqv 基于一個單目標問題的方法 ：將原來的多目標規(guī)劃問題轉化成一個單目標優(yōu)化問題，然后利用非線性優(yōu)化算法求解該單目標問題，所得解作為 MOP問題的最優(yōu)解。v 解 ：設共有 m個倉庫，第 i個倉庫的物資庫存量為 ai噸；有 n個銷售網點，第 j個銷售網點的銷售量為 bj噸。1 2。決策理論與方法 優(yōu)化決策理論與方法二次規(guī)劃 — Matlab函數應用v Optimization ToolBoxMin +fTx. AAeq。? 對于凸二次規(guī)劃， x*為全局極小點當且僅當 x*為局部極小點，當且僅當 x*為 KKT點。決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — 可行方向法x1x2決策理論與方法 優(yōu)化決策理論與方法約束非線性