動(dòng)態(tài)規(guī)劃習(xí)題詳解

1、動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃是運(yùn)籌學(xué)的一個(gè)分支，它是解決多階段決策過(guò)程最優(yōu)化問題的一種方法。該方法是由美國(guó)數(shù)學(xué)家貝爾曼(RBellman)等人在本世紀(jì)50年代初提出的。他們針對(duì)多階段決策問題的特點(diǎn)，提出了解決這類問題的“最優(yōu)化原理”，并成功地解決了生產(chǎn)管理、工程技術(shù)等方面的許多實(shí)際問題，從而建立了運(yùn)籌學(xué)的一個(gè)新分支動(dòng)態(tài)規(guī)劃。他的名著動(dòng)態(tài)規(guī)劃于1957年出版，該書是動(dòng)態(tài)規(guī)劃的第一本著作。 動(dòng)態(tài)規(guī)劃是現(xiàn)代企業(yè)管理中的一種重要決策方法，在工程技術(shù)、經(jīng)濟(jì)管理、工農(nóng)業(yè)生產(chǎn)及軍事及其它部們都有廣泛的應(yīng)用，并且獲得了顯著的效果。動(dòng)態(tài)規(guī)劃可用于解決最優(yōu)路徑問題、資源分配問題、生產(chǎn)計(jì)劃與庫(kù)存問題、投資分配問題、裝載問題、設(shè)

2、備更新與維修問題、排序問題及生產(chǎn)過(guò)程的最優(yōu)控制等。由于它所具有獨(dú)特的解題思路，在處理某些優(yōu)化問題時(shí)，常常比線性規(guī)劃或非線性規(guī)劃方法更有效。第 一 節(jié) 動(dòng)態(tài)規(guī)劃的基本方法多階段決策的實(shí)際問題很多，下面通過(guò)具體例子，說(shuō)明什么是動(dòng)態(tài)規(guī)劃模型及其求解方法。例1：最短路線問題某工廠需要把一批貨物從城市A運(yùn)到城市E，中間可經(jīng)過(guò)B1 、B2、B3、C1、C2、C3、D1、D2等城市，各城市之間的交通線和距離如下圖所示，問應(yīng)該選擇一條什么路線，使得從A到E的距離最短？C1B1 6 3D1 8 4 5B2A 5 6 4 EC2 9 8 7 2D3 6 3 6 7 1 C3B3 8 3 7下面引進(jìn)幾個(gè)動(dòng)態(tài)規(guī)劃的基

3、本概念和相關(guān)符號(hào)。(1)階段(Stage)把所給問題的過(guò)程，按時(shí)間和空間特征劃分成若干個(gè)相互聯(lián)系的階段，以便按次序去求每個(gè)階段的解，階段總數(shù)一般用字母n表示，用字母k表示階段變量。 如例l中 (最短路線問題)可看作是n=4階段的動(dòng)態(tài)規(guī)劃問題，k=2表示處于第二階段。 (2)狀態(tài)(State)狀態(tài)表示每個(gè)階段開始時(shí)系統(tǒng)所處的自然狀況或客觀條件，它描述了研究問題過(guò)程狀況。描述各階段狀態(tài)的變量稱為狀態(tài)變量，常用字母sk表示第k階段的狀態(tài)變量，狀態(tài)變量的取值范圍稱為狀態(tài)集，用Sk表示。 如例l中，第一階段的狀態(tài)為A（即出發(fā)位置）。第二階段有三個(gè)狀態(tài)：B1 、B2、B3，狀態(tài)變量s2=B2表示第2階段系

4、統(tǒng)所處的位置是B2。第2階段的狀態(tài)集S2= B1 、B2、B3。動(dòng)態(tài)規(guī)劃中的狀態(tài)變量應(yīng)具有如下性質(zhì)：當(dāng)某階段狀態(tài)給定以后，在這個(gè)階段以后過(guò)程的發(fā)展不受這個(gè)階段以前各個(gè)階段狀態(tài)的影響。也就是說(shuō)，未來(lái)系統(tǒng)所處的狀態(tài)只與系統(tǒng)當(dāng)前所處的狀態(tài)有關(guān)，而與系統(tǒng)過(guò)去所處的狀態(tài)無(wú)關(guān)，即過(guò)去歷史只能通過(guò)當(dāng)前的狀態(tài)去影響它未來(lái)的發(fā)展，這種特點(diǎn)稱為無(wú)后效性（又稱馬爾可夫性）。如果所選定的狀態(tài)變量不具備無(wú)后效性，就不能作為狀態(tài)變量來(lái)構(gòu)造動(dòng)態(tài)規(guī)劃模型。如例1中，當(dāng)某階段的初始狀態(tài)即所在的城市選定以后，從這個(gè)狀態(tài)以后的運(yùn)貨路線只與這個(gè)城市有關(guān)，不受以前的運(yùn)貨路線影響，所以是滿足狀態(tài)的無(wú)后效性的。（3）決策(Decision

5、) 當(dāng)系統(tǒng)在某階段處于某種狀態(tài)，可以采取的行動(dòng)（或決定、選擇），從而確定下一階段系統(tǒng)將到達(dá)的狀態(tài)，稱這種行動(dòng)為決策。描述決策的變量，稱為決策變量。常用字母u k(sk)表示第k階段系統(tǒng)處于狀態(tài)sk時(shí)的決策變量。決策變量的取值范圍稱為決策集，用Dk(sk)表示。 在例l的第二階段中，若從狀態(tài)B2出發(fā)，可以做出三種不同的決策，其允許的決策集為D2(B2)= C1、C2、C3，決策u 2(B2)= C2表示第二階段處于狀態(tài)B2，選擇的確行動(dòng)下一階段是走到C2。 （4）策略(Policy)系統(tǒng)從第k階段的狀態(tài)sk開始由每階段的決策按順序組成的決策序列 u k(sk) ，u k+1(sk+1)，u n(

6、sn)稱為一個(gè)策略（k=1,2, ，n）,記作。在例l中，p2,4(B2)= u 2(B2)= C2，u3(C2)= D1，u 4(D1)=E是一個(gè)策略，表示第二階段從狀態(tài)B2出發(fā)，沿著B2C2D1E的方向走到終點(diǎn)。注意策略必須是一串實(shí)際可行的序列行動(dòng)。（5）狀態(tài)轉(zhuǎn)移方程系統(tǒng)由這一階段的個(gè)狀態(tài)進(jìn)行決策后轉(zhuǎn)變到下階段的另個(gè)狀態(tài)稱為狀態(tài)轉(zhuǎn)移，狀態(tài)轉(zhuǎn)移既與狀態(tài)有關(guān)，又與決策有關(guān)，描述狀態(tài)轉(zhuǎn)移關(guān)系的方程稱為狀態(tài)轉(zhuǎn)移方程，記為：sk+1=Tk(sk，uk)它的實(shí)際意義是當(dāng)系統(tǒng)第k階段處于狀態(tài)sk做決策uk時(shí)，第k+1階段系統(tǒng)轉(zhuǎn)移到狀態(tài)sk+1。狀態(tài)轉(zhuǎn)移方程在不同的問題中有不同的具體表現(xiàn)形式，在例l中，狀

7、態(tài)轉(zhuǎn)移方程表示為：sk+1=uk(sk)。（6）階段指標(biāo)階段效益是衡量系統(tǒng)階段決策結(jié)果的一種數(shù)量指標(biāo)，記為：表示系統(tǒng)在第k階段處于狀態(tài)sk做出決策uk時(shí)所獲得的階段效益。這里的階段效益在不同的實(shí)際問題中有不同的意義。在例l中它表示兩個(gè)中轉(zhuǎn)站的距離，如表示從中轉(zhuǎn)站B2走到中轉(zhuǎn)站C2之間的距離為7。更一般地有。（7）指標(biāo)函數(shù)指標(biāo)函數(shù)是用來(lái)街量所實(shí)現(xiàn)過(guò)程的優(yōu)劣的一種數(shù)量指標(biāo)，它是一個(gè)定義在全過(guò)程和所有后部子過(guò)程上的確定的數(shù)量函數(shù)，記為：它應(yīng)具有可分離性，并滿足遞推關(guān)系式：常見的指標(biāo)函數(shù)的形式是：1）過(guò)程和任一子過(guò)程的指標(biāo)是它所包含的各階段指標(biāo)的和。既2）過(guò)程和任一子過(guò)程的指標(biāo)是它所包含的各階段指標(biāo)的

8、積。既（8）最優(yōu)值函數(shù)指標(biāo)函數(shù)的最優(yōu)值，稱為最優(yōu)值函數(shù)，記為。它表示系統(tǒng)在第k階段處于狀態(tài)sk時(shí)按最優(yōu)策略行動(dòng)所獲得總的效益。既 其中opt是最優(yōu)化（optimization）的縮寫，根據(jù)實(shí)際問題可取max(最大值)和min(最小值),表示對(duì)所有允許策略使后面算式取最優(yōu)。下面利用動(dòng)態(tài)規(guī)劃的逆推歸納法，將例1從最后一個(gè)城市E逐步推算到第一個(gè)城市A，在此表示第k階段從城市sk到城市E最短路。1)當(dāng)k=4時(shí)：要求，由于第4階段只有兩個(gè)城市D1、D2（即s4的取值為D1、D2），從D1到E只有一條路，故，同理。2)當(dāng)k=3時(shí)：s3的取值為C1、C2、C3，從C1出發(fā)到E有兩條路，一條是經(jīng)過(guò)D1到E，另

9、一條是經(jīng)過(guò)D2到E ，顯然：即從C1出發(fā)到E的最短路為7，相應(yīng)決策為，最短路線是C1D1E。同理 2)當(dāng)k=2時(shí)：s2的取值為B1、B2、B3，從B1出發(fā)到E有三條路，分別是經(jīng)過(guò)C1、C2、C3到E，則有：同理 2)當(dāng)k=1時(shí)：s1的只有一個(gè)取值為A. 從A出發(fā)到E有三條路，分別是經(jīng)過(guò)B1、B2、B3到E，則有：于是得到從A到E的最短距離17，為了找出最短路線，按計(jì)算的順序逆推回去，可得到最優(yōu)策略為：，最短路線是AB1C2D2E。第 二 節(jié) 動(dòng)態(tài)規(guī)劃的基本原理從上面的計(jì)算過(guò)程中可以看出，在求解的各個(gè)階段，利用了k階段與k+1階段之間的遞推關(guān)系：這種遞推關(guān)系稱為動(dòng)態(tài)規(guī)劃的基本方程，其中稱為邊界條

10、件。這個(gè)遞推方程，是根據(jù)下述動(dòng)態(tài)規(guī)劃的貝爾曼(RBellman)最優(yōu)化原理推導(dǎo)得來(lái)的。動(dòng)態(tài)規(guī)劃最優(yōu)化原理：“作為整個(gè)過(guò)程的最優(yōu)策略具有這樣的性質(zhì)：即無(wú)論過(guò)去的狀態(tài)和決策如何，對(duì)前面的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略?！焙?jiǎn)單地說(shuō)就是一個(gè)最優(yōu)策略的子策略也是最優(yōu)的。一般情況下，作為一個(gè)動(dòng)態(tài)規(guī)劃模型的最優(yōu)值函數(shù)在k階段與k+1階段之間必須滿足下列遞推關(guān)系：1） 加法型：若則: 即: (1)邊界條件為 2）乘法型： (2)邊界條件為 這種遞推關(guān)系式(1)、(2) 稱為動(dòng)態(tài)規(guī)劃的基本方程。這樣的求解方法稱為逆推解法（或逆序解法）。同理也可給出順推解法（或順序解法），動(dòng)態(tài)規(guī)劃的順序解法的

11、基本方程為：1）加法型： (1)邊界條件為 2）乘法型： (2)邊界條件為 注意：此時(shí)狀態(tài)轉(zhuǎn)移方程變?yōu)椋簊k=Tk(sk1，uk)通過(guò)對(duì)最短路線問題的求解，我們可以把動(dòng)態(tài)規(guī)劃方法的基本思想歸納如下：動(dòng)態(tài)規(guī)劃方法的關(guān)鍵，在于利用最優(yōu)化原理給出最優(yōu)值函數(shù)的遞推關(guān)系式和邊界條件，為此，必須先將問題的過(guò)程劃分為幾個(gè)相互聯(lián)系的階段，適當(dāng)選取狀態(tài)變量、決策變量, 狀態(tài)轉(zhuǎn)移方程及定義最優(yōu)值函數(shù)。從而把一個(gè)大問題化成一系列同類型的子問題，然后逐個(gè)求解。例3：逆推解法求解下面問題:解: 按問題的變量個(gè)數(shù)劃分階段,把它看作一個(gè)三階段決策問題。設(shè)狀態(tài)變量為s1，s2，s3，s4。并記s1c；令變量x1，x2，x3為

12、決策變量；各階段指標(biāo)按乘積方式結(jié)合。即令:令最優(yōu)值函數(shù)f k(sk)表示為第k階段的初始狀態(tài)為sk時(shí)，從第k階段到第3階段所得到的最大值。設(shè): s3= x3, s3+ x2=s2, s2+ x1=s1=c則有：x3=s3, 0x2s2, 0x1s1=c即狀態(tài)轉(zhuǎn)移方程為： s3=s2x2, s2 =s1x1由逆推解法，即最優(yōu)解x3=s3,由,得和（舍去）又，而，故為極大值點(diǎn)。所以即最優(yōu)解。求導(dǎo)并令導(dǎo)數(shù)等于0可得：，故由于s1=c，由s2 =s1x1，,由s3 =s2x2，因此最優(yōu)解為：，最大值為：例3：用順推解法求解下面問題:解:設(shè)s4c，決策變量仍為x1，x2，x3；最優(yōu)值函數(shù)f k(sk+1

13、)表示為第k階段末的結(jié)束狀態(tài)為sk+1，從第1階段到第k階段所得到的最大值。設(shè): s2= x1, s2+ x2=s3, s3+ x3=s4=c則有：x1=s2, 0x2s3, 0x3s4=c即狀態(tài)轉(zhuǎn)移方程為： s2=s3x2, s3=s4x3由順推解法，即最優(yōu)解x1=s2,最優(yōu)解。最優(yōu)解由于s4=c，由s3=s4x3，,由s2=s3x2，因此最優(yōu)解為：，最大值為：例4：用順推解法求解下面問題:解: 按問題的變量個(gè)數(shù)劃分階段,把它看作一個(gè)三階段決策問題。設(shè)狀態(tài)變量為s0，s1，s2，s3。并記s39；令變量x1，x2，x3為決策變量；最優(yōu)值函數(shù)f k(sk)表示為第k階段末的結(jié)束狀態(tài)為sk，從第

14、1階段到第k階段所得到的最大值。設(shè): 3x1=s1, s1+2x2=s2, s2+ x3=s39則有：x1=s13,0x2s22 , 0x3s39即狀態(tài)轉(zhuǎn)移方程為： s1=s22x2, s2=s3x3由順推解法，即最優(yōu)解x1=s13,由,得(它不在決策集內(nèi))則最大值在端點(diǎn)上，最大值點(diǎn)為x2=0。故得到及最優(yōu)解。由,得又，故該點(diǎn)為極小值點(diǎn)。而最大值點(diǎn)為x3=s3。故得到及最優(yōu)解。由于s3不知道，故須在對(duì)s3求一次極值，即反推回去即可得最優(yōu)解為：，最大值為：作業(yè) P214 1，5（1逆推，2順推）第 二 節(jié) 動(dòng)態(tài)規(guī)劃應(yīng)用舉例一、資源分配問題假設(shè)有某種資源的總數(shù)量為a(例如原材料、能源、機(jī)器設(shè)備、勞

15、力、食品等)，可用于生產(chǎn)n個(gè)產(chǎn)品，若生產(chǎn)j種產(chǎn)品的所用資源數(shù)為xj時(shí)，可獲得利潤(rùn)為gj(xj)，問如何分配該種資源，使所獲得的總利潤(rùn)達(dá)到最大。該問題的數(shù)學(xué)模型可表示為：當(dāng)gj(xj)都是線性函數(shù)時(shí)，它是一個(gè)線性規(guī)劃問題；當(dāng)gj(xj)是非線性函數(shù)時(shí),它是個(gè)非線性規(guī)劃問題。但當(dāng)n比較大時(shí)，求解起來(lái)是非常麻煩的。由于該問題的特殊性，可以將它看成一個(gè)多階段決策問題，并利用動(dòng)態(tài)規(guī)劃的方法來(lái)求解。我們將n個(gè)產(chǎn)品看作是n個(gè)階段，設(shè)狀態(tài)變量sk表示生產(chǎn)第k個(gè)產(chǎn)品至第n個(gè)產(chǎn)品的資源數(shù)量，。決策變量xj表示生產(chǎn)第k個(gè)產(chǎn)品的所用資源數(shù)量，。顯然狀態(tài)轉(zhuǎn)移方方程為：第k階段的階段指標(biāo)為：。最優(yōu)值函數(shù)表示生產(chǎn)第k個(gè)產(chǎn)品

16、至第n個(gè)產(chǎn)品的資源數(shù)量為sk時(shí)所獲得的最大總利潤(rùn)。則由動(dòng)態(tài)規(guī)劃最優(yōu)化原理，可得動(dòng)態(tài)規(guī)劃的基本方程為：下面我們來(lái)考慮一種資源可回收利用的資源分配問題，這類分配問題的一般描述如下：設(shè)有某種資源，初始的擁有量是s1。計(jì)劃在A、B兩個(gè)生產(chǎn)車間連續(xù)使用n個(gè)階段。巳知在A車間投入資源x時(shí)的階段收益是g(x)，在B車間投入資源y時(shí)的階段收益是h(y)。投入的資源在生產(chǎn)過(guò)程中有部分消耗,已知，每生產(chǎn)一個(gè)階段后，車間A、B的資源回收率分別為a和b，0 a，b 1?；厥盏馁Y源下一階段可繼續(xù)使用，求n階段間總收益最大的資源分配計(jì)劃。設(shè)sj為第j階段投入A、B兩個(gè)車間使用的資源數(shù)，j=1、2、n。xj為第j階段投入A

17、車間使用的資源數(shù)，投入B車間使用的資源數(shù)為yj=sj-xj，j=1、2、n。此問題的靜態(tài)規(guī)劃模型為：該模型可用動(dòng)態(tài)規(guī)劃的方法來(lái)處理。令sk為狀態(tài)變量，表示在第k階段投入A、B兩個(gè)車間使用的資源數(shù)，k=1、2、n。xk為決策變量，它表示在第k階段投入A車間使用的資源數(shù)，則yk=skxk表示在第k階段投入B車間使用的資源數(shù)，k=1、2、n。狀態(tài)轉(zhuǎn)移方程為：sk+1=axk+b(s kxk)最優(yōu)值函數(shù)表示擁有資源數(shù)為sk時(shí)，從第k階段至第n階段采取最優(yōu)分配方案進(jìn)行生產(chǎn)時(shí)所獲得的最大總收益。則動(dòng)態(tài)規(guī)劃的遞推公式 下面我們對(duì)一個(gè)具體問題，用此方法求解。 例1：機(jī)器負(fù)荷分配問題某公司新購(gòu)進(jìn)1000臺(tái)機(jī)床，

18、每臺(tái)機(jī)床都可在高、低兩種不同的負(fù)荷下進(jìn)行生產(chǎn)，設(shè)在高負(fù)荷下生產(chǎn)的產(chǎn)量函數(shù)為g(x)=10x（單位：百件），其中x為投入生產(chǎn)的機(jī)床數(shù)量，年完好率為a=0.7；在低負(fù)荷下生產(chǎn)的產(chǎn)量函數(shù)為h(y)=6y（單位：百件），其中y為投人生產(chǎn)的機(jī)床數(shù)量，年完好率為b=0.9。計(jì)劃連續(xù)使用5年，試問每年如何安排機(jī)床在高、低負(fù)荷下的生產(chǎn)計(jì)劃，使在五年內(nèi)生產(chǎn)的產(chǎn)品總產(chǎn)量達(dá)到最高。 解：該問題可看作一個(gè)5階段決策問題，一個(gè)年度就是一個(gè)階段。狀態(tài)變量sk取為第k年度度初具有的完好機(jī)床臺(tái)數(shù)。決策變量xk為第k年度中分配在高負(fù)荷下生產(chǎn)的機(jī)器臺(tái)數(shù)，則yk=skxk為第k年度中分配在低負(fù)荷下生產(chǎn)的機(jī)器臺(tái)數(shù)（假定xk、sk皆為

19、連續(xù)變量）。狀態(tài)轉(zhuǎn)移方方程為：sk+1=axk+b(sk-xk)=0.7xk+0.9(sk-xk)第k年度的產(chǎn)量為：vk(sk,xk)=10xk+6(sk-xk)最優(yōu)值函數(shù)表示擁有機(jī)床數(shù)為sk時(shí)，從第k年度至第五年度采取最優(yōu)分配方案進(jìn)行生產(chǎn)時(shí)所獲得的最大總產(chǎn)量。則動(dòng)態(tài)規(guī)劃的基本方程為： 下面第5年度開始，用逆推歸納法進(jìn)行計(jì)算。1）k=5時(shí)，有因?yàn)槭莤5的單調(diào)增加函數(shù)，故的最大解為，相應(yīng)有=10s5。 2) k=4時(shí)，有因?yàn)槭莤4的單調(diào)增加函數(shù)，故的最大解為，相應(yīng)有=17s4。3) k=3時(shí)，有因?yàn)槭莤3的單調(diào)增加函數(shù)，故的最大解為，相應(yīng)有=21.9s3。4) 當(dāng)k=2時(shí)，有 因?yàn)槭莤2的單調(diào)減

20、少函數(shù)，故的最大解為，相應(yīng)有=25.71s2。5) 當(dāng)k=1時(shí)，有因?yàn)槭莤1的單調(diào)減少函數(shù)，故的最大解為，相應(yīng)有=29.139s1。由于第l階段的初始狀態(tài)s1是給定的，即s1=1000，因此最優(yōu)目標(biāo)函數(shù)值為=29139（百件）。計(jì)算結(jié)果表明：最優(yōu)策略為，。即前兩年應(yīng)把年初全部完好機(jī)床投入低負(fù)荷生產(chǎn)，后三年應(yīng)把年初全部完好機(jī)床投入高負(fù)荷生產(chǎn)。這樣所得的產(chǎn)量最高，其最高產(chǎn)量為29139百件產(chǎn)品。同時(shí)，從求解過(guò)程還可反過(guò)來(lái)確定每年年初的狀態(tài)，即每年年初所擁有的完好機(jī)器臺(tái)數(shù)。已知s1=1000，于是可得：由此可知最優(yōu)的決策過(guò)程是：第一年將全部1000臺(tái)機(jī)器全部投入到低負(fù)荷下進(jìn)行生產(chǎn)，第一年末機(jī)床完好數(shù)

21、是900臺(tái)，第二年將900臺(tái)機(jī)器繼續(xù)投入到低負(fù)荷下進(jìn)行生產(chǎn)，第二年末機(jī)床完好數(shù)成為810臺(tái)，第三年改變策略將這810臺(tái)機(jī)床全部投入到高負(fù)荷下進(jìn)行生產(chǎn)，第三年末機(jī)床完好數(shù)為567臺(tái)，第四年將這567臺(tái)機(jī)床全部投入到高負(fù)荷下進(jìn)行生產(chǎn)，第四年末機(jī)床完好數(shù)成為397臺(tái)，第五年將這397臺(tái)機(jī)床投入到高負(fù)荷下進(jìn)行生產(chǎn)，這樣第五年末剩下的完好機(jī)床數(shù)為278臺(tái)，五年共生產(chǎn)產(chǎn)品29139（百件）。 二、生產(chǎn)與存儲(chǔ)問題假設(shè)為有一個(gè)企業(yè)，要制定某種產(chǎn)品n個(gè)階段（例如年、月、周）的生產(chǎn)（或購(gòu)買）計(jì)劃，已知初始的存儲(chǔ)量為零，第k個(gè)階段市場(chǎng)需求量為dk，每個(gè)階段企業(yè)的最大產(chǎn)量為M，單位產(chǎn)品的生產(chǎn)成本為a，每次生產(chǎn)的生產(chǎn)準(zhǔn)

22、備成本為K。問該企業(yè)如何安排生產(chǎn)和存儲(chǔ)，才能即滿足市場(chǎng)需求，又使總的費(fèi)用最少？設(shè)xk為第k個(gè)階段該產(chǎn)品的生產(chǎn)量。sk為第k個(gè)階段末該產(chǎn)品的庫(kù)存量，則有sk=sk-1+xk-dk。表示第k個(gè)階段該產(chǎn)品xk時(shí)的成本費(fèi)用，它包括生產(chǎn)準(zhǔn)備成本K和產(chǎn)品成本axk兩項(xiàng)費(fèi)用，即表示在第k個(gè)階段結(jié)束時(shí)有庫(kù)存量sk所需的存儲(chǔ)費(fèi)用。故第k個(gè)階段的總成本費(fèi)用為。上述問題的數(shù)學(xué)模型為：現(xiàn)在我們用動(dòng)態(tài)規(guī)劃的順推歸納法來(lái)求解，把它看作一個(gè)n階段決策問題。令 xk為決策變量，它表示在第k階段的生產(chǎn)量。sk為狀態(tài)變量，它表示在第k個(gè)階段末該產(chǎn)品的庫(kù)存量。則狀態(tài)轉(zhuǎn)移方程為：sk=sk-1+xk-dk。最優(yōu)值函數(shù)表示從第1階段初

23、始庫(kù)存量為0到第k階段末庫(kù)存量為sk時(shí)的最小總費(fèi)用。則其順序遞推關(guān)系式： 其中，這是因?yàn)橐环矫嬖诿總€(gè)階段企業(yè)的最大產(chǎn)量為M，另一方面由于滿足每個(gè)階段市場(chǎng)的需求量，因?yàn)榈趉-1階段末庫(kù)存量為sk-1必須非負(fù)，即:sk-1= dk+sk -xk0 , xk dk+sk。邊界條件為（或）。從邊界條件出發(fā)，利用上面順序遞推關(guān)系式，最后求出的即為所要求的最小總費(fèi)用。下面通過(guò)一個(gè)實(shí)際例子計(jì)算之。例2：某企業(yè)通過(guò)市場(chǎng)調(diào)查，估計(jì)今后四個(gè)時(shí)期市場(chǎng)對(duì)某種產(chǎn)品的需要量如下表：時(shí)期(k)1234需要量(dk)2（單位）324假定不論在任何時(shí)期，生產(chǎn)每批產(chǎn)品的固定成本費(fèi)為3(千元)，若不生產(chǎn)，則為零；生產(chǎn)單位產(chǎn)品成本費(fèi)

24、為1(千元)；每個(gè)時(shí)期生產(chǎn)能力所允許的最大生產(chǎn)批量為不超過(guò)6個(gè)單位，則任何時(shí)期生產(chǎn)x個(gè)單位產(chǎn)品的成本費(fèi)用為： 若 0x6 ， 則生產(chǎn)總成本3十1·x 若 x0 ， 則生產(chǎn)總成本0又設(shè)每個(gè)時(shí)期末未銷售出去的產(chǎn)品，在一個(gè)時(shí)期內(nèi)單位產(chǎn)品的庫(kù)存費(fèi)用為0.5(千元)，同時(shí)還假定第1時(shí)期開始之初和在第4個(gè)時(shí)期之末，均無(wú)產(chǎn)品庫(kù)存?，F(xiàn)在我們的問題是；在滿足上述給定的條件下，該廠如何安排各個(gè)時(shí)期的生產(chǎn)與庫(kù)存，使所花的總成本費(fèi)用最低？解：我們將四個(gè)時(shí)期分為4個(gè)階段，設(shè)k為階段變量，k1，2，3，4。狀態(tài)變量為sk，它表示在第k個(gè)階段末該產(chǎn)品的庫(kù)存量。決策變量為xk，它表示在第k階段的生產(chǎn)量。則狀態(tài)轉(zhuǎn)移方

25、程為：sk-1= sk-xk+dk。在第k個(gè)階段生產(chǎn)準(zhǔn)備成本為： 第k個(gè)階段結(jié)束時(shí)有庫(kù)存量sk所需的存貯費(fèi)用為：。故第k個(gè)階段的總成本費(fèi)用為。則其順序遞推關(guān)系式：其中 邊界條件，。 1）當(dāng)k=1時(shí)，由于 對(duì)s1的可能取值在0至的值分別進(jìn)行計(jì)算。 2）當(dāng)k=2時(shí)，由于 對(duì)s2的可能取值在0至( s1最大可取到4)的值分別進(jìn)行計(jì)算。3）當(dāng)k=3時(shí)，由于 對(duì)s3的可能取值在0至( s2最大可取到6)的值分別進(jìn)行計(jì)算。4）當(dāng)k=4時(shí)，由于要求的第4個(gè)階段結(jié)束時(shí)的庫(kù)存量為0，即s4=0，因此只須計(jì)算 再按計(jì)算的順序反推回去，可得到每個(gè)時(shí)期的確最優(yōu)生產(chǎn)決策為：。其相應(yīng)的最小總成本為20.5千元。三、設(shè)備更

26、新問題 現(xiàn)以一臺(tái)機(jī)器在n年內(nèi)使用和更新決策為例來(lái)說(shuō)明模型的求解方法，用表示在第k年初機(jī)器已使用t年（或稱役齡為t年），再使用1年時(shí)所獲得的收益。 表示在第k年初役齡為t年的機(jī)器，再使用1年時(shí)所需要的運(yùn)行費(fèi)用（或維修保養(yǎng)費(fèi)用）。 表示在第k年初賣掉一臺(tái)役齡為t年的機(jī)器，再買進(jìn)一臺(tái)新機(jī)器所需要凈成本費(fèi)用。 要求在n年內(nèi)機(jī)器的更新策略，使得總效益達(dá)到最大。下面建立該問題的動(dòng)態(tài)規(guī)劃模型。 設(shè)狀態(tài)變量sk表示在第k年初機(jī)器已使用的年數(shù)，即機(jī)器的役齡。決策變量xk表示在第k年初是繼續(xù)使用舊機(jī)器還是更換新機(jī)器的決策，令。狀態(tài)轉(zhuǎn)移方程為：第k階段的效益函數(shù)為。最優(yōu)值函數(shù)表示第k年初有一臺(tái)役齡為sk的機(jī)器至第n年按最優(yōu)方案進(jìn)行更新決策時(shí)所獲得的最大總效益。則由動(dòng)態(tài)規(guī)劃的最優(yōu)化原理，可得動(dòng)態(tài)規(guī)劃的基本方程為： 一個(gè)具數(shù)字例子如下：例3：設(shè)某企業(yè)在第一年初購(gòu)買一臺(tái)新設(shè)備，該設(shè)備在五年內(nèi)的年運(yùn)行收益、年運(yùn)行費(fèi)用及更換新設(shè)備的凈費(fèi)用如下表：（單位：萬(wàn)元）年份(k)役齡(t)運(yùn)行收益運(yùn)行費(fèi)用更新費(fèi)用第一