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

运筹学5-5找讲师、公开课，上诺达名师网，中国最大的培训平台qy.thea.cn第五节动态规划的应用最短路问题投资分配问题背包问题多阶段生产安排问题生产与库存问题动态规划7-5第七章动态规划运筹学5-5找讲师、公开课，上诺达名师网，中国最大的培训平台qy.thea.cn三.背包问题问题的提出建立动态规划基本方程计算举例第五节动态规划的应用动态规划7-5运筹学5-5找讲师、公开课，上诺达名师网，中国最大的培训平台qy.thea.cn1.问题的提出有一个徒步旅行者,有n种物品供他选择装入背包中。已知每种物品的重量及使用价值(物品对旅行者来说又知这位旅行者所能承受的重量不能超过a公斤，问题：他应如何选择这n种物品的件数，使得使用价值最大？所带来好处的数量指标)由下表给出：物品12…k…n重量(公斤/件)a1a2…ak…an每件使用价值c1c2…ck…cn1x2xkxnx动态规划7-5运筹学5-5找讲师、公开课，上诺达名师网，中国最大的培训平台qy.thea.cn问题：他应如何选择这n种物品的件数，使得使用价值最大？物品12…k…n重量(公斤/件)a1a2…ak…an每件使用价值c1c2…ck…cn1xkxnx建立数学模型：nnnniZcxcxcxstaxaxaxaxin11221122max..0,1,2,且为整数，x21.问题的提出动态规划7-5运筹学5-5找讲师、公开课，上诺达名师网，中国最大的培训平台qy.thea.cn2.建立动态规划基本方程总重量不超过y公斤,背包中只装前k种物品时的最大使用价值。)(yfk设动态规划7-5运筹学5-5找讲师、公开课，上诺达名师网，中国最大的培训平台qy.thea.cn1.问题的提出有一个徒步旅行者,有n种物品供他选择装入背包中。已知每种物品的重量及使用价值(物品对旅行者来说又知这位旅行者所能承受的重量不能超过a公斤，问题：他应如何选择这n种物品的件数，使得使用价值最大？所带来好处的数量指标)由下表给出：物品12…k…n重量(公斤/件)a1a2…ak…an每件使用价值c1c2…ck…cn1x2xkxnx所求：)(afn动态规划7-5运筹学5-5找讲师、公开课，上诺达名师网，中国最大的培训平台qy.thea.cn使用价值重量公斤2.建立动态规划基本方程分析：ykkxa),2,1,0(kkayxkkxaykkxc)(1kkkxayfnk,3,2总重量不超过y公斤,背包中只装前k种物品时的最大使用价值。)(yfk设yxakk0时，当1k1()fy,11ayc11ayx前k种物品第k种物品前k-1种物品)(yfk})({1kkkkkxayfxckkayx,2,1,0max动态规划7-511cx110axy运筹学5-5找讲师、公开课，上诺达名师网，中国最大的培训平台qy.thea.cn3.计算举例例3物品123重量(公斤/件)325每件使用价值8512公斤5a)5(3f求：解：)(yfk})({1kkkkkxayfxckkayx0maxnk,3,2)5(3f})5({33233xafxc3350maxax})55(12{323xfx5503maxx1,03x})0(12),5(0{22ffmax03x13x)5(2f)0(2f动态规划7-5运筹学5-5找讲师、公开课，上诺达名师网，中国最大的培训平台qy.thea.cn3.计算举例例3物品123重量(公斤/件)325每件使用价值8512解：)5(2f})5({22122xafxc2250maxax})25(5{212xfx2502maxx2,1,02x})1(10),3(5),5(0{111fffmax02x12x22x)(yfkkkayx0max)5(2f)0(2f)5(1f)3(1f)1(1f})({1kkkkkxayfxc动态规划7-5运筹学5-5找讲师、公开课，上诺达名师网，中国最大的培训平台qy.thea.cn3.计算举例例3物品123重量(公斤/件)325每件使用价值8512解：)0(2f})0({22122xafxc2200maxax})20(5{212xfx2002maxx02x})0(0{1fmax02x)(yfkkkayx0max)0(1f02x})({1kkkkkxayfxc)5(2f)0(2f)5(1f)3(1f)1(1f)0(1f动态规划7-5运筹学5-5找讲师、公开课，上诺达名师网，中国最大的培训平台qy.thea.cn3.计算举例例3解：11x111)(xcyf,11ayc11ayx)5(1f115ac358811x)3(1f113ac338801x)1(1f111ac318001x)0(1f110ac3080物品123重量(公斤/件)325每件使用价值8512)5(1f)3(1f)1(1f)0(1f,8,8,0,011x11x01x01x动态规划7-5运筹学5-5找讲师、公开课，上诺达名师网，中国最大的培训平台qy.thea.cn3.计算举例例3解：)5(2f})5({22122xafxc2250maxax})25(5{212xfx2502maxx2,1,02x})1(10),3(5),5(0{111fffmax02x12x22x)(yfk})({1kkkkkxayfxckkayx0max811x811x001x,1312x11x,13)5(2f11x12x物品123重量(公斤/件)325每件使用价值8512)5(1f)3(1f)1(1f)0(1f,8,8,0,011x11x01x01x动态规划7-5运筹学5-5找讲师、公开课，上诺达名师网，中国最大的培训平台qy.thea.cn3.计算举例例3解：)0(2f})0({22122xafxc2200maxax})20(5{212xfx2002maxx02x})0(0{1fmax02x)(yfk})({1kkkkkxayfxckkayx0max)0(1f02x,13)5(2f11x12x)0(1f001x,0)0(2f01x02x物品123重量(公斤/件)325每件使用价值8512)5(1f)3(1f)1(1f)0(1f,8,8,0,011x11x01x01x动态规划7-5运筹学5-5找讲师、公开课，上诺达名师网，中国最大的培训平台qy.thea.cn3.计算举例例3物品123重量(公斤/件)325每件使用价值8512公斤5a)5(3f求：解：nk,3,2)5(3f})5({33233xafxc3350maxax})55(12{323xfx5503maxx1,03x})0(12),5(0{22ffmax03x13x12x1311x02x001x03x12x=1311x,13)5(2f11x12x,0)0(2f01x02x动态规划7-5运筹学5-5找讲师、公开课，上诺达名师网，中国最大的培训平台qy.thea.cn4.评注：背包问题是一种数学模型，在实际问题中有着广泛的应用。背包问题实际上是运输问题中车、船、飞机、潜艇、人造卫星等运输工具的最优配载问题。因此，有着广泛的实际意义。三.背包问题动态规划7-5运筹学5-5找讲师、公开课，上诺达名师网，中国最大的培训平台qy.thea.cn货物123重量(吨/件)4128使用价值(元)30806520a吨3(20)f求：有一艘可装三种货物的货船，每种货物一件的重量及价值如下表所示：已知该船的载重量不超过20吨，问对货船如何装载，使得价值最大？例：动态规划7-5运筹学5-5找讲师、公开课，上诺达名师网，中国最大的培训平台qy.thea.cn第五节动态规划的应用最短路问题投资分配问题背包问题多阶段生产安排问题生产与库存问题第七章动态规划动态规划7-5运筹学5-5找讲师、公开课，上诺达名师网，中国最大的培训平台qy.thea.cn四.多阶段生产安排问题问题的提出建立动态规划基本方程计算举例第五节动态规划的应用动态规划7-5运筹学5-5找讲师、公开课，上诺达名师网，中国最大的培训平台qy.thea.cn四.多阶段生产安排问题1.问题的提出有某种原料，可用于两种方式的生产。原料用于生产后，除产生一定的收益外，还可以回收一部分。问题：今有原料x吨，计划进行n个阶段的生产，问每生产信息由下表给出：生产方式方式1方式2收益函数回收函数xa1)(1xg)(2xgxa21021aa，阶段如何分别确定两种生产方式原料的投入量，使总收益最大？x是原料投入量a1,a2是原料回收率12312121240605020302510155动态规划7-5运筹学5-5找讲师、公开课，上诺达名师网，中国最大的培训平台qy.thea.cn2.建立动态规划基本方程原料投入量为x吨,进行k个阶段的生产所得的最大总收益。)(xfk设动态规划7-5运筹学5-5找讲师、公开课，上诺达名师网，中国最大的培训平台qy.thea.cn四.多阶段生产安排问题1.问题的提出有某种原料，可用于两种方式的生产。原料用于生产后，除产生一定的收益外，还可以回收一部分。生产问题：今有原料x吨，计划进行n个阶段的生产，问每信息由下表给出：生产方式1方式2收益函数回收函数xa1)(1xg)(2xgxa2阶段如何分别确定两种生产方式原料的投入量，使总收益最大？所求：)(xfn1021aa，x是原料投入量a1,a2是原料回收率动态规划7-5运筹学5-5找讲师、公开课，上诺达名师网，中国最大的培训平台qy.thea.cn2.建立动态规划基本方程分析：yxy)(2yxg)(1yg)(xfk})]([)()({21121yxayafyxgygkxy0maxnk,3,2)(xfk设)(1xf原料投入量为x吨,进行k个阶段的生产所得的最大总收益。ya1)(2yxaya1)(2yxa)]([211yxayafk})()({21yxgygxy0maxk个阶段后k-1个阶段第1阶段原料投入量x吨总收益原料回收量方式1方式20yx动态规划7-5运筹学5-5找讲师、公开课，上诺达名师网，中国最大的培训平台qy.thea.cn3.计算举例例5)100(3f求：在多阶段生产安排问题中，设收益函数分别为：)(6.0)(1万元xxg)(5.0)(2万元xxg回收率分别为：4.0,1.021aa生产阶段数为：3n原料投入量：吨100x动态规划7-5运筹学5-5找讲师、公开课，上诺达名师网，中国最大的培训平台qy.thea.cn动态规划7-53.计算举例例5)100(3f求：解：在多阶段生产安排问题中，1()0.6gxx2()0.5gxx4.0,1.021aa3n100x)(1xf})()({21yxgygxy0max})(5.06.0{yxyxy0max})1.05.0{yxxy0maxx6.0)(xy当投入量为x，只进行一个阶段生产时，最优策略是把全部原料都投入生产方式1，所得