运筹学动态规划ppt课件.ppt

运筹学 动态规划 DynamicProgramming 第五章 2 第五章动态规划 重点 理解动态规划基本概念 最优化原理和基本方程 通过资源分配 生产与存储和设备更新等问题 学习应用动态规划解决多阶段决策问题 重点掌握动态规划模型结构 逆序算法原理 资源分配问题 生产与存储问题 难点为动态规划中状态变量 基本方程等的确定 3 概述 1951年Bellman提出 1957 动态规划 动态规划是解决多阶段决策问题的一种数学方法 动态规划思想 把多阶段决策问题变换为一系列互相联系的单阶段问题 然后逐个加以解决 即 把一个n维决策问题变换为几个一维最优化问题 从而一个一个地去解决 需指出 动态规划是求解某类问题的一种方法 是考察问题的一种途径 而不是一种算法 必须对具体问题进行具体分析 运用动态规划的原理和方法 建立相应的模型 然后再用动态规划求解方法去求解 应用 最短路线 资源分配 生产调度问题 4 主要内容 一 多阶段决策问题二 动态规划的基本概念三 动态规划的基本思想四 动态规划递推求解方法五 动态规划的最优性原理六 动态规划的优缺点七 动态规划问题应用举例 5 引例 图中所示为从A到G的路线网络 图中数字表示相应线路的长度 如何求出从A到G的最短路线 穷举法48条路线 6 9 4 7 15 13 13 15 11 13 13 6 8 10 9 5 3 18 16 4 8 最短路的特性 如果已有从起点到终点的一条最短路 那么从最短路线上中间任何一点出发到终点的路线仍然是最短路 证明用反证法 9 1动态规划的研究对象和引例 动态系统 包含随时间变化的因素和变量的系统 动态决策问题 系统所处的状态和时刻是进行决策的重要因素 找到不同时刻的最优决策以及整个过程的最优策略 全过程的最优 阶段 10 1 生产决策问题企业在生产过程中 由于需求是随时间变化的 因此企业为了获得全年的最佳生产效益 就要在整个生产过程中逐月或逐季度地根据库存和需求决定生产计划 多阶段决策问题的典型例子 11 2 机器负荷分配问题 某种机器 高负荷 低负荷 g g u1 产品的年产量 投入生产的机器数量 机器的年完好率为a 0 a 1 h h u2 机器的年完好率为b 0 b 1 年终完好的机器 假定开始生产时完好的机器数量为s1 要求制定一个n年计划 在每年开始时 决定如何重新分配完好的机器在两种不同的负荷下生产的数量 使在n年内产品的总产量达到最高 12 3 线性规划 非线性规划等静态的规划问题也可以通过适当地引入阶段的概念 应用动态规划方法加以解决 不包含时间因素的静态决策问题 一次决策问题 也可以适当地引入阶段的概念 作为多阶段的决策问题用动态规划方法来解决 4 最短路问题 引例 给定一个交通网络图如前 其中两点之间的数字表示距离 或花费 试求从A点到G点的最短距离 总费用最小 13 2动态规划的基本概念和定义 1 阶段 阶段变量 把所给问题的过程 适当 按时间和空间 地分为若干个相互联系的阶段 描述阶段的变量称为阶段变量 常用k表示 14 2 状态 状态变量 每个阶段开始所处的自然状态或客观条件 描述过程的状况 通常一个阶段有若干个状态 描述过程状态的变量称为状态变量 它可用一个数 一组数或一向量来描述 常用sk表示第k阶段的状态 s2 状态允许集合 状态变量的取值允许集合或范围 15 在最优控制中也称为控制 3 决策 决策变量 某一阶段 某个状态 可以做出不同的决定 选择 决定下一阶段的状态 这种决定称为决策 决策变量 描述决策的变量 uk sk 表示第k阶段当状态为sk时的决策变量 允许决策集合 常用Dk sk 表示第k阶段从状态sk出发的允许决策集合 uk sk Dk sk D2 B1 16 系统当前的状态和决策 4 多阶段决策过程 在每个阶段进行决策 控制过程的发展 其发展是通过一系列的状态转移来实现的 系统过去的历史状态和决策 s2 T1 s1 u1 s3 T2 s1 u1 s2 u2 sk 1 Tk s1 u1 s2 u2 sk uk 状态转移方程的一般形式 s2 B1 u2 C1 s3 17 能用动态规划方法求解的多阶段决策过程是一类特殊的多阶段决策过程 即具有无后效性的多阶段决策过程 图示如下 5 无后效性或马尔可夫性 如果某阶段状态给定后 则在这个阶段以后过程的发展不受这个阶段以前各阶段状态的影响 过程的过去历史只能通过当前的状态去影响它未来的发展 18 构造动态规划模型时 要充分注意状态变量是否满足无后效性的要求 状态转移方程 状态具有无后效性的多阶段决策过程的状态转移方程如下 19 由每段的决策按顺序排列组成的决策函数序列称为k子过程策略 简称子策略 记为pk n sk 即 Pk n sk uk sk uk 1 sk 1 un sn 6 策略 按顺序排列的决策组成的集合 由过程的第k 终止状态为止的过程 称为问题的后部子过程 k子过程 20 允许策略集合 可供选择的策略范围 用P表示 最优策略 达到最优效果的策略 当k 1时 此决策函数序列成为全过程的一个策略 简称策略 记为p1 n s1 即 P1 n s1 u1 s1 u2 s2 un sn 21 7 指标函数和最优值函数 指标函数 用来衡量所实现过程优劣的一种数量指标 它是定义在全过程或所有后部子过程上确定的数量函数 用Vk n表示 Vk n Vk n sk uk sk 1 uk 1 sn 1 k 1 2 n 动态规划模型的指标函数 应具有可分离性 并满足递推关系 即Vk n可以表示为sk uk Vk 1 n的函数 22 常见的指标函数的形式是 过程和它的任一子过程的指标是它所包含的各阶段的指标和 即 无后效性的结果 其中V sj uj 表示第j阶段的阶段指标 这时上式可写成 Vk n sk uk sn 1 vk sk uk Vk 1 n V5 6 V5 6 s5 u5 V6 6 v5 s5 u5 V6 6 23 过程和它的任意子过程的指标是它所包含的各阶段的指标的乘积 即 可改写成 Vk n sk uk sn 1 vk sk uk Vk 1 n sk 1 uk 1 sn 1 指标函数的最优值 记为fk sk 表示从第k阶段的状态sk到第n阶段的终止状态的采取最优策略所得到的指标函数值 即 最优值函数 24 f6 s6 f6 F1 4 f6 F2 3 f5 E1 全过程的最优值函数记为f1 s1 25 多阶段决策过程的数学模型 具有无后效性 以和式为例 26 小结 指标函数形式 和 积 无后效性 可递推 Vk n Vk n sk uk sk 1 uk 1 sn 1 k sk uk Vk 1 n sk 1 uk 1 sn 1 27 最优策略 最优目标函数值 u1 u2 un s1 s2 sn 即最优决策序列 即执行最优策略时的状态序列 解多阶段决策过程问题 应求出 f1 s1 最优轨线 28 3动态规划的基本思想和基本方程 穷举法48条路线 最短路的特性 如果已有从起点到终点的一条最短路 那么从最短路线上中间任何一点出发到终点的路线仍然是最短路 证明用反证法 29 k 5 出发点有E1 E2 E3 u5 E1 F1E1 F1 G u5 E2 F2E2 F2 G k 6 F1 G f6 F1 4F2 G f6 F2 3 u5 E3 F2E3 F2 G 30 k 3f3 C1 13u3 C1 D1f3 C2 10u3 C2 D1f3 C3 9u3 C3 D2f3 C4 12u3 C4 D3 k 2f2 B1 13u2 B1 C2f2 B2 10u2 B2 C3 k 4f4 D1 7u4 D1 E2f4 D2 6u4 D2 E2f4 D3 8u4 D3 E2 u1 A B1 31 最优决策函数序列 uk 最短路线为A B1 C2 D1 E2 F2 G u1 A B1 u2 B1 C2 u3 C2 D1 u4 D1 E2 u5 E2 F2 u6 F2 G 32 求解的各个阶段 我们利用了k阶段与k 1阶段之间的递推关系 33 最优性原理 R Bellman 一个过程的最优策略具有这样的性质 即无论其初始状态及初始决策如何 对于先前决策所形成的状态而言 余下的诸决策仍构成最优策略 最优策略的任何一部分子策略 也是它相应初始状态的最优策略 每个最优策略只能由最优子策略构成 含义 动态规划的理论基础 34 动态规划的最优性定理 设阶段数为n的多阶段决策过程 其阶段编号为k 0 1 n 1 允许策略p 0 n 1 u 0 u 1 u n 1 是最优策略的充要条件是 对任意一个k 0 k n 1和s0 S0 有 35 证明 必要性 充分性 设p0 n 1 p0 k 1 pk n 1 为任一策略 sk为由 s0 p0 k 1 所确定的k阶段的起始状态 则有 以最大化为例 36 37 推论 若允许策略p 0 n 1是最优策略 则对任意的k 0 k n 1 它的子策略p k n 1对于以s k Tk 1 s k 1 u k 1 为起点的k到n 1子过程来说 必是最优策略 注意 k段状态s k 是由s0和p 0 k 1所确定的 最优性原理 38 动态规划 逆序法 小结 将问题的过程划分成恰当的阶段 选择状态变量sk 既能描述过程的变化又满足无后效性 确定决策变量uk及每一阶段的允许决策集合Dk sk 正确写出状态转移方程 正确写出指标函数Vk n的关系 它应满足下面三个性质 1 是定义在全过程和所有后部子过程上的数量函数 2 要具有可分离性 并满足递推关系 即Vk n sk uk sn 1 k sk uk Vk 1 n sk 1 uk 1 sn 1 39 3 函数 k sk uk Vk 1 n 对于变量Vk 1 n要严格单调 求解时从边界条件开始 逆 或顺 过程行进方向 逐段递推寻优 每段决策的选取都是从全局考虑的 与该段的最优选择答案一般是不同的 在求整个问题的最优策略时 由于初始状态是已知的 每段的决策都是该段状态的函数 故最优策略所经过的各段状态便可逐次变换得到 从而确定了最优路线 40 解 可列出静态规划问题的模型如下 4动态规划与静态规划 41 分阶段 每一阶段可使用的资金数为状态变量sk 状态转移方程 确定决策变量 确定状态变量 分三个阶段 即k 3 2 1 通常可以取静态规划中的变量为决策变量 42 指标函数 基本方程 当阶段k 3时 有 43 当阶段k 2时 有 当阶段k 1时 有 是凸函数 最大值点只能在 0 s1 的端点上取得 即 2阶导数 0 最优决策 44 所以 最优投资方案是全部资金投于第3个项目 可得最大收益200万元 例2求解下面问题 考虑用动态规划的逆序法进行求解 解题思路 45 解 1 将该问题划分为三个阶段 即k 1 2 3 2 确定状态变量并可得状态转移方程 3 指标函数 46 4 基本方程 最优值函数 当阶段k 3时 有 最优决策 当阶段k 2时 有 47 因此最后可得 当阶段k 1时 有 48 动态规划的优缺点 优点 最优解是全局最优解 能得到一系列 包括子过程 的最优解 不需要对系统状态转移方程 阶段效应函数等的解析性质作任何假设 缺点 没有统一的标准模型和标准的算法可供使用 应用的局限性 要求满足 无后效性 维数灾难 问题 49 设有某种原料 总数量为a 用于生产n种产品 若分配数量xi用于生产第i种产品 其收益为gi xi 问应如何分配 才能使生产n种产品的总收入最大 5资源分配问题 5 1资源平行分配问题 静态规划模型 50 例3某公司拟将5台某种设备分配给所属的甲 乙 丙三个工厂 各工厂若获得这种设备 可以为公司提供的盈利如表 问 这五台设备如何分配给各工厂 才能使公司得到的盈利最大 51 如何划分阶段 s1的可达状态集合 s2的可达状态集合 s3的可达状态集合 决策变量uk sk 0 sk 3个阶段 xk 状态转移方程 52 s1 s2 s3 3 2 1 x1 x2 x3 基本方程 指标函数gk xk s4 53 解 将问题按工厂分为三个阶段 甲 乙 丙分别编号为1 2 3 决策变量xk 分配给生产第k个工厂的设备数量 分配给第k个工厂至第3个工厂的设备数量 状态变量sk 54 Dk sk uk 0 xk sk 基本方程 数量为sk的原料分配给第k个工厂至第3个工厂所得到的最大总收益 状态转移方程 sk 1 sk xk xk的取值范围 55 x3 0 0 x3 1 1 x3 2 2 x3 3 3 k 3 s3 0 1 2 3 4 5 0 x3 s3 s3 0 s3 3 046111212 s3 2 s3 1 56 x3 5 4 5 x3 4 4 046111212 结果可写成表格的形式 s3 4 s3 5 57 k 2 s3 s2 x2 s2 0 1 2 3 4 5 0 x2 s2 有 x2 0 0 s2 0 58 x2 1 1 s2 1 59 x2 2 2 s2 2 60 x2 3 2 s2 3 61 x2 4 1 2 s2 4 62 s2 5 x2 5 2 63 结果列于下表 k 1时 s2 s1 x1 s1 5 0 x1 s1 有 64 x1 5 0 2 65 结果可写成表格的形式 最优分配方案一 由x1 0 根据s2 s1 x1 5 0 5 查表知x2 2 由s3 s2 x2 5 2 3 故x3 s3 3 即得甲工厂分配0台 乙工厂分配2台 丙工厂分配3台 最优分配方案 66 最优分配方案二 由x1 2 根据s2 s1 x1 5 2 3 查表知x2 2 由s3 s2 x2 3 2 1 故x3 s3 1 即得甲工厂分配2台 乙工厂分配2台 丙工厂分配1台 以上两个分配方案所得到的总盈利均为21万元 问题 如果原设备台数是4台 求最优分配方案 如果原设备台数是3台 求最优分配方案 67 5 2资源连续分配问题 68 如此进行n年 如何确定投入A的资源量u1 un 使总收入最大 此问题的静态规划问题模型为 69 高负荷 产量函数g 8u 年完好率为a 0 7 机器 例4机器负荷分配问题 假定开始生产时完好机器的数量为1000台 低负荷 产量函数h 5y 年完好率为b 0 9 试问每年如何安排机器在高低两种负荷下的生产 可使5年内生产的产品总产量最高 投入生产的机器数量 70 状态变量sk 状态转移方程 决策变量uk 第k年初拥有的完好机器台数 第k年高负荷下投入的机器数 sk 1 auk b sk uk 0 7uk 0 9 sk uk 0 uk sk 分析 第k年低负荷下投入的机器数 sk uk 阶段 71 递推方程 指标函数 第k年度产量为 k 5 4 3 2 1 sk 1 阶段指标 f6 s6 0 72 则状态转移方程为 sk 1 0 7uk 0 9 sk uk k 1 2 5 解 设阶段序数k表示年度 sk为第k年初拥有的完好机器台数 第k年度高负荷下投入的机器数为uk台 基本方程为 73 f4 s4 13 6s4 u 4 s4 k 4 u 5 s5 k 5 f5 s5 8s5 0 74 依次类推可得 因此最优策略为 最高产量为23700 练习 1 每年年初的完好机器数 2 如规定在第五年结束时完好机器数为500台 该如何安排生产 75 k 4 k 5 其他略 76 6生产与存贮问题 生产周期分为n个阶段 已知最初库存量 x1阶段市场的需求 dk生产的固定成本 K单位产品的消耗费用 L单位产品的阶段库存费用 h仓库容量 M阶段生产能力为B 一个生产部门 如何在已知生产成本 库存费用和各阶段市场需求条件下 决定各阶段产量 使计划内的费用总和为最小的问题 问如何安排各阶段产量 使计划周期内的费用总和最小 77 不能超过阶段k至阶段n的需求总量 xk dk dk 1 dn k 1 2 n 阶段k的初始库存量 x1已知 xn 1 0 0 xk min M dk dk 1 dn k 1 2 n 状态变量xk 不能超过库存容量M 78 决策变量uk 不超过生产能力 阶段k的产量 uk dk dk 1 dn xk 不小于该阶段的需求和库存量之差 不超过k n阶段的总需求减去第k阶段初的库存量 dk xk uk min B dk dk 1 dn xk 79 状态转移方程 为阶段生产费用和库存费用之和 即 阶段k的生产费用 k阶段末的库存费用 动态规划基本方程 阶段效益 80 例5已知n 3 K 8 L 2 h 2 x1 1 M 4 x4 0 B 6 d1 3 d2 4 d3 3 求解生产与库存问题 解 递推方程 8 2 3 x3 14 2x3 仓库容量4 dk xk uk min B dk dk 1 dn xk 81 若x3 0 u 3 0 3 则f3 0 14 若x3 1 则f3 1 12u 3 1 2 若x3 2 则f3 2 10u 3 2 1 若x3 3 则f3 3 0u 3 0 0 f3 x3 14 2x3u3 3 x3 x3 0 3 82 k 2 容量4 4 3 uk dk xk 4 x2 u2 min B d2 d3 x2 min 6 7 x2 0 x2 min M d2 d3 min 4 7 4 83 u 2 0 4 x2 0 4 x2 u2 min 6 7 x2 x2 1 u 2 1 6 84 x2 2 u 2 2 5 4 x2 u2 min 6 7 x2 x2 3 u 2 3 4 85 x2 4 u 2 4 0 4 x2 u2 min 6 7 x2 结果见下表 86 k 1 f2 30 2 u1 6 x2 x1 u1 d1 1 u1 3 u1 2 u 1 1 2 x1 1 u 1 1 6 u 1 1 3 87 f3 14 88 最优决策 1 为 1 0 0 0 x2 u1 2 0 x3 x2 u2 d2 0 4 4 0 最优路线为 最优目标函数值为42 状态变量 u 1 1 2 u 2 0 4 u 3 0 3 89 最优决策 2 为 1 1 3 0 x2 u1 2 0 x3 x2 u2 d2 1 6 4 3 最优路线为 最优目标函数值为42 状态变量 u 1 1 3 u 2 0 6 u 3 0 0 90 最优决策 3 为 1 4 0 0 x2 x1 u1 d1 1 6 3 4 x3 x2 u2 d2 0 4 4 0 最优路线为 最优目标函数值为42 状态变量 u 1 1 6 u 2 0 0 u 3 0 3 91 例6 某商店在未来的4个月里 准备利用它的一个仓库专门经销某种产品 仓库最大容量为1000 假定该商店每月只能出卖仓库现有的货 当商店在某月订货时 下月初才能到货 预测该商店未来四个月的买卖价格如表 假设商店在1月开始经销时 仓库储有该商品500 求若不计库存费用 该商店应如何制定1月至4月的订货与销售计划 使预期获利最大 2维生产与经营问题 92 设备更新问题提法如下 以一台机器为例 n为设备计划使用年数 Ik t 为第k年 阶段 机器役龄为t年的一