1、第 1页运筹帷幄之中决胜千里之外Dynamic Programming第 5章 动态规划第 2页综 述 动态规划是运筹学的一个分支，是解决多阶段决策问题的一种最优化方法。与线性规划不同的是，动态规划没有统一的数学模型和算法，它要求对具体问题进行具体分析，因而动态规划更多地是求解多阶段决策问题的一种定量分析方法和途径。 所谓 多阶段决策问题是 指一类活动过程，它可以分为若干个相互联系的阶段，在每个阶段都需要作出决策。这个决策不仅决定这一阶段的效益，而且决定下一阶段的初始状态。每个阶段的决策确定以后，就得到一个决策序列，称为策略。多阶段决策问题就是求一个策略，使各阶段的效益的总和达到最优。第 3页
2、综 述 自从 20世纪 50年代，美国数学家贝尔曼提出动态规划的最优性原理以来，动态规划方法已获得广泛应用，它也成为现代企业管理中的一种重要的决策方法。应用动态规划可以解决诸如最优路径问题、资源分配问题、生产调度问题、库存问题、设备更新问题以及最优控制问题等。本章讨论多阶段决策问题以及动态规划的基本概念、原理和方法，并通过若干典型实例来说明动态规划在实践中的一些应用。第 4页n5.1 多阶段决策问题n5.2 最优化原理n5.3 确定性的定期多阶段决策问题n5.4 确定性的不定期多阶段决策问题 第 5章 动态规划第 5页5.1 多阶段决策问题 例 1 最短路问题 例 2 资源分配问题 例 3 生
3、产和库存问题 例 4 机金矿问题 例 5 多阶段决策问题例 1、最短线路问题最短路问题就是从某地出发，途经若干中间点最后到达目的地，要求找出路程或费用最小的路线。一般的最短路问题将在下一章讨论，这里只讨论分层的最短路问题。下面的管道设计问题 (例 5.1.1)就是其中之一。ED3D1D2C1C3C2AB3B2B1542634656122 233234n从 A点到 E点要铺设一条天然气管道，n 中间必须经过三个中间站，n第一站可在 B1、 B2、 B3中选择，n第二站可在 C1、 C2、 C3中选择，n第三站可在 D1、 D2、 D3中选择，n要求选择一条由 A 到 E的铺管路线，使总长度最短。
4、n其中两点连线上的数字表示两点间管线的长度。ED3D1D2C1C3C2AB3B2B1542634656122 233234从 A点到 E点铺设管道，可以按其地理特点自然地分成四个阶段：（如下图所示）从 A到 B是第一阶段，从 B到 C是第二阶段，从 C到 D是第三阶段，从 D到 E是第四阶段，A B C D E阶段 1 阶段 2 阶段 3 阶段 4ED3D1D2C1C3C2AB3B2B1542634656122 233234在阶段 2，从 B3点出发，只有 C1、 C3两种可选择的点，如选 C1,则 C1就是阶段 2在 B3点的决策结果；C1点既是阶段 2铺设管道的终点，又是阶段 3铺设管道的起点；ED3D1D2C1C3C2AB3B2B1542634656122 233234同样的理由，可以递推得其余阶段的铺设路线，如阶段 3在 C1点的决策是 D1， 阶段 4在 D1点的决策只有 E点；由于到 E点是整个铺设管道的终点，至此，决策过程完成，铺设一条 A点到 E点的管道是由四个阶段的管道组成的，如 A-B3-C1-D1-E， 它也称为一个策略。ED3D1D2C1C3C2AB3B2B1542634656122 233234
