1、第第8章章 動態規劃動態規劃 Dynamic Programming華國偉華國偉北京交通大學物流管理系北京交通大學物流管理系內容提要內容提要1.多階段決策過程及實例多階段決策過程及實例2.動態規劃的基本概念和基本方程動態規劃的基本概念和基本方程3.動態規劃的最優性原理和最優性定理動態規劃的最優性原理和最優性定理4.動態規劃和靜態規劃的關系動態規劃和靜態規劃的關系5.動態規劃應用舉例動態規劃應用舉例重點：重點： 理解動態規劃基本概念、最優化原理和基本方程理解動態規劃基本概念、最優化原理和基本方程; ; 通過通過資源分配、資源分配、生產與存儲和設備更新等問題生產與存儲和設備更新等問題, ,學習學習

2、 應用動態規劃解決多階段決策問題應用動態規劃解決多階段決策問題; ; 重點掌握動態規劃模型結構、逆序算法原理、資源重點掌握動態規劃模型結構、逆序算法原理、資源 分配問題、生產與存儲問題分配問題、生產與存儲問題. . 難點難點為動態規劃中為動態規劃中狀態變量、基本方程狀態變量、基本方程等的確定等的確定. . 動態規劃產生于動態規劃產生于20世紀世紀50年代年代, 美國數學美國數學家貝爾曼家貝爾曼(R. Bellman)等人提出等人提出. 動態規劃是求解某類問題的動態規劃是求解某類問題的一種方法一種方法, ,是是考察問題的一種考察問題的一種途徑途徑, ,而而不是一種算法不是一種算法. .必必須對具

3、體問題進行具體分析須對具體問題進行具體分析, ,運用動態規運用動態規劃的原理和方法劃的原理和方法, ,劃分階段劃分階段, ,建立相應的模建立相應的模型型, ,然后再去求解然后再去求解. . 動態規劃是用來解決動態規劃是用來解決多階段決策多階段決策過程最優化過程最優化的一種數量方法的一種數量方法. .其其特點特點在于在于, ,它可以把一個它可以把一個多階段決策問題變換為幾個相互聯系的同類多階段決策問題變換為幾個相互聯系的同類型單階段最優化問題型單階段最優化問題, ,從而一個一個地去解從而一個一個地去解決決. .1. 多階段決策過程及實例多階段決策過程（序貫決策過程）12n決策決策決策狀態狀態狀態

4、狀態狀態收益收益收益2 多階段決策問題多階段決策問題舉例舉例(1) 時間階段時間階段例例1 機器負荷分配問題機器負荷分配問題1x1v1S1=1000臺臺S22x2v2S33x3v3S44x4v4S55x5v5其中：其中：xi各年度不同負荷機器的臺數（向量）；各年度不同負荷機器的臺數（向量）； vi產量產量建模？建模？求解？求解？AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643123456(2) 空間階段空間階段圖中所示為從圖中所示為從A到到G的路線網絡的路線網絡, 圖中數字表示相應圖中數字表示相應線路的長度線路的長度, 如

5、何求出從如何求出從A到到G的最短路線？的最短路線？（窮舉法（窮舉法4848條路線）條路線）AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G53136876683533842212333552663123456375976813109121316 184AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G5313687668353384221233355266312345615131315111313681095318174AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G453136876683533822123335526643123456 最短路的特性：最短路

6、的特性： 如果已有從起點到終點的一條最短路，那么從如果已有從起點到終點的一條最短路，那么從最短路線上中間任何一點出發到終點的路線仍然是最短路線上中間任何一點出發到終點的路線仍然是最短路。（證明用反證法）最短路。（證明用反證法）1 1 動態規劃的研究對象和引例動態規劃的研究對象和引例動態系統動態系統： 包含隨包含隨時間變化時間變化的因素和變量的系統。的因素和變量的系統。動態決策問題動態決策問題： 系統所處的狀態和時刻是進行決策的重要因素系統所處的狀態和時刻是進行決策的重要因素. .找到不同時刻的最優決策以及整個過程的最優策略找到不同時刻的最優決策以及整個過程的最優策略. .1 12 2n n狀態

7、狀態決策決策狀態狀態決策決策狀態狀態狀態狀態決策決策全過程的最優全過程的最優階段階段 1、 生產決策問題生產決策問題 企業在生產過程中，由于需求是隨時間變化的，企業在生產過程中，由于需求是隨時間變化的，因此企業為了獲得全年的最佳生產效益，就要在整因此企業為了獲得全年的最佳生產效益，就要在整個生產過程中逐月或逐季度地個生產過程中逐月或逐季度地根據庫存和需求決定根據庫存和需求決定生產計劃。生產計劃。多階段決策問題的典型例子多階段決策問題的典型例子 2、機器負荷分配問題、機器負荷分配問題某種機器某種機器高負荷高負荷低負荷低負荷g=g(u1)產品的年產量產品的年產量投入生產的機投入生產的機器數量器數量

8、機器的年完好率為機器的年完好率為a ，0a1h=h(u2)機器的年完好率為機器的年完好率為b ，0 b1年終完好年終完好的機器？的機器？ 假定開始生產時完好的機器數量為假定開始生產時完好的機器數量為s1。要求制定。要求制定一個一個n年計劃，在年計劃，在每年開始時，決定如何重新分配每年開始時，決定如何重新分配完好完好的的機器在兩種不同的負荷下生產的數量機器在兩種不同的負荷下生產的數量，使在，使在n年內產年內產品的總產量達到最高。品的總產量達到最高。 3、線性規劃、非線性規劃線性規劃、非線性規劃等靜態的規劃問題也等靜態的規劃問題也可以通過適當地引入階段的概念，應用動態規劃方法可以通過適當地引入階段

9、的概念，應用動態規劃方法加以解決。加以解決。 不包含時間因素的靜態決策問題（一次決策問不包含時間因素的靜態決策問題（一次決策問題）也可以適當地引入階段的概念，作為多階段的題）也可以適當地引入階段的概念，作為多階段的決策問題用動態規劃方法來解決。決策問題用動態規劃方法來解決。 4、最短路問題（引例）最短路問題（引例）：給定一個交通網絡圖如給定一個交通網絡圖如前，其中兩點之間的數字表示距離（或花費），試求前，其中兩點之間的數字表示距離（或花費），試求從從A點到點到G點的最短距離（總費用最小）。點的最短距離（總費用最小）。動態規劃的基本概念1. 階段2. 狀態3. 決策4. 策略5. 狀態轉移方程6

10、. 指標函數和最優值函數建模建模AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G5313687668353384221233355266431234562 2 動態規劃的基本概念和定義動態規劃的基本概念和定義1、階段、階段變量階段、階段變量 把所給問題的過程，適當（按把所給問題的過程，適當（按時間和空間時間和空間）地分）地分為若干個相互聯系的為若干個相互聯系的階段階段；描述階段的變量稱為；描述階段的變量稱為階段階段變量變量，常用，常用 k 表示。表示。2、狀態、狀態變量狀態、狀態變量每個階段開始所處的自然狀態或客觀條件每個階段開始所處的自然狀態或客觀條件, ,描述過程描述過程的狀況

11、的狀況, ,通常一個階段有若干個狀態通常一個階段有若干個狀態. .AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G453136876683533822123335526643123456描述過程狀態的變描述過程狀態的變量稱為量稱為狀態變量狀態變量，它可用一個數、一它可用一個數、一組數或一向量來描組數或一向量來描述述, 常用常用 sk 表示第表示第 k 階段的狀態階段的狀態.s2=?狀態允許集合狀態允許集合，狀態變量的取值允許集合或范圍。狀態變量的取值允許集合或范圍。 在最優控制中也稱為在最優控制中也稱為控制控制.3、決策、決策變量決策、決策變量某一階段、某個狀態某一階段、某個狀態,

12、 ,可以做出不同的決定可以做出不同的決定( (選擇選擇),),決決定下一階段的狀態定下一階段的狀態, ,這種決定稱為這種決定稱為決策決策. .AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G453136876683533822123335526643123456決策變量決策變量, 描述決策的變量描述決策的變量.uk(sk), 表示第表示第 k 階段當狀階段當狀態為態為 sk 時的決策變量時的決策變量. 允許決策集合允許決策集合，常用常用Dk(sk)表示第表示第k階階段從狀態段從狀態sk出發的允許出發的允許決策集合決策集合. .uk(sk) Dk(sk)D2(B1)?AB1B2C1C

13、2C3C4D1D2D3E1E2E3F1F2G453136876683533822123335526643123456系統當前的系統當前的狀態和決策狀態和決策4、多階段決策過程多階段決策過程在每個階段進行決策在每個階段進行決策 控制過程的發展；控制過程的發展；其發展是通過一系列的其發展是通過一系列的狀態轉移狀態轉移來實現的；來實現的；系統過去的歷系統過去的歷史狀態和決策史狀態和決策B1C1s2=T1(s1, u1)s3=T2(s1, u1, s2, u2) sk+1=Tk(s1, u1, s2, u2 , sk, uk)狀態轉移方程狀態轉移方程的一般形式的一般形式s1=A,u1=B1,s2=?1

14、2ks1u1s2u2s3skuksk+1 能用動態規劃方法求解的多階段決策過程是一能用動態規劃方法求解的多階段決策過程是一類特殊的多階段決策過程，即具有類特殊的多階段決策過程，即具有無后效性無后效性的多階的多階段決策過程段決策過程。圖示如下：圖示如下：5、無后效性或馬爾可夫性、無后效性或馬爾可夫性 如果某階段狀態給定后，則在這個階段以后過程如果某階段狀態給定后，則在這個階段以后過程的發展不受這個階段以前各階段狀態的影響；過程的的發展不受這個階段以前各階段狀態的影響；過程的過去歷史只能通過當前的狀態去影響它未來的發展。過去歷史只能通過當前的狀態去影響它未來的發展。 構造動態規劃模型時，要充分注意

15、構造動態規劃模型時，要充分注意狀態變量狀態變量是否是否滿足無后效性的要求；滿足無后效性的要求；狀態轉移方程？狀態轉移方程？ 狀態具有無后效性的多階段決策過程的狀態轉狀態具有無后效性的多階段決策過程的狀態轉移方程如下：移方程如下：s2=T1(s1, u1) s3=T2(s2, u2) sk+1=Tk(sk, uk)AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G453136876683533822123335526643123456 由每段的決策按順序排列組成的決策函數序列稱由每段的決策按順序排列組成的決策函數序列稱為為 k 子過程策略。簡稱子過程策略。簡稱子策略子策略，記為，記為p

16、k,n(sk)，即，即，Pk,n(sk)=uk(sk),uk+1(sk+1), ,un(sn)C1D1E1F1G6、策略、策略按順序排列的決策組成的集合。按順序排列的決策組成的集合。 由過程的第由過程的第k 終止狀態為止的過程，稱為問題終止狀態為止的過程，稱為問題的的后部子過程后部子過程（k 子過程）。子過程）。AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G453136876683533822123335526643123456允許策略集合允許策略集合，可供選擇的策略范圍，用可供選擇的策略范圍，用 P 表示。表示。最優策略最優策略，達到最優效果的策略。達到最優效果的策略。 當當

17、k =1時，此決策函數序列成為全過程的一個策時，此決策函數序列成為全過程的一個策略，簡稱略，簡稱策略策略，記為，記為p1,n (s1)，即，即P1,n(s1)=u1(s1), u2(s2), , un(sn)AB1C1D1E1F1G7、指標函數和最優值函、指標函數和最優值函數數 指標函數，指標函數，用來衡量所實現過程優劣的一種數量用來衡量所實現過程優劣的一種數量指標，它是定義在全過程或所有后部子過程上確定指標，它是定義在全過程或所有后部子過程上確定的數量函數。用的數量函數。用 Vk, n 表示。表示。 Vk, n= Vk, n (sk, uk , sk+1, uk+1 , , sn+1), k

18、 =1,2, ,nAB1B2C1C2C3C4D1D2D3E1E2E3F1F2G453136876683533822123335526643123456 動態規劃模型動態規劃模型的指標函數，應具的指標函數，應具有可分離性，并滿有可分離性，并滿足足遞推遞推關系。關系。即即Vk, n可以表示為可以表示為 sk, uk,Vk+1, n 的函數。的函數。常見的指標函數的形式是：常見的指標函數的形式是： 過程和它的任一子過程的指標是它所包含的各階過程和它的任一子過程的指標是它所包含的各階段的指標段的指標和和。即。即無后效性無后效性的結果的結果nkjjjjnkknkusvsusV),(),(1, 其中其中V

19、(sj, uj ) 表示第表示第 j 階段的階段的階段指標階段指標。這時上。這時上式可寫成式可寫成 Vk, n(sk ,uk , sn+1) = vk(sk ,uk)+ Vk+1, nV5, 6= V5, 6 (s5, u5, V6, 6 ) =d5(s5,u5)+ V6, 6 AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G453136876683533822123335526643123456 過程和它的任意子過程的指標是它所包含的過程和它的任意子過程的指標是它所包含的各階段的指標的各階段的指標的乘積乘積。即。即可改寫成可改寫成Vk, n(sk ,uk , sn+1) = vk

20、(sk ,uk) Vk+1, n(sk+1, uk+1, , sn+1)nkjjjjnkknkusvsusV),(),(1, 指標函數的最優值，記為指標函數的最優值，記為 fk (sk)。表示從第。表示從第 k 階階段的狀態段的狀態 sk 到第到第 n 階段的終止狀態的采取最優策略階段的終止狀態的采取最優策略所得到的指標函數值。即所得到的指標函數值。即最優值函數：最優值函數：),()(1,nkknkuukksusVoptsfnkAB1B2C1C2C3C4D1D2D3E1E2E3F1F2G453136876683533822123335526643123456f6 (s6)=？f6 (F1)=4

21、f6 (F2)=3f5 (E1)=？全過程的最優值函數記為全過程的最優值函數記為 f1 (s1)多階段決策過程的數學模型多階段決策過程的數學模型: (具有無后效性具有無后效性, 以和式為例以和式為例)Vk, n(sk , uk , , sn+1)=j=knvj(sj, uj) optu1, u2,unsk+1=Tk(sk, uk) skSkukDkk=1,2, ,ns.t.小結小結: :方程方程: :狀態轉移方程狀態轉移方程),(1kkkkusTs概念概念: :階段變量階段變量 k狀態變量狀態變量 sk決策變量決策變量 uk ; ;動態規劃本質上是多階段決策過程動態規劃本質上是多階段決策過程;

22、 ; 效益效益指標函數形式指標函數形式: : 和、積和、積無后效性無后效性可遞推可遞推指標指標: : Vk, n= Vk, n (sk, uk , sk+1, uk+1 , , sn+1) fk (sk)= opt Vk, n(sk , uk , sn+1)uk , , un= k sk , uk ,Vk+1, n (sk+1, uk+1 , , sn+1)解多階段決策過程問題，應求出：解多階段決策過程問題，應求出：最優策略：最優策略：最優目標函數值：最優目標函數值：u1* , u2* , , un*s1* , s2* , , sn*即最優決策序列即最優決策序列即執行最優策略時的狀態序列即執行

23、最優策略時的狀態序列f1(s1)=?最優軌線：最優軌線：3 3 動態規劃的基本思想和基本方程動態規劃的基本思想和基本方程（窮舉法（窮舉法4848條路線）條路線）AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G453136876683533822123335526643123456最短路的特性：最短路的特性： 如果已有從起點到終點的一條最短路，那么從如果已有從起點到終點的一條最短路，那么從最短路線上中間任何一點出發到終點的路線仍然是最短路線上中間任何一點出發到終點的路線仍然是最短路。（證明用反證法）最短路。（證明用反證法）k=5，出發點有，出發點有 E1, E2, E373543mi

24、n)(),()(),(min)(262151611515 FfFEdFfFEdEfu5(E1)=F1E1F1Gu5(E2)=F2E2F2Gk=6， F1 G，f6(F1)=4 F2 G，f6(F2)=3u5(E3)=F2E3F2GAB1B2C1C2C3C4D1D2D3E1E2E3F1F2G45313687668353382212333552664353245min)(),()(),(min)(262251612525 FfFEdFfFEdEf93646min)(),()(),(min)(262351613535 FfFEdFfFEdEfk=3 f3(C1)=13 u3(C1)=D1 f3(C2

25、)=10 u3(C2)=D1f3(C3)=9 u3(C3)=D2f3(C4)=12 u3(C4)=D3 k=2 f2(B1)=13 u2(B1)=C2 f2(B2)=10 u2(B2)=C3k=4 f4(D1)=7 u4(D1)=E2 f4(D2)=6 u4(D2)=E2f4(D3)=8 u4(D3)=E2AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G4531368766835338221233355266435+133+16= mink=1 f1(A) = 18 = mind1(A,B1)+ f2(B1)d1(A,B2)+ f2(B2) u1(A)=B1最優決策函數序列最優決策

26、函數序列uk ： AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643最優最優策略策略最短路線為最短路線為 AB1 1C2 2D1 1E2 2F2 2Gu1(A)=B1, u2(B1)=C2, u3(C2)=D1, u4(D1)=E2, u5(E2)=F2, u6(F2)=G動態規劃基本方程動態規劃基本方程fk ( sk ) = opt vk (sk , uk ( sk ) + fk+1(sk+1 )uk Dk (sk)fn+1 ( sn+1) = 0 （邊界條件邊界條件）求解的各個階段求解的各個階段,我們利用了我們利用了k

27、階段與階段與 k+1 階段之階段之間的遞推關系間的遞推關系:f 7(s7) = 0fk ( sk ) = min dk (sk , uk ( sk ) + fk+1(sk+1 ) uk Dk (sk)k = 6, 5, 4, 3, 2, 1動態規劃基本方程動態規劃基本方程fk ( sk ) = opt vk (sk , uk ( sk ) * fk+1(sk+1 )uk Dk (sk)fn+1 ( sn+1) = 1 （邊界條件邊界條件）練習AB1B2B3C1C2C3D1D2E25112146104121139658105213最優性原理最優性原理( (R. Bellman ) )：“一個過程

28、的最優策略具有這樣的性質：即無論其一個過程的最優策略具有這樣的性質：即無論其初始狀態及初始決策如何，對于先前決策所形成的初始狀態及初始決策如何，對于先前決策所形成的狀態而言，余下的諸決策仍構成最優策略。狀態而言，余下的諸決策仍構成最優策略。”一個最優策略的子策略也是最優的。一個最優策略的子策略也是最優的。 最優策略的任何一部分最優策略的任何一部分子策略子策略，也是它相應初，也是它相應初始狀態的最優策略。每個最優策略只能由最優子策始狀態的最優策略。每個最優策略只能由最優子策略構成。略構成。含義含義動態規劃的理論基礎動態規劃的理論基礎 ),(),(),(1,1,)(1, 001, 0)(*1, 0

29、01, 01,1,01,01,0psVoptpsVoptpsVnkknkkknnsPpsPpknknkkk 動態規劃的最優性定理動態規劃的最優性定理：設階段數為：設階段數為 n 的多階段決的多階段決策過程，其階段編號為策過程，其階段編號為k=0,1,.,n-1。允許策略。允許策略p*0, n-1= ( u*0, u*1, , u*n-1 )是最優策略的是最優策略的充要條件充要條件是是: 對任意一個對任意一個 k, 0 k n-1和和 s0 S0，有，有),(111 kkkkusTs),(1,1, 01, 0 nkknppp0,100,1,1,1*0,100,100,10,1(),1,1()(,

30、)(,)(,)minminkkk nkk nnknkk nkk npsPpsPppVsVspVsAB1B2C1C2C3C4D1D2D3E1E2E3F1F2G5313687668353384221233355266301234515131315111313681095318174 推論推論：若允許策略：若允許策略 p*0, n-1 是最優策略，則對任意是最優策略，則對任意的的 k ，0 k 0332113310211330( )max29(10)200( )max29(10)90 xxf sxxf sxx（最優決策）（最優決策）2222222223302322200( )max9( )max94

31、 max94()xsxsxsf sxf sxsxsx3131211322023130( )max2()max29()xsxsf sxfsxsx*2322*330,1010 xssxxs所以所以 最優投資方案是全部資金投于第最優投資方案是全部資金投于第3個項目，可得個項目，可得最大收益最大收益200萬元。萬元。例例2 求解下面問題：求解下面問題：2213123max(0). .0,1,2,3iZxxxxxxccs txi(考慮用動態規劃的逆序法進行求解。考慮用動態規劃的逆序法進行求解。)解題思路？解題思路？csxsxsxcsxssxsxs112233112223330;0;3 , 2 , 1,

32、0)0(. .max3213212ixccxxxtsxxxZi解：解：1、將該問題劃分為三個階段，即、將該問題劃分為三個階段，即k=1，2，32、確定狀態變量并可得狀態轉移方程：、確定狀態變量并可得狀態轉移方程：3221313, 1),(xxxxsvViiii3、指標函數指標函數11044( )max ( ,)()3,2,1( )1kkkkkkkkkxsf sv s xfskf s 4、基本方程基本方程最優值函數最優值函數當階段當階段k=3時，有時，有33*333333( ) max ( )x sf sxsxs最優決策最優決策當階段當階段k=2時，有時，有32222*2222033220222

33、74)(,32)(max)(max)(22222ssfsxxsxsfxsfsxsx得最優決策得最優決策最優目標函數最優目標函數因此最后可得：因此最后可得：csfcxcsfcsxcsfcx41)(,41161)(,2132641)(,4133*33222*2411*1當階段當階段k=1時，有時，有)(274max)(max)(311102210111111xsxsfxsfsxsx最優決策最優決策41111*1641)(,41ssfsx最優目標函數最優目標函數2213123max4(0). .0,1,2,3iZxxxxxxccstxi例例2 求解下面問題：求解下面問題：練習1P212 8.5 (1

34、)練習2222123123max4212329. .0,1,2,3iFxxxxxxstxi222212322123123123112233max4212329. .0,1,2,33 ,241max212949. .0,1,2,3iiFyyyyyystxFxxxxxxstxiyxxiyxy動態規劃的優缺點動態規劃的優缺點優點優點: : 最優解是全局最優解。最優解是全局最優解。 能得到一系列（包括子過程）的最優解。能得到一系列（包括子過程）的最優解。 不需要對系統狀態轉移方程、階段效應函數等不需要對系統狀態轉移方程、階段效應函數等 的解析性質作任何假設。的解析性質作任何假設。缺點：缺點： 沒有統一

35、的標準模型和標準的算法可供使用。沒有統一的標準模型和標準的算法可供使用。 應用的局限性，要求滿足應用的局限性，要求滿足“無后效性無后效性”。 “ “維數災難維數災難”問題。問題。 設有某種原料設有某種原料,總數量為總數量為a,用于生產用于生產n 種產品種產品.若分若分配數量配數量 xi 用于生產第用于生產第 i 種產品種產品, 其收益為其收益為 gi ( xi )，問，問應如何分配應如何分配, 才能使生產才能使生產 n 種產品的總收入最大？種產品的總收入最大？5 資源分配問題資源分配問題5.1 資源平行分配問題資源平行分配問題離散決策變量離散決策變量Max Z = g1(x1)+g2(x2)+

36、 +gn(xn) s.t. x1+ x2 + + xn = a xi 0 i = 1, 2, , n靜態規靜態規劃模型劃模型 例例3 3 某公司擬將某公司擬將5 5臺某種設備分配給所屬的甲、臺某種設備分配給所屬的甲、乙、丙三個工廠乙、丙三個工廠, ,各工廠若獲得這種設備各工廠若獲得這種設備, ,可以為公可以為公司提供的盈利如表司提供的盈利如表. . 問：這五臺設備如何分配給各工廠問：這五臺設備如何分配給各工廠, ,才能使公才能使公司得到的盈利最大司得到的盈利最大. . 046111212051011111103791213012345丙丙乙乙甲甲工廠工廠 盈利盈利設備臺數設備臺數 甲甲乙乙丙丙

37、012345037912130510111111046111212如何劃分如何劃分階段階段s1的可達狀態集合的可達狀態集合s2的可達狀態集合的可達狀態集合s3的可達狀態集合的可達狀態集合決策變量決策變量 uk(sk) 0 sk3個階段個階段xk狀態轉移方程？狀態轉移方程？甲甲乙乙丙丙012345037912130510111111046111212s1s2s3321x1x2x3基本方程基本方程?指標函數指標函數gk(xk)?133kkkssxxss4解：將問題按工廠分為三個階段，甲、乙、丙分解：將問題按工廠分為三個階段，甲、乙、丙分別編號為別編號為1 1，2 2，3 3。決策變量決策變量xk:

38、 分配給第分配給第 k 個工廠的設備數量個工廠的設備數量 分配給第分配給第 k 個工廠個工廠至第至第 3 個工廠的設備個工廠的設備數量。數量。狀態變量狀態變量 sk :甲甲乙乙丙丙012345037912130510111111046111212Dk ( sk )= uk|0 xk sk 0)()(max44110sfsfxgsfkkkksxkkkk基本方程：基本方程：數量為數量為 sk 的原料分的原料分配給第配給第 k 個工廠至個工廠至第第 3 個工廠所得到個工廠所得到的最大總收益的最大總收益狀態轉移方程狀態轉移方程:sk+1 = sk - - xkxk的取值的取值范圍？范圍？甲甲乙乙丙丙0

39、123450379121305101111110461112120) 0()()(max) 0(344330333 gsfxgfsx 11) 3(3 fx3*(0) = 0 x3*(1) = 1x3*(2) = 2x3*(3) = 3k =3，s3=0,1,2,3,4,5，0 x3 s3s3 = 0s3 = 3甲甲乙乙丙丙0123450379121305101111110461112120461112124) 1 ()0(max)()(max) 1 (331 , 0443303333 ggsfxgfxsx 6) 2(3 fs3 = 2s3 = 1甲甲乙乙丙丙012345037912130510

40、11111104611121212)4(3 f 12)5(3 fx3*(5) = 4,5x3*(4) = 4046111212x3s3g3(x3)f3(s3)x*3012345012345046111212046111212012344,5結果可寫結果可寫成表格的成表格的形式形式:s3 = 4s3 = 5甲甲乙乙丙丙012345037912130510111111046111212 k =2，s3 = s2 - x2，s2=0,1,2,3,4,5，0 x2 s2，有有x2*(0) = 0s2 = 00)0()()(max)0(233220222 gsfxgfsxx3s3g3(x3)f3(s3)

41、 x*3012345012345046111212046111212012344,5x2*(1) =1s2 = 1甲甲乙乙丙丙012345037912130510111111046111212x3s3g3(x3)f3(s3) x*3012345012345046111212046111212012344,550540max)0()1()1()0(max)()(max)1(1 ,032321 ,03322022222 xxsxfgfgsfxgfs3 = s2 - x2，s2=0,1,2,3,4,5，0 x2 s2x2*(2) =2s2 = 2甲甲乙乙丙丙012345037912130510111

42、111046111212x3s3g3(x3)f3(s3) x*3012345012345046111212046111212012344,5100104560max)0()2()1()1()2()0(max)()(max)2(2, 1 ,03232322, 1 ,03322022222 xxsxfgfgfgsfxgf1401141065110max)0()3()1()2()2()1()3()0(max)()(max)3(3,2, 1 ,0323232323,2, 1 ,03322022222 xxsxfgfgfgfgsfxgfx2*(3) =2甲甲乙乙丙丙0123450379121305101

43、11111046111212x3s3g3(x3)f3(s3) x*3012345012345046111212046111212012344,5s2 = 3甲甲乙乙丙丙012345037912130510111111046111212x3s3g3(x3)f3(s3) x*3012345012345046111212046111212012344,516011411610115120max)0()4()1()3()2()2()3()1()4()0(max)()(max)4(4 , 3, 2, 1 , 032323232324 , 3, 2, 1 , 03322022222 xxsxfgfgfgf

44、gfgsfxgfx2*(4) =1,2s2 = 4210114116111110125120max)0()5()1()4()2()3()3()2()4()1()5()0(max)()(max)4(5, 4, 3, 2, 1 , 03232323232325, 4, 3, 2, 1 , 03322022222 xxsxfgfgfgfgfgfgsfxgfs2 = 5甲甲乙乙丙丙012345037912130510111111046111212x3s3g3(x3)f3(s3) x*3012345012345046111212046111212012344,5x2*(5) =2結果列于下表：結果列于下

45、表：x2s2g2(x2)+f3(s2-x2)f2(s2)x*20123450123450+00+40+60+110+120+125+05+45+65+115+1210+010+410+610+1111+011+411+611+011+411+0051014162101221,22k =1時時, s2 = s1 - x1, s1 = 5, 0 x1 s1,有有x2s2f2(s2)x*2012345051014162101221,2221013512109147163210max)0()5() 1 ()4()2()3()3()2()4() 1 ()5()0(max)()(max)(21212121

46、21215 , 4 , 3, 2, 1 , 0 ,2211011111 fgfgfgfgfgfgsfxgsfxsxx1*(5) =0,2甲甲乙乙丙丙012345037912130510111111046111212結果可寫成表格的形式結果可寫成表格的形式x1s1g1(x1)+f2(s1-x1)f1(s1)x*101234550+213+167+149+1012+513+0210,2最優分配方案一：由最優分配方案一：由 x1* = 0，根據，根據 s2 = s1- x1* = 5- 0 = 5，查表知，查表知 x2* = 2，由，由s3 = s2- x2* = 5 - 2 = 3，故，故 x3*

47、 = s3 =3。即得甲工廠分配。即得甲工廠分配0臺，乙工廠分配臺，乙工廠分配2臺，丙臺，丙工廠分配工廠分配3臺。臺。最優分配方案？最優分配方案？ 最優分配方案二：由最優分配方案二：由 x1* = 2，根據，根據 s2 = s1 - x1* = 5- 2 = 3，查表知，查表知 x2*= 2，由，由 s3 = s2 - x2*= 3 - 2 =1，故，故 x3* = s3 =1。即得甲工廠分配。即得甲工廠分配2臺，乙工廠分配臺，乙工廠分配2臺，臺，丙工廠分配丙工廠分配1臺。臺。 以上兩個分配方案所得到的總盈利均為以上兩個分配方案所得到的總盈利均為21萬元。萬元。問題：問題： 如果原設備臺數是如

48、果原設備臺數是4 4臺，求最優分配方案？臺，求最優分配方案？ 如果原設備臺數是如果原設備臺數是3 3臺，求最優分配方案？臺，求最優分配方案？ 如果原設備臺數是如果原設備臺數是6 6臺，求最優分配方案？臺，求最優分配方案？ 例例3 3 某公司擬將某公司擬將5 5臺某種設備分配給所屬的甲、臺某種設備分配給所屬的甲、乙、丙三個工廠乙、丙三個工廠, ,各工廠若獲得這種設備各工廠若獲得這種設備, ,可以為公可以為公司提供的盈利如表司提供的盈利如表. . 問：這五臺設備如何分配給各工廠問：這五臺設備如何分配給各工廠, ,才能使公才能使公司得到的盈利最大司得到的盈利最大. . 046111212051011

49、111103791213012345丙丙乙乙甲甲工廠工廠 盈利盈利設備臺數設備臺數 甲甲乙乙丙丙012345037912130510111111046111212133kkkssxxss1s2s3321x1x2x3s4Dk ( sk )= uk|0 xk sk 0)()(max44110sfsfxgsfkkkksxkkkkx3s3g3(x3)f3(s3)x*3012345012345046111212046111212112344,5x2s2g2(x2)+f3(s2-x2)f2(s2)x*20123450123450+00+40+60+110+120+125+05+45+65+115+1210

50、+010+410+610+1111+011+411+611+011+4 11+0051014162101221,22甲甲乙乙丙丙012345037912130510111111046111212資源分配問題資源分配問題 資源平行分配問題資源平行分配問題只合理分配資源只合理分配資源, 不考慮回收不考慮回收 決策變量為離散值決策變量為離散值. 銷售點分配問題；投資分配問題；貨物分配問題銷售點分配問題；投資分配問題；貨物分配問題 資源連續分配問題資源連續分配問題考慮資源回收利用考慮資源回收利用 決策變量為連續值決策變量為連續值資源連續分配問題資源連續分配問題111111211112n11111,()

51、,(),( )().()kkkkkkA BABh susaub suu uuskA Bsausug uausubb suukAsfu數量為 的某種資源,可投入 和 兩種生產.第一年:投入 數量 ，得收入回收;投入 數量,得收入回收第二年：資源數量如此進行n年,應如何決定 , , , ,使得總收入最大?：第 階段可投入 、 兩種生產的資源量, ：第 階段投入 生產的資源量；( ):kkksskn資源量 從第 階段至第 階段得到的最大總收入5.2 資源連續分配問題資源連續分配問題A種生產種生產數量數量u1投入投入 收益收益g (u1) 年終資源回收率年終資源回收率a B種生產種生產數量數量s1-u

52、1 收益收益h (s1-u1)年終資源回收率年終資源回收率b資源數量資源數量s1第一年第一年資源數量資源數量s2=au1+b(s1-u1)第二年第二年 A種生產種生產數量數量u2投入投入;收益收益g(u2);年終資源回收率年終資源回收率aB種生產種生產數量數量s2-u2;收益收益h(s2-u2);年終資源回收率年終資源回收率b到到n年年如此進行如此進行 n 年年, 如何確定投入如何確定投入 A 的資源量的資源量 u1、un, 使總收入最大？使總收入最大？此問題的靜態規劃問題模型為：此問題的靜態規劃問題模型為： nisuusbaususbaususbaustsushugZiinnnnniiii,

53、2,1,0)()()(.)()(max1222311121 1110()0()max ()()(),2,1kknnkkkkkkkkkusfsfsg uh sufaub sukn高負荷高負荷: 產量函數產量函數 g = 8u1， 年完好率為年完好率為 a=0.7，機器機器 例例4 4 機器負荷分配問題機器負荷分配問題假定開始生產時完好機器的數量為假定開始生產時完好機器的數量為10001000臺。臺。 低負荷低負荷: 產量函數產量函數 h = 5y， 年完好率為年完好率為 b=0.9。試問每年如何安排機器在高低兩種負荷下的生產試問每年如何安排機器在高低兩種負荷下的生產, ,可可使使5 5年內生產的

54、產品總產量最高年內生產的產品總產量最高? ?投入生產的機投入生產的機器數量器數量 狀態變量狀態變量 sk狀態轉移方程狀態轉移方程決策變量決策變量 uk第第 k 年初擁有的完年初擁有的完好機器臺數好機器臺數第第 k 年高負荷下投年高負荷下投入的機器數入的機器數sk+1 = auk+ b(sk - - uk) = 0.7uk+ 0.9 (sk - -uk)0 uk sk分析：分析：第第 k 年低負荷下投年低負荷下投入的機器數入的機器數sk uk階段？階段？遞推方程？遞推方程？ 515, 1),(kkkkusvV指標函數指標函數第第k年度產量為年度產量為)( 58),(kkkkkkusuusv fk

55、(sk) =max 8uk+5(sk-uk)+fk+1(0.7uk+0.9(sk-uk)0 uk skk = 5, 4, 3, 2, 1sk+1階段指標階段指標f6(s6) = 0 則狀態轉移方程為則狀態轉移方程為sk+1 = 0.7uk+ 0.9 (sk - - uk) k = 1, 2, , 5解：設階段序數解：設階段序數 k 表示年度表示年度, sk為第為第 k 年初擁有的完好年初擁有的完好機器臺數機器臺數, 第第 k 年度高負荷下投入的機器數為年度高負荷下投入的機器數為uk臺臺. fk(sk) =max 8uk+5(sk-uk)+fk+1(0.7uk+0.9(sk-uk)0 uk sk

56、k = 5, 4, 3, 2, 1f6(s6) = 0 基本方程為基本方程為f4(s4) = 13.6s4u*4 = s4k = 4u*5 = s5k = 5f5(s5) = 8s553max)()(58max)(550665550555555susfususfsusu44444444444054444440440()max85()(0.70.9()max13.612.2()max1.412.2usususfsusufusuusuus0依次類推可得，依次類推可得，111*1222*23333*37 .23)(08 .20)(05 .17)(ssfussfussfsu 因此因此最優策略最優策略為

57、為5*54*43*3*2*1, 0, 0sususuuu 最高產量為最高產量為23700。練習：練習：1. 每年年初的完好機器數。每年年初的完好機器數。 2. 如規定在第五年結束時完好機器數為如規定在第五年結束時完好機器數為500臺，臺，該如何安排生產？該如何安排生產？k = 4k = 553max)()(58max)(550665550555555susfususfsusu25005 . 42 . 0/ )5009 . 0(500)(9 . 07 . 05555556ssuusus*55555554.52500()3517.57500usf suss*4444440()20.750.5750

58、020.757500ufssus其他略其他略練習 1生產與存儲問題生產與存儲問題設某公司對某種產品要制訂一項n個階段的生產(或購買)計劃.已知它的初始庫存量為0,每階段生產(或購買)該產品的數量有上限的限制;每階段對該產品的需求量是已知的,公司保證供應;在n階段末的終結庫存量為0.問該公司如何制訂每個階段的生產(或采購)計劃,從而使總成本最小.時期 (k)1234需求量 (dk)2324固定成本為 3千元,單位產品成本為1千元,最大生產批量不超過6個單位,每個時期末未售出的產品,每單位需付存貯費0.5千元.按4個時期將問題分為4個階段。第k個時期內的生產成本為：0, 03 1, 1,2,.,6

59、, 6kkkkkkxcxxxx 第k時期末庫存量為vk時存貯費用為：0.5,kkkhvv第k時內的總成本為：kkkkcxhv 11110111111min,6min 2,3,4min,6minkkkkkkkkkkkkxkkkxvdfvcxhvfvdxkvdfvcxh v1kkkkvvdx狀態轉移方程： 11111111min2,6k1minxvfvcxh v時， 1111120,0min 30.5 05,2xvfxx 1111131,1min 30.5 16.5,3xvfxx 1111142,2min 30.5 28,4xvfxx 1111153,3min 30.5 39.5,5xvfxx 1

60、111164,4min 30.5 411,6xvfxx 11110111111min,6min 2,3,4min,6minkkkkkkkkkkkkxkkkxvdfvcxhvfvdxkvdfvcxh v 222222222211022221220k2min min3xxfvcxhvfvcxhvfvx 時， 22222120322122122212210min03003102min9.50201300 xfcxhfxchfchfxchfchf 2222222122042222122052222122061min1411.5,02min2514,53min3615.5,6xxxfcxhfxxfcxh