运筹学第五章动态规划.ppt

* 制定生产计划即决定每月生产多少个产品，而每个月生产多少与该月初的库存量有关， 投资 利润 0 10 20 30 40 50 60 f3(x) 0 25 60 85 110 135 155 最优 策略 (0,0,0) (0,0,10) (0,0,20) (0,0,30) (20,0,20) (20,0,30) (20,10,30) 第四阶段：求 f4(60)。即问题的最优策略。 最优策略为（20，0，30，10），最大利润为160万元。 练习： 求投资分配问题得最优策略，其中a＝50 万元，其余资料如表所示。 投资 利润 0 10 20 30 40 50 g1(x) 0 21 40 52 80 85 g2(x) 0 15 36 50 73 100 g3(x) 0 25 60 65 68 70 例：某公司打算在3个不同的地区设置4个销售点，根据市场部门估计，在不同地区设置不同数量的销售点每月可得到的利润如表所示。试问在各地区如何设置销售点可使每月总利润最大。 地区 销售点 0 1 2 3 4 1 2 3 0 0 0 16 12 10 25 17 14 30 21 16 32 22 17 x1=2，x2=1，x3=1，f3(4)=47 有一个徒步旅行者，其可携带物品重量的限度为a 公斤，设有n 种物品可供他选择装入包中。已知每种物品的重量及使用价值（作用），问此人应如何选择携带的物品（各几件），使所起作用（使用价值）最大？ 物品 1 2 … j … n 重量（公斤/件） a1 a2 … aj … an 每件使用价值 c1 c2 … cj … cn 这就是背包问题。类似的还有工厂里的下料问题、运输中的货物装载问题、人造卫星内的物品装载问题等。 四、背包问题 设xj 为第j 种物品的装件数（非负整数）则问题的数学模型如下： 用动态规划方法求解，令 fx(y) = 总重量不超过 y 公斤，包中只装有前k 种物品时的最大使用价值。 其中y ≥0， k ＝1,2, …, n 。所以问题就是求 fn(a) 其递推关系式为： 当 k=1 时，有： 例题：求下面背包问题的最优解 物品 1 2 3 重量（公斤） 3 2 5 使用价值 8 5 12 解：a＝5 ，问题是求 f3(5) 所以，最优解为 X＝（1 . 1 . 0），最优值为 Z = 13。 练习1：某厂生产三种产品，各种产品重量与利润的关系如表所示。现将此三种产品运往市场出售，运输能力总重量不超过 6 吨，问如何安排运输，使总利润最大？ 种类 1 2 3 重量（吨/公斤） 2 3 4 单件利润（元） 80 130 180 最优方案：X1 =（0.2.0）X2 =（1.0.1）Z=260 练习2：求下列问题的最优解 X=(2. 1. 0) 最优值为 Z = 13 排序问题指n 种零件经过不同设备加工是的顺序问题。其目的是使加工周期为最短。 1、n × 1 排序问题 即n 种零件经过1 种设备进行加工，如何安排？ 14 6 8 20 23 交货日期（d） 4 5 1 7 3 加工时间（t） 零件代号 例一、 五、排序问题 （1）平均通过设备的时间最小 按零件加工时间非负次序排列顺序，其时间最小。（即将加工时间由小到大排列即可） 零件加工顺序 工序时间 1 3 4 5 7 实际通过时间 1 4 8 13 20 交货时间 8 23 14 6 20 平均通过时间 延迟时间 = 13 – 6 = 7 （2）按时交货排列顺序 零件加工顺序 工序时间 1 3 4 5 7 实际通过时间 5 6 10 17 20 交货时间 8 23 14 6 20 平均通过时间 延迟时间 = 0 （3）既满足交货时间，又使平均通过时间最小 零件加工顺序 工序时间 1 3 4 5 7 实际通过时间 1 6