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

資源分配問題（離散型）

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

(j)工廠(i)0100200300400500600

10204260758590

20254557657073

30183961789095

40284765748085

表1利潤(rùn)增長(zhǎng)額

（百元）解：把對(duì)四個(gè)工廠的投資依次看成4個(gè)階段的決策過程，確定對(duì)第k個(gè)工廠的投資額看成第k個(gè)階段的決策，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個(gè)工廠的投資額。決策變量：第k階段對(duì)第k個(gè)工廠的投資額。允許決策集：狀態(tài)轉(zhuǎn)移方程：其中階段指標(biāo)函數(shù)：第k階段投資元時(shí)所產(chǎn)生的利潤(rùn)。（見上表）最優(yōu)指標(biāo)函數(shù)：第k階段狀態(tài)為且采取最佳投資策略，從第k個(gè)工廠以及以后的最大總利潤(rùn)。逆序法基本遞推方程：工廠1工廠2工廠3工廠4投資x1投資x2投資x3投資x4狀態(tài)狀態(tài)狀態(tài)投資額

(j)工廠(i)0100200300400500600

40284765748085

表1利潤(rùn)增長(zhǎng)額

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

(j)工廠(i)0100200300400500600

40284765748085

表1利潤(rùn)增長(zhǎng)額

（百元）（注意到此時(shí)=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利潤(rùn)增長(zhǎng)額

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

(j)工廠(i)0100200300400500600

40284765748085

表1利潤(rùn)增長(zhǎng)額

（百元）0100200300400500600

0100200300400500600002802847028476502847657402847657480028476574808502847657480850100200300400500600表2

k=4時(shí)決策表投資額

(j)工廠(i)0100200300400500600

10204260758590

20254557657073

30183961789095

40284765748085

表1利潤(rùn)增長(zhǎng)額

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

表1利潤(rùn)增長(zhǎng)額

（百元）投資額

(j)工廠(i)0100200300400500600

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

(j)工廠(i)0100200300400500600

30183961789095

表1利潤(rùn)增長(zhǎng)額

（百元）0100200300400500600

0100200300400500600002802847028476502847657402847657480028476574808502847657480850100200300400500600表2

k=4時(shí)決策表投資額

(j)工廠(i)0100200300400500600

30183961789095表1利潤(rùn)增長(zhǎng)額（百元）所有情況討論結(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時(shí)決策表（3）k=2時(shí)僅舉一例：投資額

(j)工廠(i)0100200300400500600

20254557657073表1利潤(rùn)增長(zhǎng)額（百元）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時(shí)決策表關(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時(shí)決策表（4）k=1時(shí)，此時(shí)投資額

(j)工廠(i)0100200300400500600

10204260758590表1利潤(rùn)增長(zhǎ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時(shí)決策表匯一表格：0100200300400500600

60013413413413312811390

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

所對(duì)應(yīng)的最優(yōu)策略分別為：時(shí)，由狀態(tài)轉(zhuǎn)移方程知：所對(duì)應(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時(shí)決策表對(duì)應(yīng)的

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

0100200300400500600

0100200300400