运筹学课件ch8动态规划

第八章动态规划DynamicProgramming 8 1动态规划数学模型MathematicalModelofDP8 2资源分配问题ResourceAssignmentProblem8 3生产与存储问题Productionandinventoryproblem8 4背包问题KnapsackProblem8 5其它动态规划模型OtherModelofDP 运筹学OperationsResearch 8 1动态规划数学模型MathematicalModelofDP v2 v3 v4 v7 v5 v9 v6 v8 v10 2 8 5 12 13 10 7 10 13 11 2 8 6 5 8 8 5 4 0 5 8 4 7 例8 1 最短路径问题图8 1表示从起点A到终点E之间各点的距离 求A到E的最短路径 图8 1 v1 第1阶段 第2阶段 第3阶段 第4阶段 阶段 第5阶段 12 17 14 20 19 2020年2月26日星期三 2 3 4 7 5 9 6 8 10 2 8 5 12 13 10 7 10 13 11 2 8 6 5 8 8 5 4 图8 2 1 第1阶段 第2阶段 第3阶段 第4阶段 阶段 第5阶段 用WinQSB软件计算时 需要对状态重新编号 如下图所示 8 1动态规划数学模型MathematicalModelofDP 2020年2月26日星期三 1 2 3 4 8 5 7 6 9 10 2 8 5 12 13 10 M 10 4 13 11 11 2 8 6 5 8 8 6 4 用WinQSB软件计算时 当某状态没有路到下阶段某状态时 添加一条虚拟决策 线条 距离很大 如下图点3到点5 8 1动态规划数学模型MathematicalModelofDP 2020年2月26日星期三 动态规划问题具有以下基本特征 1 问题具有多阶段决策的特征 阶段可以按时间划分 也可以按空间划分 2 每一阶段都有相应的 状态 与之对应 3 每一阶段都面临一个决策 选择不同的决策将会导致下一阶段不同的状态 同时 不同的决策将会导致这一阶段不同的目标函数值 4 每一阶段的最优解问题可以递归地归结为下一阶段各个可能状态的最优解问题 各子问题与原问题具有完全相同的结构 能否构造这样的递推归结 是解决动态规划问题的关键 这种递推归结的过程 称为 不变嵌入 8 1动态规划数学模型MathematicalModelofDP 2020年2月26日星期三 5 状态具有无后效性当某阶段状态确定后 此阶段以后过程的发展不受此阶段以前各阶段状态的影响 如下图所示 C2 9 0 8 1动态规划数学模型MathematicalModelofDP 2020年2月26日星期三 动态规划基本原理是将一个问题的最优解转化为求子问题的最优解 研究的对象是决策过程的最优化 其变量是流动的时间或变动的状态 最后到达整个系统最优 基本原理一方面说明原问题的最优解中包含了子问题的最优解 另一方面给出了一种求解问题的思路 将一个难以直接解决的大问题 分割成一些规模较小的相同子问题 每一个子问题只解一次 并将结果保存起来以后直接引用 避免每次碰到时都要重复计算 以便各个击破 分而治之 即分治法 是一种解决最优化问题的算法策略 动态规划求解可分为三个步骤 分解 求解与合并 8 1动态规划数学模型MathematicalModelofDP 2020年2月26日星期三 1 阶段 Stage 表示决策顺序的时段序列 阶段可以按时间或空间划分 阶段数k可以是确定数 不定数或无限数 8 1 2基本概念 3 决策 Decision xk 从某一状态向下一状态过度时所做的选择 决策变量记为xk xk是所在状态sk的函数 在状态sk下 允许采取决策的全体称为决策允许集合 记为Dk sk 各阶段所有决策组成的集合称为决策集 2 状态 State 描述决策过程当前特征并且具有无后效性的量 状态可以是数量 也可以是字符 数量状态可以是连续的 也可以是离散的 每一状态可以取不同值 状态变量记为sk 各阶段所有状态组成的集合称为状态集 8 1动态规划数学模型MathematicalModelofDP 2020年2月26日星期三 4 策略 Strategy 从第1阶段开始到最后阶段全过程的决策构成的序列称为策略 第k阶段到最后阶段的决策序列称为子策略 5 状态转移方程 Statetransformationfunction 某一状态以及该状态下的决策 与下一状态之间的函数关系 记为sk 1 T sk xk 6 指标函数或收益函数 Returnfunction 是衡量对决策过程进行控制的效果的数量指标 具体可以是收益 成本 距离等指标 分为k阶段指标函数 k子过程指标函数及最优指标函数 8 1动态规划数学模型MathematicalModelofDP 2020年2月26日星期三 k阶段指标函数 从k阶段状态sk出发 选择决策xk所产生的第k阶段指标 称为k阶段指标函数 记为vk sk xk 从k阶段状态sk出发 选择决策xk xk 1 xn所产生的过程指标 称为k子过程指标函数或简称过程指标函数 记为Vk sk xk xk 1 xn 或Vk n为阶段数 过程指标函数 最优指标函数 从k阶段状态sk出发 对所有的子策略 最优的过程指标函数称为最优指标函数 记为fk sk 通常取Vk的最大值或最小值 Opt optimization表示 max 或 min 8 1动态规划数学模型MathematicalModelofDP 2020年2月26日星期三 动态规划要求过程指标满足递推关系 即 8 2 8 1动态规划数学模型MathematicalModelofDP 2020年2月26日星期三 动态规划数学模型由式 8 4 或 8 6 边界条件及状态转移方程构成 如连和形式的数学模型 8 1动态规划数学模型MathematicalModelofDP 2020年2月26日星期三 对于可加性指标函数 上式可以写为 上式中 opt 表示 max 或 min 对于可乘性指标函数 上式可以写为 上式称为动态规划最优指标的递推方程 是动态规划的基本方程 终端条件 为了使以上的递推方程有递推的起点 必须要设定最优指标的终端条件 即确定最后一个状态n下最优指标fn sn 的值 8 1动态规划数学模型MathematicalModelofDP 2020年2月26日星期三 用逆序法列表求解例8 1 k n 5时 f5 v10 0 k 4 递推方程为 8 1动态规划数学模型MathematicalModelofDP 2020年2月26日星期三 k 3 递推方程为 表8 2 8 1动态规划数学模型MathematicalModelofDP 2020年2月26日星期三 k 2 递推方程为 表8 3 8 1动态规划数学模型MathematicalModelofDP 2020年2月26日星期三 k 1 递推方程为 表8 4 最优值是表8 4中f1 s1 的值 从v1到v10的最短路长为19 最短路线从表8 4到表8 1回朔 查看最后一列最优决策 得到最短路径为 v1 v2 v5 v7 v10 8 1动态规划数学模型MathematicalModelofDP 2020年2月26日星期三 作业 教材P188T2 下一节 资源分配问题 8 1动态规划数学模型MathematicalModelofDP 8 2资源分配问题ResourceAssignmentProblem 2020年2月26日星期三 例8 2 公司有资金8万元 投资A B C三个项目 一个单位投资为2万元 每个项目的投资效益率与投入该项目的资金有关 三个项目A B C的投资效益 万元 和投入资金 万元 的关系见表8 5 求对三个项目的最优投资分配 使总投资效益最大 8 2资源分配问题ResourceAssignmentProblem 表8 5 解 设xk为第k个项目的投资 该问题的静态规划模型为 2020年2月26日星期三 阶段k 每投资一个项目作为一个阶段 k 1 2 3 4 k 4为虚设的阶段状态变量sk 投资第k个项目前的资金数决策变量xk 第k个项目的投资额决策允许集合 0 xk sk状态转移方程 sk 1 sk xk阶段指标 vk sk xk 见表8 5中的数据 递推方程 终端条件 f4 s4 0数学模型为 8 2资源分配问题ResourceAssignmentProblem 2020年2月26日星期三 k 4 终端条件f4 s4 0 k 3 0 x3 s3 s4 s3 x3 8 2资源分配问题ResourceAssignmentProblem 2020年2月26日星期三 k 2 0 x2 s2 s3 s2 x2 8 2资源分配问题ResourceAssignmentProblem 2020年2月26日星期三 k 1 0 x1 s1 s2 s1 x1 最优解为 s1 8 x1 0 s2 s1 x1 8 x2 4 s3 s2 x2 4 x3 4 s4 s3 x3 0 投资的最优策略是 项目A不投资 项目B投资4万元 项目C投资4万元 最大效益为48万元 8 2资源分配问题ResourceAssignmentProblem 2020年2月26日星期三 例8 3 某种设备可在高低两种不同的负荷下进行生产 设在高负荷下投入生产的设备数量为x 产量为g 10 x 设备年完好率为a 0 75 在低负荷下投入生产的设备数量为y 产量为h 8y 年完好率为b 0 9 假定开始生产时完好的设备数量s1 100 制定一个五年计划 确定每年投入高 低两种负荷下生产的设备数量 使五年内产品的总产量达到最大 阶段k 运行年份 k 1 2 3 4 5 6 k 1表示第一年初 k 6表示第五年末 即第六年初 状态变量sk 第k年初完好的机器数 k 1 2 3 4 5 6 也是第k 1年末完好的机器数 其中s6表示第五年末 即第六年初 的完好机器数 s1 100 决策变量xk 第k年初投入高负荷运行的机器数 状态转移方程 sk 1 0 75xk 0 9 sk xk 8 2资源分配问题ResourceAssignmentProblem 2020年2月26日星期三 决策允许集合 Dk sk xk 0 xk sk 阶段指标 vk sk xk 10 xk 8 sk xk 终端条件 f6 s6 0递推方程 8 2资源分配问题ResourceAssignmentProblem 2020年2月26日星期三 8 2资源分配问题ResourceAssignmentProblem 2020年2月26日星期三 8 2资源分配问题ResourceAssignmentProblem 2020年2月26日星期三 因为s1 100 五年的最大总产量为f1 s1 25 7525 100 3443 75 由x1 x2 x3 0 x4 s4 x5 s5 设备的最优分配策略是 第一年至第三年将设备全部用于低负荷运行 第四年和第五年将设备全部用于高负荷运行 每年投入高负荷运行的机器数以及每年初完好的机器数为 s1 100 x1 0 s2 0 75x1 0 9 s1 x1 90 x2 0 s3 0 75x2 0 9 s2 x2 81x3 0 s4 0 75x3 0 9 s3 x3 73x4 s4 73 s5 0 75x4 0 9 s4 x4 55x5 s5 55 s6 0 75x5 0 9 s5 x5 41第五年末还有41台完好设备 8 2资源分配问题ResourceAssignmentProblem 2020年2月26日星期三 一般地 设一个周期为n年 高负荷生产时设备的完好率为a 单台产量为g 低负荷完好率为b 单台产量为h 若有t满足 则最优设备分配策略是 从1 t 1年 年初将全部完好设备投入低负荷运行 从t n年 年初将全部完好设备投入高负荷运行 总产量达到最大 在例8 3中 n 5 a 0 75 b 0 9 g 10 h 8 g h g b a 1 3333式 8 7 的求和式是完好率a的i次方累加 由a0 1 1 3333 a0 a1 1 75知 n t 1 0 t 4 则1 3年低负荷运行 4 5年为高负荷运行 8 2资源分配问题ResourceAssignmentProblem 8 7 2020年2月26日星期三 作业 教材P188T1 6 8 9 8 2资源分配问题ResourceAssignmentProblem 下一节 生产与存储问题 8 3生产与存储问题Productionandinventoryproblem 2020年2月26日星期三 8 3生产与存储问题Productionandinventoryproblem 8 4 一个工厂生产某种产品 1 6月份生产成本和产品需求量的变化情况见表8 9 表8 9 没有生产准备成本 单位产品一个月的存储费为hk 0 6元 月底交货 分别求下列两种情形6个月总成本最小的生产方案 1 1月初与6月底存储量为零 不允许缺货 仓库容量为S 50件 生产能力无限制 2 其它条件不变 1月初存量为10 2020年2月26日星期三 8 3生产与存储问题Productionandinventoryproblem 解 动态规划求解过程如下 阶段k 月份 k 1 2 7状态变量sk 第k个月初的库存量决策变量xk 第k个月的生产量状态转移方程 sk 1 sk xk dk 决策允许集合 阶段指标 终端条件 f7 s7 0 s7 0 递推方程 2020年2月26日星期三 8 3生产与存储问题Productionandinventoryproblem 当k 6时 因为s7 0 有 当k 5时 由于s5 50 则当25 s5 0时x5的值取 0 决策允许集合为 2020年2月26日星期三 8 3生产与存储问题Productionandinventoryproblem k 4时 决策允许集合为 2020年2月26日星期三 8 3生产与存储问题Productionandinventoryproblem 显然该决策不可行 x5 0 s4 x4 65 d4 d5 s5 s4 x4 d4 25 x6 45 与s5 25矛盾 因此有 k 3 当0 s4 40时 2020年2月26日星期三 8 3生产与存储问题Productionandinventoryproblem 当40 s4 50时 当k 2时 由 x2的决策允许集合为 2020年2月26日星期三 8 3生产与存储问题Productionandinventoryproblem 当k 1时 由 只要期初存量s1 20 则x1的决策允许集合为 1 期初存储量s1 0 由各阶段的最优决策xj 及状态转移方程 回朔可求出最优策略 2020年2月26日星期三 8 3生产与存储问题Productionandinventoryproblem x1 20 s2 s1 x1 d1 0 20 20 0 x2 80 s3 s2 x2 d2 0 80 30 50 x3 85 50 35 s4 s3 x3 d3 50 35 35 50 40 x4 0 s5 50 0 40 10 25 x5 25 s5 15 s6 10 15 25 0 x6 45 总成本为2876 2 期初存储量s1 10 与前面计算类似 得到x1 10 x2 80 x3 35 x4 0 x5 15 x6 45 1 6月份生产 存储详细计划表见表8 10所示 2020年2月26日星期三 8 3生产与存储问题Productionandinventoryproblem 表8 10 2020年2月26日星期三 8 3生产与存储问题Productionandinventoryproblem 2020年2月26日星期三 8 3生产与存储问题Productionandinventoryproblem 作业 教材P189T7 下一节 背包问题 8 4背包问题KnapsackProblem 2020年2月26日星期三 8 4背包问题KnapsackProblem 背包问题数学模型为 式中 ck为第k种物品的单位价值 wk是第k种物品的单位重量或体积 W是背包的重量或体积限制 动态规划的有关要素如下 阶段k 第k次装载第k种物品 k 1 2 n 状态变量sk 第k次装载时背包还可以装载的重量 或体积 决策变量xk 第k次装载第k种物品的件数决策允许集合 Dk sk dk 0 xk sk wk xk为整数 状态转移方程 sk 1 sk wkxk阶段指标 vk ckxk 2020年2月26日星期三 8 4背包问题KnapsackProblem 递推方程 终端条件 fn 1 sn 1 0 例8 5 用动态规划方法求解下列整数规划 解 终端条件 f4 x4 0 k 3时 递推方程 2020年2月26日星期三 8 4背包问题KnapsackProblem 表8 11 最优决策是 s3为0 4时 x3 0 s3为5 9时 x3 1 s3 10时 x3 2 k 2时 递推方程 2020年2月26日星期三 8 4背包问题KnapsackProblem 表8 12 2020年2月26日星期三 第2阶段的最优决策见表8 13 表8 13 k 1时 递推方程 8 4背包问题KnapsackProblem 2020年2月26日星期三 s1 10 w1 3 D1 s1 0 1 2 3 计算结果见表8 14 表8 14 由表8 14 8 13 8 11 得到两个最优解 X1 0 5 0 X2 2 2 0 最优值Z 200 8 4背包问题KnapsackProblem 2020年2月26日星期三 作业 教材P189T5 8 4背包问题KnapsackProblem 下一节 其它动态规划模型 8 5其它动态规划模型OtherModelofDP 2020年2月26日星期三 8 5其它动态规划模型OtherModelofDP 8 5 1求解线性规划模型 例8 6 用动态规划方法求解下列线性规划 解 首先将问题转化为动态规划模型 阶段数为3 决策变量为xk 状态变量为第k阶段初各约束条件右端常数的剩余值 用s1k和s2k表示 状态转移方程为 s1 k 1 s1k a1kxk s2 k 1 s2k a2kxk 终端条件 2020年2月26日星期三 8 5其它动态规划模型OtherModelofDP k 2时 决策变量x2的允许集合 k 3时 决策变量x3的允许集合 2020年2月26日星期三 8 5其它动态规划模型OtherModelofDP 状态转移方程为 2020年2月26日星期三 8 5其它动态规划模型OtherModelofDP k 1时 决策变量x1的允许集合 状态转移方程 最优解 2020年2月26日星期三 8 5其它动态规划模型OtherModelofDP 8 5 1求解非线性规划模型 例8 7 用动态规划方法求解下列非线性规划 解 阶段数为3 决策变量为xk 状