[初中教育]第四章动态规划.ppt

本电子教案改编自浙江大学蒋绍忠教授《运筹学》教程4.0版 第四章　动态规划 教学大纲 第一讲 动态规划问题的基本概念 动态规划（DP）的概念 问题的提出 基本概念 Bellman函数 一、最短路径问题 一、最短路径问题 最短路径问题――图上标号法 二、资金分配问题 三、背包问题 四、资源动态分配问题 五、极值问题 五、极值问题 六、生产库存问题 七、货担郎问题 空白 结论：Max Z＝268000元，且 s1=100台 x1*=0台 　　d1＝70000 s2= 90台　x2*=0台 　　d2＝63000 s3= 81台　x3*=81台 　　d3＝81000 s4= 54台　x4*=54台 　　d4＝54000 s5= 36台（剩余） f1 ＝ 268000 ［例5］用DP方法求解： MaxZ＝4x1＋9x2＋2x32 x1＋x2＋x3＝10 x1，x2，x3≥0 可以把这个问题理解成以下经济意义： 有个背包可装10KG，有三种物品A、B、C WA ＋WB ＋WC＝10KG，也就是一定要装满，而A、B、C的重量是可变化的； 物品A、B、C的价值分别是：4WA、9WB、2WC2 现在求背包所装物品的最大价值。 ［例5］用DP方法求解： MaxZ＝4x1＋9x2＋2x32 x1＋x2＋x3＝10 x1，x2，x3≥0 ［例6］一个工厂生产某种产品，1－7月份生产成本和产品需求量的变化情况如下表。为了调节生产和需求，工厂设有一个产品仓库，库容量H＝9，已知期初库存量为2，标示期末（七月底）库存量为0。每个月生产的产品在月末入库，月初根据当月需求发货。求七个月的生产量，能满足各月的需求，并使生产成本最低。 4 7 2 3 5 8 0 需求量rk 15 10 20 17 13 18 11 生产成本ck 7 6 5 4 3 2 1 月份 ［基本参数］ 阶段k：按月份划分，k＝1，2，3，4，5，6，7 状态sk：第k个月初的库存 决策xk：第k个月的生产量 阶段指标：第k个月的生产成本，dk（sk，xk）＝ck xk 过程指标：fk（sk）＝Min｛dk（sk，xk）＋fk＋1（sk＋1）｝ 状态转移方程：sk＋1＝sk－rk＋xk 状态允许集合：rk≤sk≤H 边界条件f8（s8）＝0，s8＝0，s1＝2 4 7 2 3 5 8 0 需求量rk 15 10 20 17 13 18 11 生产成本ck 7 6 5 4 3 2 1 月份 ［分析：决策允许范围（每月生产量变化范围）］ （1）、s8＝0，即8月初库存＝0，即7月份生产量＝0， 即7月初库存＝7月份需求量，即x7＝0，s7＝r7＝4； （2）、由s7＝s6－r6＋x6， 得：x6＝s7－s6＋r6＝4－s6＋7＝11－s6（唯一决策）； （3）、由r6≤s6≤H，得：r6≤s5－r5＋x5≤H，得9-s5≤x5≤11-s5； （4）、由r5≤s5≤H，得：r5≤s4－r4＋x4≤H，得5-s4≤x4≤12-s4； （5）、由r4≤s4≤H，得：r4≤s3－r3＋x3≤H，得8-s3≤x3≤14-s3； （6）、由r3≤s3≤H，得：r3≤s2－r2＋x2≤H，得13-s2≤x2≤17-s2； （7）、由r2≤s2≤H，得：r2≤s1－r1＋x1≤H，得8-s1≤x1≤9-s1， 而s1＝2，得6≤x1≤7； ［用Bellman方程递推］ k＝7 f7（s7）＝Min｛d7（s7，x7）＋f8（s8）｝ 　 ＝Min｛c7 x7＋0｝＝0――――――［x7*=0］ k＝6 f6（s6）＝Min｛d6（s6，x6）＋f7（s7）｝ ＝Min｛c6 x6＋0｝ ＝ Min｛110－10s6｝＝110－10s6［x6*=11－s6］ k＝5 f5（s5）＝Min｛d5（s5，x5）＋f6（s6）｝ 　　　 ＝Min｛c5 x5＋（110－10s6）｝ ＝Min｛20x5＋［110－10（s5－r5＋x5）］｝ ＝Min｛10x5－10s5＋130｝ 　　　　＝10（9-s5）－10s5＋130 ＝220－20s5―――――――― ［x5*=9-s5］ k＝4 f4（s4）＝Min｛d4（s4，x4）＋f5（s5）｝ ＝Min｛c4 x4＋（220－20s5）｝ ＝Min｛17x4＋［220－20（s4－r4＋x4）］｝ 　　　 ＝ Min｛－3x4－20s4＋280｝ ＝－3（12－