《运筹学》课程教学资源（PPT课件讲稿）第四章 动态规划（4.4）节动态规划应用——求解方法讨论

44节动态规划应用(二) 求解方法讨论 规划求解方比 求解的一般方法 逆序求解 逆序求 核心 最优化原理 的应用

4-4节动态规划应用（二） ——求解方法讨论 核心 最优化原理 的应用 求解的一般方法 逆序求解

工程路线问题 01定步数间题(逆序求解 分步计算法 表格法 标号法

一、工程路线问题 • 1、定步数问题（逆序求解） –分步计算法 –表格法 –标号法

2、不定步数间 (1)无回路有向网 对节点排序,化为定步数间题 对节点排序,用分步计算法或表 法逆序求 对节点排序,用二次标号法求

2、不定步数问题 • （1）无回路有向网络 –对节点排序，化为定步数问题 –对节点排序，用分步计算法或表 格法逆序求解 –对节点排序，用二次标号法求解

(2)般情 0函数选代法 竟选代法

(2)一般情况 • 函数迭代法 • 策略迭代法

定步数间题求解示例 定步数问题(逆序求解 运输公司拟将一批货物自地运 至,其间交通系统网绪如图42所示。图 中节点表示地点,边表示两地间的道路, 边上的数字表示两地间的运输费用 运输费用最低的路线

定步数问题求解示例 • 1． 定步数问题（逆序求解） • 例4-6 某运输公司拟将一批货物自s地运 至t地，其间交通系统网络如图4-2所示。图 中节点表示地点，边表示两地间的道路， 边上的数字表示两地间的运输费用，求总 运输费用最低的路线

a d~9 5 3 e、12 g 5 6 C 图42

1 2 3 4 图 4-2 6 8 4 7 12 4 4 1 a d b e h t g c f s 3 4 11 3 6 9 5 5 3

问题可归结为四阶段决策问题,用动 态规划方法求解如下: (解法一)分步计算法 (从第4阶段开始) ①当k=4时,ih或g,j=t;f(t)=0 若i=h,则 f:(h)=mmn+/()}=cm+/f(0)=5+0,(h)=t

问题可归结为四阶段决策问题，用动 态规划方法求解如下： （解法一）分步计算法 （从第4阶段开始） ①当k=4时，i=h或g，j=t；f5 (t)=0 若i=h，则 f h c f j  c f t j h t i j h t j t = + = + = + = = ( ) min ( ) ( ) 5 0, ( ) * 4 5 5 4

若=g,则 f(g)=m+/()}=cm+/(0)=3+0=0./=t ②当k=3时,i=d或e;jh或g 若=d则 f()=-mh+1()}=mnm h, g Icas +f(gi 9+5 min =11,j3(a)=g 8+3

当k=3时，i=d或e,f；j=h或g f g c f j  c f t j t i j g t j t = + = + = + = = = * 4 5 5 4 ( ) min ( ) ( ) 3 0 0,   j d g c f g c f h f d c f j d g d h i j j h g = =       + + =       + + = + = = 11, ( ) 8 3 9 5 min ( ) ( ) ( ) min ( ) min * 3 4 4 4 , 3 若i=g，则 若i=d,则

若i=e,则 Ceh +fi(h) f,(e)=min ci+ f())=min h J=n, g Ice +f8) 7+5 min 12. 3(e)=h 2+3 若i=千则 f3()=mimn+()}=c+f4(g) J=8 5+3=8,j3()=g

若i=e,则   j e h c f g c f h f e c f j eg eh i j j h g = =       + + =       + + = + = = 12, ( ) 12 3 7 5 min ( ) ( ) ( ) min ( ) min * 3 4 4 4 , 3 若i=f,则   j f g f f ci j f j cf g f g j g = + = = = + = + = 5 3 8, ( ) ( ) min ( ) ( ) * 3 3 4 4

③当k=2时,i=a或b,c;j=d或e,f; 若=a,则 +f3(d f2(a)=min cu+f(i)=min +f( 3+11 min =12;j2(a)=f 4+8

当k=2时，i=a或b，c；j=d或e，f； 若i=a，则   j a f c f f c f d f a c f j a f a d i j j d f = =       + + =       + + = + = = 12; ( ) 4 8 3 11 min ( ) ( ) ( ) min ( ) min * 2 3 3 3 , 2