第6章-动态规划.ppt

第6章动态规划 学习目标 了解动态决策问题的特点及其类型 理解并掌握Bellman最优化原理及其在动态规划中的应用 掌握常见的动态决策问题的建模及其求解 如最短路线问题 资源分配问题 背包问题 仓库存贮问题 生产与存贮问题等 动态决策问题 决策过程具有阶段性或时序性 与时间有关 即决策过程可划分为明显的阶段 按数据给出的形式可分为 离散型动态决策问题和连续型动态决策问题 按决策过程演变的性质可分为 确定型动态决策问题和随机型动态决策问题 动态规划的基本概念 阶段 k 一般把所给问题按时间或空间上的顺序划分互译序贯相连的几个阶段 阶段的划分 一般根据时间和空间的自然特征来划分 上例中k 1 2 3 4 5 其中第一个阶段的起点为A 终点为B1 B2或B3状态 Sk 指阶段的出发位置 即阶段的起点 如 S1 A S2 B1 B2 B3 决策 uk Sk 指从一个阶段某状态演变到下一阶段某状态的选择 即阶段的终点构成的决策集uk Sk 如 u1 S1 u1 A B1 B2 B3 u2 S2 u2 B1 u2 B2 u2 B3 C1 C2 C1 C2 C3 C2 C3 C1 C2 C3 策略 全过程各个阶段的决策uK组成的有序总体 uK 如 A B2 C1 D1 E2 F如果从A到F有38种走法 或38条路线 则有38个策略 子策略 由过程的第k阶段开始到终止状态为止的过程 称为问题的后部子过程 也称为k子过程 与之相对应的决策序列 uk sk uk 1 sk 1 un sn 称为k子过程策略 简称为k子策略 如 C1 D1 E2 F 状态转移方程 确定过程由一个状态到另一个状态的演变过程 如果给定第k阶段的起始状态sk与决策变量uk sk 则第k 1阶段的状态sk 1也就确定了 这种关系可用公式 sk 1 Tk sk uk 表示 表明了由k到k 1阶段状态转移的规律 指标函数 是评价动态规划决策结果优劣的数量指标 它定义了全过程和所有后部子过程上确定的数量函数 一般以Vk n表示 指标函数可以是时间 效率 利润 成本或产量等 Vk n Vk n sk uk sn un 一般而言 指标函数满足如下递推关系 Vk n sk uk sn un k sk uk Vk 1 n sk 1 un 最优指标函数 记为fk sk 表示从第k阶段的状态sk开始 到第n阶段的终止状态的过程 采取最优策略所得到的指标函数值 即 其中 opt表示最优的意思 可以是max或min V是函数关系 可以表示加法关系 也可以表示乘法关系或其它 在最短路线问题中 指标函数Vk n就表示在第k阶段由点sk至终点F的距离 用dk sk uk vk sk uk 表示第k阶段由点sk到点sk 1 uk sk 的距离 例如 d4 D3 E2 5 表示在第4阶段 由点D3到点E2的距离为5 fk sk 表示从第k阶段点sk到终点F的最短距离 如f4 D2 就表示从第4阶段中的点D2到点F的最短距离 指各个阶段的数量指标 记为dk sk uk 如d2 B3 C2 1 表示距离 策略指标函数 指策略的数量指标值 记为 Z d1 S1 X1 d5 S5 X5 最优策略 指策略指标函数达到最优的策略 MinZ d1 s1 u1 d5 s5 u5 最优化原理 贝尔曼最优化原理 作为整个过程的最优策略 无论过去的状态和决策如何 对前面的决策所形成的状态而言 余下的诸决策必构成最优策略 即 若M是从A到B最优路线上的任一点 则从M到B的路线也是最优路线 M A B 整个问题 将最后一阶段问题最优化 将最后两阶段问题最优化 整个问题最优化 指标函数递推方程贝尔曼最优化原理可以导出指标函数递推方程 f n Sn 为从第n个阶段到终点的最短距离 f n 1 Sn 1 为从第n 1个阶段到终点的最短距离 dn Sn Xn 为第n个阶段的距离 f 5 S5 为递推的起点 通常为已知的 求解过程由最后一个阶段的优化开始 按逆向顺序逐步向前一阶段扩展 并将后一阶段的优化结果带到扩展后的阶段中去 以此逐步向前推进 直至得到全过程的优化结果 A B1 B2 E 4 9 5 6 4 8 7 6 8 9 3 5 6 2 3 1 4 3 A B C D E 1 2 3 4 例 最短线路问题 B3 C1 C2 C3 D1 D2 解 1 k 4 起始状态集合为 s4 D1 D2 当s4 D1时 从D1到E的路线只有一条 其距离d D1 E 4 所以f4 D1 4 当s4 D2时 从D2到E的路线只有一条 其距离d D2 E 3 所以f4 D2 3 2 k 3 起始状态集合为 s3 C1 C2 C3 当s3 C1时 从C1到E的路线有两条 C1 D1 E或C1 D2 E 我们要在这两条路线中选择一条最短路线 即 其最短路线是C1 D1 E 相应的决策变量是u3 C1 D1 当s3 C2时 从C2到E的路线也有两条 C2 D1 E或C2 D2 E 其最短路线是C2 D2 E 相应的决策变量是u3 C2 D2 当s3 C3时 从C3到E的路线也有两条 C3 D1 E或C3 D2 E 其最短路线是C3 D1 E 相应的决策变量是u3 C3 D1 3 k 2 起始状态集合为 s2 B1 B2 B3 当s2 B1时 从B1出发的线路有两条B1C1和B1C2 可以计算得 其最短路线是B1 C2 D2 E 相应的决策变量是u2 B1 C2 当s2 B2时 从B2出发的线路有三条B2C1 B2C2和B2C3 可以计算得 其最短路线是B2 C3 D1 E 相应的决策变量是u2 B2 C3 当s2 B3时 从B3出发的线路有两条B3C2和B3C3 可以计算得 最短路线是B3 C2 D2 E 相应的决策变量是u2 B3 C2 4 k 1 起始状态集合为 s1 A 从A出发的线路有三条AB1 AB2和AB3 可以计算得 其最短路线是A B1 C2 D2 E 相应的决策变量是u1 A B1 因此 最优策略序列是 u1 A B1 u2 B1 C2 u3 C2 D2 u4 D2 E 动态规划的基本思想 关键在于正确地写出基本的递推关系式和恰当的边界条件 基本方程 在多阶段决策过程中 动态规划方法是既把当前一段和未来各段分开 又把当前效益和未来效益结合起来考虑的一种最优化方法在求整个问题的最优策略时 由于初始状态是已知的 而每段的决策都是该段状态的函数 故最优策略所经过的各段状态便可逐次变换得到 从而确定了最优路线 A B1 B2 E 4 9 5 6 4 8 7 6 8 9 3 5 6 2 3 1 4 3 A B C D E 1 2 3 4 动态规划的标号法 B3 C1 C2 C3 D1 D2 4 3 7 5 5 9 11 13 13 动态规划的表格计算 从最后一个阶段开始 n 4时 这一步数据为已知 是递推的起点 n 3时 第3阶段到终点分两步走 第3阶段到终点的距离等于第3阶段的距离加上第4阶段到终点的最短距离 其计算如下 n 2时 第2阶段到终点分两步走 第2阶段到终点的距离等于第2阶段的距离加上第3阶段到终点的最短距离 其计算如下 n 1时 第1阶段到终点分两步走 第1阶段到终点的距离等于第1阶段的距离加上第2阶段到终点的最短距离 其计算如下 因此 可以得到从A到E的最短路线 即最优策略 为 A B1 C2 D2 EA到E的最短距离为 f1 s1 13 课堂练习 B1 B2 B3 F C1 C2 C3 D1 D2 D3 E1 E2 3 5 4 9 5 4 3 5 1 7 1 5 8 4 6 4 2 5 4 4 2 6 9 7 2 1 A B C D E F 1 2 3 4 5 动态规划的逆序解法与顺序解法 逆序 递推 解法 即由最后一段到第一段逐步求出各点到终点的最短路线 最后求出A点到E点的最短路线 运用逆序递推方法的好处是可以始终盯住目标 不致脱离最终目标 顺序解法 其寻优方向与过程的行进方向相同 求解时是从第一段开始计算逐段向后推进 计算后一阶段时要用到前一段求优的结果 最后一段的计算结果就是全过程的最优结果 动态规划的优点 减少计算量 丰富计算结果 动态规划模型的建立 所研究的问题必须能够分成几个相互联系的阶段 且在每个阶段都具有需要进行决策的问题 在每一阶段都必须有若干个与该阶段相关的状态 识别每一阶段的状态是建立动态规划模型的关键内容 状态的选取要注意以下几个要点 在所研究问题的各阶段 都能直接或间接确定状态变量的数值 状态的后无效性 即以第k阶段的状态sk为出发点的后部子过程的最优策略应与sk状态之前的过程无关 具有明确的指标函数Vk n 且阶段指标值dk sk uk 可以计算 动态规划的求解步骤 将问题合理分成阶段 设阶段总数为n 给界条件fn sn 然后从最后一个阶段n的优化开始 逐步向前一阶段推进 直至第一阶段为止 在每一阶段都进行如下的步骤 列出本阶段所有可能的状态变量sk对每一个状态sk列出可能的决策变量uk sk 对每一对sk uk sk 计算本阶段的指标值dk sk uk 利用状态转移方程sK 1 T sk uk 对每对sk uk sk 求出Sk 1的值 计算每一对sk uk sk 的指标值dk sk uk fk 1 sk 1 将上一步中各指标值进行比较 取最优者 极大或极小 为从本阶段sk状态开始的后部子过程的最优指标fk sk 相应的决策即是本阶段以sk为起始状态的最优决策uk sk 在第一阶段的最优决策确定之后 第一阶段的最优初始s1 即可确定 然后根据状态转移方程确定下一阶段的最优状态 这样 最优策略所经过的各阶段最优状态即可逐次得到 从而确定了最优策略的状态变化路线 动态规划应用实例 定价问题 某公司考虑为某新产品定价 该产品的单价拟从每件5元 6元 7元 8元这四个价格中选取其中之一 每年年初允许变动价格 但幅度不能超过1元 该公司预计该产品畅销只有五年 五年后将被淘汰 另据销售情况的预测 在价格不同的情况下 各年的预计利润额如下表 现在问公司将如何为产品定价 以实现五年内的利润最大化 预计利润额 10 12 15 20 25 12 13 16 20 24 14 14 16 18 18 16 15 15 14 14 5元 6元 7元 8元 动态规划的表格计算 从最后一个阶段开始 n 5时 这一步数据为已知 是递推的起点 n 4时 第4阶段到终点分两步走 第4阶段的利润等于第4阶段的利润加上第5阶段的最大利润 其计算如下 n 3时 第3阶段到终点分两步走 第3阶段的利润等于第3阶段的利润加上第4阶段以后的最大利润 其计算如下 n 2时 第2阶段到终点分两步走 第2阶段的利润等于第2阶段的利润加上第3阶段以后的最大利润 其计算如下 n 1时 第1阶段到终点分两步走 第1阶段的利润等于第1阶段的利润加上第2阶段以后的最大利润 其计算如下 可知 为获得最大利润 各年的定价策略为 A4 B4 C3 D2 E1 即 第一年 8元 第二年 8元 第三年 7元 第四年 6元 第五年 5元 资源分配问题某种资源总量为a 用于生产n种产品 设分配数量xi用于生产第i种产品 第i种产品的收益为gi xi 问如何分配才使总收益最大 模型为 MaxZ g1 x1 gn xn S t x1 x2 xn a xj 0这是静态决策问题 我们可以将其化为动态模型来求解 例 某有色金属公司拟拔出50万元对所属三家冶炼厂进行技术改造 若以10万元为最小分割单位 各厂收益与投资的关系如下表所示 问对三个工厂如何分配这50万元 才能使总收益达到最大 思路 首先对工厂1进行分配 余下的工厂2进行分配 最后余下的分配给工厂3 建立如下动态规划数学模型 工厂1 工厂2 工厂3 阶段k 工厂 1 2 3状态sk 可供分配的资金量 s1 5 s2 s1 u1 s3 s2 u2决策uk 可供分配的资金量 0 u1 s1 0 u2 s2 0 u3 s3状态转移方程 sk 1 sk uk指标函数 收益 d1 u1 0 4 5 7 9 10 5 12 d2 u2 0 2 4 5 7 5 11 15 d3 u3 0 5 7 8 10 13 指标递推方程 fk sk max dk uk fk 1 sk 1 k 1 2f3 s3 max d3 u3 利用表格进行计算 从最后一个阶段开始k 3 u3 s3 k 2时 0 u2 s2 s3 s2 u2 k 1时 0 u1 s1 s2 s1 u1 可见 当s1 5 此时u1 1 s2 s1 u1 4 u2 3 s3 s2 u2 1 u3 1最优策略为 P u1 u2 u3 1 3 1 即给工厂1分配10万元 工厂2分配30万元 工厂3分配10万元 可使总收益达到最大为17万元 背包问题假设一个徒步旅行者 有n种物品供他选择后装入背包中 设这n种物品编号为1 2 j n 并已知一件第j种物品的重量为wj千克 这一件物品对他的使用价值为cj 又知这位旅行者本身所能承受的总重量不能超过W千克 问该旅行者如何选择这n种物品的件数 以对他来说使用价值最大 一般的数学模型 背包问题的动态规划模型求解 用状态变量sk表示背包中可装进第k种至第n种物品的总重量 即从k阶段开始 还可以装入的总重量 用决策变量xk表示背包中装进第k种物品的件数 则背包中装进第k种至第n种物品后的总重量为sk wkxk sk 1 sk wkxk 用fk sk 表示背包装入第k种至第n种商品所得的最大使用价值 则根据最优化原理 有如下递推方程 例 解背包问题MaxZ 8x1 5x2 12x32x1 2x2 5x3 5x1 x2 x3 0且为整数 物品A 物品B 物品C 1 2 3 阶段 物品 k状态 第k阶段时 背包可装入的重量 sk s1 5 s2 s1 w1x1 1 3 5 s3 s2 w2x2 1 3 5 决策 装入背包的物品件数 xk 0 x1 s1 w1 0 x2 s2 w2 0 x3 s3 w3 x1 0 1 2 x2 0 1 2 x3 0 1 状态转移方程 sk 1 sk wkxk阶段指标函数 价值 d1 x1 8x1 d2 x2 5x2 d3 x3 12x3 指标递推方程 利用表格进行计算 从最后一个阶段开始k 3 x3 0 s3 w3 0 s3 5 0 1 k 2时 x2 0 s2 w2 0 s2 2 0 1 2 s3 s2 w2x2 s2 2x2 k 1时 x1 0 s1 w1 0 s1 2 0 1 2 s2 s1 w1x1 5 2x1 可见 当s1 5 此时x1 2 s2 s1 2x1 1 x2 0 s3 s2 2x2 1 x3 0最优策略为 P u1 u2 u3 2 0 0 即带两件A物品 不带B物品和C物品 可使总效用达到最大为16 设备更新问题 问题 一台设备应在多少年后进行更新为最恰当 即更新的最佳策略应该如何 从而使在某一时间内的总收入达到最大 总费用达到最小 记号 Ij t 在第j年机器役龄为t年的一台机器运行所得的收入 Oj t 在第j年机器役龄为t年的一台机器运行时所需的运行费用 Cj t 在第j年机器役龄为t年的一台机器更新时所需更新净费用 折扣因子T 在第一年开始时 正在使用的机器的役龄 n 计划的年限总数 gj t 在第j年开始使用一个役龄为t年的机器时 从第j年到第n年的最佳收入 xj t 给出gj t 时 在第j年开始时的决策 保留或更新 递推关系式 其中 j 1 2 n t 1 2 j 1 j T 1gn 1 t 0对于g1 来说 允许的t值只能是T 因为当进入计划进程时 机器必然已使用了T年 假设n 5 1 T 1 其有关数据如下表 试制定5年中的设备更新策略 使在5年内的总收入达到最大 解 符号的意思见P168 当j 5时 当j 4时 当j 3时 当j 2时 当j 1时 利用动态规划解决非线性规划问题 例 用逆推解法求解下面问题 解 设状态变量为s1 s2 s3 并记s1 c 取问题中的变量x1 x2 x3为决策变量 各阶段指标函数按乘积方式结合 令最优值函数fk sk 表示为第k阶段的初始状态为sk 从k阶段