建立動(dòng)態(tài)規(guī)劃數(shù)學(xué)模型的步驟

1、 運(yùn) 籌 學(xué)動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃 3 建立動(dòng)態(tài)規(guī)劃數(shù)學(xué)模型的步驟 “最優(yōu)化原理”是動(dòng)態(tài)規(guī)劃的核心,所有動(dòng)態(tài)規(guī)劃問(wèn)題的遞推關(guān)系都是根據(jù)這個(gè)原理建立起來(lái)的,并且根據(jù)遞推關(guān)系依次計(jì)算,最終可求得動(dòng)態(tài)規(guī)劃問(wèn)題的解。 一般來(lái)說(shuō)，利用動(dòng)態(tài)規(guī)劃求解實(shí)際問(wèn)題需先建立問(wèn)題的動(dòng)態(tài)模型，具體步驟如下： 將問(wèn)題按時(shí)間或空間次序劃分成若干階段。有些問(wèn)題不具有時(shí)空次序，也可以人為地引進(jìn)時(shí)空次序，劃分階段。 正確選擇狀態(tài)變量xk。這一步是形成動(dòng)態(tài)模型的關(guān)鍵，狀態(tài)變量是動(dòng)態(tài)規(guī)劃模型中最重要的參數(shù)。一般來(lái)說(shuō)，狀態(tài)變量應(yīng)具有以下三個(gè)特性： 要能夠用來(lái)描述決策過(guò)程的演變特征。 要滿足無(wú)后效性。即如果某階段狀態(tài)已給定后，則以后過(guò)程的進(jìn)展

2、不受以前各狀態(tài)的影響，也就是說(shuō)，過(guò)去的歷史只通過(guò)當(dāng)前的狀態(tài)去影響未來(lái)的發(fā)展。 遞推性。即由k階段的狀態(tài)變量xk及決策變量uk可以計(jì)算出k+1階段的狀態(tài)變量xk+1。 確定決策變量uk及允許決策變量集合Dk(uk)。 根據(jù)狀態(tài)變量之間的遞推關(guān)系，寫(xiě)出狀態(tài)轉(zhuǎn)移方程： xk+1=T(xk, uk(xk) 建立指標(biāo)函數(shù)。一般用rk(xk, uk)描寫(xiě)階段效應(yīng)，fk（xk）表示kn階段的最優(yōu)子策略函數(shù)。 建立動(dòng)態(tài)規(guī)劃基本方程： fk（xk）= opt rk(xk, uk(xk)fk+1（xk+1） uk Dk(uk) fn+1（xn+1）=C k=n,n-1,1 以上是建立動(dòng)態(tài)規(guī)劃模型的過(guò)程，這個(gè)過(guò)程是

3、正確求解動(dòng)態(tài)規(guī)劃的基礎(chǔ)。 在動(dòng)態(tài)規(guī)劃基本方程中， rk(xk, uk)， xk+1=T(xk, uk)都是已知函數(shù)，最優(yōu)子策略fk（xk）與fk+1（xk+1）之間是遞推關(guān)系，要求出fk（xk）及uk(xk)，需要先求出fk+1（xk+1），這就決定了應(yīng)用動(dòng)態(tài)規(guī)劃基本方程求最優(yōu)策略總是逆著階段的順序進(jìn)行的。由后向前逐步計(jì)算，最終可以算出全過(guò)程的最優(yōu)策略函數(shù)值及最優(yōu)策略。 另一方面，由于k+1階段的狀態(tài)xk+1=T(xk, uk)是由前面的狀態(tài)xk和決策uk所形成的，在計(jì)算fk+1（xk+1）時(shí)還不能具體確定xk+1的值，所以，這就要求必須就k+1階段的各個(gè)可能狀態(tài)計(jì)算fk+1（xk+1），因此

4、動(dòng)態(tài)規(guī)劃方法不但能求出整個(gè)問(wèn)題的最優(yōu)策略和最優(yōu)目標(biāo)值，而且還能求出決策過(guò)程中所有可能狀態(tài)的最優(yōu)策略及最優(yōu)目標(biāo)值。 下面就按上述步驟求解例2。 例2（帶回收的資源分配問(wèn)題）某廠新購(gòu)某種機(jī)床125臺(tái)。據(jù)估計(jì)，這種設(shè)備5年后將被其它設(shè)備所代替。此機(jī)床如在高負(fù)荷狀態(tài)下工作，年損壞率為1/2，年利潤(rùn)為10萬(wàn)元；如在低負(fù)荷狀態(tài)下工作，年損壞率為1/5，年利潤(rùn)為6萬(wàn)元。問(wèn)應(yīng)如何安排這些機(jī)床的生產(chǎn)負(fù)荷，才能使5年內(nèi)獲得的利潤(rùn)最大？ 解：以年為階段，k=1，2，3，4，5 取k年初完好的機(jī)床數(shù)為狀態(tài)變量xk 以k年初投入高負(fù)荷運(yùn)行的機(jī)床數(shù)為決策變量uk，則低負(fù)荷運(yùn)行機(jī)床數(shù)是xk-uk，于是狀態(tài)轉(zhuǎn)移方程為： xk

5、+1=1/2uk+4/5（xk-uk）=0.8xk-0.3uk 以利潤(rùn)為目標(biāo)函數(shù)，則k年利潤(rùn)為： 10uk+6（xk-uk）=4uk+6xk 記fk（xk）為k年至5年末最大總利潤(rùn)，則動(dòng)態(tài)規(guī)劃基本方程為： fk（xk）= max 4uk+6xk+fk+1（0.8xk-0.3uk） 0ukxk f6（x6）=0 k=5,4,3,2,1以上是建立動(dòng)態(tài)模型的過(guò)程，下面具體求解。注意動(dòng)態(tài)規(guī)劃基本方程為：fk（xk）= max 4uk+6xk+fk+1（0.8xk-0.3uk） 0ukxk所以，當(dāng)k=5時(shí)，有f5（x5）= max 4u5+6x5+f6（x6）=10 x5 u5=x5 0u5x5當(dāng)k=4

6、時(shí)f4（x4）= max 4u4+6x4+f5（0.8x4-0.3u4） 0u4x4 = max 4u4+6x4+10（0.8x4-0.3u4） 0u4x4 = max u4+14x4=15x4 u4=x4 0u4x4當(dāng)k=3時(shí)f3（x3）= max 4u3+6x3+f4（0.8x3-0.3u3） 0u3x3 = max 4u3+6x3+15（0.8x3-0.3u3） 0u3x3 = max -0.5u3+18x3=18x3 u3=0 0u3x3 動(dòng)態(tài)規(guī)劃基本方程為： fk（xk）= max 4uk+6xk+fk+1（0.8xk-0.3uk） 0ukxk 當(dāng)k=2時(shí)f2（x2）= max 4u2+6x2+f3（0.8x2-0.3u2） 0u2x2 = max 4u2+6x2+18（0.8x2-0.3u2） 0u2x2 = max-1.4u2+20.4x2=20.4x2 u2=0 0u2x2 當(dāng)k=1時(shí)f1（x1）= max 4u1+6x1+f2（0.8x1-0.3u1） 0u1x1 = max 4u1+6x1+20.4（0.8x1-0.3u1） 0u1x1 = max -2.12u1+22.32x1=22.32x1 u1=0 0u1x1 =22.32125=2790（萬(wàn)元） 至此已算得最大總利潤(rùn)2790萬(wàn)元，再按與計(jì)算過(guò)程