运筹学动态规划应用举例课件.ppt

第七章动态规划 多阶段决策过程的最优化动态规划的基本概念和基本原理动态规划模型的建立与求解动态规划在经济管理中的应用 第四节动态规划在经济管理中的应用 连续变量的离散化解法先介绍连续变量离散化的概念 如投资分配问题的一般静态模型为 模型中 阶段数 总投资 各阶段投资数 各阶段收益 决策变量 状态变量状态转移方程 基本方程 指标函数 最优指标函数 建立它的动态规划模型 其基本方程为 其状态转移方程为 由于与都是连续变量 当各阶段指标没有特殊性而较为复杂时 要求出会比较困难 因而求全过程的最优策略也就相当不容易 这时常常采用把连续变量离散化的办法求其数值解 具体做法如下 1 令 把区间 0 a 进行分割 的大小可依据问题所要求的精度以及计算机的容量来定 2 规定状态变量及决策变量只在离散点上取值 相应的指标函数就被定义在这些离散值上 于是递推方程就变为 其中 作为离散化例子 在例5中规定状态变量和决策变量只在给出的离散点上取值 见例6 3 按逆序方法 逐步递推求出 最后求出最优资金分配方案 问如何分配投资数额才能使总效益最大 例5某公司有资金10万元 若投资于项目i i 1 2 3 的投资额为xi时 其效益分别为 例6连续变量的离散化解法 解令 将区间 0 10 分割成0 2 4 6 8 10六个点 即状态变量集合为 允许决策集合为 与均在分割点上取值 动态规划基本方程为 当k 3时 式中与的集合均为 计算结果见表7 1 当k 3时 表7 1 当k 2时 计算结果见表7 2 表7 2 当k 1时 计算结果见表7 3 表7 3 最大收益为 与例5结论完全相同 计算结果表明 最优决策为 应指出的是 这种方法有可能丢失最优解 一般得到原问题的近似解 一 背包问题一位旅行者携带背包去登山 已知他所能承受的背包重量限度为akg 现有n种物品可供他选择装入背包 第i种物品的单件重量为aikg 其价值是携带数量xi的函数ci xi i 1 2 n 问旅行者应如何选择携带各种物品的件数 以使总价值最大 例1有一辆最大货运量为10t的卡车 用以装载3种货物 每种货物的单位重量及相应单位价值见下表 应如何装载可使总价值最大 逆序解法 阶段k k 1 2 3状态变量sk 第k阶段可以装载第k种到第3种货物的重量 决策变量xk 决定装载第k种货物的数量 状态转移方程 sk 1 sk akxk最优指标函数fk sk 当可装载重量为sk 装载第k种到第3种货物所获得的最大价值 基本方程 当阶段k 3时 有 当阶段k 2时 有 当阶段k 1时 有 二 生产经营问题 在生产和经营管理中 经常遇到如何合理地安排生产计划 采购计划以及仓库的存货计划和销售计划 使总效益最高的问题 下面通过例子来说明对不同特点问题的不同处理技巧 例2生产与存贮问题 某工厂生产并销售某种产品 已知今后四个月市场需求预测如表 又每月生产j单位产品费用为 每月库存j单位产品的费用为 该厂最大库存容量为3单位 每月最大生产能力为6单位 计划开始和计划期末库存量都是零 试制定四个月的生产计划 在满足用户需求条件下总费用最小 假设第i 1个月的库存量是第i个月可销售量与该月用户需求量之差 而第i个月的可销售量是本月初库存量与产量之和 用动态规划方法求解时 对有关概念作如下分析 1 阶段 每个月为一个阶段 k 1 2 3 4 2 状态变量 为第k个月初的库存量 3 决策变量 为第k个月的生产量 4 状态转移方程 5 最优指标函数 表示第k月状态为时 采取最佳策略生产 从本月到计划结束 第4月末 的生产与存贮最低费用 6 基本方程 k 4 s5 s4 u4 g4 0 所以u4 g4 s4 4 s4 s4可取0 1 2 3 k 3 s4 s3 u3 g3 所以u3 s4 g3 s3 s3可取0 1 2 3 k 2 s3 s2 u2 g2 所以u2 s3 g2 s2 s2可取0 1 2 3 k 1 s2 s1 u1 g1 所以u1 s2 g1 s1 s1可取0 反推回去 u1 2 u2 5 u3 0 u4 4 例3采购与销售问题 某商店在未来的4个月里 准备利用它的一个仓库来专门经销某种商品 仓库最大容量能贮存这种商品l000单位 假定该商店每月只能出卖仓库现有的货 当商店在某月购货时 下月初才能到货 预测该商品未来四个月的买卖价格如表7 12所示 假定商店在1月开始经销时 仓库贮有该商品500单位 试问若不计库存费用 该商店应如何制定1月至4月的订购与销售计划 使预期获利最大 解按月份划分为4个阶段 k l 2 3 4状态变量 第k月初时仓库中的存货量 含上月订货 决策变量 第k月卖出的货物数量 第k月订购的货物数量 状态转移方程 最优指标函数 第k月初存货量为时 从第k月到4月末所获最大利润 则有逆序递推关系式为 当k 4时 显然 决策应取时才有最大值 当k 3时 这个阶段需解一个线性规划问题 因为只有两个变量x3 y3 可以用图解法 也可以用单纯形法 求解得到 时有最大值 当k 2时 求解线性规划问题 得 当k 1时 求解一个线性规划问题 得 最优策略见下表 最大利润为16000 期前存货 例4限期采购问题 随机型 某部门欲采购一批原料 原料价格在五周内可能有所变动 已预测得该种原料今后五周内取不同单价的概率如表7 14所示 试确定该部门在五周内购进这批原料的最优策略 使采购价格的期望值最小 表7 14 2020 1 29 31 可编辑 阶段k 可按采购期限 周 分为5段 k 1 2 3 4 5 状态变量 第k周的原料实际价格 决策变量 第k周如采购则 1 若不采购则 0 另外用表示 当第k周决定等待 而在以后采购时的采购价格期望值 最优指标函数 第k周实际价格为时 从第k周至第5周采取最优策略所花费的最低期望价格 则有逆序递推关系式为 解本例与前面所讨论的确定型问题不同 状态的转移不能完全确定 而按某种已知的概率分布取值 即属于随机型动态规划问题 为状态集合 500 600 700 当k 5时 因为若前四周尚未购买 则无论本周价格如何 该部门都必须购买 所以 当k 4时 由于 所以 当k 3时 由于 所以 当k 2时同理 当k 1时 所以 最优采购策略为 若第一 二 三周原料价格为500 则立即采购 否则在以后的几周内再采购 若第四周价格为500或600 则立即采购 否则等第五周再采购 而第五周时无论当时价格为多少都必须采购 按照以上策略进行采购 期望价格为 三 设备更新问题 从经济上分析 一台设备应该使用多少年更新最合算 这就是设备更新问题 一般来说 一台设备在比较新时 年运转量大 经济收入高 故障少 维修费用少 但随着使用年限的增加 年运转量减少因而收入减少 故障变多 维修费用增加 如果更新可提高年净收入 但是当年要支出一笔数额较大的购买费 为了比较不同决策的优劣 常常要在一个较长的时间内考虑更新决策问题 设备更新问题一般提法 在已知一台设备的效益函数r t 维修费用函数u t 及更新费用函数c t 条件下 要求在n年内的每年年初作出决策 是继续使用旧设备还是更换一台新的 使n年总效益最大 rk t 在第k年设备已使用过t年 或称役龄为t年 再使用1年时的效益 uk t 在第k年设备役龄为t年 再使用一年的维修费用 ck t 在第k年卖掉 台役龄为t年的设备 买进一台新设备的更新净费用 为折扣因子 0 1 表示一年以后的单位收入价值相当于现年的 单位 动态规划模型阶段变量k k 1 2 n 表示计划使用该设备的年限数 状态变量sk 第k年初 设备已使用过的年数 即役龄 决策变量xk 是第k年初更新 Replacement 还是保留使用 keep 旧设备 分别用R与K表示 状态转移方程为 阶段指标为 指标函数为 最优指标函数fk sk 表示第k年初 使用一台已用了sk年的设备 到第n年末的最大收益 则可得如下的逆序动态规划方程 实际上 例5设某台新设备的年效益及年均维修费 更新净费用如表7 15所示 试确定今后5年内的更新策略 使总收益最大 设 解如前述建立动态规划模型 n 5当k 5时 状态变量s5可取1 2 3 4 2 5 2 1 5 当k 4时 状态变量s4可取1 2 3 6 5 5 8 5 5 当k 3时 状态变量s3可取1 2 9 5 8 8 当k 2时 状态变量s2只能取1 12 5 当k 1时 状态变量s1只能取0 17 上述计算递推回去 当时 由状态转移方程 则 则查得 状态 查 推出 查 最优策略为 即第一年初购买的设备到第二 三 四年初各更新一次 用到第5年末 其总效益为17万元 k 5 s5可取1 2 3 4 k 4 s4可取1 2 3 k 3 s3可取1 2 k 2 s2可取1 k 1 s2可取0 货郎担问题一般提法为 一个货郎从某城镇出发 经过若干个城镇一次 且仅一次 最后仍回到原出发的城镇 问应如何选择行走路线可使总行程最短 这是运筹学的一个著名问题 实际中有很多问题可以归结为这类问题 四 货郎担问题 设是已知的n个城镇 城镇到城镇的距离为 现求从出发 经各城镇一次且仅一次返回的最短路程 若对n个城镇进行排列 有 n一1 2种方案 所以穷举法是不现实的 这里介绍一种动态规划方法 货郎担问题也是求最短路径问题 但与例4的最短路问题有很大不同 建动态规划模型时 虽然也可按城镇数目n将问题分为n个阶段 但是状态变量不好选择 不容易满足无后效性 为保持状态间相互独立 可按以下方法建模 设S表示从到中间所有可能经过的城市集合 S实际上是包含除与两个点之外其余点的集合 但S中的点的个数要随阶段数改变 状态变量表示 从点出发 经过S集合中所有点一次最后到达 最优指标函数为从出发经由k个城镇的S集合到Vi的最短距离 决策变量表示 从经k个中间城镇的S集合到城镇的最短路线上邻接的前一个城镇 则动态规划的顺序递推关系为 例6已知4个城市间距离如表7 16 求从v1出发 经其余城市一次且仅一次最后返回v1的最短路径与距离 解由边界