10运筹学-动态规划概论.ppt

第一年初：500辆车全部用于低负荷运输。 第二年初：还有450辆完好的车，也全部用于低负荷运输。 第三年初：还有405辆完好的车，全部用于超负荷运输。 第四年初：还有238.5辆完好的车，全部用于超负荷运输。 第五年初：还有198.45辆完好的车，全部用于超负荷运输。 到第五年末，即第六年初，还剩余138.15辆完好的车。 实现最大利润 （亿元） 第 5 讲 背 包 问 题 一般的提法为：一旅行者携带背包去登山。已知他所能承受 的背包重量的极限为a (千克)，现有n种物品可供他选择装入 背包。第i种物品的单位重量为 (千克)，其价值（可以是表 明本物品对登山者的重要性指标）是携带数量 的函数 （i=1，2，…n）.问旅行者应如何选择携带物品的件 数，以使总价值最大？ 此模型解决的是运输工具包括卫星的最优装载问题。 其数学模型为： 设 为第 i 种物品装入的件数，则背包问题可归结为如下 形式的整数规划模型： 下面从一个例子来分析动态规划建模。 例7 /P218 有一辆最大货运量为10 t 的卡车，用以装载3种 货物，每种货物的单位重量及相应单位价值如表7-4 所示。 应如何装载可使总价值最大？ 货物编号i 1 2 3 单位重量（t） 3 4 5 单位价值 ci 4 5 6 表 7- 4 设第 种货物装载的件数为 则问题可表为： 阶段k: 将可装入物品按1，2，3的顺序排序，每段装入一 种物品，共划分3个阶段，即k=1,2,3. 状态变量 ：在第k段开始时，背包中允许装入前k种 物品的总重量。 决策变量 ：装入第k种物品的件数。 状态转移方程： 最优指标函数 ：在背包中允许装入物品的总重量不超 过 kg，采取最优策略只装前k种物品时的最大使用价值 货物1 货物2 货物3 由此可得动态规划的顺序递推方程为： 货物1 货物2 货物3 K=1 时 货物1 货物2 货物3 K=1 时 注意到： 例如： 时， 其它计算结果见表7-5： 0 1 2 3 0 1 2 3 4 5 6 7 8 9 10 4×0 4×0 4×0 4×0 4×1 4×0 4×1 4×0 4×1 4×0 4×1 4×2 4×0 4×1 4×2 4×0 4×1 4×2 4×0 4×1 4×2 4×3 4×0 4×1 4×2 4×3 0 0 0 4 4 4 8 8 8 12 12 0 0 0 1 1 1 2 2 2 3 3 表 7- 5 货物1 货物2 货物3 K=2 时 其中 例如： 时， 0 1 2 3 0 1 2 3 4 5 6 7 8 9 10 4×0 4×0 4×0 4×0 4×1 4×0 4×1 4×0 4×1 4×0 4×1 4×2 4×0 4×1 4×2 4×0 4×1 4×2 4×0 4×1 4×2 4×3 4×0 4×1 4×2 4×3 0 0 0 4 4 4 8 8 8 12 12 0 0 0 1 1 1 2 2 2 3 3 表 7- 5 其它计算结果见表7-6： 0 1 2 0 1 2 3 4 5 6 7 8 9 10 5×0＋0 … … … … 5×0＋4 5×1＋0 … 5×0＋12 5×1＋8 5×2＋0 0 5 13 0 1 1 表 7- 6 货物1 货物2 货物3 K=3 时 0 1