《清华大学运筹学课件动态规划》由会员分享，可在线阅读，更多相关《清华大学运筹学课件动态规划（58页珍藏版）》请在金锄头文库上搜索。
1、动态规划动态规划 基本概念 多阶段问题 建模与求解 迭代求解方法 主要内容 基本概念 多阶段问题 建模与求解 迭代求解方法 主要内容 基本概念基本概念 1 v 4 v 3 v 5 v 2 v 5 1 0.5 5 3 7 5 2 6 2 例、（无阶段划分）最短路问题例、（无阶段划分）最短路问题 下图五个城市，任何两个城市间均有道路相连，往返 路程一样，由图中数字所示。求每个城市到第五个城 市的最短路线和最短路程 下图五个城市，任何两个城市间均有道路相连，往返 路程一样，由图中数字所示。求每个城市到第五个城 市的最短路线和最短路程 ( , ),( )T s uSsS uU s 状态转移函数 阶段指
2、标函数 状态转移函数 阶段指标函数 ( , )0d s s 1 v 4 v 3 v 5 v 2 v 5 1 0.5 5 3 7 5 2 6 2 状态与状态集状态与状态集 ,1,5 i Sv i 决策与决策集决策与决策集 ( ),1,5 , i U sv isS 策略与策略集策略与策略集 ,1,5 ii PuU vi 对每个初始状态，以极小化阶段指标函数之和为 目标，确定一个能够转移到末状态的最优策略 对每个初始状态，以极小化阶段指标函数之和为 目标，确定一个能够转移到末状态的最优策略 5 v 问题 （） 问题 （）( , ),( )d s usS uU s 马尔可夫（马尔可夫（Markov）性
3、（或无后效性）性（或无后效性） 1 v 4 v 3 v 5 v 2 v 5 1 0.5 5 3 7 5 2 6 2 以任何状态为初始状态进行决策所产生的 效果，不受如何到达这个状态的决策影响 以任何状态为初始状态进行决策所产生的 效果，不受如何到达这个状态的决策影响 最优性原理最优性原理 1 v 4 v 3 v 5 v 2 v 5 1 0.5 5 3 7 5 2 6 2 若在自到的最优路线上，那么这条路线 上自到的部分就是自到的最优路线 若在自到的最优路线上，那么这条路线 上自到的部分就是自到的最优路线 5 v j v j v 5 v i v 5 v j v 理由：马尔科夫性理由：马尔科夫性
4、1 v 4 v 3 v 5 v 2 v 5 1 0.5 5 3 7 5 2 6 2 根据最优性原理，最优值函数一定满足最优值方程根据最优性原理，最优值函数一定满足最优值方程 定义各点到目的地的最优值函数定义各点到目的地的最优值函数 , f ssS min, u U s f sd s uf T s usS 动态规划的核心是解最优值方程动态规划的核心是解最优值方程 多阶段问题多阶段问题 1 B 2 B 1 C A 2 C 3 C 4 C 1 D 2 D 3 D 1 E F 2 E 4 5 2 3 6 8 7 7 5 8 4 5 3 4 8 4 4 3 5 6 2 1 3 3 选择从至的最短路铺设输
5、油管道选择从至的最短路铺设输油管道AF （多阶段决策）最短路问题（多阶段决策）最短路问题 阶段阶段1 状态状态 k s 状态集状态集 k S 212 ,BBS 决策决策 k u 决策集决策集() kk Us 如：如： 2124 ,)(EEDU 策略策略 ,55 , kk puu )(,),( 555 , sUsUP kkk 阶段阶段2 阶段阶段3 阶段阶段4 阶段阶段5 1 B 2 B 1 C A 2 C 3 C 4 C 1 D 2 D 3 D 1 E F 2 E 4 5 2 3 6 8 7 7 5 8 4 5 3 4 8 4 4 3 5 6 2 1 3 3 1 s 2 s 3 s 5 s 4
6、 s 6 s 1 u 2 u 5 u 4 u 3 u 策略集策略集,5k P 1 B 2 B 1 C A 2 C 3 C 4 C 1 D 2 D 3 D 1 E F 2 E 4 5 2 3 6 8 7 7 5 8 4 5 3 4 8 4 4 3 5 6 2 1 3 3 1 (,),() kkkkkkkkk T s uSsSuUs 过程指标函数过程指标函数 状态转移函数状态转移函数 5 ,5,5 (|), kkkiii i k Vpsds u 阶段指标函数阶段指标函数 (,),() kkkkkkkk ds usSuUs 用动态规划的术语描述最短路问题 已知 用动态规划的术语描述最短路问题 已知6
7、 , 2 , 1,kSk状态集状态集 (,),(),1,2,5 kkkkkkkkk T s uusS uUsk 状态转移函数 问题 阶段指标函数 决策集 状态转移函数 问题 阶段指标函数 决策集5 , 2 , 1,),(kSssU kkkk (,),(),1,2,5 kkkkkkkk ds usS uUsk 求使下述过程指标函数达到最小求使下述过程指标函数达到最小5 , 15 , 1 Pp 5 1,51,51 1 (|), kkk k Vpsds u 最短路问题的动态规划模型最短路问题的动态规划模型 5 1,51,51 1 1 min(|), s.t. ,( ), 15 kkk k kkkkk
8、kkkk Vpsds u sTs usSuUsk 满足马尔可夫性：满足马尔可夫性： k s 给定，系统在阶段以后的状态和系统经由什 么路径到达无关，即和的取值无关 给定，系统在阶段以后的状态和系统经由什 么路径到达无关，即和的取值无关121 , k sss k k s 最优值函数一定满足最优值方程最优值函数一定满足最优值方程 min, u U s f sd s uf T s usS 多阶段最短路问题的逆推求解多阶段最短路问题的逆推求解 定义最优值函数为从到终点的最短路程，并根 据多阶段结构将其表示为 定义最优值函数为从到终点的最短路程，并根 据多阶段结构将其表示为 1 min, min, k
9、u U s kkkkk u Us f sd s uf T s u fsds ufTs usS f s s ,1,6 kk f sfssSk 终止条件：终止条件： 66 0,f sfssS 利用多阶段结构，可得到最优性方程的以下等价式利用多阶段结构，可得到最优性方程的以下等价式 5 4 3 2 1 66 55655 ( ) 44544 ( ) 33433 ( ) 22322 ( ) 11211 ( ) ( )0, ( )min, ( )min, ( )min, ( )min, ( )min, u Us u Us u Us u Us u Us f ssS f sds ufTs usS f sds
10、ufTs usS f sds ufTs usS f sds ufTs usS f sds ufT s usS 结论：最优值函数可以用以下公式逆推确定结论：最优值函数可以用以下公式逆推确定 f s 最短路问题的逆推结果（最优决策可由最优值得到）最短路问题的逆推结果（最优决策可由最优值得到） 1 B 2 B 1 C A 2 C 3 C 4 C 1 D 2 D 3 D 1 E F 2 E 4 5 2 3 6 8 7 7 5 8 4 5 3 4 8 4 4 3 5 6 2 1 3 3 4 0 3 7 5 5 12 10 8 9 13 15 17 多阶段最短路问题的顺推求解多阶段最短路问题的顺推求解 定
11、义最优值函数为从起点到的最短路程，并根 据多阶段结构将其表示为 定义最优值函数为从起点到的最短路程，并根 据多阶段结构将其表示为 , , 11 , , min, min, k kk T s us sS u U s kkkk Ts us sSu Us fsd s ufs fsds ufssS fs s ,1,6 kk fsfssSk 初始条件：初始条件： 11 0,fsfssS 由于对任意成立，所以由于对任意成立，所以k 1 , kkkkk STS US 1 11 2 22 3 33 4 44 11 2112 , ,( ) 3223 , ,( ) 4334 , ,( ) 5445 , ,( )
12、6 ( )0, ( )min, ( )min, ( )min, ( )min, ( T s us s S u Us Ts us s S u Us T s us s S u Us Ts us s S u Us f ssS f sds ufssS f sds ufssS f sds ufssS f sds ufssS f 5 55 556 , ,( ) )min, Ts us s S u Us sds ufssS 结论：最优值函数可以用以下公式顺推确定结论：最优值函数可以用以下公式顺推确定 f s 1 B 2 B 1 C A 2 C 3 C 4 C 1 D 2 D 3 D 1 E F 2 E 4
13、5 2 3 6 8 7 7 5 8 4 5 3 4 8 4 4 3 5 6 2 1 3 3 14 17 14 11 12 14 6 7 10 12 4 5 0 最短路问题的顺推结果（最优决策可由最优值得到）最短路问题的顺推结果（最优决策可由最优值得到） 一般性动态规划模型（其中表示某种运算，如加法）一般性动态规划模型（其中表示某种运算，如加法） 111222 1 min (or max ), s.t. ,( ), 1 nnn kkkkkkkkk ds uds uds u sTs usSuUskn 逆推求解逆推求解 11 1 ( ) ( )0, ( )min,1 k nn kkkkk u Us
14、fssS fsds ufTs usS kn 顺推求解顺推求解 11 11 , ,( ) ( )0, ( )min,1, k kk kkkk Ts us s Su Us f ssS fsds ufssSkn （的含义根据问题定）（的含义根据问题定）0 问题：动态规划方法能否保证最优解？ 动态规划方法如何节省计算量？ 问题：动态规划方法能否保证最优解？ 动态规划方法如何节省计算量？ 穷举（可保证最优解）穷举（可保证最优解） 1 B 2 B 1 C A 2 C 3 C 4 C 1 D 2 D 3 D 1 E F 2 E 4 5 2 3 6 8 7 7 5 8 4 5 3 4 8 4 4 3 5 6 2 1 3 3 总路径数总路径数 2 3 2 224 加法次数加法次数 5 24120 逆推求解
