1、第八章 動態規劃動態規劃（Dynamic Programming，簡記為DP）是運籌學的另一個重要分支，是解決多階段決策過程最優化的一種數量化方法，是由美國數學家貝爾曼（R.Bellman）所建立.1951年他提出了解決多階段決策問題的“最優化原理”并且研究了許多實際問題，從而創建了解決多階段決策最優化問題的一種新的方法動態規劃（相對于它，前面討論的規劃問題稱為靜態規劃）.實踐證明，D P方法在工程技術、企業管理、工農業生產及軍事等部門都有廣泛的應用.動態規劃的成功之處在于，它可以把一個n維決策問題變換為一個一維最優化問題，（把一個多階段決策問題變換為一系列互相聯系的單階段問題），然后一個一個

2、地求解，這是經典極值方法所做不到的，特別對于離散性問題，由于解析數學無法施展其術，而動態規劃的方法就成為非常有用的工具.應該指出的是動態規劃是求解某類問題的一種方法，是考察問題的一種途徑，而不是一種特殊的算法，它不象線性規劃那樣有統一的數學模型和算法（如單純形法），而必須對具體問題進行具體分析，針對不同問題運用D P的原理和方法，建立起相應的模型，然后再用動態規劃方法去求解.因此，學習動態規劃時，除了要對動態規劃的基本原理和方法正確理解外，還應以豐富的想象力去建立模型（數學與藝術的結晶），用靈活的技巧去求解.1 多階段決策問題在實踐中，人們常會遇到這樣一類決策問題，即由于過程的特殊性，可以將決

3、策的全過程依據時間或空間劃分為若干個互相聯系的階段，在每一階段要做出決策，而一個階段的決策，不僅影響本階段的活動，還會影響下一階段的活動及其決策，從而影響整個決策過程.各個階段的決策，構成一個決策序列，稱為一個策略，由于每一階段常有很多方案可供選擇，因此，每一階段也能作出若干不同的決策.這樣各階段的各自很多不同決策就構成了許多不同的策略.由于每階段的不同決策其效果是不同的.因而由此所構成的不同策略的效果一般也不同，那么在諸多可供選擇的策略中，選擇哪一策略才能使一項待行的活動取得最佳效果？這類問題就是多階段決策問題.例8.1 100多年前，有位美國推銷員乘驛站馬車，經過不友好的印地安地區向東旅行

4、，雖然他的起點州A(state ,狀態)和目的地州E是固定的，但在途中要走過哪些州，卻有相當大的選擇余地.如圖8-1所示：2C1B16442D1343674 2343AEC2B2431D235C3B3 1 2 3 4 圖8-1 旅行線路圖他從州A出發，旅行至州E目的地，需要4個驛程（stage，階段），而從第1天開始每天都有不同的選擇，此推銷員是一個謹慎的人，十分關心他這次旅行中的安全，在經過一番思考后，他想到一個相當巧妙的辦法來確定他的最安全途徑，人身保險當時是很歡迎驛站乘客投保的，因為每張保險單（policy，策略）的收費是考慮了該行程的安全程度后訂出的，所以最安全的途徑應當是人身保險單最

5、低廉的途徑，設州i至州j的行程上，保險費記cij，如圖8-1所示.問題為求從 State A到 State E走哪條途徑使保險單的總費用達到最小？（如果把cij看成是距離，則問題是求AE的最短路）這是一個典型的多階段決策問題.值得注意的是，作出各相繼驛程上最佳決策.不一定產生總的最佳決策（即Greedy算法未必取得最佳策略）.如 A 2 B1 4 C2 3 D2 4 E 費用和為13而 A 3 B3 1 C2 更低廉求解該問題可以有以下兩種思路：方法一：窮舉法 即列出所有的可行路徑，逐個路徑進行比較，并從中選出最佳路徑.對于例8-1，分為4個階段：A B ( B1 , B2 , B3 )為第一

6、階段；3條路 B C ( C1 , C2 , C3 )為第二階段；3條路 C D ( D1 , D2 )為第三階段； 2條路 D E 為第四階段；1條路從而所有的可行路徑共有 33 2 1=18 最短路徑為 A 3 B3 1 C2 3 D2 4 E總費用（最短時間）為 11 .方法二：運用了如下常識性的結論：如果A=S1S2SkSnE 是AE的最短路，則該路上任一點SkSk+1SnE是SkE的最短路.（可以反證）利用該結論，我們構造求解方法.設Sk表示在第k個驛程上出發州的集合（狀態集合）， S1 = A， S2 = B1，B2，B3， S3 = C1，C2，C3，S4 = D1，D2； uk

7、(sk) = sk+1 表示在第k個驛程從 sk 出發所作的決策 , 如：u2(B1) = C1 或 C2 或 C3 ( C1，C2，C3 表示第k驛程從B1出發的允許決策集合) ；fk(sk) 表示從第k個驛程的出發州skE的最短路的費用和，f1(S1) 即為所求.顯然，求AE的最短路，可轉化為求三個性質完全相同、但規模較小的子問題，即分別從B1，B2，B3到E的最短路問題，若已知f2（B1）、f2（B2）、f2（B3），則 ，同樣，也可轉化為三個性質完全相同，但規模更小的子問題，依次類推，我們可從最后驛程開始，逆向求出AE的最短路.當k=4時， 當k=3時， 當k=2時， 當k=1時，沿決

8、策順推出來得最安全道路為AB3C2D2E，最小費用為11，這就是動態規劃求解方法的一般思想，由于求解過程與行進方向相反，所以稱為逆序解法.此方法的優點：減少計算量，以上過程僅用了18次加法，11次比較，計算效率遠高于窮舉法.豐富了計算結果，不僅求出AE的最短路徑，而且求出了任一中間點至E的最短路徑.由例8.1可知，動態規劃問題具有以下基本特征：1、 題具有多階段決策的特征.階段可以按時間劃分，也可以按空間劃分.2、 每一階段都有相應的“狀態”與之對應，描述狀態的量稱為“狀態變量”.3、 每一階段都面臨一個決策，選擇不同的決策將會導致下一階段不同的狀態，同時，不同的決策將會導致這一階段不同的目標

9、函數值.4、 每一階段的最優解問題可以遞歸地歸結為下一階段各個可能狀態的最優解問題，各子問題與原問題具有完全相同的結構.能否構造這樣的遞推歸結，是解決動態規劃問題的關鍵.這種遞推歸結的過程，稱為“ 不變嵌入”.例8.2 機器負荷分配問題某種機器可以在高低兩種不同負荷下進行生產，在高負荷下生產時，產品的年產量G和投入生產的機器數量X的關系為G=G（X），這時機器的年完好率為a，即如果年初完好的機器數量為X，到年終時完好的機器數就為aX（0a1）；在低負荷下生產時，產品的年產量H和投入生產的機器數量Y的關系為H=H（Y），機器的完好率b（0b1）且ab.假定開始生產時完好的機器數量為S1，要制定一

10、個五年計劃，確定每年投入高、低兩種負荷下生產的完好機器數量，使5年內產品的總產量達到最大.顯然，這是一個5階段的多階段決策問題.2動態規劃的基本概念和基本方程一、 動態規劃的基本概念1、階段. 階段（stage） 是對整個過程的自然劃分，為能應用動態規劃方法，首先必須根據實際問題所處的時間，空間或其他條件，把所研究的問題恰當地劃分成若干個相互聯系的階段.用k=1，2，n表示階段序號，把k稱為階段變量，如例8-1中，n=4，k=1，2，3，4.2、 狀態. 狀態（state） 表示每個階段開始時所面臨的自然狀況或客觀條件，既是該階段某一支路的始點，又是前一階段某一支路的終點.描述狀態的變量稱為狀

11、態變量，記作sk，它表示第k階段所處的狀態，狀態變量取值的全體，稱為允許狀態集合，記作Sk，顯然有skSk，如例1-1中，S1=A，S2=B1，B2，B3，etc，而s3可取B1，B2，B3.注意，作為動態規劃的狀態，應具有這樣的重要性質：如果某階段狀態給定后，則在這階段以后過程的發展不受這階段以前各段狀態的影響，換句話說，過程的過去歷史只能通過當前的狀態去影響它未來的發展，當前的狀態是以往歷史的一個總結，這個性質稱為無后效性（也稱為馬爾科夫性），（如在力的作用下的位移不考慮初速，則是有后效性的）.從例8.1的求解過程中可看出，是逐段逆推求解，如果不具有無后效性，就不可能在不知道前面狀態的情況

12、下逆推求解，所以必須正確選擇狀態變量，使它所確定的過程具有無后效性，否則不能用動態規劃方法.3、 決策.當某階段的狀態確定后，可以作出各種不同的選擇，從而確定下一階段的狀態，這種選擇稱為決策（decision），描述決策的變量稱為決策變量，可用一個數，一組數或向量描述，由于各階段的決策取決于狀態變量sk，所以常用uk（sk）表示第k階段當狀態處于sk時的決策變量，是狀態變量的函數.決策變量允許取值的范圍稱為允許決策集合，常用Dk（sk）表示第k階段從狀態sk出發的允許決策集合，顯然有uk（sk） Dk（sk）.在例8-1中，D1（A）=B1，B2，B3，D2（B1）=C1，C2，C3，等等.4

13、、策略.策略（policy）是一個按順序排列的決策組成的集合，由過程的第k階段開始到終止狀態為止的過程，稱為問題的后部子過程.由每階段的決策按順序排列組成的可行決策函數序列uk(sk) ，uk+1(sk+1)， un(sn) ，稱為k子過程策略，簡稱子策略，記為 pk，n（sk）= uk(sk)， uk+1(sk+1), ,un(sn) .當k=1時，此決策函數序列稱為全過程的一個策略，簡稱策略，記p1，n（s1）.可供選擇的策略有一定的范圍，稱為允許策略集合，用P1,n(s1) 表示，從P1,n(s1)中找出達到最優效果的策略稱為最優策略， p1,n*= p1,n*（s1）= u1*(s1)

14、 ，u2*(s2),，un*(sn) .例如，例8.1 中 P 表示了18條從 A到 E的不同途徑.5、狀態轉移方程. 狀態轉移方程（equation of state transition） 反映前后階段狀態之間的關系的方程. 能否成功地應用動態規劃方法，重要條件之一就是所設狀態變量和決策變量必須滿足：sk，uk(sk) 的取值一經確定，則下一段狀態變量sk+1的取值規律也能隨之確定，即sk+1與sk，uk之間必須能夠建立一種明確的數量對應關系， 記為：sk+1=Tk（sk，uk），稱為狀態轉移方程，利用它可將各階段的狀態變量用一個數學關系式聯系起來.如例8.1中sk+1= uk(sk).例

15、8.2 中uk表示第k階段投入高負荷的機器數，則：sk+1=auk+b（sk-uk）.6、指標函數和最優值函數. 指標函數（objective function）有階段的指標函數和過程的指標函數之分，階段的指標函數是對應某一階段狀態和從該狀態出發的一個階段的決策的某種效益度量，用vk（sk，uk）表示.過程指標函數（又稱目標函數）是用來衡量所實現過程優劣的一種數量指標，它是定義在全過程和所有后部子過程上的數量函數，記作Vk,n，即Vk,n=Vk,n（sk，uk，sk+1，uk+1，sn，un） (k=1,2,，n).當k=1時，就是全過程的指標函數，當初始狀態給定時，若過程的策略也確定了，因而

16、指標函數也是初始狀態和策略的函數, Vk,n=Vk,n（sk，pk,n（sk）.指標函數應具有可分離性，即Vk,n可表示為： Vk,n（sk，uk，sk+1，uk+1，sn，un）=且對于Vk+1，n嚴格單調.常見的指標函數的形式有：1 全過程和它的任一后部子過程的指標函數等于各階段指標函數之和，即： Vk,n（sk，uk，sk+1，uk+1，sn，un）=其中vj（sj，uj）表示第j階段的階段指標，也可表示為： 或 例1-1就是這樣的指標函數形式.2 全過程和它的任一后部子過程的指標函數等于各階段指標函數之積，即： .指標函數的最優值，稱為最優值函數（optimal value funct

17、ion），記fk(sk)，它表示從第k階段的狀態sk開始到第n階段的終點止狀態的過程，采取最優策略所得到的指標函數值，即： （8.1）（opt即optimization，具體問題可取min，max）或： （8.2）f1（s1）即為全過程的最優策略.二、動態規劃的最優化原理與最優性定理為了求最優策略，必須通過求指標函數的最優值即求fk（sk）才能確定，但是如果僅僅依據上面（8-1）或（8-2）式還是很難確定的，因為它們仍然是一個多變量的最優化問題，為了將多變量的決策問題轉化為多階段單變量的決策問題，50年代初，R.Bellman等人提出了如下“最優化原理”，作為動態規劃的理論基礎，它能解決許多類

18、型的多階段決策過程最優化的問題.動態規劃的最優化原理 作為整個過程的最優化策略應具有這樣的性質，即無論過去的狀態和決策如何，對于前面的決策所形成的狀態而言，余下的諸決策必須構成最優策略.簡言之，一個最優策略的子策略必須最優，根據最優化原理，可將一個多階段決策過程轉化為一個序貫決策過程，即把一個含有n個變量的決策問題轉化為n個單變量決策問題，當實現這種轉化，還需要滿足兩個基本條件，這就是指標函數的可分性和狀態變量的無后效性，但要注意，最優化原理僅僅是策略最優性的必要條件，不是普遍成立的.動態規劃的最優性定理 對于初始狀態s1S1，策略p1，n*=u1*，u2*，un* P1,n（s1）是最優策略

19、的充要條件是對于任意的k，10時，是一個連續的具有唯一最小值的單峰函數.k=2 ，對u2的不同取值計算得表8-11.表8-11 第二階段計算表u2s2f2（s2）u201234000018.568.147.086.857.116.853k=1 ， 對u1的不同取值計算得表8-12：表8-12 第一階段計算表u1s1f1（s1）u1012316.857.116.466.486.462 至此，求得最優策略是第一次生產2個，如果都不合格，則第二次生產3個，如果再都不合格，則第三次生產5個，這樣能使期望值費用最小，其期望費用為646元（近似值）.五、 裝載問題例8-7 有一艘貨船準備裝載N種貨物，已知

20、第j種貨物的單位重量為wj，其價值為vj，假如該貨船的最大載重量為W，要求確定每種貨物的裝載件數，在不超過最大載重允許的條件下，使貨船裝運物資的總價為最大.解：若用uj表示第j種貨物的裝載件數，則問題歸結為如下整數規劃問題： s.t. uj0且為整數為用動態規劃方法求解，先將此問題轉化為動態規劃模型，將裝載N種貨物看作依次分為N個階段，用j（j=1，2N）來代表階段，第j階段的狀態表示可用于第j，j+1，N階段的裝載重量，用Wj表示，用uj表示第j階段裝載第j種物資的件數，則ujWj/wj，（a表示a的最大整數部分）.狀態轉移可表示為Wj+1=Wj-wjuj，fj（Wj）表示在第j階段尚可裝載

21、Wj重量時，裝載第j，j+1，N種貨物的最大總價值，則遞推方程為： j = N, N-1, ,2,1若已知有關數據如表8-13， 且W=5，表8-13 有關數據jwjvj126523803130j=3 W3/w3=5/1=5 W3的可能取值為從0到5，計算得表8-14.表8-14 第三階段計算表 u3w330 u3f3（w3）u3*0123450000103030120306060230306090903403060901201204503060901201501505j=2 W2/w2=5/3=1 w2的可能取值為從0到5，計算得表8-15. u2W280 u2+f3（W2-3 u2）f2（

22、w2）u2*0100+0=00010+30=3030020+60=6060030+90=9080+0=8090040+120=12080=30=110120050+150=15080+60=1401500表8-15 第二階段計算表 j=1 W1/w1=5/2=2 計算得表8-16.表8-16 第一階段計算表 u1w165u1+f2（W1-2u1）f1（w1）u1*01250+150=15065+90=155130+30=1601602回代可得，當W1=5時，u1*=2，此時，W2= W1-2u1=1，故u2*=0，又W3= W2-3 u2=1，故u3*=1，f1（5）=160，見表8-17.表

23、8-17 第一階段計算表 j123wj511uj*201注意，若對每種貨物，只有裝與不裝（即uj=0或1，j=1N）兩種選擇，則該問題即為背包問題.六、背包問題所謂的背包問題是指對于N種具有不同重量和不同價值的物品，在攜帶物品總重量限制的情況下，決定這N種物品中每一種物品多少數量裝入背包內，使得裝入背包物品的總價值最大.例8.8 某咨詢公司有10個工作日可以去處理四種類型的咨詢項目，每種類型的咨詢項目中待處理的客戶數量、處理每個客戶所需工作日數以及所獲得的利潤如表8-18所示.顯然該公司在10天內不能處理完所有的客戶，它可以自己挑選一些客戶，其余的請其他咨詢公司去做，該咨詢公司應如何選擇客戶使

24、得在這10個工作日中獲利最大？表8-18咨詢項目類型待處理客戶數處理每個客戶所需工作日數處理每個客戶所獲利潤123443221347281120解：用動態規劃來求解此題.我們把此問題分成四個階段，第一階段我們決策將處理多少個第一種咨詢項目類型中的客戶，第二階段決策將處理多少個第二種咨詢項目類型中的客戶，第三階段、第四階段我們也將作出類似的決策.我們設=分配給第k種咨詢項目到第四種咨詢項目的所有客戶的總工作日（第k階段的狀態變量）.=在第k種咨詢項目中處理客戶的數量（第k階段的決策變量）.已知 ，并有 并從與的定義可知.從第四階段開始計算.K=4.顯然將個工作日（=0，1，10）盡可能分配給第四類咨詢項目，即時，第四階段的指標值為最大，其中，表示取不大于的最大整數，符號 為取整符號，故有 由于第四階段是最后的階段，故有因為至多為10，所以的取值為0或1，其數值計算見表8-19.表8-19 第四階段計算表 01000100200300400500600702018020190201100201第三階段：K=3.當把（=0，1，2，3，10）個工作日分配給第四類和第三類咨詢項目時，則對每個值，都有一種最優勢分配方案，使其最大盈利即最優3子過程最優指標函數值為：因為因為至多為10，