交通系统动态规划.pdf

空中交通系统优化与管理 第五章 动态规划 什么是动态规划  动态规划是解决多阶段决策过程最优化 的一种方法。  1951年美国数学家贝尔曼 （R·Bellman） 等人提出了解决这类问题的 “最优化原 理”，并研究了许多实际问题。 什么是动态规划  在工程技术、企业管理、工农业生产及军 事部门中都有广泛应用：解决最优路径问 题、资源分配问题、生产调度问题、库存 问题、装载问题、排序问题、设备更新问 题、生产过程最优控制问题等等。  动态规划模型分类：离散确定型、离散随 机型、连续确定型、连续随机型。 5.1多阶段决策问题的最优化  多阶段决策问题，是指可将过程划分为 若干个互相联系的阶段，在它的每一个 阶段都需要作出决策，并且一个阶段的 决策确定以后，常影响下一阶段的决策， 从而影响整个过程的活动。  各个阶段所确定的决策就构成一个决策 序列，通常称为策略。 5.1多阶段决策问题的最优化  由于每一个阶段可供选择的决策往往不只 一个，因而就有许多策略可供选择。  多阶段的决策问题，就是要在允许选择的 那些策略中，选择一个最优策略，使在预 定的标准下达到最好的效果。 5.1多阶段决策问题的最优化  阶段往往可以用时段来表示。  在各个时间阶段，采用不同的决策是随 时间而变动的，这就有 “动态”的含义。  它是在时间的推移过程中要在每一段选 择最恰当的决策，以期整体上达到最优。 5.1多阶段决策问题的最优化  动态规划在一定条件下也可以解决一些与 时间无关的问题，只要人为地引进时段 因素以后，这些问题就可变为一个多阶段 决策问题。 5.1多阶段决策问题的最优化  例1 生产与存贮问题  某工厂每月需供应市场一定数量的产 品，并将所余产品存入仓库。一般某月 适当增加产量可降低生产成本，但超产 部分存入仓库会增加库存费用。要求确 定一个逐月的生产计划，在满足需求条 件下，使一年的生产与存贮费用之和最 小。  全年分为12个阶段逐次决策。 5.1多阶段决策问题的最优化  例2投资决策问题  某公司现有资金Q万元，在今后5年内考 虑给A，B，C，D 4个项目投资，这些项 目投资的回收期限、回报率均不相同， 问该公司应如何确定这些项目每年的投 资额，使到第5年末拥有资金的本利总 额最大。  这是一个5阶段决策问题。 5.1多阶段决策问题的最优化  例3设备更新问题  企业在使用设备时都要考虑设备的更 新问题，因为设备越陈旧所需的维修费用 越多，但购买新设备则要一次性支出较大 的费用；现某企业要决定一台设备未来8 年的更新计划，已预测了第j年购买设备 的价格为Kj，设Gj为设备经过j年后的残 值，Cj为设备连续使用j-1年后在第j年 的维修费(j＝1，2，…，8)，问应在哪些 年更新设备可使总费用最小。  这是一个8阶段决策问题 5.1多阶段决策问题的最优化  例4：最短路线问题 图5-3 5.2动态规划的基本概念和基本原理 5.2.1 动态规划的基本概念 使用动态规划方法解决多阶段决策 问题，首先要将实际问题写成动态规划 模型，此时要用到以下概念： (1)阶段； (2)状态； (3)决策和策略； (4)状态转移； (5)指标函数。 5.2.1 动态规划的基本概念 例4最短路线问题 如图5-3所示，给 定一个线路网络 图，要从A地向F 地铺设一条输油 管道，各点间连 线上的数字表示 距离，问应选择 什么路线，可使