动态规划.ppt

第章动态规划
第一页，共44页。
1
Visual FoxPro
主要内容
*
Visual FoxPro
第二页，共44页。
一般方法与求解步骤
动态规划简介
动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法。
20世纪50年代美国数学家贝尔曼（）等人在研究多阶段决策过程的优化问题时，提出了著名的最优性原理，创立了解决多阶段过程优化问题的新方法——动态规划。
动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。
*
Visual FoxPro
第三页，共44页。
一般方法

1. 几个概念
多阶段决策问题，是指这样的一类特殊的活动过程，问题可以分解成若干相互联系的阶段，在每一个阶段都要做出决策，形成一个决策序列，该决策序列也称为一个策略。
对于每一个决策序列，可以在满足问题的约束条件下用一个数值函数（即目标函数）衡量该策略的优劣。多阶段决策问题的最优化求解目标是获取导致问题最优值的最优决策序列（最优策略），即得到最优解。
*
Visual FoxPro
第四页，共44页。
2. 举例说明
*
Visual FoxPro
第五页，共44页。
*
Visual FoxPro
第六页，共44页。
3. 最优性原理
最优性原理：“作为整个过程的最优策略具有这样的性质，无论过去的状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略”。
也就是说,最优决策序列中的任何子序列都是最优的。
最优性原理体现为问题的最优子结构特性。当一个问题的最优解中包含了子问题的最优解时，则称该问题具有最优子结构特性。
最优子结构特性是动态规划求解问题的必要条件。
*
Visual FoxPro
第七页，共44页。
例如，求得在数字串847313926中插入5个乘号，使乘积最大的最优解为：
8*4*731*3*92*6=38737152
该最优解包含了在84731中插入2个乘号使乘积最大为8*4*731；在7313中插入1个乘号使乘积最大为731*3；在3926中插入2个乘号使乘积最大为3*92*6等子问题的最优解，这就是最优子结构特性。
最优性原理是动态规划的基础。任何一个问题，如果失去了这个最优性原理的支持，就不可能用动态规划设计求解。
4. 最优子结构特性
*
Visual FoxPro
第八页，共44页。
（1） 把所求最优化问题分成若干个阶段，找出最优解的性质，并刻划其结构特性。
（2） 将问题发展到各个阶段时所处不同的状态表示出来，确定各个阶段状态之间的递推关系，并确定初始（边界）条件。
（3） 应用递推求解最优值。
（4） 根据计算最优值时所得到的信息，构造最优解。
构造最优解就是具体求出最优决策序列。通常在计算最优值时，根据问题具体实际记录更多的信息，根据所记录的信息构造出问题的最优解。
动态规划求解步骤
*
Visual FoxPro
第九页，共44页。
装载问题
*
Visual FoxPro
第十页，共44页。