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

资源分配问题（离散型）例：设有6万元资金用于4个工厂的扩建，已知每个工厂的利润增长额同投资额的大小有关，见下表。问应如何确定对这四个工厂的投资额，使总利润增长额最大？投资额(j)工厂(i)010020030040050060010204260758590202545576570733018396178909540284765748085表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)010020030040050060040284765748085表1利润增长额（百元）解：（1）k=4时考虑：若到最后一个，第4个工厂投资时，还有资金，若投资于第4个工厂的资金为，则最大利润为工厂1工厂2工厂3工厂4投资x1投资x2投资x3投资x4状态状态状态投资额(j)工厂(i)010020030040050060040284765748085表1利润增长额（百元）（注意到此时=0）自然问：现在还有多少钱？即=？=0，100，200，300，400，500，600都有可能。下面分情况讨论：工厂1工厂2工厂3工厂4投资x1投资x2投资x3投资x4状态状态状态投资额(j)工厂(i)010020030040050060040284765748085表1利润增长额（百元）时，时，其他种情况类似讨论，我们把所有的结果汇总成一个表2。投资额(j)工厂(i)010020030040050060040284765748085表1利润增长额（百元）01002003004005006000100200300400500600002802847028476502847657402847657480028476574808502847657480850100200300400500600表2k=4时决策表投资额(j)工厂(i)0100200300400500600102042607585902025455765707330