【正文】 (x)分別為由 gi(x)和 hj(x)構(gòu)成的向量值函數(shù)， ?,?分別為對應(yīng)于 g(x)和 h(x)的拉格朗日乘子向量。 這個方向就是我們從 x0出發(fā)尋求最優(yōu)解的搜索方向！ 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 — 幾個概念 ?例： min f(x)=x1+x2 . g(x)=1x12x22?0 ?圖描述了該問題的相關(guān)概念。設(shè) x0為 COP問題的任一可行解，對某一方向 d來說，若 ???00使得對于任意 ??[0,?0]，均有 x0+?d?S，稱 d為x0的一個可行方向。 S={x|gi(x)?0 ? hj(x)=0}為可行域。off39。 fun為 f(x)的函數(shù)形式， x0為初始解向量。 ? 迭代改進(jìn) ：計算新的迭代點 xk+1，即 xk+1=xkG1(xk)g(xk)。 設(shè) f(x)在 x*點二階可微，若梯度 ?f(x*)=0且 Hesse矩陣 ?2f(x*)是正定 的，則 x*是 f(x)的一個嚴(yán)格局部極小點。 lb=zeros(2,1)。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 線性規(guī)劃 — 內(nèi)點算法 X空間 內(nèi)點 目標(biāo)函數(shù) 目標(biāo)函數(shù)最速下降方向 Y1空間 中心點 投影尺度變換 1 目標(biāo)函數(shù)最速下降方向 Y2空間 中心點 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 線性規(guī)劃 — Matlab函數(shù)應(yīng)用 ? Optimization ToolBox Min fTx . A 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 線性規(guī)劃 — 內(nèi)點算法 ? 1972年， V. Klee和 G. L. Minty指出 Dantzig的單純形算法的迭代次數(shù)為 O(2n)，是一個指數(shù)時間算法，不是優(yōu)良算法。人體正?；顒舆^程中需要 m種基本的營養(yǎng)成分，且每人每天至少需要攝入第 i種營養(yǎng)成分 bi個單位。決策理論與方法 (2) —— 優(yōu)化決策理論與方法 合肥工業(yè)大學(xué)管理學(xué)院 2021年 6月 15日 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 確定性決策 ?確定性決策 ：指未來狀態(tài)是確定的（即只有一種狀態(tài)）一類決策問題，每一個行動方案對應(yīng)著一個確定的結(jié)果值，此時決策函數(shù)僅依賴于決策變量。已知第 j種食物中包含第 i種營養(yǎng)成分的量為 aij個單位。那么是否存在求解線性規(guī)劃問題的多項式時間算法？ ? 1984年， N. Karmarkar提出了一種 投影尺度算法 ，其計算效果能夠同單純形法相比較，掀起了線性規(guī)劃 內(nèi)點算法 的熱潮。x≤b Aeq A=[1 1。 ?充要條件 。k+1→k 。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 無約束非線性規(guī)劃 — Matlab函數(shù)應(yīng)用 ?用法 ? 創(chuàng)建一個 matlab文件，如 function f = myfun(x) f = f(x)。)。 ?有約束非線性規(guī)劃問題 (COP)是指 f(x),gi(x),hj(x)至少有一個是非線性的，且 I或 ??至少有一個為非空。顯然若 d滿足 dT?gi(x)?0， dT?hj(x)=0，則 d一定是可行方向。 x1 x2 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 — 極小值存在條件 ?一階必要條件 ? 幾何特征 ：若 x*是 COP問題的局部極小點且函數(shù) f(x), gi(x), hj(x)在 x*處可微，則 dT?f(x*)?0。 ? 二階充分條件 ? 設(shè) x*是 COP問題的 KKT點。下面介紹幾種約束優(yōu)化的求解方法：可行方向法、序列無約束化法和 SQP法。 ?基本思想： 將約束條件通過某種轉(zhuǎn)換與目標(biāo)函數(shù)合并形成一個無約束優(yōu)化問題。若目標(biāo)函數(shù)的 Hesse矩陣 Q是半正定 (或正定 )的，則 QP問題為(嚴(yán)格 )凸二次規(guī)劃 (CQP)。 ? 設(shè) (xk,?k)是第 k次迭代結(jié)果，根據(jù)牛頓法，有： ???????? ????????????????????????????????????????????????????)()()(0)()(),()),(()),((121211kkkkTkkkkxxkkkkkkkkkkxhxhxfxhxhxLxxLxLxx???????2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 — SQP法 ? 上述迭代過程等價于如下的二次規(guī)劃的迭代。 x0=[x1,x2,…,xn]。 ? 創(chuàng)建另一個 matlab文件，如 function [c, ceq] = confun(x) c = [ + x(1)*x(2) x(1) x(2)。)。A。6], x=[x1。 lb=[0。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 優(yōu)化決策理論與方法 線性規(guī)劃 非線性規(guī)劃（約束和非約束） 多目標(biāo)規(guī)劃 組合優(yōu)化與整數(shù)規(guī)劃 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 多目標(biāo)規(guī)劃 — 管理實例 ? (物資調(diào)度 )假設(shè)物資調(diào)度部門計劃將某種物資從若干個存儲倉庫調(diào)運到若干個銷售網(wǎng)點銷售?？傔\輸費用為 ?i?jcijxij； ?約束條件 ? 每個倉庫的運出量不超過倉庫的庫存量： ?jxij?ai； ? 運到每個銷售網(wǎng)點的量與其銷售能力相匹配： ?ixij=bj； ? 每個倉庫的運出量非負(fù)： xij?0。有效解通常也稱為 Pareto最優(yōu)解。j?? ? 權(quán)重設(shè)置 要求 ： ?k?k=1, ?k?0(k=1,2,…, p)。 ?分層排序法 ：將目標(biāo)函數(shù)按重要度依次排序，然后在前一個目標(biāo)函數(shù)的最優(yōu)解集中尋找下一個目標(biāo)的最優(yōu)解集，并把最后一個目標(biāo)的最優(yōu)解作為 MOP問題的最優(yōu)解?！eq。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 多目標(biāo)規(guī)劃 — Matlab函數(shù)應(yīng)用 ? 用法 ? 創(chuàng)建一個 matlab文件，如 function f = myfun(x) f(1) = f1(x)。b。 f(3)= x(1) + 3*x(2) 18。 ? 定義 ? 指定初始搜索點： x0=[。 ???SjjFS cm i n2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 組合優(yōu)化 — 基本概念 ?常見的組合優(yōu)化問題： ? 最短路問題 ：給定一定的路長分布，確定從某個地點到另一個地點使路長最短的路徑。aa=(1 0 1 1 0)T。 ?求解方法： Gomory割平面法、分支定界法、分解算法。x . A s t a b e1 e2 e3 e5 e4 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 整數(shù)規(guī)劃 — 標(biāo)準(zhǔn)型 ?整數(shù)規(guī)劃是一類特殊的組合優(yōu)化問題。 ? 關(guān)聯(lián)矩陣： A=(aij)|V| |E|。goal attainment SQP, QuasiNewton, line_search39。 f(5)= x(1) + x(2) 8。beq。…。ub。 ceq = ceq(x)。 2. 第 j層： min fj(x),x?Sj1， j=2,…, p 3. 最后將 Sp中的點作為多目標(biāo)問題的最優(yōu)解。i?I hj(x)=0。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 多目標(biāo)規(guī)劃 — 求解方法 ?直接求解多目標(biāo)規(guī)劃問題的有效解集是 NP難問題。 ),1。試建立描述物資調(diào)運過程的數(shù)學(xué)模型。Aeq=[]。 ? 表示其它矩陣或向量 A=[1 1。Aeq。mediumscale: SQP, QuasiNewton, linesearch39。 ceq = []。b。x?b Aeq 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 二次規(guī)劃 — 極小點存在條件 ?充要條件 ? 可行點 x*是 QP問題的局部極小點當(dāng)且僅當(dāng) x*為一個 KKT點且對于任意非零可行方向 d，有 dTQd?0。因此也將此類方法稱為 罰函數(shù)法 ，所形成的無約束優(yōu)化函數(shù)成為 罰函數(shù) 。 ?可行方向法的基本思想 ：當(dāng)某個可行方向同時也是目標(biāo)函數(shù)的下降方向時，沿此方向移動一定會在滿足可行性的情況下改進(jìn)迭代點的目標(biāo)函數(shù)值。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 — 極小值存在條件 ? 例： min f(x)=x12+x22 . x1+x2?4 x1,x2?0 ? 解： g1(x)=x1+x24?0。 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*處的拉格朗日乘子。 ? 下降方向 。對于 gi(x0)?0，或者等號成立，或者大于號成立。 或者 [x,fval] = fminsearch(myfun,x0,options)。 x0=[x1,x2,…,xn] [x,fval] = fminunc(myfun,x0) 或 [x,fval] = fminsearch(myfun,x0) 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 無約束非線性規(guī)劃 — Matlab函數(shù)應(yīng)用 ?例 ： min f(x)=ex1(4x12+2x22+4x1x2+2x2+1) ?解 ： ? 創(chuàng)建一個