[理学]运筹学 第8章动态规划.ppt

一、动态规划的基本概念和基本原理 背包问题 五、排序问题 投资分配问题 两种资源的分配问题 此问题可写成静态规划问题 用动态规划方法求解(这属于二维动态规划问题) 生产与存贮问题 若已知某企业所生产产品的生产费用，存贮费用和市场的需求量，在其生产能力和存贮能力许可的前提下，正确确定各个时期的生产量，使既完成交货计划，又使总支出最少，即生产与存贮问题。 例： 某船厂根据合同，从当年起连续4年年末要为客户提供规格型号相同的大型客货船，每年的交船数及生产每艘船的生产费用见下表 1 3 2 2 每年需交付的船数(dk) 6.0 6.0 6.3 6.5 每艘船的生产费用(ck) 单位:百万元 1 2 3 4 年度(k) 该厂的生产能力为每年6艘船，在进行生产的年度，船厂还要支出经常费60万元，若造出的船当年不交货，则每艘船每积压一年造成的积压损失费为40万元，假定开始时及第四年年末交货均无积压船只。问该厂应如何安排这四年的生产计划，既要按时交货又使所花的总费用最小。 ① ② ③ ④ ③ ① ② 13.6 7.5 0.8 总费用 v4+f5=f4 0 0 0 以后各期 费用f5(s5) 0 0 0 期末 存量s5 13.6 7.5 0.8 本期费用v4 2 1 0 可能生产量x4 0 1 2 期初 存船s4 4 阶段 k 2.4* 0.8 2 1.6 0 4 8.7* 8.9 7.5 0.8 1 2 1.2 8.1 0 1 3 14.4* 15.2 14.8 13.6 7.5 0.8 0 1 2 0.8 7.7 14.0 0 1 2 2 20.9 21.1 20.7* 13.6 7.5 0.8 0 1 2 7.3 13.6 19.9 1 2 3 1 26.8 27.0 26.6* 总费用 v3+f4 13.6 7.5 0.8 以后各期 费用f4(s4) 0 1 2 期末 存量s4 13.2 19.5 25.8 本期费用v3 2 3 4 可能生产量x3 0 期初 存船s3 3 阶段 k 27.8* 28.5 28.2 28.5 28.2 26.6 20.7 14.4 8.7 2.4 0 1 2 3 4 1.2 7.8 13.8 19.8 25.8 0 1 2 3 4 3 34.0 34.1 33.8* 34.1 33.8* 26.6 20.7 14.4 8.7 2.4 0 1 2 3 4 7.4 13.4 19.4 25.4 31.4 1 2 3 4 5 2 39.6 39.7 39.4* 39.7 39.4* 26.6 20.7 14.4 8.7 2.4 0 1 2 3 4 13.0 19.0 25.0 31.0 37.0 2 3 4 5 6 1 45.2 45.3 45.0* 45.3 总费用 v2+f3 26.6 20.7 14.4 8.7 以后各期 费用f3(s3) 0 1 2 3 期末 存量s3 18.6 24.6 30.6 36.6 本期费用v2 3 4 5 6 可能生产量x2 0 期初 存船s2 2 阶段 k 16.4* 17.3 17.0 14.4 8.7 2.4 2 3 4 2.0 8.6 14.6 0 1 2 5 22.3* 22.6 22.9 22.6 20.7 14.4 8.7 2.4 1 2 3 4 1.6 8.2 14.2 20.2 0 1 2 3 4 总费用 v2+f3 以后各期 费用f3(s3) 期末 存量s3 本期费用v2 可能生产量x2 期初 存船s2 2 阶段 k 51.6* 52.0 52.4 52.4 52.9 53.0 45.0 39.4 33.8 27.8 22.3 16.4 0 1 2 3 4 5 6.6 12.6 18.6 24.6 30.6 36.6 1 2 3 4 5 6 0 总费用 v1+f2 以后各期 费用f2(s2) 期末 存量s2 本期费用v1 可能生产量x1 期初 存船s1 1 阶段 k 51.6 45.0 14.4 13.6 6.6 30.6 0.8 13.6 1 5 0 2 0 2 0 0 0 0 2 0 总费用 vk+fk+1 本期费用vk 最佳生产量xk 期末 存量sk+1 期初 存船sk 1 2 3 4 阶段 k 采购与销售问题 某商店在未来的四个月里，准备利用它的一个仓库专门经销某种商品，仓库最大容量能贮有这种商品1000单位。假定该商店每月只能出售仓库现有的货。当商店在某月购货时，下个月初才能到货。预测该商店未来四个月的买卖价格见下表。假定商店在1月开始经销时，仓库贮有该商品500单位。试问若不计库存费用，该商店应如何制定1月至4月的订购与销售计划，使预期获利最大。 12 8 13 17 销售单价(pk) 10 9 11 15 购买单价(ck) 1