清华大学运筹学课件动态规划

《清华大学运筹学课件动态规划》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、动态规划主要内容基本概念多阶段问题建模与求解迭代求解方法基本概念例、（无阶段划分）最短路问题下图五个城市，任何两个城市间均有道路相连，往返路程一样，由图中数字所示。求每个城市到第五个城市的最短路线和最短路程v5232vv14755561vv20.53v状态与状态集Svii,1,,5523决策与决策集2vv14Us()vii,1,,5,sS575561策略与策略集vv20.53PuUviii,1,,5状态转移函数TsuSsSuUs(,),,()阶段指标函数dsu(,),sSuUs,()（）dss(,)0问题对每个初始状态，

2、以极小化阶段指标函数之和为目标，确定一个能够转移到末状态v5的最优策略v5232vv14755561vv20.53马尔可夫（Markov）性（或无后效性）以任何状态为初始状态进行决策所产生的效果，不受如何到达这个状态的决策影响v5232vv14755561vv20.53最优性原理若vj在自vi到v5的最优路线上，那么这条路线上自vj到v5的部分就是自vj到v的最优路线5理由：马尔科夫性v5232vv14755561vv20.53定义各点到目的地的最优值函数fssS,根据最优性原理，最优值函数一定满足最优值方程fsmindsufTsu,,,sS

3、uUs动态规划的核心是解最优值方程多阶段问题（多阶段决策）最短路问题2C158B13D13445CE625146AD22F5833CE734123B8D2374C4选择从A至F的最短路铺设输油管道阶段1阶段2阶段3阶段4阶段5sususususus11223344556状态sk2C15状态集Sk8B13D1344决策uk5CE625146决策集Uskk()AD22F5833策略C341E273puukk,5,,5B8D2374策略集Pk,5C4如：S2B1,B2U4(D2)E1,E2Pk,5Uk(sk),,U5(s5)2C158B13D13

4、445CE625146AD22F5833CE734123B8D2374C4状态转移函数Tsukkk(,)Sk1,sSuUskkk,kk()阶段指标函数dsukkk(,),sSuUskkk,kk()5过程指标函数Vpskkk,5(

5、),5dsuii,iik用动态规划的术语描述最短路问题已知状态集S,k1,2,,6k决策集U(s),sS,k1,2,,5kkkk状态转移函数Tsu(,)usSuUsk,,(),1,2,,5kkkkkkkkk阶段指标函数dsu(,),sSuUsk,(),1,2,,5kkkkkkkk问题求p1,

6、5P1,5使下述过程指标函数达到最小5Vps1,5(

7、)1,51dsukkk,k1最短路问题的动态规划模型5minVps1,5(1,5

8、)1dsukkk,k1s.t.sTs,usSuU,,(),1sk5kk1kkkkkkk满足马尔可夫性：给定sk，系统在k阶段以后的状态和系统经由什么路径到达sk无关，即和s1,s2,,sk1的取值无关最优值函数一定满足最优值方程fsmindsufTsu,,,sSuUs多阶段最短路问题的逆推求解定义最优值函数fs为从s到终点的最短路程，并根据多阶段结构将其表示为f

9、sfssSkkk,,1,,6终止条件：fsfs660,sS利用多阶段结构，可得到最优性方程的以下等价式fsmindsufTsu,,uUsfskkmindsufTsu,k1k,,sSkuUsk结论：最优值函数fs可以用以下公式逆推确定fs()0,sS66f55()minsds,uf6Tsu5,,sS5uUs5()f44()minsds,uf5Tsu4,,sS4uUs4()f33()minsds,uf4Tsu3

10、,,sS3uUs3()f22()minsds,uf3Tsu2,,sS2uUs2()f11()minsds,uf2Tsu1,,sS1uUs1()最短路问题的逆推结果（最优决策可由最优值得到）12132C1578B1310D13444517CE62551406A8D223F583315C3451E273B298D374C4多阶段最短路问题的顺推求解定义最优值函数fs为从起点到s的最短路程，并根据多阶段结