第9章-动态规划DP.ppt

单击此处编辑母版标题样式,爱校园课件,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,动态规划,DP（Dynamic Programming）,动,态规划是现代企业管理中一种重要的决策方法，它是解决多阶段决策过程最优化的一种数学方法。,爱校园课件,一、多段决策问题的提出,例1生产与存储问题某工厂每季度需供应市场一定数量的产品（600，700，500，1200），未销售完的产品存入仓库（每件每季度1元），现要制定生产计划，在满足市场需求的条件下，使一年的生产与存储费用最少。生产费用为：件数的平方成正比，比例系数为0.005。,爱校园课件,爱校园课件,爱校园课件,爱校园课件,例2最短路问题,设有一辆汽车由,A,城到,B,城，中间可经过,V,1,到,V,8,城市，各城市的交通路线及距离如下图所示，问应选择哪一条路线，可使总距离最短。,爱校园课件,爱校园课件,爱校园课件,由上述例题可知，在实际生产、科学试验、经济活动的过程中，有一类活动的过程，由于其特殊性。可将该过程分为若干个相联系的阶段，在每个阶段都要做出决策，全部过程的决策就形成一个,决策序列,，每一个阶段的决策有许多种方案选择，从而形成多种决策策略，在这些决策策略中选择一个最优的策略，使在预定的标准下达到最好效果，这就是多阶段决策问题。,爱校园课件,二、多阶段决策的有关概念,爱校园课件,爱校园课件,爱校园课件,爱校园课件,爱校园课件,爱校园课件,三、动态规划的基本思想和基本方程,爱校园课件,以最短路线为例介绍动态规划的思想。常识告诉我们，最短路线有一个重要特点：如果由起点,A,经过,B,C,D,E,F,点到达终点,G,是一条最短的路线，则由点,B,出发经过,C,D,E,F,点到达终点,G,的这条子路线。就必然是从点,B,出发到达终点的所有可能选择的不同路线中最短的一条。此特点可用反正发来证明。,爱校园课件,根据最短路线这一特点，我们就得到了寻找最短路线的方法，假设已求得从点,B,出发到达终点的最短路线，再选择从,A,到,B,两点间的一条最短路线，就求得了从起点,A,到终点,G,的一条最短路线。那么，如何求从点,B,出发到达终点的最短路线呢，再假设已求得从点,C,出发到达终点的最短路线，再选择从,B,到,C,两点间的一条最短路线，就求得了从起点,B,到终点,G,的一条最短路线。,爱校园课件,以这样的思路，只要能求出,F,到,G,的最短路，就可以求出,E,到,G,的最短路，从而递推的求出，,D,C,B,A,到,G,的最短路。所以动态规划方法就是从终点逐段向始点方向寻找最优解的一种方法，即就是从最后一段开始，用由后向前逐步递推的方法，求出各点到,G,点的最短路线，最后求得有,A,点到,G,点的最短路线。,爱校园课件,爱校园课件,爱校园课件,爱校园课件,爱校园课件,爱校园课件,爱校园课件,爱校园课件,四、动态规划的最优性原理（,R.Bellman,原理）,“,作为整个过程的最优策略具有这样的性质：无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的决策必须构成最优策略。”简言之，一个最优策略的子策略总是最优的。,爱校园课件,五、解法举例,现利用动态规划的基本方程求解例1中的生产与存储问题,。,爱校园课件,爱校园课件,爱校园课件,爱校园课件,爱校园课件,爱校园课件,爱校园课件,爱校园课件,爱校园课件,爱校园课件,休息,爱校园课件,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C,1,C,3,D,1,A,B,1,B,3,B,2,D,2E,C,2,一、最短路径问题,求从,A,到,E,的最短路径,爱校园课件,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C,1,C,3,D,1,A,B,1,B,3,B,2,D,2,E,C,2,f,5,(E)=0,爱校园课件,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C,1,C,3,D,1,A,B,1,B,3,B,2,D,2,E,C,2,f,4,(D,1,)=5,f,5,(E)=0,爱校园课件,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C,1,C,3,D,1,A,B,1,B,3,B,2,D,2,E,C,2,f,4,(D,2,)=2,f,5,(E)=0,f,4,(D,1,)=5,爱校园课件,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C,1,C,3,D,1,A,B,1,B,3,B,2,D,2,E,C,2,f,4,(D,2,)=2,f,5,(E)=0,f,3,(C,1,)=8,f,4,(D,1,)=5,爱校园课件,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C,1,C,3,D,1,A,B,1,B,3,B,2,D,2,E,C,2,f4,(D,2,)=2,f,5,(E)=0,f,3,(C,2,)=7,f,4,(D,1,)=5,f,3,(C,1,)=8,爱校园课件,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C,1,C,3,D,1,A,B,1,B,3,B,2,D,2,E,C,2,f,4,(D,2,)=2,f,5,(E)=0,f,3,(C,3,)=12,f,4,(D,1,)=5,f,3,(C,1,)=8,f,3,(C,2,)=7,爱校园课件,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C,1,C,3,D,1,A,B,1,B3,B,2,D,2,E,C,2,f,4,(D,2,)=2,f,5,(E)=0,f,3,(C,3,)=12,f,4,(D,1,)=5,f,2,(B,1,)=20,f,3,(C,2,)=7,f,3,(C,1,)=8,爱校园课件,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C,1,C,3,D,1,A,B,1,B,3,B,2,D,2,E,C,2,f,4,(D,2,)=2,f,5,(E)=0,f,3,(C,3,)=12,f,4,(D,1,)=5,f,2,(B,2,)=14,f,3,(C,2,)=7,f,3,(C,1,)=8,f,2,(B,1,)=21爱校园课件,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C,1,C,3,D,1,A,B,1,B,3,B,2,D,2,E,C,2,f,4,(D,2,)=2,f,5,(E)=0,f,3,(C,3,)=12,f,4,(D,1,)=5,f,2,(B,3,)=19,f,3,(C,2,)=7,f,3,(C,1,)=8,f,2,(B,1,)=21,f,2,(B,2,)=14,爱校园课件,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C,1,C,3,D,1,A,B,1,B,3,B,2,D,2,E,C,2,f4,(D,2,)=2,f,5,(E)=0,f,3,(C,3,)=12,f,4,(D,1,)=5,f,2,(B,3,)=19,f,3,(C,2,)=7,f,3,(C,1,)=8,f,1,(A)=19,f,2,(B,2,)=14,f,2,(B,1,)=21,爱校园课件,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C,1,C,3,D,1,A,B,1,B,3,B,2,D,2,E,C,2,f,4,(D,2,)=2,f,5,(E)=0,f,3,(C,3,)=12,f,4,(D,1,)=5,f,2,(B,3,)=19,f,3,(C,2,)=7,f,3,(C,1,)=8,f,1,(A)=19,f,2,(B,2,)=14,f,2,(B,1,)=21,状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态,A （A，B,2,）B,2,爱校园课件,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C,1,C,3,D,1,A,B,1,B,3,B,2,D,2,E,C,2,f,4,(D,2,)=2,f,5,(E)=0,f,3,(C,3,)=12,f,4,(D,1,)=5,f,2,(B,3,)=19,f,3,(C,2,)=7,f,3,(C,1,)=8,f,1,(A)=19,f,2,(B,2,)=14f,2,(B,1,)=21,状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态,A （A，B,2,）B,2,（B,2,，C,1,）C,1,爱校园课件,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C,1,C,3,D,1,A,B,1,B,3,B,2,D,2,E,C,2,f,4,(D,2,)=2,f,5,(E)=0,f,3,(C,3,)=12,f,4,(D,1,)=5,f,2,(B,3,)=19,f,3,(C,2,)=7,f,3,(C,1,)=8,f,1,(A)=19,f,2,(B,2,)=14,f,2,(B,1,)=21,状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态,A （A，B,2,）B,2,（B,2,，C,1,）C,1,（C,1,，D,1,）D,1,爱校园课件,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C,1,C,3,D,1,A,B,1,B,3,B,2,D,2,E,C,2,f,4,(D,2,)=2,f,5,(E)=0,f,3,(C,3,)=12,f,4,(D,1,)=5,f,2,(B,3,)=19,f,3,(C,2,)=7,f,3,(C,1,)=8,f,1,(A)=19,f,2,(B,2,)=14,f,2,(B,1,)=21,状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态,A （A，B,2,）B,2,（B,2,，C,1,）C,1,（C,1,，D,1,）D,1,（D,1,，E）E,从,A,到,E,的最短路径为19，路线为,AB,2,C,1,D,1,E,爱校园课件,