复件 7.1动态规划11.ppt

第七章动态规划 7 1动态规划的基本概念和方法 什么是动态规划 它能解决哪些类型的问题 它是如何来求解的 在城市A和E之间要铺设一条输气管道 途中要经过三个地区 每个地区有若干个可供选择的转运点 构成许多不同的输气路线 两点之间连线上的数字表示两点间的距离 或费用 试求一条从A到E的铺管线路 使总距离最短 或总费用最小 例 3 3 2 1 18 例如当k 20时 加法次数为4 2550833966227 1015次 比较1 3726075472977 1014次 若用1亿次 秒的计算机计算需要约508天 如果从A到E的站点有k个 除A E之外每站有3个位置 则 总共有3k 1 2条路径 计算各路径长度总共要进行 k 1 3k 1 2次加法以及3k 1 2 1次比较 某工厂每月需供应市场一定数量的产品 供应需求所余产品应存入仓库 一般地 某月适当增加产量可降低生产成本 但超产部分存入仓库会增加库存费用 要确定一个逐月的生产计划 在满足需求的条件下 使一年的生产与存储费用之和最小 例 创始人 贝尔曼 R Bellman 1 概念 动态规划是解决多阶段决策过程最优化问题的一种方法 一 动态规划的概念 多阶段决策过程是指可以按照时间序列分解为若干相互联系的阶段 在每一个阶段都要做出决策 全部过程的决策是一个决策序列 故也称为序贯决策过程 2 动态规划的分类 离散决策过程 连续决策过程 确定决策过程 随机决策过程 离散确定型决策 连续确定型决策 离散随机型决策 连续随机型决策 用途 最优路径问题 资源分配问题 生产计划与库存问题 投资问题 装载问题 生产过程的最优控制问题 3 动态规划的用途 动态规划的解题思路 是将一个n阶段的决策问题转化为依次求解n个具有递推关系的单阶段的决策问题 从而简化计算过程 1 阶段 把所给问题的过程 恰当的分成若干个相互联系的阶段 以便能按一定的次序去求解 描述阶段的变量常用k表示 如 例1中包括4个阶段 例2中包括12个阶段 二 动态规划中的基本概念 动态规划中的基本概念 2 状态 表示每个阶段开始所处的自然状况或客观条件 他描述了研究问题过程的状况 又称不可控因素 第k阶段的状态就是第k阶段所有始点的集合 Sk 以后的发展不受以前的阶段状态的影响 无后效性 如 例1中 第一阶段状态为A 第二阶段则有三个状态 城市1 2 3即 S1 A S2 1 2 3 动态规划中的基本概念 3 决策 当过程处于某一阶段的某个状态时 可以做出不同的决定 或选择 从而确定下一阶段的状态 这种决定称为决策 描述决策的变量称为决策变量 它可用一个数 一组数或向量来描述 常用Uk Sk 表示 决策变量的取值往往限制在一定范围内 称此范围为允许决策集合 常用Dk Sk 表示 如 例1中第2阶段的状态集合S2 1 2 3 从城市1出发 可选择走城市4 5 6 即 其允许的决策集合为D2 1 4 5 6 如果我们决定选择城市5 则此时决策变量可表示为u2 1 5 动态规划中的基本概念 4 策略 各段决策确定后 整个问题的决策序列就构成一个策略 表示为 p1 n u1 u2 un 允许策略集合最优策略 动态规划中的基本概念 5 状态转移方程 动态规划中本阶段的状态往往是上一阶段的决策结果 如果给定了第 阶段的状态Sk 本阶段决策为 则第k 1段的状态Sk 1也就完全确定 他们的关系可用下面公式表示 Sk 1 Tk Sk uk 如 例1中状态转移方程Sk 1 uk 动态规划中的基本概念 6 指标函数 用于衡量所选定策略优劣的数量指标称为指标函数 一个n阶段决策过程 从1到n叫做问题的原过程 V1 n S1 p1 n 原过程效益值Vk n Sk pk n 后部子过程的效益值最优指标函数记为 fk sk 表示 第k段状态Sk采用最优策略p k n到过程终止时的最佳效益 f1 s1 就表示从初始状态s1到全过程结束的整体最优函数 如 例1中指标函数是距离V2 4 2 f2 2 f1 A 7 2动态规划的基本原理 设 d Sk uk 表示由状态Sk点出发采用决策uk到达下一阶段Sk 1点时的两点距离 第一步 从K 4开始 状态变量S4可取两种状态7 8f4 7 4f4 8 3 第二步 从K 3开始 状态变量S3可取4 5 6三个值 则 第三步 从K 2开始 状态变量S2可取1 2 3三个值 则 第四步 从K 1开始 状态变量只有一个值A 则 1 5 8 A E 过程行进方向 动态规划寻优途径 后向动态规划 f5 s5 0 动态规划的基本方程 边界条件 从k k 1的递推关系 终点条件 动态规划方法的基本思想归纳 动态规划方法的关键在于正确地写出基本的递推关系式和恰当的边界条件 恰当的选取选取状态变量和决策变量及定义最优值函数 从而把一个大问题化成一族同类型的子问题 然后逐个求解 在多阶段决策过程中 动态规划方法是既把当前一段和未来各段分开 又把当前效益和未来效益结合起来考虑的一种最优化方法 每段决策的选取是从全局来考虑的 与该段的最优选择答案一般是不一样的 在求整个问题的最优策略时 由于初始状态是已知的 而每段的决策都是该段状态的函数 故最优策略所经过的各段状态可逐次得到 从而确定最优路线 9 4 3 7 5 5 11 13 17 标号法 1 减少了计算量 优点 2 丰富了计算结果 练习 14 6 7 13 11 10 13 16 19 标号法 每月库存j单位产品的费用为E j 0 5j 千元 该厂最大库存容量为3台 每月最大生产能力为6台 计划开始和计划期末库存量都是零 例2 某工厂生产并销售某种大型电机 已知今后4个月市场需求预测如下表 每月生产j单位产品费用为 假设第i 1个月的库存量是第i个月可销售量与该月用户需求量之差 而第i个月的可销售量是本月初库存量与产量之和 要求 试制定4个月的生产计划 在满足用户需求条件下总费用最小 1 阶段 每个月为一个阶段 k 1 2 3 4 2 状态变量 sk为第k个月初的库存量 3 决策变量 uk为第k个月的生产量 4 状态转移方程 sk 1 sk uk gk 5 最优指标函数 fk sk 表示第k个月状态为sk时采取最佳策略生产 从本月到计划结束 第4月末 的生产与存贮最低费用 基本概念 第一步 k 4时 根据题意 本月产量应为 u4 4 s4 s4的取值只能为0 1 2 3 f4 s4 min C u4 E s4 可得 第二步 k 3时 s3的取值范围与库存能力 生产能力 需求量均有关 s3 0 1 2 3 u3的允许决策集合应满足 至少为g3 s3 2 s3 不超过 g3 g4 s3 6 s3 并不超过 g3 3 s3 5 s3 f3 s3 min C u3 E s3 f4 s3 u3 g3 第三步 k 2时 第四步 k 1时 总费用最低为f1 0 21千元 第一个月产量为2台 第二个月产量为5台 第三个月不生产 第四个月产量为4台 f5 s5 0 基本方程 一个过程的最优策略具有这样的性质 即无论初始状态及初始决策如何 对于先前决策所形成的状态而言 其以后的所有决策必构成最优策略 动态规划的最优化原理 7 3动态规划模型的建立与求解 如上例 动态规划中生产存贮问题的基本方程可归纳为 fn 1 sn 1 0 一般的动态规划基本方程可以表示为 fk sk opt dk sk uk fk 1 sk 1 k 1 2 n uk dksk fn 1 sn 1 0 例 某公司有资金a万元 拟投资于n个项目 已知对第i个项目投资xi万元 收益为gi xi 问应如何分配资金可使总收益最大 静态规划模型 设 x1 x2 x3 xn 使得 xi 0 并满足 阶段 n个项目 决策变量 uk为原静态问题中的变量xk 状态变量 sk每阶段可以使用的资金 初始状态 s1