动态规划在经济管理中 的应用一多维背包间题 补充:动态规划 >背包问题的扩展:多维背包问题 现有一辆载重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)