运筹学课件-第七章动态规划.ppt

第七章动态规划 动态决策问题 决策过程具有阶段性和时序性 与时间有关 的决策问题 即决策过程可划分为明显的阶段 动态规划 D P DynamicProgram 动态规划是解决多阶段决策过程最优化问题的一种方法 广泛应用于工业技术 生产管理 企业管理 经济 军事等领域 可用于解决最优路径问题 资源分配问题 生产计划与库存 投资 装载 排序等问题及生产过程的最优控制等 动态规划 D P 的起源 1951年 美 数学家R Bellman等提出最优化原理 从而建立动态规划 名著 动态规划 于1957年出版 动态决策问题分类 1 按数据给出的形式分为 离散型动态决策问题 连续型动态决策问题 2 按决策过程演变的性质分为 确定型动态决策问题 随机型动态决策问题 其中离散确定型是最基本的 本章主要针对这种类型的问题 介绍动态规划的基本思想 原理和方法 这些对其它类型的问题也适用 第七章动态规划 一 多阶段决策过程的最优化二 基本概念和基本原理三 动态规划模型的建立与求解四 动态规划在经济管理中的应用 一 多阶段决策过程的最优化 多阶段决策过程 多阶段决策过程 本意是指这样一类特殊的活动过程 它们可以按时间顺序分解成若干相互联系的阶段 称为 时段 在每一个时段都要做出决策 全部过程的决策是一个决策序列 所以多阶段决策问题属序贯决策问题 动态的含义 动态规划方法与 时间 关系很密切 随着时间过程的发展而决定各时段的决策 产生一个决策序列 这就是 动态 的意思 多阶段决策过程最优化的目标 达到整个活动过程的总体效果最优 例1生产与存贮问题某工厂每月需供应市场一定数量的产品 并将所余产品存入仓库 一般某月适当增加产量可降低生产成本 但超产部分存入仓库会增加库存费用 要求确定一个逐月的生产计划 在满足需求条件下 使一年的生产与存贮费用之和最小 显然 可以把每个月作为一个阶段 全年分为12个阶段逐次决策 例2投资决策问题某公司现有资金Q万元 在今后5年内考虑给A B C D4个项目投资 这些项目投资的回收期限 回报率均不相同 问该公司应如何确定这些项目每年的投资额 使到第5年末拥有资金的本利总额最大 这是一个5阶段决策问题 例3设备更新问题企业在使用设备时都要考虑设备的更新问题 因为设备越陈旧所需的维修费用越多 但购买新设备则要一次性支出较大的费用 现某企业要决定一台设备未来8年的更新计划 已预测了第j年购买设备的价格为Kj 设Gj为设备经过j年后的残值 Cj为设备连续使用j 1年后在第j年的维修费 j 1 2 8 问应在哪些年更新设备可使总费用最小 这是一个8阶段决策问题 每年年初要作出决策 是继续使用旧设备 还是购买新设备 几个例子 几个例子 例4 基建投资问题 一家公司有三个工厂 每个厂都需要进行扩建 公司用于扩建的资金总共为7万元 各个厂的投资方案及扩建后预期可获得的利润如表所示 单位 万元 现在公司要确定时各厂投资多少才能使公司的总利润达到最大 解 在这个问题中 因为每个厂都有几种投资方案 所以要对每个厂作出一项决策 总共要作出三个决策 同时 这三个厂的总投资不能超过7万元 如果我们把每个厂看成是一个阶段 这就是一个多阶段的决策问题 几个例子 例5 货船装运问题 有四种货物准备装到一艘货船上 第i i 1 2 3 4 种货物的每一箱重量是wi 单位 吨 其价值是vi 单位 干元 如表所示 假定这艘货船的总载重量是10吨 现在要确定这四种货物应各装几箱才能使装载货物的总价值达到最大 解 在这个问题中 因为对每一种货物要确定装载的箱数 也就是要作出一项决策 所以总共要作出四个决策 同时 各种货物的总重量不能超过10吨 如果我们把每一种货物看成是一个阶段 这也是一个多阶段的决策问题 几个例子 例6 最短路程问题 假定从A地到E地要铺设一条管道 其中要经过若干个中间点 如图 图中两点之间连线上的数字表示两地间的距离 现在要选择一条铺设管道的路线使总长度最短 解 在问题中 从A到B1 B2 B3中的哪一个点要作出一项决策 从B1 B2 B3中的某点到C1 C2 C3中的哪一个点又要作出一项决策等 所以总共要作出四个决策 因此可以把整个路程分为A B 包括B1 B2 B3 C 包括C1 C2 C3 和D 包括Dl D2 四个阶段 这是 个多阶段的决策问题 二 动态规划的基本概念和基本原理 1 阶段 将所给问题的过程 按时间或空间特征分解成若干互相联系的阶段 以便按次序去求每阶段的解 常用字母k表示阶段变量 动态规划模型要用到的概念 1 阶段 2 状态 3 决策和策略 4 状态转移 5 指标函数 2 状态 各阶段开始时的客观条件叫做状态 状态变量 描述各阶段状态的变量 用sk表示第k阶段的状态变量状态集合 状态变量的取值集合 用Sk表示 动态规划中的状态应具有如下性质 当某阶段状态给定以后 在这阶段以后过程的发展不受这段以前各段状态的影响 无后效性 一阶段 S1 A 二阶段 S2 B1 B2 B3 三阶段 S3 C1 C2 C3 四阶段 S4 D1 D2 3 决策 当各段的状态取定以后 就可以作出不同的决策 或选择 从而确定下一阶段的状态 这种决定称为决策 决策变量 表示决策的变量 称为决策变量 常用uk sk 表示第k阶段当状态为sk时的决策变量 允许决策集合 决策变量的取值往往限制在一定范围内 我们称此范围为允许决策集合 用Dk sk 表示第k阶段从状态sk出发的允许决策集合 D2 B1 C1 C2 D2 B2 C1 C2 C3 如状态为B1时选择C2 可表示为 u2 B1 C2 策略 各段决策确定后 整个问题的决策序列就构成一个策略 用p1 n u1 s1 u2 s2 un sn 表示 对每个实际问题 可供选择的策略有一定范围 称为允许策略集合 记作P1 n 使整个问题达到最优效果的策略就是最优策略 4 状态转移方程 动态规划中本阶段的状态往往是上一阶段状态和上一阶段的决策结果 第k段的状态sk 本阶段决策为uk sk 则第k 1段的状态sk 1也就完全确定 它们的关系可用公式表示 sk 1 Tk sk uk sk 1 uk sk 5 指标函数 用于衡量所选定策略优劣的数量指标 它分为阶段指标函数和过程指标函数 阶段指标函数是指第k段 从状态sk出发 采取决策uk时的效益 用d sk uk 表示 d B1 C2 一个n段决策过程 从1到n叫作问题的原过程 对于任意一个给定的k 1 k n 从第k段到第n段的过程称为原过程的一个后部子过程 V1 n s1 p1 n 表示初始状态为s1采用策略p1 n时原过程的指标函数值 而Vk n sk pk n 表示在第k段 状态为sk采用策略pk n时 后部子过程的指标函数值 最优指标函数记为fk sk 表示从第k段状态sk采用最优策略到过程终止时的最佳效益值 f2 B1 f1 A 动态规划的基本思想 最简单的方法 穷举法 共有多少条路径 依次计算并比较 动态规划方法 本方法是从过程的最后一段开始 用逆序递推方法求解 逐步求出各段各点到终点的最短路线 最后求得起始点到终点的最短路线 动态规划的基本思想 第一步 k 5状态s5 E1 E2 4 3 f5 E1 4 f5 E2 3 第二步 k 4状态 D1D2D3 u4 D1 E1 u4 D2 E2 u4 D3 E1 7 5 5 第三步 k 3状态 C1C2C3C4 u3 C1 D1 u3 C2 D2 u3 C3 D2 f3 C1 12 f3 C2 10 f3 C3 8 u3 C4 D3 f3 C4 9 12 10 8 9 第四步 k 2状态 B1B2 u2 B1 C2 u2 B2 C3 f2 B1 13 f2 B2 15 13 15 第五步 k 1状态 A u1 A B1 f1 A 17 17 即从A到F的最短距离为17 最优路线为 A B1 C2 D2 E2 F 练习 求从A到E的最短路径 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 D2 E C2 f5 E 0 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 D2 E C2 f4 D1 5 f5 E 0 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 D2 E C2 f4 D2 2 f5 E 0 f4 D1 5 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 D2 E C2 f4 D2 2 f5 E 0 f3 C1 8 f4 D1 5 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 D2 E C2 f4 D2 2 f5 E 0 f3 C2 7 f4 D1 5 f3 C1 8 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 D2 E C2 f4 D2 2 f5 E 0 f3 C3 12 f4 D1 5 f3 C1 8 f3 C2 7 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 D2 E C2 f4 D2 2 f5 E 0 f3 C3 12 f4 D1 5 f2 B1 20 f3 C2 7 f3 C1 8 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 D2 E C2 f4 D2 2 f5 E 0 f3 C3 12 f4 D1 5 f2 B2 14 f3 C2 7 f3 C1 8 f2 B1 21 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 D2 E C2 f4 D2 2 f5 E 0 f3 C3 12 f4 D1 5 f2 B3 19 f3 C2 7 f3 C1 8 f2 B1 21 f2 B2 14 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 D2 E C2 f4 D2 2 f5 E 0 f3 C3 12 f4 D1 5 f2 B3 19 f3 C2 7 f3 C1 8 f1 A 19 f2 B2 14 f2 B1 21 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 D2 E C2 f4 D2 2 f5 E 0 f3 C3 12 f4 D1 5 f2 B3 19 f3 C2 7 f3 C1 8 f1 A 19 f2 B2 14 f2 B1 21 状态最优决策状态最优决策状态最优决策状态最优决策状态 A A B2 B2 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 D2 E C2 f4 D2 2 f5 E 0 f3 C3 12 f4 D1 5 f2 B3 19 f3 C2 7 f3 C1 8 f1 A 19 f2 B2 14 f2 B1 21 状态最优决策状态最优决策状态最优决策状态最优决策状态 A A B2 B2 B2 C1 C1 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 D2 E C2 f4 D2 2 f5 E 0 f3 C3 12 f4 D1 5 f2 B3 19 f3 C2 7 f3 C1 8 f1 A 19 f2 B2 14 f2 B1 21 状态最优决策状态最优决策状态最优决策状态最优决策状态 A A B2 B2 B2 C1 C1 C1 D1 D1 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 D2 E C2 f4 D2 2 f5 E 0 f3 C3 12 f4 D1 5 f2 B3 19 f3 C2 7 f3 C1 8 f1 A 19 f2 B2 14 f2 B1 21 状态最优决策状态最优决策状态最优决策状态最优决策状态 A A B2 B2 B2 C1 C1 C1 D1 D1 D1 E E从A到E的最短路径为19 路线为A B2 C1 D1 E 可以看出 在求解的各阶段 都利用了第k段和第k 1段的如下关系 这种递推关系称为动态规划的基本方程 第二个式子称为边界条件 这种在图上直接计算的方法称为标号法 动态规划标号法较之穷举法的优点 第一 容易算出 其次 动态规划的计算结果不仅得到了从起始点到最终点的最短路线 而且得到了中间段任一点到最终点的最短路线 动态规划方法的基本思想 1 将多阶段决策过程划分阶段 恰当地选取状态变量 决策变量及定义最优指标函数 从而把问题化成一族同类型的子问题 然后逐个求解 2 求解时从边界条件开始 逆 或顺 过程行进方向 逐段递推寻优 在每一个子问题求解时 都要使用它前面已求出的子问题的最优结果 最后一个子问题的最优解 就是整个问题的最优解 3 动态规划方法是既把当前一段与未来各段分开 又把当前效益和未来效益结合起来考虑的一种最优化方法 因此每段的最优决策选取是从全局考虑的 与该段的最优选择一般是不同的 动态规划的基本方程 依据原理 最优化原理一个过程的最优策略具有这样的性质 即无论初始状态及初始决策如何 对于先前决策所形成的状态而言 其以后的所有决策应构成最优策略 三 动态规划模型的建立与求解 一 动态规划模型的建立 二 逆序解法与顺序解法 三 基本方程分段求解时的几种常用算法 一 动态规划模型的建立 建立动态规划的模型关键 在于识别问题的多阶段持征 将问题分解成为可用递推关系式联系起来的若干子问题 或者说正确地建立具体问题的基本方程 而正确建立基本递推关系方程的关键又在于正确选择状态变量 保证各阶段的状您变量具有递推的状态转移关系sk 1 Tk sk uk 下面以资源分配问题为例介绍动态规划的建模条件及解法 资源分配问题是动态规划的典型应用之一 资源可以是资金 原材料 设备 劳力等 资源分配就是将一定数量的一种或几种资源恰当地分配给若干使用者 以获取最大效益 一 动态规划模型的建立 例5某公司有资金10万元 若投资于项目i i 1 2 3 的投资额为xi时 其收益分别为g1 x1 4x1 g2 x2 9x2 g3 x3 2x32 问应如何分配投资数额才能使总收益最大 这是一个与时间无明显关系的静态最优化问题 可列出其静态模型 也可以人为地赋予时段概念 把问题转化为一个3段决策过程 关键问题是如何正确选择状态变量 使各后部子过程之间具有递进关系 一 动态规划模型的建立 例5某公司有资金10万元 若投资于项目i i 1 2 3 的投资额为xi时 其收益分别为g1 x1 4x1 g2 x2 9x2 g3 x3 2x32 问应如何分配投资数额才能使总收益最大 K 1 K 2 第k段时 所以 建立动态规划模型 阶段k 本例中取1 2 3状态变量sk 第k段可以投资于第k项到第3个项目的资金数决策变量xk 决定给第k个项目投资的资金数 状态转移方程 sk 1 sk xk 最优指标函数fk sk 当可投资金数为sk时 投资第k 3项所得的最大收益数 基本方程为 模型 建立动态规划模型的要点1 分析题意 识别问题的多阶段特性 按时间或空间的先后顺序适当地划分为满足递推关系的若干阶段 对非时序的静态问题要人为地赋予 时段 概念 2 正确地选择状态变量 使其具备两个必要待征 1 可知性 即过程演变的各阶段状态变量的取值 能直接或间接地确定 2 能够确切地描述过程的演变且满足无后效性 即由第k阶段的状态sk出发的后部子过程 可以看作是一个以sk为初始状态的独立过程 3 根据状态变量与决策变量的含义 正确写出状态转移方程sk 1 Tk sk uk 或转移规则 4 根据题意明确指标函数vk n最优指标函数fk sk 以及k阶段指标vk sk uk 的含义 并正确列出最优指标函数的递推关系及边界条件 即基本方程 二 逆序解法与顺序解法 如果寻优的方向与多阶段决策过程的实际行进方向相反 从最后一段开始计算逐段前推 求得全过程的最优策略 称为逆序解法 顺序解法的寻优方向同于过程的行进方向 计算时从第一段开始逐段向后递推 计算后一阶段要用到前一阶段的求优结果 最后一段计算的结果就是全过程的最优结果 求解步骤 第一步 k 0状态 s1 A f0 A 0 第二步 k 1状态 B1B2 u1 B1 A u1 B2 A f1 B1 4 f2 B2 5 4 5 第三步 k 2状态 C1C2C3 u2 C1 B1 u2 C2 B1 u2 C3 B1 f2 C1 6 f2 C2 7 f2 C3 10 u2 C4 B2 f2 C4 12 6 7 10 12 第四步 k 3状态 D1D2D3 u3 D1 C1或C2 u3 D2 C2 u3 D3 C3 f3 D1 11 f3 D2 12 f3 D3 14 11 12 14 第五步 k 4状态 E1E2 u4 E1 D1 u4 E2 D2 f4 E1 14 f4 E2 14 14 14 第六步 k 5状态 F u5 F E2 f5 F 17 17 即从A到F的最短距离为17 最优路线为 A B1 C2 D2 E2 F 顺序解法的基本方程 逆序解法与顺序解法建模的不同点 1 状态转移方式不同sk 1 Tk sk uk sk Tk sk 1 uk 2 指标函数的定义不同逆序解法中 我们定义最优指标函数fk sk 表示第k段从状态sk出发 到终点后部子过程最优效益值 f1 s1 是整体最优函数值 顺序解法中 定义最优指标函数fk sk 1 表示第k段时从起点到状态sk 1的前部子过程最优效益值 fn sn 1 是整体最优函数值 3 基本方程形式不同 1 当指标函数为阶段指标和形式逆序解法 则基本方程为 则基本方程为 顺序解法 2 当指标函数为阶段指标积形式逆序解法 则基本方程为 则基本方程为 顺序解法 最短路程问题 假定从A地到E地要铺设一条管道 其中要经过若干个中间点 如图 图中两点之间连线上的数字表示两地间的距离 现在要选择一条铺设管道的路线使总长度最短 练习 A B1 C2 D2 E 三 基本方程分段求解时的几种常用算法 1 离散变量的分段穷举算法动态规划模型中的状态变量与决策变量若被限定只能取离散值 则可采用分段穷举法 如例4的求解方法就是分段穷举算法 由于每段的状态变量和决策变量离散取值个数较少 所以动态规划的穷举法要比一般的穷举法有效 用分段穷举法求最优指标函数值时 最重要的是正确确定每段状态变量取值范围和允许决策集合的范围 例5 某公司有资金10万元 若投资于项目i i 1 2 3 的投资额为xi时 其收益分别为g1 x1 4x1 g2 x2 9x2 g3 x3 2x32 问应如何分配投资数额才能使总收益最大 2 连续变量的解法当动态规划模型中状态变量与决策变量为连续变量 就要根据方程的具体情况灵活选取求解方法 如经典解析方法 线性规划方法 非线性规划法或其它数值计算方法等 如在例5中 状态变量与决策变量均可取连续值而不是离散值 所以每阶段求优时不能用穷举方法处理 下面分别用逆序解法求解 其动态规划模型已建立如下 阶段k 本例中取1 2 3状态变量sk 第k段可以投资于第k项到第3个项目的资金数决策变量xk 决定给第k个项目投资的资金数 状态转移方程 sk 1 sk xk 最优指标函数fk sk 当可投资金数为sk时 投资第k 3项所得的最大收益数 基本方程为 状态转移方程 sk 1 sk xk k 3时 k 2时 状态转移方程 sk 1 sk xk k 1时 状态转移方程 sk 1 sk xk 状态转移方程 sk 1 sk xk k 1时 最优投资方案为全部资金投于第3个项目 可得最大收益200万元 连续变量的解法 顺序解法 建立动态规划模型 阶段k 本例中取1 2 3决策变量xk 决定给第k个项目投资的资金数状态变量sk 1 表示可用于第1到第k个项目投资的金额 则有 s4 10s3 s4 x3s2 s3 x2s1 s2 x1状态转移方程 sk sk 1 xk最优指标函数fk sk 1 表示第k段投资额为sk 1时第1到第k项目所获的最大收益 基本方程为 动态规划在经济管理中应用 一 背包问题 背包问题的一般提法是 一位旅行者携带背包去登山 已知他所能承受的背包重量限度为a千克 现有n种物品可供他选择装入背包 第i种物品的单件重量为ai干克 其价值 可以是表明本物品对登山的重要性的数量指标 是携带数量xi的函数ci xi i 1 2 n 问旅行者应如何选择携带各种物品的件数 以使总价值最大 其他如车 胎 飞机 潜艇 人造卫星等工具的最优装载问题 机床加工中零件最优加工 下料问题 投资决策问题 均等同于背包问题 背包问题的整数规划模型 背包问题的动态规划模型 1阶段k 将可装入物品按1 2 n排序 每段装一种物品 共划分为n个阶段 即k 1 2 n 2状态变量sk 1 在第k段开始时 背包中允许装入前k种物品的总重量 3决策变量xk 装入第k种物品的件数 4状态转移方程 sk sk 1 akxk5允许决策集合为 Dk sk 1 xk o xk sk 1 ak xk为整数 其中 sk 1 ak 表示不超过sk 1 ak的最大整数 6最优指标函数fk sk 1 表示在背包中允许装入物品的总重量不超过sk 1千克 采用最优策略只装前k种物品时的最大使用价值 7则可得到动态规划的顺序递推方程为 注 当xi仅表示装入 取1 和不装 取0 第i种物品 则本模型就是0 1背包问题 例 有一辆最大货运量为10吨的卡车 用以装载3种货物 每种货物的单位重量及相应单位价值如表所示 应如何装载可使总价值最大 设第i种货物装载的件数为xi i