【正文】 動態(tài)規(guī)劃方法簡介 動態(tài)規(guī)劃是解決多階段決策過程最優(yōu)化問題的一種方法。由美國數(shù)學家貝爾曼（ Ballman）等人在 20世紀 50年代提出。他們針對 多階段決策問題 的特點，提出了解決這類問題的“最優(yōu)化原理”，并成功地解決了生產(chǎn)管理 、 工程技術等方面的許多實際問題 。 動態(tài)規(guī)劃是現(xiàn)代企業(yè)管理中的一種重要決策方法，可用于最優(yōu)路徑問題、資源分配問題、生產(chǎn)計劃和庫存問題、投資問題、裝載問題、排序問題及生產(chǎn)過程的最優(yōu)控制等。 一 .多階段決策過程最優(yōu)化 多階段決策過程 是指這樣一類特殊的活動過程，他們可以按時間順序分解成若干相互聯(lián)系的階段，在每個階段都要做出決策，全部過程的決策是一個決策序列，所以多階段決策問題也稱為序貫決策問題 。 動態(tài)規(guī)劃的基本原理 1 2 n ? 狀態(tài) 決策 狀態(tài) 決策 狀態(tài) 狀態(tài) 決策 圖示 多階段決策問題，不論其本身是否與時間有關，由于分為階段依次解決，這便具有明顯的時序性，而在各階段中所采取的決策是隨階段而變動的，不同階段采取不同決策，這便是動態(tài)的含義 .階段往往可以用時段來表示，但動態(tài)規(guī)劃在一定條件下也可以解決一些與時間無關的靜態(tài)最優(yōu)化問題，只要人為地引入 “ 時段 ” 因素，就可以將其轉(zhuǎn)化為一個多階段決策問題。 動態(tài)規(guī)劃是用來解決多階段決策過程最優(yōu)化的一種數(shù)量方法。其特點在于，它可以把一個 n 維決策問題變換為幾個一維最優(yōu)化問題，從而一個一個地去解決。 需指出：動態(tài)規(guī)劃是求解某類問題的一種方法， 是考察問題的一種途徑 ，而不是一種算法。必須對具體問題進行具體分析，運用動態(tài)規(guī)劃的原理和方法，建立相應的模型，然后再用動態(tài)規(guī)劃方法去求解。 二、多階段決策問題舉例 1)工廠生產(chǎn)過程 ：由于市場需求是一隨著時間而 變化的因素，因此，為了取得全年最佳經(jīng)濟效益，就要在全年的生產(chǎn)過程中，逐月或者逐季度地根據(jù)庫存和需求情況決定生產(chǎn)計劃安排。 2)設備更新問題 ： 一般企業(yè)用于生產(chǎn)活動的設備 ， 剛買來時故障少 ， 經(jīng)濟效益高 ， 即使進行轉(zhuǎn)讓 ， 處理價值也高 ， 隨著使用年限的增加 ， 就會逐漸變?yōu)楣收隙?，維修費用增加 ， 可正常使用的工時減少 ，加工質(zhì)量下降 ， 經(jīng)濟效益差 ， 并且 ， 使用的年限越長 、 處理價值也越低 ， 自然 ， 如果賣去舊的買新的 ， 還需要付出更新費 ． 因此就需要綜合權衡決定設備的使用年限 ， 使總的經(jīng)濟效益最好 。 3)連續(xù)生產(chǎn)過程的控制問題 ： 一般化工生產(chǎn)過程中 ， 常包含一系列完成生產(chǎn)過程的設備 ， 前一工序設備的輸出則是后一工序設備的輸入 ， 因此 ， 應該如何根據(jù)各工序的運行工況 ， 控制生產(chǎn)過程中各設備的輸入和輸出 ， 以使總產(chǎn)量最大 。 4)運輸網(wǎng)絡問題 （ 最短路問題 ） ： 如圖 1所示的運輸網(wǎng)絡 ， 點間連線上的數(shù)字表示兩地距離 (也可是運費 、 時間等 )， 要求從 v1至 v10的最短路線 。 這種運輸網(wǎng)絡問題也是靜態(tài)決策問題 。但是 ， 按照網(wǎng)絡中點的分布 ， 可以把它分為 4個階段 ， 而作為多階段決策問題來研究 。 以上所舉問題的發(fā)展過程都與時間因素有關 ， 階段的劃分常取時間區(qū)段來表示 ，并且各個階段上的決策往往也與時間因素有關 ， 這就使它具有了 “ 動態(tài) ” 的含義 ，所以把處理這類動態(tài)問題的方法稱為動態(tài)規(guī)劃方法 。 不過 ， 實際中尚有許多不包含時間因素的一類 “ 靜態(tài) ” 決策問題 ， 就其本質(zhì)而言是一次決策問題 ， 是非動態(tài)決策問題 ， 但是也可以人為地引入階段的概念當作多階段決策問題 ， 應用動態(tài)規(guī)劃方法加以解決 。 三 、 動態(tài)規(guī)劃方法導引 例 1： 為了說明動態(tài)規(guī)劃的基本思想方法和特點 ， 下面以圖 1所示為例討論的求最短路問題的方法 。 第一種方法稱做 全枚舉法 或 窮舉法 。 它的基本思想是列舉出所有可能發(fā)生的方案和結(jié)果 ，再對它們一一進行比較 ， 求出最優(yōu)方案 。 這里從 v1到 v10的路程可以分為 4個階段 。 第一段的走法有三種 ， 第二三兩段的走法各有兩種 ， 第四段的走法僅一種 ， 因此共有 3 2 2 1＝ 12條可能的路線 ， 分別算出各條路線的距離 ， 最后進行比較 ， 可知最優(yōu)路線是 v1 → v3 → v7 → v9 → v10 ,最短距離是 18． 顯然 ， 當組成交通網(wǎng)絡的節(jié)點很多時 ， 用窮舉法求最優(yōu)路線的計算工作量將會十分龐大 ， 而且其中包含著許多重復計算 ． 第二種方法即所謂 “ 局部最優(yōu)路徑 ”法 ， 是說某人從 k出發(fā) ， 他并不顧及全線是否最短 ， 只是選擇當前最短途徑 ，“ 逢近便走 ” ， 錯誤地以為局部最優(yōu)會致整體最優(yōu) ， 在這種想法指導下 ， 所取決策必是 v1 →v 3 →v 5 → v8 → v10 ，全程長度是 20；顯然 ， 這種方法的結(jié)果常是錯誤的 ． 第三種方法是 動態(tài)規(guī)劃方法 。 動態(tài)規(guī)劃方法尋求該最短路問題的基本思想是 ，首先將問題劃分為 4個階段 ， 每次的選擇總是綜合后繼過程的一并最優(yōu)進行考慮 ， 在各段所有可能狀態(tài)的最優(yōu)后繼過程都已求得的情況下 ， 全程的最優(yōu)路線便也隨之得到 。 為了找出所有可能狀態(tài)的最優(yōu)后繼過程 ， 動態(tài)規(guī)劃方法總是從過程的最后階段開始考慮 ， 然后逆著實際過程發(fā)展的順序 ，逐段向前遞推計算直至始點 。 具體說 ， 此問題先從 v10開始 ， 因為 v10是終點 。 再無后繼過程 ， 故可以接著考慮第 4階段上所有可能狀態(tài) v8 ,v9的最優(yōu)后續(xù)過程 ． 因為從v8 ,v9 到 v10的路線是唯一的 ， 所以 v8 ,v9 的最優(yōu)決策和最優(yōu)后繼過程就是到 v10 ， 它們的最短距離分別是 5和 3。 接著考慮階段 3上可能的狀態(tài) v5 ,v6 , v7 , 到 v10的最優(yōu)決策和最優(yōu)后繼過程 ． 在狀態(tài) V5上 ，雖然到 v8是 8， 到 v9是 9， 但是綜合考慮后繼過程整體最優(yōu) ， 取最優(yōu)決策是到 v9,最優(yōu)后繼過程是v5→ v9 → v10 ， 最短距離是 12． 同理 ， 狀態(tài) v6的最優(yōu)決策是至 v8 ； v7的最優(yōu)決策是到 v9 。 同樣 ， 當階段 3上所有可能狀態(tài)的最優(yōu)后繼過程都已求得后 ， 便可以開始考慮階段 2上所有可能狀態(tài)的最優(yōu)決策和最優(yōu)后繼過程 ， 如 v2的最優(yōu)決策是到 v5,最優(yōu)路線是 v2→ v5→ v9→ v10 ， 最短距離是 15…依此類推 ， 最后可以得到從初始狀態(tài) v1的最優(yōu) 決 策 是 到 v3 最 優(yōu) 路 線 是v1→ v3→ v7→ v9→ v10 ， 全程的最短距離是18。 圖 5—1中粗實線表示各點到 v10的最優(yōu)路線 ， 每點上方括號內(nèi)的數(shù)字表示該點到終點的最短路距離 。 綜上所述可見 ， 全枚舉法雖可找出最優(yōu)方案 ，但不是個好算法 ， 局部最優(yōu)法則完全是個錯誤方法 ， 只有 動態(tài)規(guī)劃方法屬較科學有效的算法 。 它的基本思想是 ， 把一個比較復雜的問題分解為一系列同類型的更易求解的子問題 ， 便于應用計算機 。 整個求解過程分為兩個階段 ， 先按整體最優(yōu)的思想逆序地求出各個子問題中所有可能狀態(tài)的最優(yōu)決策與最優(yōu)路線值 ， 然后再順序地求出整個問題的最優(yōu)策略和最優(yōu)路線 。 計算過程中 ， 系統(tǒng)地刪去了所有中間非最優(yōu)的方案組合 ， 從而使計算工作量比窮舉法大為減少 。 四、動態(tài)規(guī)劃的基本概念與基本方程 使用動態(tài)規(guī)劃方法解決多階段決策問題 ， 首先要將實際問題寫成動態(tài)規(guī)劃模型 ， 同時也為了今后敘述和討論方便 ，這里需要對動態(tài)規(guī)劃的下述一些基本術語進一步加以說明和定義 ： (一 ) 階段 為了便于求解和表示決策及過程的發(fā)展順序 ， 而把所給問題恰當?shù)貏澐譃槿舾蓚€相互聯(lián)系又有區(qū)別的子問題 ， 稱之為多段決策問題的階段 。 一個階段 ， 就是需要作出一個決策的子問題 ， 通常 ， 階段是按決策進行的時間或空間上先后順序劃分的 。用以描述階段的變量叫作階段變量 ， 一般以 k表示階段變量 ． 階段數(shù)等于多段決策過程從開始到結(jié)束所需作出決策的數(shù)目 ， 圖 1所示的最短路問題就是一個四階段決策過程 ， 。 1 , 2 , 3 , 4k ? （ 二 ） 狀態(tài) 。 用以描述事物 (或系統(tǒng) )在某特定的時間與空間域中所處位置及運動特征的量 ， 稱為狀態(tài) 。 反映狀態(tài)變化的量叫做狀態(tài)變量 。 狀態(tài)變量必須包含在給定的階段上確定全部允許決策所需要的信息 。按照過程進行的先后 ， 每個階段的狀態(tài)可分為初始狀態(tài)和終止狀態(tài) ， 或稱輸入狀態(tài)和輸出狀態(tài) ， 階段 k的初始狀態(tài)記作 sk， 終止狀態(tài)記為 sk+1。 但為了清楚起見 ， 通常定義階段的狀態(tài)即指其初始狀態(tài) 。 狀態(tài)應描述過程特征 。能直接或間接觀測 。具有無后效性 . 某階段的狀態(tài)給定后，則過程未來發(fā)展不受該階段以前各階段狀態(tài)的影響 2． 可能狀態(tài)集 一般狀態(tài)變量的取值有一定的范圍或允許集合 ， 稱為可能狀態(tài)集 ， 或可達狀態(tài)集 。 通?？赡軤顟B(tài)集用相應階段狀態(tài) sk的大寫字母 Sk表示 ，sk∈ Sk， 可能狀態(tài)集可以是一離散取值的集合 ，也可以為一連續(xù)的取值區(qū)間 ． 在圖 1所示的最短路問題中 ， 第一階段狀態(tài)為 v1， 狀態(tài)變量 s1的狀態(tài)集合 S1={v1}；第二階段則有三個狀態(tài)：v2 ,v3 ,v4 , 狀 態(tài) 變 量 s2 的 狀 態(tài) 集 合S2={v2 ,v3 ,v4} ； 第 三 階 段 也 有 三 個 狀態(tài) :v5 ,v6 ,v7 ， 狀態(tài)變量 s3 的狀態(tài)集合S3={v5 ,v6 ,v7} ；第四階段則有二個狀態(tài)： v8 ,v9 , 狀態(tài)變量 s4的狀態(tài)集合 S4={v8 ,v9} ； （ 三 ） 決策 所謂 決策 ， 就是確定系統(tǒng)過程發(fā)展的方案 。決策的實質(zhì)是關于狀態(tài)的選擇 ， 是決策者從給定階段狀態(tài)出發(fā)對下一階段狀態(tài)作出的選擇 。 用以描述決策變化的量稱之決策變量 ， 和狀態(tài)變量一樣 ， 決策變量可以用一個數(shù) ， 一組數(shù)或一向量來描述 ， 也可以是狀態(tài)變量的函數(shù) ， 記以 uk= uk(sk)， 表示于階段 k狀態(tài) sk時的決策變量 。 決策變量的取值往往也有一定的允許范圍 ，稱之允許決策集合 。 決策變量 uk(sk)的允許決策集用 Uk(sk)表示 , uk(sk)∈ Uk(sk)允許決策集合實際是決策的約束條件 。 （ 四 ） 狀態(tài)轉(zhuǎn)移方程 系統(tǒng)在階段 k處于狀態(tài) sk， 執(zhí)行決策 uk(sk)的結(jié)果是系統(tǒng)狀態(tài)的轉(zhuǎn)移 ， 即系統(tǒng)由階段 k的初始狀態(tài) sk轉(zhuǎn)移到終止狀態(tài) sk+1， 系統(tǒng)由階段 k到階段k+1的狀態(tài)轉(zhuǎn)移完全由階段 k的狀態(tài) sk和決策 uk(sk)所確定 ， 與系統(tǒng)過去的狀態(tài) s1,s2,… ,sk1及其決策 u1(s1), u2(s2)…uk1(sk1)無關 。 系統(tǒng)狀態(tài)的這種轉(zhuǎn)移 ， 用數(shù)學公式描述即有： ))(,(1 kkkkk susTs ??(1) （ 五 ） 、 策略 策略 (Policy)也叫決策序列 ． 策略有全過程策略和 k部子策略之分 ， 全過程策略是指具有 n個階段的全部過程 ， 由依次進行的 n個階段決策構(gòu)成 的 決 策 序 列 ， 簡 稱 策 略 ， 表示為p1,n{u1,u2,…,un}。 從 k階段到第 n階段 ， 依次進行的階段決策構(gòu)成的決策序列稱為 k部子策略 ,表示為 pk,n{uk,uk+1,…,un} ， 顯然當 k=1時的 k部子策略就是 全過程策略 。 在實際問題中 ， 由于在各個階段可供選擇的決策有許多個 ， 因此 ， 它們的不同組合就構(gòu)成了許多可供選擇的決策序列 (策略 )， 由它們組成的集合 ，稱之 允許策略集合 ， 記作 P1,n ， 從允許策略集中 ，找出具有最優(yōu)效果的策略稱為 最優(yōu)策略 。 (六 ) 指標函數(shù) 用來衡量策略或子策略或決策的效果的某種 數(shù)量指標 ， 就稱為指標函數(shù) 。 它是定義在全過程或各子過程或各階段上的確定數(shù)量函數(shù) 。 對不同問題 ， 指標函數(shù)可以是諸如費用 、 成本 、 產(chǎn)值 、 利潤 、 產(chǎn)量 、 耗量 、 距離 、時間 、 效用 ， 等等 。 例如：圖