背包问题、多阶段生产安排问题.ppt

1、第五节 动态规划的应用,最短路问题 投资分配问题 背包问题 多阶段生产安排问题 生产与库存问题,第七章 动态规划,三. 背包问题,问题的提出 建立动态规划基本方程 计算举例,第五节 动态规划的应用,1.问题的提出,有一个徒步旅行者,有n种物品供他选择装入背包中。,已知每种物品的重量及使用价值(物品对旅行者来说,又知这位旅行者所能承受的重量不能超过a公斤，,问题：,他应如何选择这n种物品的件数，使得使用价值最大？,所带来好处的数量指标)由下表给出：,问题：,他应如何选择这n种物品的件数，使得使用价值最大？,建立数学模型：,1.问题的提出,2.建立动态规划基本方程,总重量不超过y公斤,背包中只装前

2、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.计算举例,例3,解：,13,0,= 13,4.评注：,背包问题是一种数学模型，在实际问题中有着广泛的应用。背包问题实际上是运输问题中车、船、飞机、潜艇、人造卫星等运输工具的最优配载问题。因此，有着广泛的实际意义。,三.背包问题,有一艘可装三种货物的货船，每种货物一件的重量及价值如下表所示：,已知该船的载重量不超过20吨，问对货船如何装载，使得价值最大？,例：,第五节 动态规划的应用,最短路问题 投资分配问题 背包问题 多阶段生产安排问题 生产与库存问题,第七章 动态规划,四.多阶段生产安排问题,问题的提出 建立动态规划基本方程 计算举例,第五节 动态规划的应用,四.多阶段生产

4、安排问题,1.问题的提出,有某种原料，可用于两种方式的生产。原料用于生,产后，除产生一定的收益外，还可以回收一部分。,问题：,今有原料x 吨，计划进行n个阶段的生产，问每,生产信息由下表给出：,阶段如何分别确定两种生产方式原料的投入量，,使总收益最大？,x是原料投入量,a1, a2是原料回收率,40,60,50,20,30,25,10,15,5,2.建立动态规划基本方程,原料投入量为x 吨,进行k个阶段的生产所得的最大总收益。,四.多阶段生产安排问题,1.问题的提出,有某种原料，可用于两种方式的生产。原料用于生产,后，除产生一定的收益外，还可以回收一部分。生产,问题：,今有原料x 吨，计划进行

5、n个阶段的生产，问每,信息由下表给出：,阶段如何分别确定两种生产方式原料的投入量，,使总收益最大？,所求：,x是原料投入量,a1, a2是原料回收率,2.建立动态规划基本方程,分析：,原料投入量为x 吨,进行k个阶段的生产所得的最大总收益。,k个阶段,后k-1个阶段,第1阶段,原料投入量x 吨,总收益,原料回收量,方式1,方式2,3.计算举例,例5,在多阶段生产安排问题中，,设收益函数分别为：,回收率分别为：,生产阶段数为：,原料投入量：,3.计算举例,例5,解：,在多阶段生产安排问题中，,当投入量为x，只进行一个阶段生产时，最优策略是把全部原料都投入生产方式1， 所得最大收益为0.6x (万

6、元)。,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,解：,分析阶段收益和阶段回收量：,原料投入

7、量：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,有一艘可装三种货物的货船，每种货物一件的重量及价值如下表所示：,已知该船的载

8、重量不超过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,

9、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.问题的提出,在背包问题中，除受质量条件限制外

10、，还可以受背包体积等条件的限制。若增加背包体积限制为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.计算