运筹学-动态规划(二)(名校讲义).ppt

1、第十九讲 动态规划（二）,1 具有隐含阶段和无限阶段问题的算法 2 不定期阶段决策问题的求解函数迭代与策略迭代,1 具有隐含阶段和无限阶段问题的算法（1）,一、具有隐含阶段（即阶段有限，但不明显） 动态规划法的一个重要环节是需有阶段划分，其中，转移函数往往是从一个阶段转移到另一个阶段。例如：xk+1=g(xk，uk，k)， 表明从kk+1的转变关系。显然，这有明显的阶段划分。 然而，转移函数亦可定义为一个集合转移到另一个集合，该转移函数特点示于图3-10。,1 具有隐含阶段和无限阶段问题的算法（2）,非交叉集合的函数转移，有明显的划分，简图示于图3-11。,例3-6敷设管道问题（设无回路） 已

2、知从A到M的管道铺设的可行路线及其费用于图3-12。 求从A到M的最低费用铺设线路。,1 具有隐含阶段和无限阶段问题的算法（3）,解本问题无明显阶段划分，可令： 每个节点表示“状态”。 节点链（管道）的选择为决策变量。 其求解步骤如下： (i) I(M)=0（终端条件） (ii) 从M上推，找直接联结的状态点，共有3个点：J、K、L。它们到达终点的最小费用为： I(J)=min2+ I(K)，4+ I(M)，2+ I(L)尚不确定 I(K)=min4+ I(M)=4 I(L)=min3+ I(M)=3 于是： I(J)=min2+4，4，2+3=4,1 具有隐含阶段和无限阶段问题的算法（4）,

3、(iii)再从J、K、L向前推 I(H)=min3+ I(K)，3+ I(J)=min3+4，3+4=7 I(I)=min2+ I(L)=min2+3=5 全部计算结果示如图3-13中。,图中数字表示从该点到终点M铺设管道的最低费用。例如，A至M的最低费用为14，其路线为：ABEGILM。,1 具有隐含阶段和无限阶段问题的算法（5）,例3-7挑硬币问题 N个硬币，有一枚较重，其它等重。现要求用等臂天平来选 出重币。希确定出一定能找出这枚重币的最少称重次数。 解令：硬币数为状态变量x I(x)表示使用最优策略在批量为x个硬币中一定能找出重币 中所需最少称量次数。 u为决策变量，放在天平每边的硬币

4、数。 现分析每次u的最佳选择。显然，从x个硬币中选出2u个硬 币分放天平2边，必有下述2种可能： 1）天平平衡，说明重币在剩余的(x2u)个硬币中。 2）天平不平衡，说明重币在天平重的一边的u个硬币中。,1 具有隐含阶段和无限阶段问题的算法（6）,因此，u的选择应符合下式： I(x)=1+ maxI(u)，I(x2u) I(1)=0 (1) 式中加1，是因为I(1)=0，而把x分成u及x2u，且找出硬 币所在区需秤一次。 式（1）表明，需从I(u)和I(x2u)中选取最大者再取极小， 故应选u使之I(u)尽量与I(x2u)相等，即： ux2u u x 故应选u= 或 +1。,1 具有隐含阶段和

5、无限阶段问题的算法（7）,根据此法，对任何N都可用递推公式求出。其公式为： 3k1x3k I(x)=k 即： k为log3x的最小整数：x与I(x)的对应见表3-8。,1 具有隐含阶段和无限阶段问题的算法（8）,表3-8 x与I(x)对应表,二、无限阶段过程（有明显阶段，但是阶段数无限）（略）,2 不定期阶段决策问题的求解函数迭代与策略迭代 （1）,解 显然，该问题从几何图形上无明显阶段划分，路线中经过几点亦无限制，如果采用动态规划算法，必须加以处理。,本节不想从理论上推导这些方法，只准备结合例题介绍这 些方法的步骤。 例3-9已知5个地区（点）之间的距离示于图3-14中。求任 一点到终点的最

6、短路线。,2 不定期阶段决策问题的求解函数迭代与策略迭代 （2）,设各点之间的距离为cij，令f(i)为由i点出发到终点N的最短 距离，则知： f(i)=mincij+f(j) i=1，2，N1 f(N)=0 (cNN=0) 显然，上述表达式在计算时会出现循环现象，不能采用简 单的递推迭代，与第三节一样，此处亦可采用函数迭代法 与策略迭代法。 一、函数迭代法 以段数（本例为到达终点容许经过最多的点步数）为参变 数。计算中，逐步求出只容许1步，然后只容许2步，直 至只容许N1步到达N点的最短路径。具体步骤如下：,2 不定期阶段决策问题的求解函数迭代与策略迭代 （3）,先选一个初始函数f1(i)，

7、令每个点只许一步到达终点。即： f1(i)=ciN i=1，2，N1 f1(N)=0 i=N 递推：令fk(i)表示k步内到达的最短路径。则： fk(i)= i=1，2，N1 fk(N)=0 结合本例计算。 1)只容许走一步到达=5点的各点对应最短路线为： f1(i)=ci5 2)最多走两步到达5点的各点对应最短路线为： 设i=1，则f2(1)=,2 不定期阶段决策问题的求解函数迭代与策略迭代 （4）,=minc11+f1(1)，c12+f1(2)，c13+f1(3)，c14+f1(4)，c15+f1(5) =min0+2，6+7，5+5，2+3，2+0 =2 同理，i=2，3，4时可得：f2

8、(2)=5.5，f2(3)=4，f2(4)=3。 3)f3(i)= 4)f4(i)= 由于f3=f4，故结束。具体结果示于表3-9。 不难看出： (i) fk(i)单调下降，且收敛于一固定值（即最优解） (ii) fk(i)不超过N1步可收敛于f(i)（即最优解）,2 不定期阶段决策问题的求解函数迭代与策略迭代 （5）,表3-9 例3-9的函数迭代结果,2 不定期阶段决策问题的求解函数迭代与策略迭代 （6）,二、策略迭代法 先给出初始策略u0(i)，i=1，2，N1。然后逐步求新 策略，当uk(i)=uk1(i)时，即结束。其步骤为： 选一无回路的初始策略u0(i) ，i=1，2，N1,表 示

9、在此策略下i点应到达的下一点。 由策略uk(i)，求指标值函数fk(i)。 fk(i)= i=1，2，N1；k=0，1，2 fk(N)=0 由fk(i)，求策略uk+1(i)，令 uk+1(i)=,2 不定期阶段决策问题的求解函数迭代与策略迭代 （7）,返回，反复迭代，直到uk (i)= uk1(i)为止。此时，uk (i)， fk1(i)即为最优策略及最优目标值。 用该法计算例3-9如下： 1）设初始无回路策略u0(i)为： u0(1)=5，u0(2)=4，u0(3)=5，u0(4)=3 2)由u0(i)计算f0(i) f0(i)= ，f0(5)=0 应先算f0(1)和f0(3) f0(1)

10、= =c1，5+f0(5)=2 f0(3)=c3，5+f0(5)=5 f0(4)=c4，3+f0(3)=1+5=6 f0(2)=c2，4+f0(4)=5+6=11,2 不定期阶段决策问题的求解函数迭代与策略迭代 （8）,3)由f0(i)求出u1(i)，即： u1(i)= (令u(i)=j) j=1，2，N1 当i=1，则： u1(1) =arg c11+f0(1)，c12+f0(2)，c13+f0(3)，c14+f0(4)，c15+f0(5) =arg 0+2，6+11，5+5，2+6，2+0 =arg2=5 同理可求得： u1(2)=3，u1(3)=5，u1(4)=5,2 不定期阶段决策问题的求解函数迭代与策略迭代 （9）,即：u1(i)=5，3，5，5 然后，以这些策略求出f1(i