【大学竞赛】数学建模辅导 优化(p88).ppt

三、动态规划方法导引 例1：为了说明动态规划的基本思想方法和特点，下面以图1所示为例讨论的求最短路问题的方法。 第一种方法称做全枚举法或穷举法。它的基本思想是列举出所有可能发生的方案和结果，再对它们一一进行比较，求出最优方案。这里从v1到v10的路程可以分为4个阶段。第一段的走法有三种，第二三两段的走法各有两种，第四段的走法仅一种，因此共有3×2×2×1＝12条可能的路线，分别算出各条路线的距离，最后进行比较，可知最优路线是v1 →v3 → v7 → v9 →v10 ,最短距离是18． 显然，当组成交通网络的节点很多时，用穷举法求最优路线的计算工作量将会十分庞大，而且其中包含着许多重复计算． 第二种方法即所谓“局部最优路径”法，是说某人从k出发，他并不顾及全线是否最短，只是选择当前最短途径，“逢近便走”，错误地以为局部最优会致整体最优，在这种想法指导下，所取决策必是v1 →v3 →v5 → v8 → v10 ，全程长度是20；显然，这种方法的结果常是错误的． 第三种方法是动态规划方法。动态规划方法寻求该最短路问题的基本思想是，首先将问题划分为4个阶段，每次的选择总是综合后继过程的一并最优进行考虑，在各段所有可能状态的最优后继过程都已求得的情况下，全程的最优路线便也随之得到。 为了找出所有可能状态的最优后继过程，动态规划方法总是从过程的最后阶段开始考虑，然后逆着实际过程发展的顺序，逐段向前递推计算直至始点。 具体说，此问题先从v10开始，因为v10是终点。再无后继过程，故可以接着考虑第4阶段上所有可能状态v8 ,v9的最优后续过程．因为从v8 ,v9 到v10的路线是唯一的，所以v8 ,v9 的最优决策和最优后继过程就是到v10 ，它们的最短距离分别是5和3。 接着考虑阶段3上可能的状态v5 ,v6 , v7 , 到v10的最优决策和最优后继过程．在状态V5上，虽然到v8是8，到v9是9，但是综合考虑后继过程整体最优，取最优决策是到v9,最优后继过程是v5→v9 → v10 ，最短距离是12．同理，状态v6的最优决策是至v8 ；v7的最优决策是到v9 。 同样，当阶段3上所有可能状态的最优后继过程都已求得后，便可以开始考虑阶段2上所有可能状态的最优决策和最优后继过程，如v2的最优决策是到v5,最优路线是v2→v5→v9→v10 ，最短距离是15…依此类推，最后可以得到从初始状态v1的最优决策是到v3最优路线是v1→v3→v7→v9→v10 ，全程的最短距离是18。图5—1中粗实线表示各点到v10的最优路线，每点上方括号内的数字表示该点到终点的最短路距离。 综上所述可见，全枚举法虽可找出最优方案，但不是个好算法，局部最优法则完全是个错误方法，只有动态规划方法属较科学有效的算法。它的基本思想是，把一个比较复杂的问题分解为一系列同类型的更易求解的子问题，便于应用计算机。整个求解过程分为两个阶段，先按整体最优的思想逆序地求出各个子问题中所有可能状态的最优决策与最优路线值，然后再顺序地求出整个问题的最优策略和最优路线。计算过程中，系统地删去了所有中间非最优的方案组合，从而使计算工作量比穷举法大为减少。 四、动态规划的基本概念与基本方程 使用动态规划方法解决多阶段决策问题，首先要将实际问题写成动态规划模型，同时也为了今后叙述和讨论方便，这里需要对动态规划的下述一些基本术语进一步加以说明和定义： (一) 阶段 为了便于求解和表示决策及过程的发展顺序，而把所给问题恰当地划分为若干个相互联系又有区别的子问题，称之为多段决策问题的阶段。一个阶段，就是需要作出一个决策的子问题，通常，阶段是按决策进行的时间或空间上先后顺序划分的。用以描述阶段的变量叫作阶段变量，一般以k表示阶段变量．阶段数等于多段决策过程从开始到结束所需作出决策的数目，图1所示的最短路问题就是一个四阶段决策过程， 。 五、建模举例：最短路径问题 阶段k：每投资一个项目作为一个阶段； 状态变量xk：投资第k个项目前的资金数； 决策变量dk：第k个项目的投资； 决策允许集合：0≤dk≤xk 状态转移方程：xk+1=xk-dk 阶段指标：vk(xk ,dk)见表中所示； 递推方程：fk(xk)=max{vk(xk ,dk)+fk+1(xk+1)} 终端条件：f4(x4)=0 k=4，f4(x4)=0k=3，0≤d3≤x3，x4=x3-d3 k=2，0≤d2≤x2，x3=x2-d2 k=1，0≤d1≤x1，x2=x1-d1 （三）、建立动态规划模型的步骤 1、划分阶段 划分