運籌學第六章

1、第第6章章 動態(tài)規(guī)劃動態(tài)規(guī)劃第第1節(jié)節(jié) 多階段決策過程及實例多階段決策過程及實例第第2節(jié)節(jié) 動態(tài)規(guī)劃的基本概念和方程動態(tài)規(guī)劃的基本概念和方程第第3節(jié)節(jié) 動態(tài)規(guī)劃的最優(yōu)性原理和最優(yōu)性定理動態(tài)規(guī)劃的最優(yōu)性原理和最優(yōu)性定理第第4節(jié)節(jié) 動態(tài)規(guī)劃和靜態(tài)規(guī)劃的關系動態(tài)規(guī)劃和靜態(tài)規(guī)劃的關系第第5節(jié)節(jié) 動態(tài)規(guī)劃應用舉例動態(tài)規(guī)劃應用舉例 第第1節(jié)節(jié) 多階段決策過程及實例多階段決策過程及實例 動態(tài)規(guī)劃研究的對象是多階段決策問題。動態(tài)規(guī)劃研究的對象是多階段決策問題。 所謂多階段決策問題是指一類活動過程，它所謂多階段決策問題是指一類活動過程，它可以分為若干個相互聯(lián)系的階段，在每個階段都可以分為若干個相互聯(lián)系的階段，在

2、每個階段都需要作出決策。這個決策不僅決定這一階段的效需要作出決策。這個決策不僅決定這一階段的效益，而且決定下一階段的初始狀態(tài)。益，而且決定下一階段的初始狀態(tài)。 每個階段的決策確定以后，就得到一個決策每個階段的決策確定以后，就得到一個決策序列，稱為策略。多階段決策問題就是求一個策序列，稱為策略。多階段決策問題就是求一個策略，使各階段的效益的總和達到最優(yōu)。略，使各階段的效益的總和達到最優(yōu)。多階段決策問題的典型例子：多階段決策問題的典型例子： 1 . 生產決策問題：企業(yè)在生產過程中，由于需生產決策問題：企業(yè)在生產過程中，由于需求是隨時間變化的，因此企業(yè)為了獲得全年的最佳求是隨時間變化的，因此企業(yè)為了

3、獲得全年的最佳生產效益，就要在整個生產過程中逐月或逐季度地生產效益，就要在整個生產過程中逐月或逐季度地根據(jù)庫存和需求決定生產計劃。根據(jù)庫存和需求決定生產計劃。 2. 機器負荷分配問題：某種機器可以在高低機器負荷分配問題：某種機器可以在高低兩種不同的負荷下進行生產。在高負荷下進行生產兩種不同的負荷下進行生產。在高負荷下進行生產時，產品的年產量時，產品的年產量g和投入生產的機器數(shù)量和投入生產的機器數(shù)量u1的關的關系為系為g=g(u1)12n狀態(tài)狀態(tài)決策決策狀態(tài)狀態(tài)決策決策狀態(tài)狀態(tài)狀態(tài)狀態(tài)決策決策 這時，機器的年完好率為這時，機器的年完好率為a，即如果年初完好機，即如果年初完好機器的數(shù)量為器的數(shù)量為

4、u，到年終完好的機器就為，到年終完好的機器就為au, 0a1。 在低負荷下生產時，產品的年產量在低負荷下生產時，產品的年產量h和投入生和投入生產的機器數(shù)量產的機器數(shù)量u2的關系為的關系為 h=h(u2) 假定開始生產時完好的機器數(shù)量為假定開始生產時完好的機器數(shù)量為s1。要求制。要求制定一個五年計劃，在每年開始時，決定如何重新定一個五年計劃，在每年開始時，決定如何重新分配完好的機器在兩種不同的負荷下生產的數(shù)量，分配完好的機器在兩種不同的負荷下生產的數(shù)量，使在五年內產品的總產量達到最高。使在五年內產品的總產量達到最高。 相應的機器年完好率相應的機器年完好率b, 0 b0，故比較，故比較0,10的端

5、點的端點101002910332232112 sxxss,xxss*因為因為 最優(yōu)投資方案是全部資金投最優(yōu)投資方案是全部資金投于第于第3個項目，可得最大收益?zhèn)€項目，可得最大收益200萬元。萬元。S29/2)s(fxmax)s(fsx221011411 29100959994101121111100111100111 xss,xsxsmaxxsxmax)(f*xx0401010200100241011111211110011 *xx)(fx)(fx)xs(xmax)(f2229s)s(f 22222s)s(f 當當當當時時時時矛盾，舍去矛盾，舍去。（最優(yōu)決策）（最優(yōu)決策）S29/2 當階段當階段

6、k= =n時時逆推解法小結：逆推解法小結： 設已知初始狀態(tài)設已知初始狀態(tài)s s1 1，最優(yōu)值函數(shù)，最優(yōu)值函數(shù)fk k( (sk k) )表示從表示從k階段到階段到n階段所得到的最大效益。以求最大化為例來階段所得到的最大效益。以求最大化為例來說明。說明。nnnsDunnxsvsfnnn,max)(),(),(),(222111, 1nnnnxsvxsvxsvV即即其中其中s表示狀態(tài)，表示狀態(tài)，x表示決策（控制）。表示決策（控制）?？傻米顑?yōu)決策可得最優(yōu)決策xn n= =xn n( (sn n) )和最優(yōu)值和最優(yōu)值fn n( (sn n) )。若若D(D(s sn n) )只有一個決策只有一個決策,

7、 ,則可寫成則可寫成 xn n= =xn n( (sn n) )。具體方法如下：具體方法如下： 當階段當階段k=n-1時時 nnnnnsDunnsfxsvsfnnn111)(11,max111 111 nnnnx,sTs其中狀態(tài)轉移方程其中狀態(tài)轉移方程得到最優(yōu)決策得到最優(yōu)決策xn-1-1= = xn-1-1( (sn-1-1) )和最優(yōu)值和最優(yōu)值fn-1-1( (sn-1-1) )。 當階段當階段k=k時時 11)(,maxkkkkksDukksfxsvsfkkk kkkkx,sTs 1其中狀態(tài)轉移方程其中狀態(tài)轉移方程得最優(yōu)決策得最優(yōu)決策xk= = xk( (sk) )和最優(yōu)值和最優(yōu)值fk(

8、(sk) )。如此類推，直到第一階段。如此類推，直到第一階段。當階段當階段k=1時時 ,22111)(11max111sfxsvsfsDs其中狀態(tài)轉移方程其中狀態(tài)轉移方程.,1112xsTs 得得最優(yōu)決策最優(yōu)決策x1 1= = x1( (s1 1) )和最優(yōu)值和最優(yōu)值f1 1( (s1 1) )。 由于初始狀態(tài)由于初始狀態(tài)s s1 1已知已知, ,故故x1 1= =x1 1( (s1 1) )和和f1 1( (s1 1) )是確是確定的定的, ,根據(jù)狀態(tài)轉移方程按照上述遞推過程相反順根據(jù)狀態(tài)轉移方程按照上述遞推過程相反順序推算下去，就可逐步確定出每階段的決策及效序推算下去，就可逐步確定出每階段

9、的決策及效益。益。例例3 用順推解法求解下面問題用順推解法求解下面問題: 321003213212,i,x)c(cxxx. t . sxxxZmaxi設設s4=c, fk(sk+1)表示第表示第k階段的結束狀態(tài)為階段的結束狀態(tài)為 sk+1，從從1階段到階段到k階階 段的最大值。分三個階段，即段的最大值。分三個階段，即 k=1，2，3;解：解：設狀態(tài)變量（因此可得狀態(tài)轉移方程）設狀態(tài)變量（因此可得狀態(tài)轉移方程） ：csxsxsxcsxssxsxs433221433322120;0;確定決策變量：確定決策變量：x1, x2, x332213131xxx)x,s(vViiii, 指標函數(shù)指標函數(shù) 最

10、優(yōu)指標函數(shù)：最優(yōu)指標函數(shù)：fk(sk+1)1)(3 , 2 , 1)(),(max)(10101sfksfxsvsfkkkkksxkkkk 基本方程基本方程當階段當階段k=1時，有時，有2*12121)(max)(21sxsxsfsx當階段當階段k=2時，有時，有得最優(yōu)決策得最優(yōu)決策33323*232202122032274)(,32)(max)(max)(23232ssfsxxsxsfxsfsxsx最優(yōu)目標函數(shù)最優(yōu)目標函數(shù)當階段當階段k=3時，有時，有)(274max)(max)(334303230434343xsxsfxsfsxsx最優(yōu)決策最優(yōu)決策44434*3641)(,41ssfsx最

11、優(yōu)目標函數(shù)最優(yōu)目標函數(shù)因此最后可得：因此最后可得：443*33323*221*1641)(,41161)(,213241)(,41csfcxcsfcsxcsfcx例例4 用動態(tài)規(guī)劃方法解下面問題用動態(tài)規(guī)劃方法解下面問題解：設狀態(tài)變量為解：設狀態(tài)變量為s0、s1、 s2、s3)3,2, 1(,0923.1224max321232221ixxxxtsxxxFi 按問題中變量的個數(shù)分為三個階段，即按問題中變量的個數(shù)分為三個階段，即k=1，2，3 確定決策變量：確定決策變量：x1, x2, x3 fk(sk)表示第表示第k階段的結束狀態(tài)為階段的結束狀態(tài)為 sk，從，從1階段到階段到k階階 段的最大值。

12、段的最大值。 確定狀態(tài)變量確定狀態(tài)變量(因此可得狀態(tài)轉移方程因此可得狀態(tài)轉移方程)：332211332221110,20,39,2,3sxsxsxsxssxssx狀態(tài)轉移方程狀態(tài)轉移方程最優(yōu)目標函數(shù)最優(yōu)目標函數(shù) f1(s1)=(4/9)s12 當階段當階段k=1時，有時，有 f1(s1)=max 4x12 X1s1/3最優(yōu)決策為最優(yōu)決策為x1*=s1/3當階段當階段k=2時，有時，有),(max294max)(max)(2222/0222222/011222/022222222xshxsxsfxsfsxsxsx因該點不在允許決策集合內，最大值點只能在因該點不在允許決策集合內，最大值點只能在0，

13、s2/2端點上取得，即端點上取得，即222222780916914sxsxdxdh解得由4)2(,94)0(2222222sshsh所以所以h2(s2,x2)的最大值點在的最大值點在x2=0處，故得到處，故得到f2(s2)=(4/9)s22及相應的最優(yōu)解及相應的最優(yōu)解x2*=0。當階段當階段k=3時，有時，有),(max94122max)(122max)(33302332302223033333333xshxsxsfxsfsxsxsx233333112098944sxsxdxdh解得由故該點為極小值點。又, 09442332dxhd122)(,1294)0(2333233sshsh而。及相應的

14、最優(yōu)解處，所以的最大值點在故33233333322122)(),(sxsxfsxxsh由于由于s3不知道，故須再對不知道，故須再對s3求一次極值，即求一次極值，即122max)(max2390339033ssfxx為最大值。所以得才能達到最大值。時顯然，當1741292)9()(921333fsfs174)9(max; 9, 0, 013*21fFxxx最大值為可求得最優(yōu)解為再按計算的順序反推算 當階段當階段k= =1時時順推解法小結：順推解法小結： 設已知初始狀態(tài)設已知初始狀態(tài)s sn+1n+1，最優(yōu)值函數(shù)，最優(yōu)值函數(shù)fk k( (s) )表示第表示第k階段末的結束狀態(tài)為階段末的結束狀態(tài)為s

15、 s，從，從1 1階段到階段到k階段所得到的最階段所得到的最大效益。以求最大化為例來說明。大效益。以求最大化為例來說明。),(,1211111)(21max111xsTsxsvsfsDs其中),(),(),(222111, 1nnnnxsvxsvxsvV即即其中其中s表示狀態(tài)，表示狀態(tài)，x表示決策（控制）。表示決策（控制）?？傻米顑?yōu)決策可得最優(yōu)決策x1 1= =x1 1( (s2 2) )和最優(yōu)值和最優(yōu)值f1 1( (s2 2) )。若若D D1 1( (s s1 1) )只有一個決策只有一個決策, ,則可寫成則可寫成 x1 1= =x1 1( (s2 2) )。具體方法如下：具體方法如下：

16、當階段當階段k=2時時21222)(32,max222sfxsvsfsDx2322, xsTs其中狀態(tài)轉移方程其中狀態(tài)轉移方程得到最優(yōu)決策得到最優(yōu)決策x2= = x2( (s3) )和最優(yōu)值和最優(yōu)值f2( (s3) )。 當階段當階段k=k時時 kkkkksDskksfxsvsfkkk1)(1,maxkkkkxsTs,1其中狀態(tài)轉移方程其中狀態(tài)轉移方程得最優(yōu)決策得最優(yōu)決策xk= = xk( (sk+1) )和最優(yōu)值和最優(yōu)值fk( (sk+1) )。如此類推，直到第如此類推，直到第n n階段。階段。 當階段當階段k=n時時,1)(1maxnnnnnsDxnnsfxsvsfnnn其中狀態(tài)轉移方程其

17、中狀態(tài)轉移方程.,1nnnnxsTs得得最優(yōu)決策最優(yōu)決策xn n= = xn( (sn+1n+1) )和最優(yōu)值和最優(yōu)值fn n( (sn+1n+1) )。 由于終止狀態(tài)由于終止狀態(tài)s sn+1n+1已知已知, ,故故xn n= =xn n( (sn+1n+1) )和和fn n( (sn+1n+1) )是確定的是確定的, ,根據(jù)狀態(tài)轉移方程按照上述遞推過程相根據(jù)狀態(tài)轉移方程按照上述遞推過程相反順序推算下去，就可逐步確定出每階段的決策反順序推算下去，就可逐步確定出每階段的決策及效益。及效益。動態(tài)規(guī)劃的優(yōu)缺點：動態(tài)規(guī)劃的優(yōu)缺點：優(yōu)點優(yōu)點: . 最優(yōu)解是全局最優(yōu)解。最優(yōu)解是全局最優(yōu)解。 . 能得到一系

18、列（包括子過程）的最優(yōu)解。能得到一系列（包括子過程）的最優(yōu)解。 . 不需要對系統(tǒng)狀態(tài)轉移方程、階段效應函數(shù)不需要對系統(tǒng)狀態(tài)轉移方程、階段效應函數(shù)等的解析性質作任何假設。等的解析性質作任何假設。缺點：缺點： .沒有統(tǒng)一的標準模型和標準的算法可供使用。沒有統(tǒng)一的標準模型和標準的算法可供使用。 .應用具有局限性，要求滿足應用具有局限性，要求滿足“無后效性無后效性”。 . 存在存在“維數(shù)災難維數(shù)災難”問題，變量的個數(shù)增加，問題，變量的個數(shù)增加，計算的難度成倍增加。計算的難度成倍增加。第第5節(jié)節(jié) 動態(tài)規(guī)劃應用舉例動態(tài)規(guī)劃應用舉例 5.1節(jié)節(jié) 一維資源分配問題一維資源分配問題 設有某種原料，總數(shù)量為設有某

19、種原料，總數(shù)量為a，用于生產，用于生產n種產品。種產品。若分配數(shù)量若分配數(shù)量xi用于生產第用于生產第i 種產品，其收益為種產品，其收益為g gi i(x(xi i) )問應如何分配，才能使生產問應如何分配，才能使生產n種產品的總收入最大？種產品的總收入最大？ 將數(shù)量一定的一種或若干種資源，恰當?shù)胤峙鋵?shù)量一定的一種或若干種資源，恰當?shù)胤峙浣o若干個使用者，使效益函數(shù)為最優(yōu)。給若干個使用者，使效益函數(shù)為最優(yōu)。max z =g1(x1)+ g2(x2)+ + gn(xn)x1+x2+ xn=axi0 i=1,2, ,ns.t.決策集合：決策集合：D Dk( (sk)=)=uk|0|0 uk= =xk

20、 sk )(max)(1 , 1)()(max)(10nnsxnnkkkkksxkkxgsfnkxsfxgsfnnkkuk: :分配給生產第分配給生產第k種產品的原料數(shù)量，即種產品的原料數(shù)量，即uk= =xk；sk: :分配給用于生產第分配給用于生產第k種至第種至第n種產品的原料數(shù)量；種產品的原料數(shù)量；狀態(tài)轉移方程：狀態(tài)轉移方程： sk+1+1= =sk- -uk= =sk- -xk最優(yōu)值函數(shù)最優(yōu)值函數(shù)fk( (sk):):數(shù)量為數(shù)量為sk的原料分配給第的原料分配給第k種產品種產品至第至第n種產品所得到的最大總收益，動態(tài)規(guī)劃的遞推種產品所得到的最大總收益，動態(tài)規(guī)劃的遞推關系為：關系為：某工業(yè)部

21、門根據(jù)國家計劃的安排，擬將某種高效某工業(yè)部門根據(jù)國家計劃的安排，擬將某種高效率的設備率的設備5 5臺分配給所屬的甲、乙、丙三個工廠，臺分配給所屬的甲、乙、丙三個工廠，各工廠若獲得這種設備，可以為公司提供的盈利各工廠若獲得這種設備，可以為公司提供的盈利如表。如表。問：這五臺設備如何分配給各工廠，才能使公司問：這五臺設備如何分配給各工廠，才能使公司得到的盈利最大。得到的盈利最大。例例1 1 工工 廠廠盈利盈利 設備臺數(shù)設備臺數(shù) 甲甲 乙乙 丙丙 0 1 2 3 4 5 0 3 7 9 12 13 0 5 10 11 11 11 0 4 6 11 12 12 解：將問題按工廠分為解：將問題按工廠分為

22、三個階段，甲、乙、丙三個階段，甲、乙、丙分別編號為分別編號為1 1，2 2，3 3。 工工 廠廠盈盈利利 設設備備臺臺數(shù)數(shù) 甲甲 乙乙 丙丙 0 1 2 3 4 5 0 3 7 9 12 13 0 5 10 11 11 11 0 4 6 11 12 12 = g30=0=maxk=3時，時，0 s3 5， 0 x3 s3f3(s3)=maxg3x3 0 x3s3f4(s4)=0g3(0)g3(1) =4x3 *(1) =1S3=0, f3(0)=max g3x3+ f4(s4) 0 x3s3x3 *(0) =0 x3=0,1S3=1, f3(1)=max g3x3+ f4(s4) 0 x3s3

23、 工工廠廠盈盈 利利 設設 備備 臺臺 數(shù)數(shù) 甲甲 乙乙 丙丙 0 1 2 3 4 5 0 3 7 9 1 2 1 3 0 5 1 0 1 1 1 1 1 1 0 4 6 1 1 1 2 1 2 2) 2 (6) 2 () 1 () 0 (max)()(max) 2 (2*33332 , 1 , 04433033333xgggsfxgfxsxs3) 3 (11) 3 () 2 () 1 () 0 (max)()(max) 3 (3*333333 , 2 , 1 , 04433033333xggggsfxgfxsxs4) 4 (12) 4 () 3 () 2 () 1 () 0 (max)()(

24、max) 4 (4*3333334 , 3 , 2 , 1 , 04433033333xgggggsfxgfxsxs5) 5 (12) 5 () 4 () 3 () 2 () 1 () 0 (max)()(max) 5 (5*33333335 , 4 , 3 , 2 , 1 , 04433033333xggggggsfxgfxsxs 工工 廠廠盈盈 利利 設設 備備 臺臺 數(shù)數(shù) 甲甲 乙乙 丙丙 0 1 2 3 4 5 0 3 7 9 12 13 0 5 10 11 11 11 0 4 6 11 12 12 g3(x3) x3 s3 0 1 2 3 4 5 f3(s3) x*3 0 1 2 3

25、 4 5 0 4 6 11 12 12 0 4 6 11 12 12 0 1 2 3 4 5 當階段當階段k=2時，時， s3=s2-x2， 0 s2 5， 0 x2 s2，有有0) 0 (0) 0 ()()(max) 0 (0*22332202222xgsfxgfssx1) 1 (50540max) 0() 1 () 1 () 0(max)()(max) 1 (1*21 , 032321 , 033220222222xfgfgsfxgfxxsxs2) 2 (100104560max) 0 () 2 () 1 () 1 () 2 () 0 (max)()(max) 2 (2*22 , 1 ,

26、03232322 , 1 , 033220222222xfgfgfgsfxgfsxxsx2) 3 (1401141065110max) 0 () 3 () 1 () 2() 2() 1 () 3 () 0 (max)()(max) 3 (3*23 , 2 , 1 , 0323232323 , 2 , 1 , 033220222222xfgfgfgfgsfxgfsxxsx2 , 1) 4 (16011411610115120max) 0 () 4 () 1 () 3 () 2 () 2 () 3 () 1 () 4 () 0 (max)()(max) 4 (4*24 , 3 , 2 , 1 ,

27、032323232324 , 3 , 2 , 1 , 033220222222xfgfgfgfgfgsfxgfsxxsx2) 5 (210114116111110125120max) 0 () 5 () 1 () 4 () 2 () 3 () 3 () 2 () 4 () 1 () 5 () 0 (max)()(max) 5 (5*25 , 4 , 3 , 2 , 1 , 03232323232325 , 4 , 3 , 2 , 1 , 033220222222xfgfgfgfgfgfgsfxgfsxxsxg2(x2)+f3(s2-x2) x2 s2 0 1 2 3 4 5 f2(s2) x*

28、2 0 1 2 3 4 5 0 0+4 0+6 0+11 0+12 0+12 5+0 5+4 5+6 5+11 5+12 10+0 10+4 10+6 10+11 11+0 11+4 11+6 11+0 11+4 11+0 0 5 10 14 16 21 0 1 2 2 1,2 2 結果列于下表：結果列于下表：f3(1-0)=f3(1)g3(x3) x3 s3 0 1 2 3 4 5 f3(s3) x*3 0 1 2 3 4 5 0 4 6 11 12 12 0 4 6 11 12 12 0 1 2 3 4 5 =4 f3(5-3)=f3(2)=max =21g1(0)+f2(5)g1(1)+

29、f2(4)g1(2)+f2(3)g1(3)+f2(2)g1(4)+f2(1)g1(5)+f2(0) =max g1x1+ f2(s1- x1) x1=0,1,2,3,4,5當階段當階段k=1時，時， s2=s1-x1， s1=5， 0 x1 s1，有有S1=5, f1(S1 )=max g1x1+ f2(s2) 0 x1s1x1*(5)=0, 20+213+167+149+1012+513+0= maxg1(x1)+f2(s1-x1) x1 s1 0 1 2 3 4 5 f1(s1) x*1 5 0+21 3+16 7+14 9+10 12+5 13+0 21 0,2 結果可寫成表格的形式結果

30、可寫成表格的形式g2(x2)+f3(s2-x2) x2 s2 0 1 2 3 4 5 f2(s2) x*2 0 1 2 3 4 5 0 0+4 0+6 0+11 0+12 0+12 5+0 5+4 5+6 5+11 5+12 10+0 10+4 10+6 10+11 11+0 11+4 11+6 11+0 11+4 11+0 0 5 10 14 16 21 0 1 2 2 1,2 2 S2*=s1*-x1*=5-0=5S3*=s2*-x2*=5-2=3max逆推到第一張表逆推到第一張表g3(x3) x3 s3 0 1 2 3 4 5 f3(s3) x*3 0 1 2 3 4 5 0 4 6 1

31、1 12 12 0 4 6 11 12 12 0 1 2 3 4 5 g2(x2)+f3(s2-x2) x2 s2 0 1 2 3 4 5 f2(s2) x*2 0 1 2 3 4 5 0 0+4 0+6 0+11 0+12 0+12 5+0 5+4 5+6 5+11 5+12 10+0 10+4 10+6 10+11 11+0 11+4 11+6 11+0 11+4 11+0 0 5 10 14 16 21 0 1 2 2 1,2 2 S3*=s2*-x2*=5-2=3x3*=3x2*=2按計算表格的順序逆推，可知最優(yōu)分配方案有兩個：按計算表格的順序逆推，可知最優(yōu)分配方案有兩個：甲工廠分配甲

32、工廠分配0臺，乙工廠分配臺，乙工廠分配2臺臺,丙工廠分配丙工廠分配3臺。臺。甲工廠分配甲工廠分配2臺，乙工廠分配臺，乙工廠分配2臺，丙工廠分配臺，丙工廠分配1臺。臺。 以上兩個分配方案所得到的總盈利均為以上兩個分配方案所得到的總盈利均為21萬元萬元1.2 資源連續(xù)分配問題資源連續(xù)分配問題: 一般問題的提法是一般問題的提法是 A種生產種生產數(shù)量數(shù)量u1投入投入 收益收益g(u1) 年終資源回收率年終資源回收率a如此進行如此進行n年，如何確定投入年，如何確定投入A的資源量的資源量u1、un，使總收入最大？使總收入最大？ B種生產種生產數(shù)量數(shù)量s1-u1 收益收益h(s1-u1) 年終資源回收率年終

33、資源回收率b資源數(shù)量資源數(shù)量s1第一年第一年資源數(shù)量資源數(shù)量s2=au1+b(s1-u1)第二年第二年 A種生產種生產數(shù)量數(shù)量u2投入投入;收益收益g(u2);年終回收率年終回收率a B種生產種生產數(shù)量數(shù)量s2-u2;收益收益h(s2-u2);年終回收率年終回收率b到到n年年此問題的靜態(tài)規(guī)劃問題模型為此問題的靜態(tài)規(guī)劃問題模型為： nisuusbaususbaususbaustsushugZiinnnnniiii,2,1,0)()()(.)()(max1222311121動態(tài)規(guī)劃的逆推關系方程為：動態(tài)規(guī)劃的逆推關系方程為： 1 , 2 , 1)()()(max)()()(max)(100nkus

34、baufushugsfushugsfkkkkkkksukknnnsunnnnnn最后求得得最后求得得f1(s1)即為所求問題的最大收入。即為所求問題的最大收入。 高負荷高負荷: 產量函數(shù)產量函數(shù) g=8u1, u1是投入生產的機器是投入生產的機器 數(shù)量，年完好率為數(shù)量，年完好率為 a=0.7， 低負荷低負荷: 產量函數(shù)產量函數(shù) h=5y， y是投入生產的機器是投入生產的機器數(shù)量，數(shù)量， 年完好率為年完好率為b=0.9。 假定開始生產時完好機器的數(shù)量為假定開始生產時完好機器的數(shù)量為1000臺。臺。 機器機器 例例2 2 機器負荷分配問題機器負荷分配問題解：設階段數(shù)解：設階段數(shù)k表示年度。表示年度

35、。 試問每年如何安排機器在高低兩種負荷下的生試問每年如何安排機器在高低兩種負荷下的生產，可使產，可使5年內生產的產品總產量最高。年內生產的產品總產量最高。狀態(tài)變量狀態(tài)變量sk為第為第k年度初擁有的完好機器臺數(shù)；年度初擁有的完好機器臺數(shù)； 決策變量決策變量uk為第為第k年度中分配高負荷下生產的機年度中分配高負荷下生產的機 器器臺數(shù)。臺數(shù)。低負荷下生產的機器臺數(shù)是低負荷下生產的機器臺數(shù)是sk-uk。 狀態(tài)轉移方程狀態(tài)轉移方程5 , 2 , 1),( 9 . 07 . 0)(1kusuusbauskkkkkkk第第k年度產量為年度產量為)(58),(kkkkkkusuusv 遞推方程為遞推方程為 1

36、 , 2 , 5)( 9 . 07 . 0()( 58max)(0)(1066kusufususfsfkkkkkkksukkkk指標函數(shù)指標函數(shù)515 , 1),(kkkkusvV允許決策集合允許決策集合 0 uk sk當當k=5時時 , f5(s5)= max 8u5+5 s5 - u5 + f6(s6) 0u5 s5=max 3u5+5 s5 0u5 s5u5*= s5 , f5(s5)=8 s5當當k=4時時 , f4(s4)= max 8u4+5( s4 u4 ) + f5(0.7 u4+0.9(s4 u4 ) 0u4 s4= max 13.6u4+12.2( s4- u40u4 s4

37、= max 1.4u4+12.2 s40u4 s4u4*= s4 , f4(s4)=13.6s4依次類推可得依次類推可得， u3*=s3 f3(s3)=17.5 s3 u2*=0 f2(s2)=20.8 s2 u1*=0 f1(s1)=23.7 s1最高產量為最高產量為f1(s1) =23700(臺臺)。因此最優(yōu)策略為因此最優(yōu)策略為: u1*=0, u2*=0, u3*=s3, u4*= s4 u5*= s5, u5*= s5 , f5(s5)=8 s5u4*= s4 , f4(s4)=13.6s45.2 生產存貯問題生產存貯問題 一個生產部門，如何在已知生產成本、庫存一個生產部門，如何在已知

38、生產成本、庫存費用和各階段市場需求條件下，決定各階段產量，費用和各階段市場需求條件下，決定各階段產量，使計劃內的費用總和為最小的問題。使計劃內的費用總和為最小的問題。例例8. 某工廠要對一種產品制訂今后四個時期的生某工廠要對一種產品制訂今后四個時期的生產計劃，據(jù)估計在今后四個時期內，市場對于該產計劃，據(jù)估計在今后四個時期內，市場對于該產品的需求量如下表所示。假定該廠生產每批產產品的需求量如下表所示。假定該廠生產每批產品的固定成本品的固定成本3千元，若不生產就為千元，若不生產就為0；每單位產；每單位產品成本為品成本為1千元；每個時期生產能力所允許的最大千元；每個時期生產能力所允許的最大生產批量為

39、不超過生產批量為不超過6個單位；每個時期未售出的產個單位；每個時期未售出的產品，每單位需付存貯費品，每單位需付存貯費0.5千元。還假定在第一個千元。還假定在第一個時期的初始庫存量為時期的初始庫存量為0，第四個時期末的庫存量也，第四個時期末的庫存量也為為0。問該廠應如何安排各個時期的生產與庫存，。問該廠應如何安排各個時期的生產與庫存，才能在滿足市場需求條件下，使總成本最小。才能在滿足市場需求條件下，使總成本最小。時 期 (k) 1 2 3 4 需求量 (dk) 2 3 2 4 解：設解：設dk為第為第k階段的需求量，階段的需求量，xk為第為第k階段的生產量階段的生產量，vk為第為第k時期末庫存量

40、。有時期末庫存量。有vk= vk-1+ xk- dk把生產的四個時期作為四個階段，把生產的四個時期作為四個階段，k=1, 2, 3, 4。由題。由題意知，第意知，第k階段的生產成本為階段的生產成本為66, 2 , 1,1300)(kkkkkkxxxxxc當當當?shù)诘趉時期末庫存量為時期末庫存量為vk時的存儲費用為時的存儲費用為hk(vk)=0.5vk第第k時期內的總成本為時期內的總成本為ck(xk)+hk(vk)動態(tài)規(guī)劃的順序遞推關系式為動態(tài)規(guī)劃的順序遞推關系式為)()(min)(6 , 5 , 4 , 3 , 2 , 1),6 ,min()()()(min)(1111)6,min(111011

41、1vhxcvfkdvxdvfvhxcvfdvxkkkkkkkkkkkxkkkk邊界條件其中當當k=1時，由時，由f1(v1)=minc1(x1)+h1(v1) 對對v1在在0與與 之間之間的值分別進行計算的值分別進行計算即即v1=0, 1, 2, 3, 4，于是由，于是由x1=minv1+2,6知，知，x1可可取值為取值為2, 3, 4, 5, 6。分別計算如下：。分別計算如下：f1(0)=min3+ x1 +0.50=5所以所以x1=2426 , 9min6 ,min421jjddx1=min(v1+2,6)x1=2 f1(1)=min3+ x1 +0.51=6.5 所以所以x1=3f1(2

42、)=min3+ x1 +0.52=8 所以所以x1=4f1(3)=min3+ x1 +0.53=9.5 所以所以x1=5f1(4)=min3+ x1 +0.54=11 所以所以x1=6k=2，f2(v2)=minc2(x2)+h2(v2)+f1(v2+3-x2) 0 x2minv2+3, 6 x1=3x1=4x1=5x1=6v2可在可在0與與 之間取值。即之間取值。即v2可取可取值值0, 1, 2, 3。x2可在可在0與與minv2+3, 6之間取值。分別計算如下：之間取值。分別計算如下： 36 ,min432jjdd由由 有有x2=0。 5 . 9565 . 65845 . 90min) 0

43、() 0() 3 () 1 () 0() 2() 2() 0() 1 () 3 () 0() 0(min) 0(1221221221223022fhcfhcfhcfhcfx5 .1155 . 75 . 65 . 685 . 55 . 95 . 4115 . 0min)0() 1 ()4() 1 () 1 () 3()2() 1 ()2() 3() 1 () 1 ()4() 1 ()0(min) 1 (1221221221221224022fhcfhcfhcfhcfhcfx由由 有有x2=0。 用同樣的方法計算用同樣的方法計算f2(2)=minc2(x2)+h2(2)+f1(5x2)=14 ,

44、有有x2=5 0 x25 f2(3)=minc2(x2)+h2(3)+f1(6x2)=15.5，有，有x2=6 0 x26k=3，f3(v3)=minc3(x3)+h3(v3)+f2(v3+2x3) ，v3可在可在0與與min4, 62=4之間取值。之間取值。x3可在可在0與與minv3+2, 6之間取之間取值。值。 分別計算如下：分別計算如下： 有有x3=0。 145 . 955 .114140min)0()0()2() 1 ()0() 1 ()2()0()0(min)0(2332332333fhCfhCfhCf用同樣的方法計算用同樣的方法計算 f3(2)=minc3(x3)+h3(2)+f

45、2(4x3)=17.5，有，有x3=40 x34 f3(3)=minc3(x3)+h3(3)+f2(5x3)=19，有，有x3=50 x35 f3(4)=minc3(x3)+h3(4)+f2(6x3)=20.5，有，有x3=60 x36有有x3=0或或3。 16*5 . 95 . 65 .115 . 5145 . 4*55.155 . 0min) 0() 1 () 3 () 1 () 1 () 2() 2() 1 () 1 () 3 () 1 () 0(min) 1 (2332332332333fhcfhcfhcfhcfk=4，因要求第，因要求第4時期末的庫存量為時期末的庫存量為0，即，即v4

46、=0，故有，故有 f4(0)=minc4(x4)+h4(0)+f3(4x4) 0 x44 x4=0。5 .201471665 .175194*5 .200min)0()4() 1 ()3()2()2()3() 1 ()4()0(min3434343434fCfcfcfcfc按計算順序反推算，可找出每個時期的最優(yōu)生產按計算順序反推算，可找出每個時期的最優(yōu)生產決策為決策為:x1=5，x2=0，x3=6，x4=0其相應的最小總成本為其相應的最小總成本為20.5千元。千元。 例例10 某車間需要按月在月底都要供應一定數(shù)量的部件某車間需要按月在月底都要供應一定數(shù)量的部件總裝車間，由于生產條件的變化，該車

47、間在各月中生總裝車間，由于生產條件的變化，該車間在各月中生產每單位這種部件所耗費的工時不同，各月份的生產產每單位這種部件所耗費的工時不同，各月份的生產量于當月的月底前，全部要存入倉庫以備后用。已知量于當月的月底前，全部要存入倉庫以備后用。已知總裝車間的各個月份的需求量以及在加工車間生產該總裝車間的各個月份的需求量以及在加工車間生產該部件每單位數(shù)所需工時數(shù)如表部件每單位數(shù)所需工時數(shù)如表6-7所示。所示。 設庫存容量設庫存容量H=9，開始時庫存量為，開始時庫存量為2，期終庫存量為，期終庫存量為0。表表6-70 8 5 3 2 7 411 18 13 17 20 10月份需求量月份需求量 dk單位工

48、時單位工時 ak 0 1 2 3 4 5 6 月份月份 k 需要制定一個半年生產計劃，使得既滿足需要需要制定一個半年生產計劃，使得既滿足需要和庫存容量的限制，又使得總耗費工時數(shù)最少。和庫存容量的限制，又使得總耗費工時數(shù)最少。 解解 這是一個多階段決策問題，采用逆序解法。這是一個多階段決策問題，采用逆序解法。 按月份劃分階段，即階段變量為按月份劃分階段，即階段變量為k=0，1，2，6。 狀態(tài)變量狀態(tài)變量 第第k月的部件庫存量（上月月的部件庫存量（上月產品送入后，本月需求量送出前）。產品送入后，本月需求量送出前）。 決策變量決策變量 表示第表示第k月生產的部件數(shù)量。月生產的部件數(shù)量。 kuks 狀

49、態(tài)轉移方程為狀態(tài)轉移方程為階段指標階段指標最優(yōu)值函數(shù)最優(yōu)值函數(shù) 表示在表示在k月開始的庫存量為月開始的庫存量為sk，從第從第k月到月到6月末所生產部件的最小累計工時數(shù)。月末所生產部件的最小累計工時數(shù)。 遞推關系式為遞推關系式為kkua)(kksf0)(6 , 5 , 4 , 3 , 2 , 1 , 0),(min)(771)(sfkdusfuasfkkkkkksDvkkkkk, 0:)(6,.,1 , 011HdusduusDHsdkdusskkkkkkkkkkkkkk故允許決策集合為且 當當k=6時，因要求期終庫存量為時，因要求期終庫存量為0，即，即s7=0。因每月。因每月的生產是供應下月的

50、需要，故第的生產是供應下月的需要，故第6月不用生產，月不用生產，即即u6=0。因此。因此f6(s6)=0, s6=d6=4當當k=5時，由時，由s6=s5+u5-d5有有u5=11-s5 所以所以 f5(s5)=min(a5u5)=10(11-s5)=110-10s5最優(yōu)解最優(yōu)解u5*=11-s5當當k=4時，時，u5=11-s51301010min)2(1011020min)(min)(44444444544)(4444444suusudusfuasfuusDu4*4444444444444444444444592022013010)9(10)(119)(, 9119 , 0max, 011

51、9sussssfsussDssusususHdusd及最優(yōu)解故得為所以又因而又有由3*3333333331217244)(125 , 0max)(sussfsussD及最優(yōu)解故得為又280203min)3(2022017min)(min)(,333)(333)(333433)(33333333333suusudusfuasfksDusDusDu時當1*11111111111111211)(111318442)(1713)(337135min)(min)(,11111sussfsussDsudusfuasfkusDu及最優(yōu)解故得為其中時當222222222222222322)(221413273

52、)(148 , 0max)(329174min)(min)(,22222sussfsussDsudusfuasfkusDu及最優(yōu)解故得為其中時當。相應的最小總工時數(shù)為，月的最優(yōu)生產計劃為：月到所以從為：即得各階段的最優(yōu)決策再按計算順序反推之，和所以因及最優(yōu)解故得為其中時當357403947504, 0, 3, 9, 4, 77357, 2911379)(98)(442187min)(min)(,0*5*4*3*2*1*0*0000*00000000000000100)(000000uuuuuuufssussfsussDsudusfuasfkusDu 個人、單位等隨時均有設備更新問題。自行車、個

53、人、單位等隨時均有設備更新問題。自行車、彩電、設備隨著使用年限的增加而設備陳舊，處理價彩電、設備隨著使用年限的增加而設備陳舊，處理價格愈低，因此需要維修和更新的費用增加。處于各種格愈低，因此需要維修和更新的費用增加。處于各種階段的設備總是面臨保留還是更新問題。保留還是更階段的設備總是面臨保留還是更新問題。保留還是更新，應該從整個計劃期間的總回收額來考慮，而不能新，應該從整個計劃期間的總回收額來考慮，而不能從局部的某個階段的回收額來考慮，是一個多階段的從局部的某個階段的回收額來考慮，是一個多階段的決策問題。決策問題。 5.3 5.3 設備更新問題設備更新問題設備更新問題提法如下（以一臺機器為例）

54、：設備更新問題提法如下（以一臺機器為例）： n n為設備計劃使用年數(shù)。為設備計劃使用年數(shù)。 I Ik k(t)(t) 為第為第k k年（階段）機器役齡為年（階段）機器役齡為t t年的一臺機年的一臺機器運行（在使用一年）所得的收入。器運行（在使用一年）所得的收入。 O Ok k(t)(t) 為第為第k k年機器役齡為年機器役齡為t t年的一臺機器運行年的一臺機器運行（在使用一年）時所需運行的費用（或維修費用）（在使用一年）時所需運行的費用（或維修費用） 。 C Ck k(t)(t) 為第為第k k年機器役齡為年機器役齡為t t年的一臺機器更新時年的一臺機器更新時所需更新的凈費用（處理一臺役齡為所

55、需更新的凈費用（處理一臺役齡為t t的舊設備，買的舊設備，買進一臺新設備的更新凈費用）。進一臺新設備的更新凈費用）。 為折扣因子，表示一年以后的收入是上一年的為折扣因子，表示一年以后的收入是上一年的 單位。單位。 要求在要求在n n年內的每年年初作出決策，是繼續(xù)使用年內的每年年初作出決策，是繼續(xù)使用舊設備還是更換一臺新的，使舊設備還是更換一臺新的，使n n年內總效益最大？年內總效益最大？建立動態(tài)規(guī)劃模型如下：建立動態(tài)規(guī)劃模型如下： RxKxsskkkk111 階段效益為：階段效益為：RxKxscOIsOsIxsvkkkjjjkjkjkkj)() 0() 0()()(),( 階段階段k（k=1，

56、2，n）：表示計劃使用該設備的）：表示計劃使用該設備的年限數(shù)。年限數(shù)。 狀態(tài)變量狀態(tài)變量sk：第：第k年初，設備已使用過的年數(shù)，即役年初，設備已使用過的年數(shù)，即役齡。齡。 決策變量決策變量xk：是第：是第k年初更新，還是保留使用舊設年初更新，還是保留使用舊設備，分別用備，分別用R，K表示。表示。狀態(tài)轉移方程為：狀態(tài)轉移方程為： 最優(yōu)指標函數(shù)最優(yōu)指標函數(shù)fk(sk)：表示第：表示第k年初，使用一臺已用了年初，使用一臺已用了sk年的設備，到第年的設備，到第n年末的最大收益，動態(tài)規(guī)劃的基本年末的最大收益，動態(tài)規(guī)劃的基本方程為方程為0)()(),(max)(1111nnkkkkjRorKxkksfsfxsvsfk實際上實際上RxKxfscOIsfsOsIsfkkkkkkkkkkkkkkk) 1 ()() 0 () 0 () 1()()(max)(11例：設某臺新設備的年效益及年均維修費用、更新凈例：設某臺新設備的年效益及年均維修