《动态规划04142.ppt》由会员分享，可在线阅读，更多相关《动态规划04142.ppt（13页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第5章 动态规划6.1动态规划的基本原理动态规划的基本原理6.2动态规划的数学模型动态规划的数学模型6.3动态规划的求解方法动态规划的求解方法6.4动态规划在管理决策中的应用举例动态规划在管理决策中的应用举例6.1 动态规划的基本原理动态规划的基本原理6.1.l多阶段决策问题的解法多阶段决策问题的解法 在企业管理的决策活动中，有一类重要问题，对这类问题进行决策将产生广泛、持续性影响。这类问题作决策时，有时需要从时间上划分阶段，按顺序对各个阶段作决策。例如产品生产计划的逐月(季、年)安排这个决策活动，确定了某个月的生产计划，则这个月的生产计划将直接影响到后面各月的计划安排；有时需要从空间上划分为
2、若干部分。对各部分逐个作决策。关于时间和空间的实际问题都具有“动态”的特性。我们进行决策的最终目标将是在一定的资源条件下，使所安排的逐个时期的生产计划或工程项目的投资分配计划，从整体上能达到最优的效果。解决这类具有“动态”特性的决策问题时，可以按照下面的基本思想进行工作。首先，把较为复杂的决策问题视为多阶段决策问题，按问题的时间或空间关系将问题分解为几个相互联系的阶段，从而使每一阶段上的决策问题都是一个较易求解的“子问题”，在实际决策时从初始状态开始按顺序逐段进行直到终止状态为止；然后，按“动态”的特点，有顺序地(逐次地)做出每一阶段上的最优决策，具体求解时通常按逆序进行，即从最后一个阶段开始
3、到最初阶段为止。需要强调的是，做这种最优决策时必须同时考虑并保证这一阶段以前的各阶段上对“子问题”所做出的决策，从整体来说是最优决策。动态规划是美国数学家贝尔曼(R.Bellman)于1957年首先提出的。贝尔曼在其动态规划一书中指出了应用动态规划求优时的最优化原则就是：“作为整个过程的最优策略具有这样的性质：即无论初始状态和决策如何，对前面的决策所形成的状态而言，余下的所有决策必须构成一个最优策略。”这个原则便作为我们建立动态规划数学模型的理论基础。6.1.2最短路线问题最短路线问题?最短路线问题就是说给定了初始点及终点以最短路线问题就是说给定了初始点及终点以及由始点到终点的各种可能途径，要
4、求寻找及由始点到终点的各种可能途径，要求寻找一条由始点到终点的最短路线。对于不同的一条由始点到终点的最短路线。对于不同的实际问题也就是求距离（或时间、运输费用）实际问题也就是求距离（或时间、运输费用）的最小值。的最小值。?动态规划方法就是从终点逐段向始点方向寻找最短路线的方法。解题步骤如下：把问题划分为几个阶段。按阶段顺序首先考虑最后阶段即第四阶段的最优决策，也就是走哪条路线最短。按阶段顺序依次考虑第三、第二，第一阶段的最优决策，为此只需确定每一阶段上各初始点的最优决策即可。?用动态规划方法逐段求解时，每个阶段上的求优方法基本相同，而且比较简单，这种方法明显优于枚举法（穷举法），每一阶段的计算
5、都要利用上一阶段的计算结果，因而减少了很多计算量。阶段数愈多，这种效果愈明显。6.2 动态规划的数学模型动态规划的数学模型6.2.1动态规划的基本概念?动态规划的基本概念与符号阶段：用动态规划方法解题，原问题必须能划分为若干阶段。阶段是按问题的时间或空间特征来划分的。状态与状态变量：状态可理解为事物的某种特征。状态的改变意味着事物发生变化。在动态 规划问题中，状态是划分阶段的依据，状态的变化就意味着阶段的推移，因此解题时首先应明确每一阶段开始时的一切可能状态。决策和决策变量：决策就是各阶段对状态演变各种可能性的选择描述决策的变量，称为决策变量。策略:多阶段决策问题中，把每个阶段做出的决策组成的
6、序列称作是策略。把解决问题时产生的的效果最优的策略称为最优策略。阶段损益函数(或称阶段效应)：用动态规划方法求解问题时，把用以衡量策略优劣的数量指标称为损益函数，其取值称为损益值。最优损益函数:是用以表示某阶段、某状态的最优后部策略的数量指标。6.2.2动态规划的数学模型建立方法动态规划的数学模型建立方法?动态规划的数学模型包括目标函数和约束条件两部分。动态规划方法应将问题首先划分为若干个阶段。在动态约束的条件下求得每个阶段的最优损益函数。?动态规划的递推公式或函数基本方程为：（6-5）6.3 动态规划的求解方法动态规划的求解方法6.3.1动态规划递推公式的迭代解法动态规划递推公式的迭代解法?这个解法就是利用递推公式（6-5）直接求解。6.3.2动态规划的网络标号法动态规划的网络标号法?网络标号法就是直接在网络图上进行计算的方法。6.3.3动态规划的离散化算法动态规划的离散化算法?动态规划是解决多阶段决策的有效方法，决策变量的取值及状态变量的取值，则有取连续值及离散值之分这时便产生了动态规划的离散化算法。6.4 动态规划在管理决策中的应用动态规划在管理决策中的应用举例举例动动态态规规划划的的应应用用范范围围很很广广，在在管管理理决决策策方方面可解决以下几个问题面可解决以下几个问题：?生产计划问题?资源分配、存储问题?设备更新问题