动态规划相关知识(ppt 68页).ppt

动态规划 Dynamicprogramming 动态规划的基本思想 最短路径问题 投资分配问题 背包问题 动态规划是解决多阶段决策过程最优化问题的一种方法 由美国数学家贝尔曼 Ballman 等人在20世纪50年代提出 他们针对多阶段决策问题的特点 提出了解决这类问题的 最优化原理 并成功地解决了生产管理 工程技术等方面的许多实际问题 动态规划是现代企业管理中的一种重要决策方法 可用于最优路径问题 资源分配问题 生产计划和库存问题 投资问题 装载问题 排序问题及生产过程的最优控制等 动态规划模型的分类 以 时间 角度可分成 离散型和连续型 从信息确定与否可分成 确定型和随机型 从目标函数的个数可分成 单目标型和多目标型 7 1动态规划的基本原理多阶段决策过程最优化多阶段决策过程是指这样一类特殊的活动过程 他们可以按时间顺序分解成若干相互联系的阶段 在每个阶段都要做出决策 全部过程的决策是一个决策序列 所以多阶段决策问题也称为序贯决策问题 例7 1生产与存储问题某工厂每月需供应市场一定数量的产品 供应需求所剩余产品应存入仓库 一般地说 某月适当增加产量可降低生产成本 但超产部分存入仓库会增加库存费用 要确定一个每月的生产计划 在满足需求条件下 使一年的生产与存储费用之和最小 例7 2投资决策问题某公司现有资金Q亿元 在今后5年内考虑给A B C D四个项目投资 这些项目的投资期限 回报率均不相同 问应如何确定这些项目每年的投资额 使到第五年末拥有资金的本利总额最大 例7 3设备更新问题企业在使用设备时都要考虑设备的更新问题 因为设备越陈旧所需的维修费用越多 但购买新设备则要一次性支出较大的费用 现在某企业要决定一台设备未来8年的更新计划 已预测到第j年购买设备的价格为Kj Gj为设备经过j年后的残值 Cj为设备连续使用j 1年后在第j年的维修费用 j 1 2 8 问应在哪年更新设备可使总费用最小 动态规划的基本概念阶段 状态 决策和策略 状态转移 指标函数 例7 4 不定阶段最短路线问题 如图是一个五座城市的及其相连道路的交通图 线上的数字是对应的路长 问 应如何选择行驶路线 才能使从A B C D各城市到E城市的行驶路程最短 A E D C B 2 5 2 7 5 5 6 1 0 5 3 从图中可以看出 任意两座城市之间都有道路相通 我们把从一座城市直达另一座城市作为一个阶段 例从A城市到E城市的阶段数 少则一个 例从A城市直达E城市 多则无限 例从A城市通过其他B C D三城市循环到E城市 为避免循环 加上约束条件 每个城市至多经过一次 于是从A城市到达E城市的阶段数有下列四种情形 1 从A城市直达E城市 一个阶段 于是从A城市到达E城市的阶段数有下列四种情形 1 从A城市直达E城市 一个阶段 2 从A城市通过其他B C D三城市之一到E城市 二个阶段 于是从A城市到达E城市的阶段数有下列四种情形 3 从A城市通过其他B C D三城市之二到E城市 三个阶段 于是从A城市到达E城市的阶段数有下列四种情形 3 从A城市通过其他B C D三城市之二到E城市 三个阶段 4 从A城市通过其他B C D三城市各一次到E城市 四个阶段 例7 5 一定阶段最短路问题 W先生每天驾车去公司上班 如图 W先生的住所位于A 公司位于F 图中的直线段代表公路 交叉点代表路口 直线段上的数字代表两路口之间的平均行驶时间 现在W先生的问题是要确定一条最省时的上班路线 A3B14C13D1 4532 B22C23D2E1 1234 C34D35E22F A B1 B2 C1 C2 C3 D1 D2 D3 E1 E2 F 4 1 5 4 4 4 4 5 3 3 3 3 3 2 2 2 2 A B C D E F 1阶段 Stage 将所给问题的过程 按时间或空间特征分解成若干个相互联系的阶段 以便按次序去求每阶段的解 常用k表示阶段变量 我们把从A到F看成一个五阶段问题 2状态 State 各阶段开始时的客观条件叫做状态 描述各阶段状态的变量称为状态变量 常用sk表示第k阶段的状态变量 状态变量的取值集合称为状态集合 用Sk表示 动态规划中的状态具有如下性质 当某阶段状态给定以后 在这阶段以后的过程的发展不受这段以前各段状态的影响 即 过程的过去历史只能通过当前状态去影响它未来的发展 这称为无后效性 如果所选定的变量不具备无后效性 就不能作为状态变量来构造动态规划模型 3决策和策略 DecisionandPolicy 当各段的状态确定以后 就可以做出不同的决定 或选择 从而确定下一阶段的状态 这种决定称为决策 决策变量用dk Sk 表示 允许决策集合用Dk Sk 表示 各个阶段决策确定后 整个问题的决策序列就构成一个策略 用p1 n d1 d2 dn 表示 对每个实际问题 可供选择的策略有一定的范围 称为允许策略集合 用P表示 使整个问题达到最优效果的策略就是最优策略 4状态转移方程动态规划中本阶段的状态往往是上一阶段的决策结果 如果给定了第k段的状态Sk 本阶段决策为dk Sk 则第k 1段的状态Sk 1由公式 Sk 1 Tk Sk dk 确定 称为状态转移方程 5指标函数用于衡量所选定策略优劣的数量指标称为指标函数 最优指标函数记为fk Sk 动态规划的基本思想 从过程的最后一段开始 用逆序递推方法求解 逐步求出各段各点到终点E最短路线 最后求出A点到E点的最短路线 A B1 B2 C1 C2 C3 D1 D2 D3 E1 E2 F 4 1 5 4 4 4 4 5 3 3 3 3 3 2 2 2 2 A B C D E F 当K 5时 此时d5 S5 F 其初始状态E1或E2 故f5 E1 4 f5 E2 2用d5 S5 表示最优决策 A B1 B2 C1 C2 C3 D1 D2 D3 E1 E2 F 4 1 5 4 4 4 4 5 3 3 3 3 3 2 2 2 2 A B C D E F 当K 4时 有两个阶段 初始状态S4可以是D1 D2或D3 如果S4 D1 则下一步只能取E1 故f4 D1 r D1 E1 f5 E1 2 4 6最短路线 D1 E1 F最优解 d4 D1 E1 A B1 B2 C1 C2 C3 D1 D2 D3 E1 E2 F 4 1 5 4 4 4 4 5 3 3 3 3 3 2 2 2 2 A B C D E F 如果S4 D2 则下一步能取E1或E2 故f4 D2 Minr D2 E1 f5 E1 r D2 E2 f5 E2 Min 4 4 3 2 5最短路线 D2 E2 F最优解 d4 D2 E2 A B1 B2 C1 C2 C3 D1 D2 D3 E1 E2 F 4 1 5 4 4 4 4 5 3 3 3 3 3 2 2 2 2 A B C D E F 如果S4 D3 则下一步只能取E2 故f4 D3 r D3 E2 f5 E2 5 2 7最短路线 D3 E2 F最优解 d4 D3 E2 A B1 B2 C1 C2 C3 D1 D2 D3 E1 E2 F 4 1 5 4 4 4 4 5 3 3 3 3 3 2 2 2 2 A B C D E F 当K 3时 还有三个阶段 初始状态S3可以是C1 C2或C3 如果S3 C1 则下一步能取D1或D2 故f3 C1 Minr C1 D1 f4 D1 r C1 D2 f4 D2 Min 3 6 3 5 8最短路线 C1 D2 E2 F最优解 d3 C1 D2 A B1 B2 C1 C2 C3 D1 D2 D3 E1 E2 F 4 1 5 4 4 4 4 5 3 3 3 3 3 2 2 2 2 A B C D E F 如果S3 C2 则下一步能取D2或D3 故f3 C2 Minr C2 D2 f4 D2 r C2 D3 f4 D3 Min 3 5 2 7 8最短路线 C2 D2 E2 F最优解 d3 C2 D2 A B1 B2 C1 C2 C3 D1 D2 D3 E1 E2 F 4 1 5 4 4 4 4 5 3 3 3 3 3 2 2 2 2 A B C D E F 如果S3 C3 则下一步只能取D3 故f3 C3 r C3 D3 f4 D3 4 7 11最短路线 C3 D3 E2 F最优解 d3 C3 D3 A B1 B2 C1 C2 C3 D1 D2 D3 E1 E2 F 4 1 5 4 4 4 4 5 3 3 3 3 3 2 2 2 2 A B C D E F 当K 2时 还有四个阶段 初始状态S2可以是B1或B2 如果S2 B1 则下一步能取C1或C2 故f2 B1 Minr B1 C1 f3 C1 r B1 C2 f3 C2 Min 4 8 5 8 12最短路线 B1 C1 D2 E2 F最优解 d2 B1 C1 A B1 B2 C1 C2 C3 D1 D2 D3 E1 E2 F 4 1 5 4 4 4 4 5 3 3 3 3 3 2 2 2 2 A B C D E F 如果S2 B2 则下一步能取C2或C3 故f2 B2 Minr B2 C2 f3 C2 r B2 C3 f3 C3 Min 2 8 1 11 10最短路线 B2 C2 D2 E2 F最优解 d2 B2 C2 A B1 B2 C1 C2 C3 D1 D2 D3 E1 E2 F 4 1 5 4 4 4 4 5 3 3 3 3 3 2 2 2 2 A B C D E F 当K 1时 五个阶段的原问题 初始状态S1是A 则下一步能取B1或B2 故f1 A Minr A B1 f2 B1 r A B2 f2 B2 Min 3 12 4 10 14最短路线 A B2 C2 D2 E2 F最优解 d1 A B2 最短用时14 A B1 B2 C1 C2 C3 D1 D2 D3 E1 E2 F 4 1 5 4 4 4 4 5 3 3 3 3 3 2 2 2 2 A B C D E F A B1 B2 C1 C2 C3 D1 D2 D3 E1 E2 F 4 1 5 4 4 4 4 5 3 3 3 3 3 2 2 2 2 A B C D E F A B1 B2 C1 C2 C3 D1 D2 D3 E1 E2 F 4 1 5 4 4 4 4 5 3 3 3 3 3 2 2 2 2 A B C D E F A B1 B2 C1 C2 C3 D1 D2 D3 E1 E2 F 4 1 5 4 4 4 4 5 3 3 3 3 3 2 2 2 2 A B C D E F A B1 B2 C1 C2 C3 D1 D2 D3 E1 E2 F 4 1 5 4 4 4 4 5 3 3 3 3 3 2 2 2 2 A B C D E F A B1 B2 C1 C2 C3 D1 D2 D3 E1 E2 F 4 1 5 4 4 4 4 5 3 3 3 3 3 2 2 2 2 A B C D E F 动态规划的函数方程 DP 建立DP函数方程是指确定过程的阶段及阶段数 规定状态变量和决策变量的取法 给出各阶段的状态集合 允许决策集合 状态转移方程和指标函数等 在上面的计算过程中 利用了第k阶段与第k 1阶段的关系 fk Sk Minr Sk dk Sk fk 1 Sk 1 dk Sk k 1 2 3 4 5f6 S6 0这种递推关系称为动态规划的函数基本方程 贝尔曼 Ballman 最优化原理作为整个过程的最优策略具有这样的性质 即无论过去的状态和决策如何 对前面的决策所形成的状态而言 余下的诸决策必须构成最优策略 这就是说 不管引导到这个现时状态的头一个状态和决策是什么 所有的未来决策应是最优的 动态规划的优点 可把一个N维优化问题化成N个一