離散型動態(tài)規(guī)劃問題(舉例)

資源分配問題（離散型）

例：設(shè)有6萬元資金用于4個工廠的擴建，已知每個工廠的利潤增長額同投資額的大小有關(guān)，見下表。問應(yīng)如何確定對這四個工廠的投資額，使總利潤增長額最大？投資額

(j)工廠(i)0100200300400500600

10204260758590

20254557657073

30183961789095

40284765748085

表1利潤增長額

（百元）解：把對四個工廠的投資依次看成4個階段的決策過程，確定對第k個工廠的投資額看成第k個階段的決策，k=1,2,3,4。圖示如下：工廠1工廠2工廠3工廠4投資x1投資x2投資x3投資x4狀態(tài)狀態(tài)狀態(tài)狀態(tài)變量：可用于第k,k+1,…n個工廠的投資額。決策變量：第k階段對第k個工廠的投資額。允許決策集：狀態(tài)轉(zhuǎn)移方程：其中階段指標函數(shù)：第k階段投資元時所產(chǎn)生的利潤。（見上表）最優(yōu)指標函數(shù)：第k階段狀態(tài)為且采取最佳投資策略，從第k個工廠以及以后的最大總利潤。逆序法基本遞推方程：工廠1工廠2工廠3工廠4投資x1投資x2投資x3投資x4狀態(tài)狀態(tài)狀態(tài)投資額

(j)工廠(i)0100200300400500600

40284765748085

表1利潤增長額

（百元）解：（1）k=4時考慮：若到最后一個，第4個工廠投資時，還有資金，若投資于第4個工廠的資金為，則最大利潤為工廠1工廠2工廠3工廠4投資x1投資x2投資x3投資x4狀態(tài)狀態(tài)狀態(tài)投資額

(j)工廠(i)0100200300400500600

40284765748085

表1利潤增長額

（百元）（注意到此時=0）自然問：現(xiàn)在還有多少錢？即=？

=0，100，200，300，400，500，600都有可能。下面分情況討論：工廠1工廠2工廠3工廠4投資x1投資x2投資x3投資x4狀態(tài)狀態(tài)狀態(tài)投資額

(j)工廠(i)0100200300400500600

40284765748085

表1利潤增長額

（百元）時，時，其他種情況類似討論，我們把所有的結(jié)果匯總成一個表2。投資額

(j)工廠(i)0100200300400500600

40284765748085

表1利潤增長額

（百元）0100200300400500600

0100200300400500600002802847028476502847657402847657480028476574808502847657480850100200300400500600表2

k=4時決策表投資額

(j)工廠(i)0100200300400500600

10204260758590

20254557657073

30183961789095

40284765748085

表1利潤增長額

（百元）（2）k=3時到第三個工廠投資時，可利用的資金還有，若向第三個工廠投資（萬元），則自此即以后最大利潤為：

表1利潤增長額

（百元）投資額

(j)工廠(i)0100200300400500600

30183961789095同樣問：=？，即現(xiàn)在還有多少錢？它是允許決策集上界。同理僅舉一例：投資額

(j)工廠(i)0100200300400500600

30183961789095

表1利潤增長額

（百元）0100200300400500600

0100200300400500600002802847028476502847657402847657480028476574808502847657480850100200300400500600表2

k=4時決策表投資額

(j)工廠(i)0100200300400500600

30183961789095表1利潤增長額（百元）所有情況討論結(jié)果匯總成下表：0100200300400500600

01002003004005006000+00+2818+00+4718+2839+00+6518+4739+2861+00+7418+6539+4761+2878+00+8018+7439+6561+7478+2890+00+8518+8039+7461+6578+4790+2895+0028476789108126000200300300300表3

k=3時決策表（3）k=2時僅舉一例：投資額

(j)工廠(i)0100200300400500600

20254557657073表1利潤增長額（百元）0100200300400500600

01002003004005006000+00+2818+00+4718+2839+00+6518+4739+2861+00+7418+6539+4761+2878+00+8018+7439+6561+7478+2890+00+8518+8039+7461+6578+4790+2895+0028476789108126000200300300300表3

k=3時決策表關(guān)于的其它取值情況及相應(yīng)的最優(yōu)決策列于下表0100200300400500600

01002003004005006000+00+2825+00+4725+2845+00+6725+4745+2857+00+8925+6745+4757+2865+00+10825+8945+6757+4765+2870+00+12625+10845+8957+6765+4770+2873+002853739211413400100200100或200100200

表4k=2時決策表（4）k=1時，此時投資額

(j)工廠(i)0100200300400500600

10204260758590表1利潤增長額（百元）0100200300400500600

01002003004005006000+00+2825+00+4725+2845+00+6725+4745+2857+00+8925+6745+4757+2865+00+10825+8945+6757+4765+2870+00+12625+10845+8957+6765+4770+2873+002853739211413400100200100或200100200表4k=2時決策表匯一表格：0100200300400500600

60013413413413312811390

1340或100或200表5k=1時決策表此時對應(yīng)最大值134的有三個值：

所對應(yīng)的最優(yōu)策略分別為：時，由狀態(tài)轉(zhuǎn)移方程知：所對應(yīng)的0100200300400500600

01002003004005006000+00+2825+00+4725+2845+00+6725+4745+2857+00+8925+6745+4757+2865+00+10825+8945+6757+4765+2870+00+12625+10845+8957+6765+4770+2873+002853739211413400100200100或200100200表4k=2時決策表對應(yīng)的

再由狀態(tài)轉(zhuǎn)移方程對應(yīng)的

0100200300400500600

0100200300400