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

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

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

3、正確求解動態(tài)規(guī)劃的基礎(chǔ)。 在動態(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)用動態(tài)規(guī)劃基本方程求最優(yōu)策略總是逆著階段的順序進(jìn)行的。由后向前逐步計算，最終可以算出全過程的最優(yōu)策略函數(shù)值及最優(yōu)策略。 另一方面，由于k+1階段的狀態(tài)xk+1=T(xk, uk)是由前面的狀態(tài)xk和決策uk所形成的，在計算fk+1（xk+1）時還不能具體確定xk+1的值，所以，這就要求必須就k+1階段的各個可能狀態(tài)計算fk+1（xk+1），因此

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

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

6、時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時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 動態(tài)規(guī)劃基本方程為： fk（xk）= max 4uk+6xk+fk+1（0.8xk-0.3uk） 0ukxk 當(dāng)k=2時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時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（萬元） 至此已算得最大總利潤2790萬元，再按與計算過程