离散型动态规划问题(举例)

资源分配问题（离散型）

例：设有6万元资金用于4个工厂的扩建，已知每个工厂的利润增长额同投资额的大小有关，见下表。问应如何确定对这四个工厂的投资额，使总利润增长额最大？投资额

(j)工厂(i)0100200300400500600

10204260758590

20254557657073

30183961789095

40284765748085

表1利润增长额

（百元）解：把对四个工厂的投资依次看成4个阶段的决策过程，确定对第k个工厂的投资额看成第k个阶段的决策，k=1,2,3,4。图示如下：工厂1工厂2工厂3工厂4投资x1投资x2投资x3投资x4状态状态状态状态变量：可用于第k,k+1,…n个工厂的投资额。决策变量：第k阶段对第k个工厂的投资额。允许决策集：状态转移方程：其中阶段指标函数：第k阶段投资元时所产生的利润。（见上表）最优指标函数：第k阶段状态为且采取最佳投资策略，从第k个工厂以及以后的最大总利润。逆序法基本递推方程：工厂1工厂2工厂3工厂4投资x1投资x2投资x3投资x4状态状态状态投资额

(j)工厂(i)0100200300400500600

40284765748085

表1利润增长额

（百元）解：（1）k=4时考虑：若到最后一个，第4个工厂投资时，还有资金，若投资于第4个工厂的资金为，则最大利润为工厂1工厂2工厂3工厂4投资x1投资x2投资x3投资x4状态状态状态投资额

(j)工厂(i)0100200300400500600

40284765748085

表1利润增长额

（百元）（注意到此时=0）自然问：现在还有多少钱？即=？

=0，100，200，300，400，500，600都有可能。下面分情况讨论：工厂1工厂2工厂3工厂4投资x1投资x2投资x3投资x4状态状态状态投资额

(j)工厂(i)0100200300400500600

40284765748085

表1利润增长额

（百元）时，时，其他种情况类似讨论，我们把所有的结果汇总成一个表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同样问：=？，即现在还有多少钱？它是允许决策集上界。同理仅举一例：投资额

(j)工厂(i)0100200300400500600

30183961789095

表1利润增长额

（百元）0100200300400500600

0100200300400500600002802847028476502847657402847657480028476574808502847657480850100200300400500600表2

k=4时决策表投资额

(j)工厂(i)0100200300400500600

30183961789095表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时决策表（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时决策表关于的其它取值情况及相应的最优决策列于下表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时决策表此时对应最大值134的有三个值：

所对应的最优策略分别为：时，由状态转移方程知：所对应的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

0100200300400