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