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

《运筹学-动态规划(二)(名校讲义).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、数转移，有明显的划分，简图示于 图3-11。XIX(2)XTX(1)图3-11明显阶段转移[例3-6]敷设管道问题（设无回路）已知从A到M的管道铺设的可行路线及其费用于图3-12。求从A到M的最低费用铺设线路。BEHKMACFILJGD32334422422433432223322图3-12管道铺设方案图§1具有隐含阶段和无限阶段问题的算法（3）[解]本问题无明显阶段划分，可令：·每个节点表示“状态”。·节点链（管道）的选择为决策变量。其求解步骤如下：(i)I(M)=0（终端条件）(ii)从M上推，找直接联结的状态点，共有3个点：J、K、L。它们到达终

3、点的最小费用为：I(J)=min{2+I(K)，4+I(M)，2+I(L)}尚不确定I(K)=min{4+I(M)}=4I(L)=min{3+I(M)}=3于是：I(J)=min{2+4，4，2+3}=4§1具有隐含阶段和无限阶段问题的算法（4）(iii)再从J、K、L向前推I(H)=min{3+I(K)，3+I(J)}=min{3+4，3+4}=7I(I)=min{2+I(L)}=min{2+3}=5全部计算结果示如图3-13中。B11A14C13D11F10E9G7I5L3J4MK4H7图3-13[例3-6]结果示意图图中数字表示从该点到终点M铺设

4、管道的最低费用。例如，A至M的最低费用为14，其路线为：A→B→E→G→I→L→M。§1具有隐含阶段和无限阶段问题的算法（5）[例3-7]挑硬币问题N个硬币，有一枚较重，其它等重。现要求用等臂天平来选出重币。希确定出一定能找出这枚重币的最少称重次数。[解]令：硬币数为状态变量xI(x)表示使用最优策略在批量为x个硬币中一定能找出重币中所需最少称量次数。u为决策变量，放在天平每边的硬币数。现分析每次u的最佳选择。显然，从x个硬币中选出2u个硬币分放天平2边，必有下述2种可能：1）天平平衡，说明重币在剩余的(x－2u)个硬币中。2）天平不平衡，说明重币在天

5、平重的一边的u个硬币中。§1具有隐含阶段和无限阶段问题的算法（6）因此，u的选择应符合下式：I(x)=1+{max[I(u)，I(x－2u)]}I(1)=0(1)[式中加1，是因为I(1)=0，而把x分成u及x－2u，且找出硬币所在区需秤一次]。式（1）表明，需从I(u)和I(x－2u)中选取最大者再取极小，故应选u使之I(u)尽量与I(x－2u)相等，即：u≈x－2uu≈x故应选u=或+1。§1具有隐含阶段和无限阶段问题的算法（7）根据此法，对任何N都可用递推公式求出。其公式为：3k－1＜x≤3kI(x)=k即：k为≥log3x的最小整数：x与I(

6、x)的对应见表3-8。§1具有隐含阶段和无限阶段问题的算法（8）xI(x)213142……92103……273……3kk表3-8x与I(x)对应表二、无限阶段过程（有明显阶段，但是阶段数无限）（略）§2不定期阶段决策问题的求解—函数迭代与策略迭代（1）[解]显然，该问题从几何图形上无明显阶段划分，路线中经过几点亦无限制，如果采用动态规划算法，必须加以处理。１234522753510.565图3-14本节不想从理论上推导这些方法，只准备结合例题介绍这些方法的步骤。[例3-9]已知5个地区（点）之间的距离示于图3-14中。求任一点到终点⑤的最短路线。§2不

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

8、1(i)，令每个点只许一步到达终点。即：f1(i)=ciNi=1，2，…，N－1f1(N)=0