第五节 动态规划的应用,最短路问题 投资分配问题 背包问题 多阶段生产安排问题 生产与库存问题,第七章 动态规划,三. 背包问题,问题的提出 建立动态规划基本方程 计算举例,第五节 动态规划的应用,1.问题的提出,有一个徒步旅行者,有n种物品供他选择装入背包中。,已知每种物品的重量及使用价值(物品对旅行者来说,又知这位旅行者所能承受的重量不能超过a公斤，,问题：,他应如何选择这n种物品的件数，使得使用价值最大？,所带来好处的数量指标)由下表给出：,问题：,他应如何选择这n种物品的件数，使得使用价值最大？,建立数学模型：,1.问题的提出,2.建立动态规划基本方程,总重量不超过y公斤,背包中只装前k种物品时的最大使用价值。,1.问题的提出,有一个徒步旅行者,有n种物品供他选择装入背包中。,已知每种物品的重量及使用价值(物品对旅行者来说,又知这位旅行者所能承受的重量不能超过a公斤，,问题：,他应如何选择这n种物品的件数，使得使用价值最大？,所带来好处的数量指标)由下表给出：,所求：,使用价值,重量 公斤,2.建立动态规划基本方程,分析：,总重量不超过y公斤,背包中只装前k种物品时的最大使用价值。,前k种物品,第k种物品,前k-1种物品,3.计算举例,例3,解：,3.计算举例,例3,解：,3.计算举例,例3,解：,3.计算举例,例3,解：,3.计算举例,例3,解：,8,8,0,3.计算举例,例3,解：,3.计算举例,例3,解：,13,0,= 13,4.评注：,背包问题是一种数学模型，在实际问题中有着广泛的应用。背包问题实际上是运输问题中车、船、飞机、潜艇、人造卫星等运输工具的最优配载问题。因此，有着广泛的实际意义。,三.背包问题,有一艘可装三种货物的货船，每种货物一件的重量及价值如下表所示：,已知该船的载重量不超过20吨，问对货船如何装载，使得价值最大？,例：,第五节 动态规划的应用,最短路问题 投资分配问题 背包问题 多阶段生产安排问题 生产与库存问题,第七章 动态规划,四.多阶段生产安排问题,问题的提出 建立动态规划基本方程 计算举例,第五节 动态规划的应用,四.多阶段生产安排问题,1.问题的提出,有某种原料，可用于两种方式的生产。原料用于生,产后，除产生一定的收益外，还可以回收一部分。,问题：,今有原料x 吨，计划进行n个阶段的生产，问每,生产信息由下表给出：,阶段如何分别确定两种生产方式原料的投入量，,使总收益最大？,x是原料投入量,a1, a2是原料回收率,40,60,50,20,30,25,10,15,5,2.建立动态规划基本方程,原料投入量为x 吨,进行k个阶段的生产所得的最大总收益。,四.多阶段生产安排问题,1.问题的提出,有某种原料，可用于两种方式的生产。原料用于生产,后，除产生一定的收益外，还可以回收一部分。生产,问题：,今有原料x 吨，计划进行n个阶段的生产，问每,信息由下表给出：,阶段如何分别确定两种生产方式原料的投入量，,使总收益最大？,所求：,x是原料投入量,a1, a2是原料回收率,2.建立动态规划基本方程,分析：,原料投入量为x 吨,进行k个阶段的生产所得的最大总收益。,k个阶段,后k-1个阶段,第1阶段,原料投入量x 吨,总收益,原料回收量,方式1,方式2,3.计算举例,例5,在多阶段生产安排问题中，,设收益函数分别为：,回收率分别为：,生产阶段数为：,原料投入量：,3.计算举例,例5,解：,在多阶段生产安排问题中，,当投入量为x，只进行一个阶段生产时，最优策略是把全部原料都投入生产方式1， 所得最大收益为0.6x (万元)。,3.计算举例,例5,解：,3.计算举例,例5,解：,当投入量为x，进行两个阶段生产时，最优策略：把全部原料都投入第一阶段生产方式2， 两个阶段所得最大收益为0.74x (万元)。,3.计算举例,例5,解：,3.计算举例,例5,解：,当投入量为x，进行三个阶段生产时，最优策略：把全部原料都投入第一阶段生产方式2，三个阶段所得最大收益为0.796x (万元)。,3.计算举例,例5,解：,结论：,原料投入量：x 吨,阶段数,第一阶段,方式1,方式2,最大收益,1,x,0,0.6x,2,0,x,0.74x,3,0,x,0.796x,3.计算举例,例5,解：,分析阶段收益和阶段回收量：,原料投入量：100 吨,阶段数,阶段收益,阶段原料回收量,1,2,3,100,40,16,y,x-y,y,x-y,y,x-y,3.计算举例,例5,解：,结论：,原料投入量：100 吨,阶段数,阶段收益,1,2,3,1,2,3,1,2,1,2,1,2,100,40,16,y,x-y,y,x-y,y,x-y,四.多阶段生产安排问题,问题的提出 建立动态规划基本方程 计算举例,第五节 动态规划的应用,第五节 动态规划的应用,最短路问题 投资分配问题 背包问题 多阶段生产安排问题 生产与库存问题,第七章 动态规划,作业：P351 9,有一艘可装三种货物的货船，每种货物一件的重量及价值如下表所示：,已知该船的载重量不超过20吨，问对货船如何装载，使得价值最大？,作业1,解答：,有一艘可装三种货物的货船，每种货物一件的重量及价值如下表所示：,已知该船的载重量不超过20吨，问对货船如何装载，使得价值最大？,最优策略：第1、2、3种货物分别为：1，0，2 件,求多阶段生产安排问题的最优策略。,其中收益函数为：,回收率为：,生产阶段数为：,原料投入量：,作业1,解答：,解：,解答：,解：,解答：,解：,解答：,解：,解答：,解：,解答：,解：,解答：,解：,结论：,阶段数,阶段收益,回收原料数量,1,2,3,1,2,3,4,5,1,2,100,y,x-y,1,2,90,y,x-y,1,2,81,y,x-y,1,2,56.7,y,x-y,4,1,2,39.69,y,x-y,5,+,三(2).二维背包问题,问题的提出 建立动态规划基本方程 计算举例,第五节 动态规划的应用,1.问题的提出,在背包问题中，除受质量条件限制外，还可以受背包体积等条件的限制。若增加背包体积限制为b,并设第i种物品每件的体积为bi立方米，,问题：,他应如何选择这n种物品的件数，使得使用价值最大？,重量不能超过a公斤，体积不能超过b立方米。,建立数学模型：,1.问题的提出,2.建立动态规划基本方程,总重量不超过W公斤,总体积不超过V立方米，背包中只装前k种物品时的最大使用价值。,1.问题的提出,在背包问题中，除受质量条件限制外，还可以受背包体积等条件的限制。若增加背包体积限制为b,并设第i种物品每件的体积为bi立方米，,问题：,他应如何选择这n种物品的件数，使得使用价值最大？,重量不能超过a公斤，体积不能超过b立方米。,求：,2.建立动态规划基本方程,总重量不超过W公斤,总体积不超过V，背包中只装前k种物品时的最大使用价值。,重量 公斤,分析：,前k种物品,第k种物品,前k-1种物品,体积 立方米,使用价值,2.建立动态规划基本方程,总重量不超过W公斤,总体积不超过V，背包中只装前k种物品时的最大使用价值。,当k = 1时，,3.计算举例,例4 有一辆最大运货量为12吨，最大容量为10立方米的卡车，装载两种货物A和B。求A,B各装多少件卡车的价值最大？,解：,设货物A、B的装载件数为,3.计算举例,例4,解：,3.计算举例,例4 有一辆最大运货量为12吨，最大容量为10立方米的卡车，装载两种货物A，B。,解：,最优方案：A货物装4件，B货 物不装，最大价值为8 。,4.评注：,凡具有正系数不等式约束的整数线性规划问题都可以用动态规划方法求解。若有m个约束条件，则认为是m维背包问题。,三(2).二维背包问题,