1、數學建模基礎數學建模基礎青島科技大學數理學院王天順 4 動態規劃動態規劃 4.1 多階段決策問題與動態規劃 4.2 動態規劃的基本概念 4.3 動態規劃的步驟 4.4 動態規劃的應用 1 求解靜態規劃問題 2 資源分配問題 3 不確定性采購問題 4 排序問題 例2 機器負荷分配問題 某種機器可以在高低兩種不同的負荷下進行生產在高負荷下進行生產時，產品的年產量g和投入生產的機器數量u的關系為 gg(u), 這時機器的年完好率為a（0a1)在低負荷下生產時，產品的年產量h和投入生產的機器數量v的關系為hh(v), 這時機器的年完好率為b（ab1）假定開始生產時完好的機器數量為s1，要求制定一個五年

2、計劃,在每年開始時決定機器在兩種不同負荷下生產的數量,使五年內產品的總產量最高。4.1 多階段決策問題與動態規劃例1最短路問題以上兩個問題都可以劃分為先后多個決策階段。這類問題就稱為多階段決策問題。多階段決策問題的過程如下圖所示： 狀態狀態狀態狀態決策決策決策狀態 多階段決策問題和我們前面遇到的決策問題不同，它是和時間有關的。與時間有關的活動過程稱為動態過程，其優化方法稱為動態規劃。而與時間無關的活動過程稱為靜態過程，相應的優化方法稱為靜態規劃。 (1)階段（stage）把所研究的決策問題，按先后順序劃分為若干相互聯系的決策步驟，以便按一定的次序進行求解。描述階段的變量稱階段變量，常用k表示。

3、 (2)狀態（state）狀態表示每個階段開始時所處的自然狀況或客觀條件，它描述了影響決策的因素隨決策進程的變化情況，它既是前面階段所作決策的結果，又是本階段作出決策的出發點和依據。描述狀態的變量稱為狀態變量，第k階段的狀態變量常用sk表示。通常，在第一階段狀態變量s1是確定的，稱初始狀態。 (3)決策（decision）決策表示在某一階段處于某種狀態時，決策者在若干種方案中作出的選擇決定。描述決策的變量稱決策變量，第k階段的決策變量常用uk表示。決策變量的取值會受到狀態變量的制約，被限制在某一范圍之內。4.2 動態規劃的基本概念（一） (4)策略（policy）把從第一階段開始到最后階段終止

4、的整個決策過程，稱為問題的全過程；而把從第k階段開始到最后階段終止的決策過程，或稱為k子過程。在全過程上，各階段的決策按順序排列組成的決策序列p1,n u1,u2,un 稱為全過程策略，簡稱策略；而在k子過程上的決策序列pk,n uk,uk+1,un 稱為k子過程策略，也簡稱子策略。 (5)狀態轉移方程 若第k階段的狀態變量值為sk，當決策變量uk的取值決定后，下一階段狀態變量sk+1的值也就完全確定。即sk+1的值對應于sk和uk的值。這種對應關系記為sk+1Tk(sk,uk)，稱為狀態轉移方程。狀態轉移方程描述了由一個階段的狀態到下一階段的狀態的演變規律。4.2 動態規劃的基本概念（二）

5、(6)指標函數和最優值函數 指標函數分為階段指標函數和過程指標函數。階段指標函數是對某一階段的狀態和決策產生的效益值的度量，用vk(sk,uk)表示。過程指標函數是指過程所包含的各階段的狀態和決策所產生的總的效益值，記為 Vk,nVk,n(sk,uk,sk+1,uk+1,sn,un) 動態規劃所要求的過程指標函數應具有可分離性，即可表達為它所包含的各階段指標函數的函數形式。常見的兩種過程指標函數形式是： 各階段指標函數的和 Vk,nvj(sj,uj)； 各階段指標函數的積 Vk,nvj(sj,uj)。 把過程指標函數Vk,n對k子過程策略pk,n求最優，得到一個關于狀態sk的函數，稱為最優值函

6、數，記為fk(sk)。即 fk(sk) opt Vk,n(sk,uk,sn,un) uk,un式中的“opt”（optimization）可根據具體問題而取min或max。 (7)基本方程 通常動態規劃問題的最優值函數滿足遞推關系式。設過程指標函數為各階段指標函數的和的形式，即Vk,nvj(sj,uj)，則有 fk(sk) opt vk(sk,uk)+fk+1(sk+1) ukDk(sk) (kn,n-1,1) 遞推方程 fn+1(sn+1)0 邊界條件遞推方程和邊界條件一起稱為動態規劃的基本方程。 可根據邊界條件，從k=n開始，由后向前逆推，逐步求得各階段的最優決策和相應的最優值，最后求出f

7、1(s1)時，就得到整個問題的最優解。 例 最 短 路 問 題此問題的基本方程為此問題的基本方程為f fk k(s(sk k) )MindMindk k(u(uk k)+f)+fk+1k+1(s(sk+1k+1) ) u uk kDDk k(s(sk k) ) k k6,5,4,3,2,16,5,4,3,2,1f f7 7(s(s7 7) )0 04.3 動態規劃的步驟（一）動態規劃的步驟（一）當k=6時s s6 6 u u6 6 D D( (u u6 6) )+ +f f7 7( (s s7 7) ) F F6 6( (s s6 6) ) F F1 1 F F1 1G G 4 4+ +0 0

8、= =4 4* * 4 4 F F2 2 F F2 2G G 3 3+ +0 0= =3 3* * 3 3 按基本方程由后向前繼續遞推有按基本方程由后向前繼續遞推有:當k=5時當k=4時s s4 4 u u4 4 d d( (u u4 4) )+ +f f5 5( (s s5 5) ) f f4 4( (s s4 4) ) D D1 1 D D1 1E E1 1 D D1 1E E2 2 2 2+ +7 7= =9 9 2 2+ +5 5= =7 7* * 7 7 D D2 2 D D2 2E E2 2 D D2 2E E3 3 1 1+ +5 5= =6 6* * 2 2+ +9 9= =1

9、 11 1 6 6 D D3 3 D D3 3E E2 2 D D3 3E E3 3 3 3+ +5 5= =8 8* * 3 3+ +9 9= =1 12 2 8 8 s s5 5 u u5 5 d d( (u u5 5) )+ +f f6 6( (s s6 6) ) f f5 5( (s s5 5) ) E E1 1 E E1 1F F1 1 E E1 1F F2 2 3 3+ +4 4= =7 7* * 5 5+ +3 3= =8 8 7 7 E E2 2 E E2 2F F1 1 E E2 2F F2 2 5 5+ +4 4= =9 9 2 2+ +3 3= =5 5* * 5 5 E

10、 E3 3 E E3 3F F1 1 E E3 3F F2 2 6 6+ +4 4= =1 10 0 6 6+ +3 3= =9 9* * 9 9 當當k=3時時s s3 3 u u3 3 d d( (u u3 3) )+ +f f4 4( (s s4 4) ) f f3 3( (s s3 3) ) C C1 1 C C1 1D D1 1 C C1 1D D2 2 6 6+ +7 7= =1 13 3* * 8 8+ +6 6= =1 14 4 1 13 3 C C2 2 C C2 2D D1 1 C C2 2D D2 2 3 3+ +7 7= =1 10 0* * 5 5+ +6 6= =1

11、 11 1 1 10 0 C C3 3 C C3 3D D2 2 C C3 3D D3 3 3 3+ +6 6= =9 9* * 3 3+ +8 8= =1 11 1 9 9 C C4 4 C C4 4D D2 2 C C4 4D D3 3 8 8+ +6 6= =1 14 4 4 4+ +8 8= =1 12 2* * 1 12 2 當當k=2時時當當k=1時時s s2 2 u u2 2 d d( (u u2 2) )+ +f f3 3( (s s3 3) ) f f2 2( (s s2 2) ) B B1 1 B B1 1C C1 1 B B1 1C C2 2 B B1 1C C3 3 1

12、 1+ +1 13 3= =1 14 4 3 3+ +1 10 0= =1 13 3* * 6 6+ +9 9= =1 15 5 1 13 3 B B2 2 B B2 2C C2 2 B B2 2C C3 3 B B2 2C C4 4 8 8+ +9 9= =1 17 7 7 7+ +9 9= =1 16 6* * 6 6+ +1 12 2= =1 18 8 1 16 6 s s1 1 u u1 1 d d( (u u1 1) )+ +f f2 2( (s s2 2) ) f f1 1( (s s1 1) ) A A A AB B1 1 A AB B2 2 5 5+ +1 13 3= =1 1

13、8 8* * 3 3+ +1 16 6= =1 19 9 1 18 8 由此可以看出，由此可以看出，A到到G的最短路長為的最短路長為18，路徑為：，路徑為： AB1C2D1E2F2G現在把動態規劃法的步驟歸納如下：現在把動態規劃法的步驟歸納如下：(1) (1) 將所研究問題的過程劃分為將所研究問題的過程劃分為n n個恰當的階段，個恰當的階段， k k 1,2,n 1,2,n；(2) (2) 正確地選擇狀態變量正確地選擇狀態變量S Sk k，并確定初始狀態并確定初始狀態S S1 1的值；的值；(3) (3) 確定決策變量確定決策變量u uk k以及各階段的允許決策集以及各階段的允許決策集D Dk

14、 k(S(Sk k) )；(4) (4) 給出狀態轉移方程；給出狀態轉移方程；(5) (5) 給出滿足要求的過程指標函數給出滿足要求的過程指標函數V Vk,nk,n及相應的最優及相應的最優 值函數；值函數；(6) (6) 寫出遞推方程和邊界條件，建立基本方程；寫出遞推方程和邊界條件，建立基本方程；(7) (7) 按照基本方程遞推求解。按照基本方程遞推求解。 以上步驟是動態規劃法處理問題的基本步驟，其以上步驟是動態規劃法處理問題的基本步驟，其中的前六步是建立動態規劃模型的步驟。中的前六步是建立動態規劃模型的步驟。4.3 動態規劃的步驟（二）動態規劃的步驟（二）例：機器負荷問題例：機器負荷問題 某

15、種機器可以在高低兩種不同的負荷下進行生產在高負荷下進行生產時，產品的年產量g和投入生產的機器數量u的關系為 g8u, 這時機器的年完好率為a=0.7在低負荷下生產時，產品的年產量h和投入生產的機器數量v的關系為h5v, 這時機器的年完好率為b=0.9假定開始生產時完好的機器數量為s1，要求制定一個五年計劃,在每年開始時決定機器在兩種不同負荷下生產的數量,使五年內產品的總產量最高。(1)按年數劃分為5個階段，k=1,2,3,4,5(2)取第k年初完好的機器數sk為狀態變量, s1=1000(3)取第k年投入高負荷的機器數xk為決策變量, 0 xksk(4)狀態轉移方程為 sk+1=0.7xk+0

16、.9(sk-xk)=0.9sk-0.2xk(5)指標函數為Vk,5=8xj+5(sj-xj)=(5sj+3xj)(6)基本方程為 fk(sk) max 5sj+3xj +fk+1(sk+1) k=5,4,3,2,1 0 xksk f6(s6)0解:當k=5時f5(s5) max5s5+3x5+f6(s6)= max5s5+3x5=8s5 (x5*=s5) 0 x5s5 0 x5s5當k=4時f4(s4)max5s4+3x4+8s5=max5s4+3x4+8(0.9s4-0.2x4) 0 x4s4 0 x4s4 = max12.2s4+1.4x4=13.6s4 (x4*=s4) 0 x4s4當k

17、=3時f3(s3)max5s3+3x3+13.6s4=max5s3+3x3+13.6(0.9s3-0.2x3) 0 x3s3 0 x3s3 = max17.24s3+0.28x3=17.5s3 (x3*=s3) 0 x3s3當k=2時f2(s2)=max5s2+3x2+17.52s3=max5s2+3x2+17.52(0.9s2-0.2x2) 0 x2s2 0 x2s2 = max20.77s2-0.504x2=20.7s4 (x2*=0) 0 x2s2當k=1時f1(s1)=23.7s1 (x1*=0)f1(1000)=23700s1=1000, x1*=0s2=900, x2*=0s3=8

18、10, x3*=810s4=576, x4*=576s5=397, x5*=397 某些靜態規劃問題可用動態規劃法來求解。某些靜態規劃問題可用動態規劃法來求解。 例例 用動態規劃法求解用動態規劃法求解 max z=x12.x22.x3 x1+x2+x3=c xi0 i=1,2,34.4 動態規劃的應用動態規劃的應用(一一) 1 求解靜態規劃問題求解靜態規劃問題 資源分配問題可描述如下：設有某種原料，資源分配問題可描述如下：設有某種原料，總數量為總數量為a，分配給，分配給n個使用者。已知第個使用者。已知第i個使用個使用者得到數量者得到數量xi的資源，可創造的收益為的資源，可創造的收益為gi（xi

19、）。）。問應如何分配該資源，才能使總收益最大。問應如何分配該資源，才能使總收益最大。4.4 動態規劃的應用動態規劃的應用(二二) 用動態規劃法處理這種問題時，通常把給一用動態規劃法處理這種問題時，通常把給一個使用者分配資源的過程看成一個階段，按個使用者分配資源的過程看成一個階段，按n n個使用者分成先后個使用者分成先后n n個決策階段。即先給第個決策階段。即先給第1 1個個使用者分配資源，為第一階段；再給第使用者分配資源，為第一階段；再給第2 2個使個使用者分配，為第用者分配，為第2 2階段；依此類推，最后給第階段；依此類推，最后給第n n個使用者分配，為第個使用者分配，為第n n階段。階段。

20、 2 資源分配問題資源分配問題 例例 某工業部門根據國家計劃安排，擬將某工業部門根據國家計劃安排，擬將五臺某種高效率的機器分配給所屬的甲、五臺某種高效率的機器分配給所屬的甲、乙、丙三個工廠，各工廠得到不同數量的乙、丙三個工廠，各工廠得到不同數量的機器可獲得的收益如下表。問應如何分配機器可獲得的收益如下表。問應如何分配機器，才能使各廠的總效益最大。機器，才能使各廠的總效益最大。 工工廠廠機機器器數數 甲甲 乙乙 丙丙0 01 12 23 34 45 50 0 0 0 0 03 3 5 5 4 4 7 7 1 10 0 6 6 9 9 1 11 1 1 11 1 1 12 2 1 11 1 1 1

21、2 2 1 13 3 1 11 1 1 12 2 某單位準備在以后的某單位準備在以后的n n個時期內采購一批物資。各個時期內采購一批物資。各時期的價格不是確定的，而是按照某種已知的概率分時期的價格不是確定的，而是按照某種已知的概率分布取值。試制定采購策略，確定在哪一時期以什么價布取值。試制定采購策略，確定在哪一時期以什么價格采購，能使采購價的數學期望值最低。這類問題也格采購，能使采購價的數學期望值最低。這類問題也適合用動態規劃法進行處理。下面通過實例加以說明。適合用動態規劃法進行處理。下面通過實例加以說明。例例7 7 某廠生產上需要在近五周某廠生產上需要在近五周內采購一批原料，而估計在未內采購

22、一批原料，而估計在未來五周的價格有波動，其浮動來五周的價格有波動，其浮動價格和概率策得如下表。試確價格和概率策得如下表。試確定該廠應在哪一周以什么價格定該廠應在哪一周以什么價格購入，能使其采購價的數學期購入，能使其采購價的數學期望值最小，并求出期望值。望值最小，并求出期望值。價價 格格 概概 率率 5 50 00 0 6 60 00 0 7 70 00 00 0. . 3 30 0. . 3 30 0. .4 44.4 動態規劃的應用(三) 3 不確定性采購問題 設有n個工件需要在機床A、B上加工，每個工件都必須先經過A而后B兩道加工工序。以ai、bi分別表示工件i(1in)在A、B上的加工時間。問應如何在兩機床上安排各工件的加工順序，使在機床A上加工第一個工件開始到在機床B上加工完最后一個工件為止，所用的加工總時間最少？ 加工工件在機床A上有加工順序問題，在機床B上也有加工順序問題。可以證明：最優加工順序在兩臺機床上可同時實現。因此，最優排序方案可以只在機床A、B上加工順序相同的排序中尋找。即使如此，所有可能的方案仍有n!個，這是一個不小的數