动态规划在经济管理中 的应用一背包问题 补充:动态规划 例2:背包问题 位旅行者携带背包去登山,已知他所能承受的背包重量限度为a千 克,现有n种物品可供他选择装入背包,第种物品的单件重量为a1千 克,其价值(可以是表明本物品对登山的重要性的数量指标)是携 带数量x的函数c;x;(i=1,2,…,n),问旅行者应该如何选择携带 各种物品的件数,以使总价值最大?(背包问题等同于车、船、人造 卫星等工具的最优装载等,有广泛的实际意义) 代数模型(一维背包问题): 设x1为第i物品装入的件数,则整数规划模型: 目标(总价值最大):MaxP=Σcr1 总重量约束:∑a1x;≤a 非负约束:x1≥0且为整数(i=1,2,…,n) 在 Excel中的解法:用本书9.1节的一般整数规划 >背包问题的扩展 当x仅表示装入(取1)和不装(取0)第种物品,则本模型就是0-1背包 问题。 多维背包问题:当约束条件不止一个时,如多总体积的限制等 RuC Information School, Ye Xiang, 2007
补充：动态规划 RUC Information School，Ye Xiang，2007 动态规划在经济管理中 的应用－背包问题 ➢ 例2：背包问题 ❖ 一位旅行者携带背包去登山，已知他所能承受的背包重量限度为a千 克，现有n种物品可供他选择装入背包，第i种物品的单件重量为ai千 克，其价值（可以是表明本物品对登山的重要性的数量指标）是携 带数量xi的函数cixi（i=1，2，…，n），问旅行者应该如何选择携带 各种物品的件数，以使总价值最大？(背包问题等同于车、船、人造 卫星等工具的最优装载等，有广泛的实际意义) 代数模型（一维背包问题）： 设xi为第i种物品装入的件数，则整数规划模型： 目标(总价值最大)：Max P=cixi 总重量约束： aixi a 非负约束：xi 0 且为整数（i=1，2，…，n） 在Excel中的解法：用本书9.1节的一般整数规划 ➢ 背包问题的扩展 ➢ 当xi仅表示装入(取1)和不装(取0)第i种物品，则本模型就是0-1背包 问题。 ➢ 多维背包问题：当约束条件不止一个时，如多总体积的限制等
动态规划在经济管理中 的应用一0-1背包问题 补充:动态规划 >背包问题的扩展:0-1背包问题 某人准备外出旅游,行装中有A、B、C、D、E共5件备 选物品,其重量和价值如表所示,假定行李总重不得 超过13Kg,求总价值最大的行李构成方案。 物品 ABCDE 数学模型: 重量Kg7543 设x为第i种物品是否装入(1-是,0- 价值百元94320.5 否),则0-1整数规划模型: 目标(总价值最大): MaxP=9x1+4x2+3x3+2x4+0.5x5 重量约束:7x1+5x2+4x3+3x4+x≤13 0-1约束:x为0或1(=1,2,3,4,5) RuC Information School, Ye Xiang, 2007
补充：动态规划 RUC Information School，Ye Xiang，2007 动态规划在经济管理中 的应用－0-1背包问题 ➢ 背包问题的扩展：0-1背包问题 某人准备外出旅游，行装中有A、B、C、D、E共5件备 选物品，其重量和价值如表所示，假定行李总重不得 超过13Kg，求总价值最大的行李构成方案。 物品 A B C D E 重量/Kg 7 5 4 3 1 价值/百元 9 4 3 2 0.5 数学模型： 设xi为第i种物品是否装入（1-是，0- 否），则0-1整数规划模型： 目标(总价值最大)： Max P=9x1+4x2+3x3+2x4+0.5x5 重量约束：7x1+5x2+4x3 +3x4+x513 0-1约束：xi为0或1（i=1,2,3,4,5）
动态规划在经济管理中 的应用一多维背包间题 补充:动态规划 >背包问题的扩展:多维背包问题 现有一辆载重w=5t,最大装载体积v=8m3卡车作为运输 工具,可装载三种货物,已知每种货物各8件,其他有 关信息如表所示,求携带货物价值最大的装载方案。 货物品单件货单件货单件货 数学模型: 种k 物重量物体积物价值 设x为第k种物品装入的件数,则整 Wtwm3|p/万元 数规划模型: 2 30 目标(总价值最大) MaxP=30x1+75x2+60x3 2 3 4 75 重量约束:x1+3x2+2x3S5 3 2 3 体积约束:2x1+4x2+3x3≤8 货物件数:x≤8(k=1,2,3 非负约束:xk≥0且为整数(k=1,2,3) RuC Information School, Ye Xiang, 2007
补充：动态规划 RUC Information School，Ye Xiang，2007 动态规划在经济管理中 的应用－多维背包问题 ➢ 背包问题的扩展：多维背包问题 现有一辆载重w=5t，最大装载体积v=8m3卡车作为运输 工具，可装载三种货物，已知每种货物各8件，其他有 关信息如表所示，求携带货物价值最大的装载方案。 货物品 种k 单件货 物重量 wk /t 单件货 物体积 vk /m3 单件货 物价值 pk /万元 1 1 2 30 2 3 4 75 3 2 3 60 数学模型： 设xk为第k种物品装入的件数，则整 数规划模型： 目标(总价值最大)： Max P=30x1+75x2+60x3 重量约束：x1+3x2+2x3 5 体积约束：2x1+4x2+3x3 8 货物件数：xk 8 (k=1,2,3) 非负约束：xk 0 且为整数(k=1,2,3)
动态规划在经济管理中的 应用一生产经营问题 补充:动态规划 在生产和经营中,经常遇到如何合理安排 生产计划、采购计划以及仓库的存货计划 和销售计划,使总效益最大的问题。以下 是几个例子 口例3:P206生产进度安排(动态规划方法) 口例4:生产与库存问题(动态规划的另外 种写法:网络最优化中的最小费用流问题) 例5:P87习题3.3(多种解法) 例6:采购与销售问题 RuC Information School, Ye Xiang, 2007
补充：动态规划 RUC Information School，Ye Xiang，2007 动态规划在经济管理中的 应用－生产经营问题 • 在生产和经营中，经常遇到如何合理安排 生产计划、采购计划以及仓库的存货计划 和销售计划，使总效益最大的问题。以下 是几个例子 例3：P206 生产进度安排（动态规划方法） 例4：生产与库存问题（动态规划的另外一 种写法：网络最优化中的最小费用流问题） 例5：P87 习题3.3（多种解法） 例6：采购与销售问题
动态规划在经济管理中的应用补充:动态规划 生产经营问题(续) 例3:P206生产进度安排(动态规划方法) 在Exce中的解法,主要利用: 本月剩余量R=上月剩余量R1+ 本月生产量(x+y1) 本月计划安装量N 具体见本章的“补充一动态规划问题”的 Exce文件 RuC Information School, Ye Xiang, 2007
补充：动态规划 RUC Information School，Ye Xiang，2007 动态规划在经济管理中的应用 －生产经营问题（续） 例3： P206 生产进度安排（动态规划方法） 在Excel中的解法，主要利用： 本月剩余量Ri=上月剩余量Ri -1＋ 本月生产量（xi+yi）－ 本月计划安装量Ni 具体见本章的“补充－动态规划问题”的 Excel文件