【正文】 2 1] [x, fval] = linprog(f,A,b,[],[],lb) x=[0。 lb=zeros(2,1)。 b=[40。 x2≥0解 ：將 max變?yōu)?min， min –z=x12x2則： f=[1。x=beqlb≤x≤ub? 其中： f, x, b, beq, lb和 ub均為向量； A和 Aeq為矩陣。決策理論與方法 優(yōu)化決策理論與方法線性規(guī)劃 — 內(nèi)點(diǎn)算法X空間內(nèi)點(diǎn)目標(biāo)函數(shù)目標(biāo)函數(shù)最速下降方向Y1空間中心點(diǎn)投影尺度變換 1目標(biāo)函數(shù)最速下降方向Y2空間中心點(diǎn)投影尺度變換2決策理論與方法 優(yōu)化決策理論與方法線性規(guī)劃 — Matlab函數(shù)應(yīng)用v Optimization ToolBoxMin fTx. A決策理論與方法 優(yōu)化決策理論與方法線性規(guī)劃 — 內(nèi)點(diǎn)算法可行域內(nèi)點(diǎn)初始基可行解基可行解目標(biāo)函數(shù)目標(biāo)函數(shù)最速下降方向決策理論與方法 優(yōu)化決策理論與方法線性規(guī)劃 — 內(nèi)點(diǎn)算法v 投影尺度算法? 如何穿過(guò)可行域的內(nèi)部快速達(dá)到最優(yōu)解呢？ Karmarkar發(fā)現(xiàn)： (1)如果一個(gè)內(nèi)點(diǎn)位于可行域 (多胞形、多面體 )的中心，那么目標(biāo)函數(shù)的最速下降方向是比較好的方向；(2)存在一個(gè)適當(dāng)?shù)淖儞Q，能夠?qū)⒖尚杏蛑薪o定的內(nèi)點(diǎn)置于變換后的可行域的中心。? 內(nèi)點(diǎn)算法的思想是從可行域內(nèi)的任意一點(diǎn) (任一可行解 )出發(fā)，穿越可行域的內(nèi)部達(dá)到最優(yōu)解。決策理論與方法 優(yōu)化決策理論與方法線性規(guī)劃 — 內(nèi)點(diǎn)算法v 內(nèi)點(diǎn)算法的思想? 已知線性規(guī)劃問(wèn)題的可行域是一個(gè)多面體，最優(yōu)點(diǎn)在多面體的某個(gè)極點(diǎn)取到。決策理論與方法 優(yōu)化決策理論與方法線性規(guī)劃 — 內(nèi)點(diǎn)算法v1972年， V. Klee和 G. L. Minty指出 Dantzig的單純形算法的迭代次數(shù)為 O(2n)，是一個(gè)指數(shù)時(shí)間算法，不是優(yōu)良算法。v 單純形算法的基本思想? 從某個(gè)極點(diǎn)開(kāi)始獲得一個(gè)可行解；? 判斷該可行解是不是目標(biāo)解。? 最優(yōu)解分析 ：在端點(diǎn) (或稱為極點(diǎn)。已知第 j種食物中包含第 i種營(yíng)養(yǎng)成分的量為 aij個(gè)單位。決策理論與方法 優(yōu)化決策理論與方法優(yōu)化決策理論與方法線性規(guī)劃非線性規(guī)劃（約束和非約束）多目標(biāo)規(guī)劃組合優(yōu)化與整數(shù)規(guī)劃決策理論與方法 優(yōu)化決策理論與方法線性規(guī)劃 — 管理實(shí)例v (食譜問(wèn)題 )假設(shè)市場(chǎng)上有 n種不同的食物，第 j種食物的單價(jià)為 cj。決策理論與方法 優(yōu)化決策理論與方法優(yōu)化問(wèn)題分類v 整數(shù)規(guī)劃 ：當(dāng)決策變量的取值均為整數(shù)時(shí)稱為整數(shù)規(guī)劃；若某些變量取值為整數(shù)，而另一些變量取值為實(shí)數(shù)，則成為混合整數(shù)規(guī)劃。v 決策的已知變量 ：? 決策變量及其取值范圍v 解決問(wèn)題的主要理論方法 ：最優(yōu)化理論與方法v 注： 最優(yōu)化理論與方法（數(shù)學(xué)規(guī)劃）也可以求解不確定性決策問(wèn)題、隨機(jī)性決策問(wèn)題決策理論與方法 優(yōu)化決策理論與方法確定性決策v 優(yōu)化決策方法的問(wèn)題求解過(guò)程? 辨識(shí)目標(biāo) C，確定優(yōu)化的標(biāo)準(zhǔn)，如：利潤(rùn)、時(shí)間、能量等? 確定影響決策目標(biāo)的決策變量 x，形成目標(biāo)函數(shù) C=f(x)? 明確決策變量的取值范圍，形成約束函數(shù)? 設(shè)計(jì)求解算法，尋找決策目標(biāo)在決策變量所受限制的范圍內(nèi)的極小化或極大化。決策理論與方法 (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ù)僅依賴于決策變量。v 特點(diǎn) ：狀態(tài)是確定的；決策問(wèn)題變?yōu)閮?yōu)化問(wèn)題。? 最優(yōu)化問(wèn)題的一般形式為：決策理論與方法 優(yōu)化決策理論與方法優(yōu)化問(wèn)題分類v 可行點(diǎn) 與 可行域 ：滿足約束條件的 x稱為可行點(diǎn)，所有可行點(diǎn)的集合稱為可行域，記為 S；v 約束優(yōu)化 與 無(wú)約束優(yōu)化 ：當(dāng) S?Rn時(shí)，稱為約束優(yōu)化；當(dāng) S=Rn時(shí)，稱為無(wú)約束優(yōu)化；v 多目標(biāo)優(yōu)化 ：若 f是多個(gè)目標(biāo)函數(shù)構(gòu)成的一個(gè)向量值函數(shù)，則稱為多目標(biāo)規(guī)劃；v 線性規(guī)劃 與 非線性規(guī)劃 ：當(dāng) f,g,h均為線性函數(shù)時(shí)稱為線性規(guī)劃，否則稱為非線性規(guī)劃。v 動(dòng)態(tài)規(guī)劃 與 多層規(guī)劃 ：若決策是分成多個(gè)階段完成的，前后階段之間相互影響，則稱為動(dòng)態(tài)規(guī)劃；若決策是分成多個(gè)層次完成的，不同層次之間相互影響，則稱為多層規(guī)劃。人體正?；顒?dòng)過(guò)程中需要 m種基本的營(yíng)養(yǎng)成分，且每人每天至少需要攝入第 i種營(yíng)養(yǎng)成分 bi個(gè)單位。問(wèn)在滿足人體基本營(yíng)養(yǎng)需求的前提下什么樣的配食方案最經(jīng)濟(jì)？v 設(shè)食譜中包含第 j種食物的量為 xj，則：決策理論與方法 優(yōu)化決策理論與方法線性規(guī)劃 — 標(biāo)準(zhǔn)型決策理論與方法 優(yōu)化決策理論與方法線性規(guī)劃 — 單純形算法v 解空間分析? 可行域分析 ： n維空間；第一象限； m個(gè)超平面。極點(diǎn)向量中，至少有 nm個(gè) 0分量 )處取極值。若是，算法結(jié)束；否則尋找下一個(gè)極點(diǎn)（確定 入基變量 和 出基變量 ），直至找到目標(biāo)解。那么是否存在求解線性規(guī)劃問(wèn)題的多項(xiàng)式時(shí)間算法？v1984年， N. Karmarkar提出了一種 投影尺度算法 ，其計(jì)算效果能夠同單純形法相比較，掀起了線性規(guī)劃 內(nèi)點(diǎn)算法 的熱潮。在給定初始可行解后，沿著什么樣的路徑到達(dá)最優(yōu)解呢？? 單純形法是從某個(gè)基可行解開(kāi)始，沿著多面體的邊移動(dòng)最終找到最優(yōu)解。 N. Karmarkar的 投影尺度算法 就是一種典型的內(nèi)點(diǎn)算法?；谶@兩點(diǎn)， Karmarkar構(gòu)造了一種稱為 投影尺度算法 的內(nèi)點(diǎn)算法。x≤bAeq[x, fval] = linprog(f,A,b,Aeq,beq,lb,ub)決策理論與方法 優(yōu)化決策理論與方法線性規(guī)劃 — Matlab函數(shù)應(yīng)用v 例： max z=x1+2x2. ? x1+x2≤40? 2x1+x2≤60? x1≥0。2]。60]。 A=[1 1。40], fval= 80x1x2x1+x2=402x1+x2=60Z=x1+2x2決策理論與方法 優(yōu)化決策理論與方法優(yōu)化決策理論與方法線性規(guī)劃非線性規(guī)劃（約束和非約束）多目標(biāo)規(guī)劃組合優(yōu)化與整數(shù)規(guī)劃決策理論與方法 優(yōu)化決策理論與方法無(wú)約束非線性規(guī)劃 — 標(biāo)準(zhǔn)型v Min f(x)。對(duì)于任意點(diǎn)x*?Rn, 它是函數(shù) f的最小點(diǎn) (或局部極小點(diǎn) )嗎？v 例如： min f(x)=ex1(4x12+2x22+4x1x2+2x2+1)決策理論與方法 優(yōu)化決策理論與方法無(wú)約束非線性規(guī)劃 — 復(fù)習(xí)v 梯度向量 vHesse矩陣vTaylor展開(kāi)決策理論與方法 優(yōu)化決策理論與方法無(wú)約束非線性規(guī)劃 — 極小值存在條件v 必要條件 。v 充分條件 。v 充要條件 。決策理論與方法 優(yōu)化決策理論與方法無(wú)約束非線性規(guī)劃 — 牛頓法v 基本思想 ：在一個(gè)點(diǎn)附近，用目標(biāo)函數(shù) f(x)的二階Taylor多項(xiàng)式近似 f(x)，并用該 Taylor多項(xiàng)式的最小點(diǎn)近似 f(x)的最小點(diǎn)。決策理論與方法 優(yōu)化決策理論與方法無(wú)約束非線性規(guī)劃 — 牛頓法v 設(shè) xk是第 k次迭代結(jié)果，記 gk=g(xk)=?f(xk)；Gk=G(xk)=?2f(xk)。? 收斂性檢驗(yàn) ：計(jì)算 g(xk)，若 ||g(xk)||≤e，則算法終止；否則計(jì)算 G(xk)。k+1→ k。決策理論與方法 優(yōu)化決策理論與方法無(wú)約束非線性規(guī)劃 — 準(zhǔn)牛頓法v 牛頓法算法的優(yōu)點(diǎn)是收斂速度快 (利用了 Hesse矩陣)。v 基本思想 ：在迭代過(guò)程中只利用目標(biāo)函數(shù) f(x)和梯度 g(x)的信息，構(gòu)造 Hesse矩陣的近似矩陣，由此獲得一個(gè)搜索方向，生產(chǎn)新的迭代點(diǎn)。決策理論與方法 優(yōu)化決策理論與方法無(wú)約束非線性規(guī)劃 — Matlab函數(shù)應(yīng)用v Optimization ToolBoxMin f(x)v Matlab提供了兩個(gè)求解無(wú)約束非線性規(guī)劃的函數(shù)? [x,fval] = fminunc(fun,x0)? [x,fval] = fminsearch(fun,x0)v 用法相似，算法內(nèi)部的搜索策略不同。決策理論與方法 優(yōu)化決策理論與方法無(wú)約束非線性規(guī)劃 — Matlab函數(shù)應(yīng)用v 用法? 創(chuàng)建一個(gè) matlab文件，如 function f = myfun(x)f = f(x)。 x0=[x1,x2,…,xn] [x,fval] = fminunc(myfun,x0) 或 [x,fval] = fminsearch(myfun,x0)決策理論與方法 優(yōu)化決策理論與方法無(wú)約束非線性規(guī)劃 — Matlab函數(shù)應(yīng)用v 例 ： min f(x)=ex1(4x12+2x22+4x1x2+2x2+1)v 解 ：? 創(chuàng)建一個(gè)