運(yùn)籌學(xué)第六章

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

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

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

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

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

6、k= =n時(shí)時(shí)逆推解法小結(jié)：逆推解法小結(jié)： 設(shè)已知初始狀態(tài)設(shè)已知初始狀態(tài)s s1 1，最優(yōu)值函數(shù)，最優(yōu)值函數(shù)fk k( (sk k) )表示從表示從k階段到階段到n階段所得到的最大效益。以求最大化為例來(lái)階段所得到的最大效益。以求最大化為例來(lái)說(shuō)明。說(shuō)明。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) )只有一個(gè)決策只有一個(gè)決策,

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

8、(sk) )。如此類推，直到第一階段。如此類推，直到第一階段。當(dāng)階段當(dāng)階段k=1時(shí)時(shí) ,22111)(11max111sfxsvsfsDs其中狀態(tài)轉(zhuǎn)移方程其中狀態(tài)轉(zhuǎn)移方程.,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)轉(zhuǎn)移方程按照上述遞推過(guò)程相反順根據(jù)狀態(tài)轉(zhuǎn)移方程按照上述遞推過(guò)程相反順序推算下去，就可逐步確定出每階段的決策及效序推算下去，就可逐步確定出每階段

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

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

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

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

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

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

15、 s，從，從1 1階段到階段到k階段所得到的最階段所得到的最大效益。以求最大化為例來(lái)說(shuō)明。大效益。以求最大化為例來(lái)說(shuō)明。),(,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) )只有一個(gè)決策只有一個(gè)決策, ,則可寫成則可寫成 x1 1= =x1 1( (s2 2) )。具體方法如下：具體方法如下：

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

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

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

19、種原料，總數(shù)量為a，用于生產(chǎn)，用于生產(chǎn)n種產(chǎn)品。種產(chǎn)品。若分配數(shù)量若分配數(shù)量xi用于生產(chǎn)第用于生產(chǎn)第i 種產(chǎn)品，其收益為種產(chǎn)品，其收益為g gi i(x(xi i) )問(wèn)應(yīng)如何分配，才能使生產(chǎn)問(wèn)應(yīng)如何分配，才能使生產(chǎn)n種產(chǎn)品的總收入最大？種產(chǎn)品的總收入最大？ 將數(shù)量一定的一種或若干種資源，恰當(dāng)?shù)胤峙鋵?shù)量一定的一種或若干種資源，恰當(dāng)?shù)胤峙浣o若干個(gè)使用者，使效益函數(shù)為最優(yōu)。給若干個(gè)使用者，使效益函數(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: :分配給生產(chǎn)第分配給生產(chǎn)第k種產(chǎn)品的原料數(shù)量，即種產(chǎn)品的原料數(shù)量，即uk= =xk；sk: :分配給用于生產(chǎn)第分配給用于生產(chǎn)第k種至第種至第n種產(chǎn)品的原料數(shù)量；種產(chǎn)品的原料數(shù)量；狀態(tài)轉(zhuǎn)移方程：狀態(tài)轉(zhuǎn)移方程： sk+1+1= =sk- -uk= =sk- -xk最優(yōu)值函數(shù)最優(yōu)值函數(shù)fk( (sk):):數(shù)量為數(shù)量為sk的原料分配給第的原料分配給第k種產(chǎn)品種產(chǎn)品至第至第n種產(chǎn)品所得到的最大總收益，動(dòng)態(tài)規(guī)劃的遞推種產(chǎn)品所得到的最大總收益，動(dòng)態(tài)規(guī)劃的遞推關(guān)系為：關(guān)系為：某工業(yè)部

21、門根據(jù)國(guó)家計(jì)劃的安排，擬將某種高效某工業(yè)部門根據(jù)國(guó)家計(jì)劃的安排，擬將某種高效率的設(shè)備率的設(shè)備5 5臺(tái)分配給所屬的甲、乙、丙三個(gè)工廠，臺(tái)分配給所屬的甲、乙、丙三個(gè)工廠，各工廠若獲得這種設(shè)備，可以為公司提供的盈利各工廠若獲得這種設(shè)備，可以為公司提供的盈利如表。如表。問(wèn)：這五臺(tái)設(shè)備如何分配給各工廠，才能使公司問(wèn)：這五臺(tái)設(shè)備如何分配給各工廠，才能使公司得到的盈利最大。得到的盈利最大。例例1 1 工工 廠廠盈利盈利 設(shè)備臺(tái)數(shù)設(shè)備臺(tái)數(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 解：將問(wèn)題按工廠分為解：將問(wèn)題按工廠分為

22、三個(gè)階段，甲、乙、丙三個(gè)階段，甲、乙、丙分別編號(hào)為分別編號(hào)為1 1，2 2，3 3。 工工 廠廠盈盈利利 設(shè)設(shè)備備臺(tái)臺(tái)數(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時(shí)，時(shí)，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è) 備備 臺(tái)臺(tái) 數(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è) 備備 臺(tái)臺(tái) 數(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 當(dāng)階段當(dāng)階段k=2時(shí)，時(shí)， 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 結(jié)果列于下表：結(jié)果列于下表：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當(dāng)階段當(dāng)階段k=1時(shí)，時(shí)， 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 結(jié)果可寫成表格的形式結(jié)果

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按計(jì)算表格的順序逆推，可知最優(yōu)分配方案有兩個(gè)：按計(jì)算表格的順序逆推，可知最優(yōu)分配方案有兩個(gè)：甲工廠分配甲

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

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

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

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

36、 , 2 , 5)( 9 . 07 . 0()( 58max)(0)(1066kusufususfsfkkkkkkksukkkk指標(biāo)函數(shù)指標(biāo)函數(shù)515 , 1),(kkkkusvV允許決策集合允許決策集合 0 uk sk當(dāng)當(dāng)k=5時(shí)時(shí) , f5(s5)= max 8u5+5 s5 - u5 + f6(s6) 0u5 s5=max 3u5+5 s5 0u5 s5u5*= s5 , f5(s5)=8 s5當(dāng)當(dāng)k=4時(shí)時(shí) , 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最高產(chǎn)量為最高產(chǎn)量為f1(s1) =23700(臺(tái)臺(tái))。因此最優(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 生產(chǎn)存貯問(wèn)題生產(chǎn)存貯問(wèn)題 一個(gè)生產(chǎn)部門，如何在已知生產(chǎn)成本、庫(kù)存一個(gè)生產(chǎn)部門，如何在已知

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

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

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

41、1vhxcvfkdvxdvfvhxcvfdvxkkkkkkkkkkkxkkkk邊界條件其中當(dāng)當(dāng)k=1時(shí)，由時(shí)，由f1(v1)=minc1(x1)+h1(v1) 對(duì)對(duì)v1在在0與與 之間之間的值分別進(jìn)行計(jì)算的值分別進(jìn)行計(jì)算即即v1=0, 1, 2, 3, 4，于是由，于是由x1=minv1+2,6知，知，x1可可取值為取值為2, 3, 4, 5, 6。分別計(jì)算如下：。分別計(jì)算如下：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之間取值。分別計(jì)算如下：之間取值。分別計(jì)算如下： 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。 用同樣的方法計(jì)算用同樣的方法計(jì)算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之間取之間取值。值。 分別計(jì)算如下：分別計(jì)算如下： 有有x3=0。 145 . 955 .114140min)0()0()2() 1 ()0() 1 ()2()0()0(min)0(2332332333fhCfhCfhCf用同樣的方法計(jì)算用同樣的方法計(jì)算 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時(shí)期末的庫(kù)存量為時(shí)期末的庫(kù)存量為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按計(jì)算順序反推算，可找出每個(gè)時(shí)期的最優(yōu)生產(chǎn)按計(jì)算順序反推算，可找出每個(gè)時(shí)期的最優(yōu)生產(chǎn)決策為決策為:x1=5，x2=0，x3=6，x4=0其相應(yīng)的最小總成本為其相應(yīng)的最小總成本為20.5千元。千元。 例例10 某車間需要按月在月底都要供應(yīng)一定數(shù)量的部件某車間需要按月在月底都要供應(yīng)一定數(shù)量的部件總裝車間，由于生產(chǎn)條件的變化，該車

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

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

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

50、需要，故第的生產(chǎn)是供應(yīng)下月的需要，故第6月不用生產(chǎn)，月不用生產(chǎn)，即即u6=0。因此。因此f6(s6)=0, s6=d6=4當(dāng)當(dāng)k=5時(shí)，由時(shí)，由s6=s5+u5-d5有有u5=11-s5 所以所以 f5(s5)=min(a5u5)=10(11-s5)=110-10s5最優(yōu)解最優(yōu)解u5*=11-s5當(dāng)當(dāng)k=4時(shí)，時(shí)，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時(shí)當(dāng)1*11111111111111211)(111318442)(1713)(337135min)(min)(,11111sussfsussDsudusfuasfkusDu及最優(yōu)解故得為其中時(shí)當(dāng)222222222222222322)(221413273

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

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

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

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

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