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