吉林大学远程教育-运筹学(第6章动态规划应用举例)技术总结.ppt

运 筹 学; 动态规划是一种将复杂问题转化为比较简单问题的最优化方法，一些线性规划、非线性规划及整数规划都可以用动态规划方法来求解。因此，动态规划在存贮控制、网络流、作业安排、生产控制等方面都有所讨论，在工程技术、工业生产、经济、军事以及自动控制等领域都有广泛的应用，并获得了显著的效果。 但是动态规划不存在一种标准的数学形式，对于动态规划方法的使用，有时可以说是一种艺术，它需要对动态规划问题的一般结构有较深入的了解，在一个具体问题中，如何定义状态、决策、阶段效应等，以及如何得到问题的基本方程表达式，在很大程度上还有赖于分析者的经验、洞察和判断能力。这就需要练习和实践，以及总结已有的研究成果。本章通过一些典型的应用问题，介绍动态规划的建模和基本解题方法。; §1 资源分配问题;在应用动态规划方法去处理这一类资源分配问题时，通常将资源分给每项活动的过程看作一个阶段，每个阶段都要确定对一种活动的资源投放量。 这时，状态变量xk可选择k阶段初所拥有的资源量，即xk是要在第k项到第n项活动间分配的资源量。 决策变量uk常常选对活动k的资源投放量，决策变量的允许集合是： 0≤uk≤xk; 例1 某公司拟将5百万元资金投放下属的A、B、C三个企业，各企业获得资金后的收益如表所示，试确定总收益最大的投资分配方案。; K=3 x3 =0，1，2，3，4，5 f3（0）=0， u3（0）=0； f3（1）=1, u3（1）=1； f3（2）=2， u3（2）=2； f3（3）=3，u3（3）=3； f3（4）=4， u3（4）=4； f3（5）=5，u3（5）=5; g2（0）+f3（4） 0+4 g2（1）+f3（3） 0+3 f2（4）=max g2（2）+f3（2）=max 1+2 =4, g2（3）+f3（1） 2+1 g2（4）+f3（0） 4+0 u2（4）=0或4； g2（0）+f3（5） 0+5 g2（1）+f3（4） 0+4 f2（5）=max g2（2）+f3（3）=max 1+3 =7, g2（3）+f3（2） 2+2 g2（4）+f3（1） 4+1 g2（5）+f3（0） 7+0 u2（5）=5； K=1 x1 =5 g1（0）+f2（5） 0+7 g1（1）+ f2（4） 2+4 f1（5）=max g1（2）+ f2（3）=max 2+3 =7, g1（3）+ f2（2） 3+2 g1（4）+ f2（1） 3+1 g1（5）+f2（0） 3+0 u1（5）=0.;运 筹 学;第六章 动态规划应用举例;例2 某工厂要制订今后四个时期某产品的生产计划，据估计今后四个时期内，市场对于该产品的需求量如下表所示：;k=4 注意：xk+1=xk+uk-dk，∴x4=x5-u4+d4=2+4-u4，而u4≤5，∴x4=1，2，3，4 ; 注意：u3≥3-x3，u3≤min｛5,6-x3｝, x3+u3-2=x4 0.5×2+2+1+f4（1） 4+7.5 ∴ f3（2）=min 0.5×2+2+2+f4（2）=min 5+7 =11.5 0.5×2+2+3+f4（3） 6+6.5 0.5×2+2+4+f4（4） 7+6 u3（2）=1 0.5×3+0+f4（1） 1.5+7.5 f3（3）=min 0.5×3+2+1+f4（2）=min 4.5+7 =9