公选课-动态规划.ppt

动态规划Dynamic Programming
1 动态规划基本概念与方法
2 动态规划应用举例
动态规划是一项最优化技术,而不是一种算法;具体问题具体分析处理。
动态规划是一种将实际问题分解为更小的、相似的子问题,并存储子问题的解而避免计算重复的子问题,以解决最优化问题的方法策略。
一般来说,只要原问题可以划分成规模更小的子问题,并且原问题的最优解中包含了子问题的最优解,就可以考虑用动态规划解决。
一、多阶段决策问题与动态规划方法
[例1] 时间阶段——生产负荷问题
某种机器可以在高、低两种负荷下进行生产。高负荷年产量8,;低负荷年产量5,。现有完好机器1000台,需制定一个5年计划,以决定每年安排多少台机器投入高、低负荷生产,使5年的总产量最大。
不同时间阶段的决策问题:
(1)工厂生产过程:由于市场需求随着时间而变化,为了取得最佳经济效益,要在生产过程中,逐月或者逐季度地根据库存和需求情况决定生产计划安排。
(2)设备更新问题:设备刚买来时故障少,经济效益高,转让处理价值也高;随着使用年限的增加,故障多,经济效益差,处理价值也越低。如果卖去旧的买新的,,使总的经济效益最好。
[例2] 空间阶段——最短路问题
如图为一线路网络,现要从A点铺设一条管道到E点,图中两点间连线上数字表示两点间距离。现需选一条由A到E的铺管线路,使总距离最短。
多阶段决策问题的特点:
适合于用动态规划方法求解的只是一类特殊的多阶段决策问题,即具有“无后效性”的多阶段决策过程。
无后效性:某阶段的状态一旦确定,则此后过程的演变不再受此前各状态及决策的影响。即“未来与过去无关”,当前的状态是此前历史的一个完整总结。
(1)全枚举法或穷举法
从A到E的路程可分为4个阶段,共有16条可能的路线,
分别算出各条路线的距离,最后进行比较,可知最优路线是A →B2→ C1 → D1 →E ,最短距离是19。
当节点很多时,计算量庞大,且包含许多重复计算。
(2)动态规划方法
基本思想:从过程的最后阶段开始考虑,逆着实际过程发展的顺序,找出所有可能状态的最优后继过程,逐段向前递推计算直至始点。
计算过程中删去了所有中间非最优的方案组合,从而使计算量比穷举法大为减少。
(5,E)
(2,E)
(8,D1)
(7, D2)
(12, D2 )
(20, C1)
(14 , C1 )
(19 , C2 )
(19 , B2 )
二、基本概念与方程
1、基本概念
阶段——分步求解的过程,用阶段变量k表示,k= 1, …, n
状态——每阶段初可能的情形或位置,用状态变量sk表示,sk的取值集合称为状态集合Sk 。