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

《背包问题、多阶段生产安排问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

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

2、何选择这n种物品的件数，使得使用价值最大？物品12…k…n重量(公斤/件)a1a2…ak…an每件使用价值c1c2…ck…cn建立数学模型：1.问题的提出动态规划7-52.建立动态规划基本方程总重量不超过y公斤,背包中只装前k种物品时的最大使用价值。动态规划7-51.问题的提出有一个徒步旅行者,有n种物品供他选择装入背包中。已知每种物品的重量及使用价值(物品对旅行者来说又知这位旅行者所能承受的重量不能超过a公斤，问题：他应如何选择这n种物品的件数，使得使用价值最大？所带来好处的数量指标)由下表给出：物品12…k…n重量(公斤/件)a1a2

3、…ak…an每件使用价值c1c2…ck…cn所求：动态规划7-5使用价值重量公斤2.建立动态规划基本方程分析：总重量不超过y公斤,背包中只装前k种物品时的最大使用价值。前k种物品第k种物品前k-1种物品动态规划7-53.计算举例例3物品123重量(公斤/件)325每件使用价值8512解：动态规划7-53.计算举例例3物品123重量(公斤/件)325每件使用价值8512解：动态规划7-53.计算举例例3物品123重量(公斤/件)325每件使用价值8512解：动态规划7-53.计算举例例3解：物品123重量(公斤/件)325每件使用价值851

4、2动态规划7-53.计算举例例3解：880物品123重量(公斤/件)325每件使用价值8512动态规划7-53.计算举例例3解：物品123重量(公斤/件)325每件使用价值8512动态规划7-53.计算举例例3物品123重量(公斤/件)325每件使用价值8512解：130=13动态规划7-54.评注：背包问题是一种数学模型，在实际问题中有着广泛的应用。背包问题实际上是运输问题中车、船、飞机、潜艇、人造卫星等运输工具的最优配载问题。因此，有着广泛的实际意义。三.背包问题动态规划7-5货物123重量(吨/件)4128使用价值(元)308065

5、有一艘可装三种货物的货船，每种货物一件的重量及价值如下表所示：已知该船的载重量不超过20吨，问对货船如何装载，使得价值最大？例：动态规划7-5第五节动态规划的应用最短路问题投资分配问题背包问题多阶段生产安排问题生产与库存问题第七章动态规划动态规划7-5四.多阶段生产安排问题问题的提出建立动态规划基本方程计算举例第五节动态规划的应用动态规划7-5四.多阶段生产安排问题1.问题的提出有某种原料，可用于两种方式的生产。原料用于生产后，除产生一定的收益外，还可以回收一部分。问题：今有原料x吨，计划进行n个阶段的生产，问每生产信息由下表给出：生产方

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

7、，使总收益最大？所求：x是原料投入量a1,a2是原料回收率动态规划7-52.建立动态规划基本方程分析：原料投入量为x吨,进行k个阶段的生产所得的最大总收益。k个阶段后k-1个阶段第1阶段原料投入量x吨总收益原料回收量方式1方式2动态规划7-53.计算举例例5在多阶段生产安排问题中，设收益函数分别为：回收率分别为：生产阶段数为：原料投入量：动态规划7-5动态规划7-53.计算举例例5解：在多阶段生产安排问题中，当投入量为x，只进行一个阶段生产时，最优策略是把全部原料都投入生产方式1，所得最大收益为0.6x(万元)。123121212yx-y

8、3.计算举例例5解：动态规划7-53.计算举例例5解：当投入量为x，进行两个阶段生产时，最优策略：把全部原料都投入第一阶段生产方式2，两个阶段所得最大收益为0.74x(万元)。12312121