動態(tài)規(guī)劃的基本概念ppt課件.ppt

運籌學 動態(tài)規(guī)劃 1 第五章動態(tài)規(guī)劃 動態(tài)規(guī)劃是運籌學的一個重要分支 它是從1951年開始 由美國人貝爾曼 R Belman 為首的一個學派發(fā)展起來的 動態(tài)規(guī)劃在經濟 管理 軍事 工程技術等方面都有廣泛的應用 動態(tài)規(guī)劃是解決多階段決策過程的最優(yōu)化問題的一種方法 所謂多階段決策過程是指這樣一類決策過程 它可以把一個復雜問題按時間 或空間 分成若干個階段 每個階段都需要作出決策 以便得到過程的最優(yōu)結局 由于在每個階段采取的決策是與時間有關的而且前一階段采取的決策如何 不但與該階段的經濟效果有關 還影響以后各階段的經濟效果 可見這類多階段決策問題是一個動態(tài)的問題 因此 處理的方法稱為動態(tài)規(guī)劃方法 然而 動態(tài)規(guī)劃也可以處理一些本來與時間沒有關系的靜態(tài)模型 這只要在靜態(tài)模型中人為地引入 時間 因素 分成時段 就可以把它看作是多階段的動態(tài)模型 用動態(tài)規(guī)劃方法去處理 動態(tài)規(guī)劃對于解決多階段決策問題的效果是明顯的 但也有一定的局限性 首先 它沒有統(tǒng)一的處理方法 必須根據問題的各種性質并結合一定的技巧來處理 另外當變量的維數增大時 總的計算量及存貯量急劇增大 由于計算機的存貯量及計算速度的限制 目前的計算機仍不能用動態(tài)規(guī)劃方法來解決較大規(guī)模的問題 這就是所謂 維數障礙 2 需指出 動態(tài)規(guī)劃是求解某類問題的一種方法 是考察問題的一種途徑 而不是一種算法 必須對具體問題進行具體分析 運用動態(tài)規(guī)劃的原理和方法 建立相應的模型 然后再用動態(tài)規(guī)劃方法去求解 1動態(tài)規(guī)劃的基本概念 1 1多階段決策問題在研究社會經濟 經營管理和工程技術領域內的有關問題中 有一類特殊形式的動態(tài)決策問題 多階段決策問題 在多階段決策過程中 系統(tǒng)的動態(tài)過程可以按照時間進程分為相互聯(lián)系而又相互區(qū)別的各個階段 在每個階段都要進行決策 系統(tǒng)在每個階段存在許多不同的狀態(tài) 在某個時點的狀態(tài)往往要依某種形式受到過去某些決策的影響 而系統(tǒng)的當前狀態(tài)和決策又會影響系統(tǒng)過程今后的發(fā)展 因而在尋求多階段決策問題的最優(yōu)解時 重要的是不能僅僅從眼前的局部利益出發(fā)進行決策 而需要從系統(tǒng)所經過的整個期間的總效應出發(fā) 有預見性地進行動態(tài)決策 找到不同時點的最優(yōu)決策及整個過程的最優(yōu)策略 下面舉例說明什么是多階段決策問題 4 例1 最短路線問題 在線路網絡圖1中 從A至E有一批貨物需要調運 圖上所標數字為各節(jié)點之間的運輸距離 為使總運費最少 必須找出一條由A至E總里程最短的路線 A B1 B2 E B3 C2 C3 C1 D2 D3 D1 4 5 3 4 4 4 3 1 6 5 8 8 7 7 10 2 9 6 為了找到由A至E的最短線路 可以將該問題分成A B C D E4個階段 在每個階段都需要作出決策 即在A點需決策下一步到B1還是到B2或B3 同樣 若到達第二階段某個狀態(tài) 比如B1 需決定走向C1還是C2 依次類推 可以看出 各個階段的決策不同 由A至E的路線就不同 當從某個階段的某個狀態(tài)出發(fā)作出一個決策 則這個決策不僅影響到下一個階段的距離 而且直接影響后面各階段的行進線路 所以這類問題要求在各個階段選擇一個恰當的決策 使這些決策序列所決定的一條路線對應的總路程最短 圖1 5 例2 帶回收的資源分配問題 某廠新購某種機床125臺 據估計 這種設備5年后將被其它設備所代替 此機車如在高負荷狀態(tài)下工作 年損壞率為1 2 年利潤為10萬元 如在低負荷狀態(tài)下工作 年損壞率為1 5 年利潤為6萬元 問應如何安排這些機床的生產負荷 才能使5年內獲得的利潤最大 本問題具有時間上的次序性 在五年計劃的每一年都要作出關于這些機床生產負荷的決策 并且一旦作出決策 不僅影響到本年利潤的多少 而且影響到下一年初完好機床數 從而影響以后各年的利潤 所以在每年初作決策時 必須將當年的利潤和以后各年利潤結合起來 統(tǒng)籌考慮 與上面例1 例2類似的多階段決策問題還有資源分配 生產存貯 可靠性 背包 設備更新問題等等 6 1 2動態(tài)規(guī)劃的基本概念1 階段動態(tài)規(guī)劃問題通常都具有時間或空間上的次序性 因此求解這類問題時 首先要將問題按一定的次序劃分成若干相互聯(lián)系的階段 以便能按一定次序去求解 如例1 可以按空間次序劃分為A B C D E4個階段 而例2 按照時間次序可分成5個階段 2 狀態(tài)在多階段決策過程中 每階段都需要作出決策 而決策是根據系統(tǒng)所處情況決定的 狀態(tài)是描述系統(tǒng)情況所必需的信息 如例1中每階段的出發(fā)點位置就是狀態(tài) 例2中每年初擁有的完好機床數是作出機床負荷安排的根據 所以年初完好機床數是狀態(tài) 一般地 狀態(tài)可以用一個變量來描述 稱為狀態(tài)變量 記第k階段的狀態(tài)變量為xk k 1 2 n 7 3 決策 多階段決策過程的發(fā)展是用各階段的狀態(tài)演變來描述的 階段決策就是決策者從本階段某狀態(tài)出發(fā)對下一階段狀態(tài)所作出的選擇 描述決策的變量稱為決策變量 當第k階段的狀態(tài)確定之后 可能作出的決策要受到這一狀態(tài)的影響 這就是說決策變量uk還是狀態(tài)變量xk的函數 因此 又可將第k階段xk狀態(tài)下的決策變量記為uk xk 在實際問題中 決策變量的取值往往限制在某一范圍之內 此范圍稱為允許決策變量集合 記作Dk uk 如例2中取高負荷運行的機床數uk為決策變量 則0 uk xk xk是k階段初完好機床數 為允許決策變量集合 4 狀態(tài)轉移方程 在多階段決策過程中 如果給定了k階段的狀態(tài)變量xk和決策變量uk 則第k 1階段的狀態(tài)變量xk 1也會隨之而確定 也就是說xk 1是xk和uk函數 這種關系可記為xk 1 T xk uk 稱之為狀態(tài)轉移方程 8 5 策略 在一個多階段決策過程中 如果各個階段的決策變量uk xk k 1 2 n 都已確定 則整個過程也就完全確定 稱決策序列 u1 x1 u2 x2 un xn 為該過程的一個策略 從階段k到階段n的決策序列稱為子策略 表示成 uk xk uk 1 xk 1 un xn 如例1中 選取一路線A B1 C2 D2 E就是一個策略 u1 A B1 u2 B1 C2 u3 C2 D2 u4 D2 E 由于每一階段都有若干個可能的狀態(tài)和多種不同的決策 因而一個多階段決策的實際問題存在許多策略可供選擇 稱其中能夠滿足預期目標的策略為最優(yōu)策略 例1中存在12條不同路線 其中A B2 C1 D2 E是最短線路 6 指標函數 用來衡量過程優(yōu)劣的數量指標 稱為指標函數 在階段k的xk狀態(tài)下執(zhí)行決策uk 不僅帶來系統(tǒng)狀態(tài)的轉移 而且也必然對目標函數給予影響 階段效應就是執(zhí)行階段決策時給目標函數的影響 9 多階段決策過程關于目標函數的總效應是各階段的階段效應累積形成的 常見的全過程目標函數有以下兩種形式 1 全過程的目標函數等于各階段目標函數的和 即 R r1 x1 u1 r2 x2 u2 rn xn un 2 全過程的目標函數等于各階段目標函數的積 即 R r1 x1 u1 r2 x2 u2 rn xn un 指標函數的最優(yōu)值 稱為最優(yōu)函數值 一般 f1 x1 表示從第1階段x1狀態(tài)出發(fā)至第n階段 最后階段 的最優(yōu)指標函數 fk xk 表示從第k階段xk狀態(tài)出發(fā)至第n階段的最優(yōu)指標函數 k 1 2 n 10 2動態(tài)規(guī)劃的最優(yōu)性原理 多階段決策過程的特點是每個階段都要進行決策 具有n個階段的決策過程的策略是由n個相繼進行的階段決策構成的決策序列 由于前階段的終止狀態(tài)又是后一階段的初始狀態(tài) 因此確定階段最優(yōu)決策不能只從本階段的效應出發(fā) 必須通盤考慮 整體規(guī)劃 就是說 階段k的最優(yōu)決策不應只是本階段的最優(yōu) 而必須是本階段及其所有后續(xù)階段的總體最優(yōu) 即關于整個后部子過程的最優(yōu)決策 對此 貝爾曼在深入研究的基礎上 針對具有無后效性的多階段決策過程的特點 提出了著名的多階段決策的最優(yōu)性原理 整個過程的最優(yōu)策略具有這樣的性質 即無論過程過去的狀態(tài)和決策如何 對前面的決策所形成的狀態(tài)而言 余下的諸決策必須構成最優(yōu)策略 簡而言之 最優(yōu)性原理的含意就是 最優(yōu)策略的任何一部分子策略也必須是最優(yōu)的 11 如例1 A B2 C1 D2 E是由A到E的最短路線 我們在該路線上任取一點C1 按照最優(yōu)性原理C1 D2 E應該是C1到E的最短路 很容易用反證法證明這一結論的正確性 從而說明最優(yōu)性原理的正確性 按最優(yōu)性原理 可以將例1分成A B C D E4個階段 由后向前逐步求出各點到E的最短線路 直至求出A至E的最短線路 K 4時 出發(fā)點有D1 D2 D3 記f4 Di i 1 2 3 為Di到E的最短距離 u4 Di 表示從狀態(tài)Di出發(fā)采取的決策 顯然 f4 D1 7 u4 D1 Ef4 D2 8 u4 D2 Ef4 D3 6 u4 D3 EK 3時 出發(fā)點有C1 C2 C3 f3 C1 min d C1D1 f4 D1 d C1D2 f4 D2 min 4 7 2 8 10 u3 C1 D2f3 C2 min d C2D2 f4 D2 d C2D3 f4 D3 min 5 8 7 6 13 u3 C2 D2或D3f3 C3 min d C3D2 f4 D2 d C3D3 f4 D3 min 10 8 9 6 15 u3 C3 D3 12 K 2時 出發(fā)點有B1 B2 B3f2 B1 min d B1C1 f3 C1 d B1C2 f3 C2 min 6 10 4 13 16 u2 B1 C1f2 B2 min d B2C1 f3 C1 d B2C3 f3 C3 min 3 10 1 15 13 u2 B2 C1f2 B3 min d B3C2 f3 C2 d B3C3 f3 C3 min 8 13 4 15 19 u2 B3 C3K 1時 出發(fā)點只有Ad AB1 f2 B1 4 16f1 A mind AB2 f2 B2 5 13 18 d AB3 f2 B3 3 19u1 A B2由f1 A 18 可知從起點A到終點E的最短距離為18 13 為了找出最短線路 再按計算順序反推回去 可求出最優(yōu)決策序列 即由u1 A B2 u2 B2 C1 u3 C1 D2 u4 D2 E組成最優(yōu)策略 也就是最短線路為 A B2 C1 D2 E 從上面的例子不難看出 對于最短線路問題 有如下的遞推關系 函數方程 fk xk min d xk uk xk fk 1 T xk uk fn 1 xn 1 0k n n 1 1 一般情況下 多階段決策問題存在下面的遞推關系 fk xk opt rk xk uk xk fk 1 T xk uk uk Dk uk fn 1 xn 1 Ck n n 1 1這里rk xk uk xk 是第階段采用uk xk 決策產生的階段效應 fn 1 xn 1 C是邊界條件 號大多數情況下是 號 也可能是 號 稱上述遞推關系為動態(tài)規(guī)劃的基本方程 這個方程是最優(yōu)化原理的具體表達形式 14 在基本方程中 rk xk uk xk 1 T xk uk 都是已知函數 最優(yōu)子策略fk xk 與fk 1 xk 1 之間是遞推關系 要求出fk xk 及uk xk 需要先求出fk 1 xk 1 這就決定了應用動態(tài)規(guī)劃基本方程求最優(yōu)策略總是逆著階段的順序進行的 另一方面 由于k 1階段的狀態(tài)xk 1 T xk uk 是由前面的狀態(tài)和決策所形成的 在計算fk 1 xk 1 時還不能具體確定xk 1的 這就要求必須就k 1階段的各個可能狀態(tài)計算fk 1 xk 1 因此動態(tài)規(guī)劃不但能求出整個問題的最優(yōu)策略和最優(yōu)目標值 而且還能求出決策過程中所有可能狀態(tài)的最優(yōu)策略及最優(yōu)目標值 15 3建立動態(tài)規(guī)劃數學模型的步驟 最優(yōu)化原理 是動態(tài)規(guī)劃的核心 所有動態(tài)規(guī)劃問題的遞推關系都是根據這個原理建立起來的 并且根據遞推關系依次計算 最終可求得動態(tài)規(guī)劃問題的解 一般來說 利用動態(tài)規(guī)劃求解實際問題需先建立問題的動態(tài)模型 具體步驟如下 將問題按時間或空間次序劃分成若干階段 有些問題不具有時空次序 也可以人為地引進時空次序 劃分階段 正確選擇狀態(tài)變量xk 這一步是形成動態(tài)模型的關鍵 狀態(tài)變量是動態(tài)規(guī)劃模型中最重要的參數 一般來說 狀態(tài)變量應具有以下三個特性 要能夠用來描述決策過程的演變特征 要滿足無后效性 即如果某階段狀態(tài)已給定后 則以后過程的進展不受以前各狀態(tài)的影響 也就是說 過去的歷史只通過當前的狀態(tài)去影響未來的發(fā)展 遞推性 即由k階段的狀態(tài)變量xk及決策變量uk可以計算出k 1階段的狀態(tài)變量xk 1 16 確定決策變量uk及允許決策變量集合Dk uk 根據狀態(tài)變量之間的遞推關系 寫出狀態(tài)轉移方程 xk 1 T xk uk xk 建立指標函數 一般用rk xk uk 描寫階段效應 fk xk 表示k n階段的最優(yōu)子策略函數 建立動態(tài)規(guī)劃基本方程 fk xk opt rk xk uk xk fk 1 xk 1 uk Dk uk fn 1 xn 1 Ck n n 1 1以上是建立動態(tài)規(guī)劃模型的過程 這個過程是正確求解動態(tài)規(guī)劃的基礎 在動態(tài)規(guī)劃基本方程中 rk xk uk xk 1 T xk uk 都是已知函數 最優(yōu)子策略fk xk 與fk 1 xk 1 之間是遞推關系 要求出fk xk 及uk xk 需要先求出fk 1 xk 1 這就決定了應用動態(tài)規(guī)劃基本方程求最優(yōu)策略總是逆著階段的順序進行的 由后向前逐步計算 最終可以算出全過程的最優(yōu)策略函數值及最優(yōu)策略 17 另一方面 由于k 1階段的狀態(tài)xk 1 T xk uk 是由前面的狀態(tài)xk和決策uk所形成的 在計算fk 1 xk 1 時還不能具體確定xk 1的值 所以 這就要求必須就k 1階段的各個可能狀態(tài)計算fk 1 xk 1 因此動態(tài)規(guī)劃方法不但能求出整個問題的最優(yōu)策略和最優(yōu)目標值 而且還能求出決策過程中所有可能狀態(tài)的最優(yōu)策略及最優(yōu)目標值 下面就按上述步驟求解例2 18 例2 帶回收的資源分配問題 某廠新購某種機床125臺 據估計 這種設備5年后將被其它設備所代替 此機床如在高負荷狀態(tài)下工作 年損壞率為1 2 年利潤為10萬元 如在低負荷狀態(tài)下工作 年損壞率為1 5 年利潤為6萬元 問應如何安排這些機床的生產負荷 才能使5年內獲得的利潤最大 解 以年為階段 k 1 2 3 4 5取k年初完好的機床數為狀態(tài)變量xk以k年初投入高負荷運行的機床數為決策變量uk 則低負荷運行機床數是xk uk 于是狀態(tài)轉移方程為 xk 1 1 2uk 4 5 xk uk 0 8xk 0 3uk以利潤為目標函數 則k年利潤為 10uk 6 xk uk 4uk 6xk記fk xk 為k年至5年末最大總利潤 則動態(tài)規(guī)劃基本方程為 fk xk max 4uk 6xk fk 1 0 8xk 0 3uk 0 uk xkf6 x6 0k 5 4 3 2 1 19 以上是建立動態(tài)模型的過程 下面具體求解 注意動態(tài)規(guī)劃基本方程