第五章 动态规划 山大刁在筠 运筹学讲义

第五章动态规划教学重点：用递推的方法求解最短路线问题，有限资源分配问题，旅行售货员问题，最优线路问题等。教学难点：有限资源分配问题。教学课时：10学时主要教学环节的组织：将最优化原理应用于几种典型多阶段问题当中，结合实例给学生以具体的认识，通过习题加以巩固。第一节多阶段决策问题教学重点：通过具体实例得多阶段决策问题的模型，讨论多阶段决策问题的解决方法。教学难点：多阶段决策问题的解法。教学课时：1学时主要教学环节的组织：给出具体的多阶段决策问题，讨论多阶段决策问题的算法—递推法。实例最短路问题---例1最短路问题就是从某地出发，途经若干中间点最后到达目的地，要求找出路程或费用最小的路线。一般的最短路问题将在下一章讨论，这里只讨论分层的最短路问题。下面的管道设计问题(例5.1.1)就是其中之一。5542634656122233234ED3D1D2C1C3C2AB3B2B1从A点到E点要铺设一条煤气管道，中间必须经过三个中间站，第一站可在B1、B2、B3中选择，第二站可在C1、C2、C3中选择，第三站可在D1、D2、D3中选择，要求选择一条由A到E的铺管路线，使总长度最短。其中两点连线上的数字表示两点间管线的长度。从A点到E点铺设管道，可以按其地理特点自然地分成四个阶段：（如下图所示）从A到B是第一阶段，从B到C是第二阶段，从C到D是第三阶段，从D到E是第四阶段。AABCDE阶段1阶段2阶段3阶段4在阶段2，从B3点出发，只有C1、C3两种可选择的点，如选C1,则C1就是阶段2在B3点的决策结果；C1点既是阶段2铺设管道的终点，又是阶段3铺设管道的起点；同样的理由，可以递推得其余阶段的铺设路线，如阶段3在C1点的决策是D1，阶段4在D1点的决策只有E点；由于到E点是整个铺设管道的终点，至此，决策过程完成，铺设一条A点到E点的管道是由四个阶段的管道组成的，如A---B3---C1---D1---E，它也称为一个策略。可以看出，各个阶段的决策不同，铺设的管道也不同，并且当某个阶段的始点给定后，它直接影响着后面各阶段的行进路线和管道的长短，而后面各阶段的路线的选取不受这点以前各阶段路线的影响。因此，最短路线问题可简化为四个阶段决策问题，使由这四个阶段决策组成决策序列，也称为策略所决定的一条路线的总长度最短。例2资源分配问题（略）例3生产-库存问题（略）一般多阶段决策问题有一个系统，可以分成若干个阶段，任意一个阶段，系统的状态可以用表示（可以是数量、向量、集合等）。在每一阶段的每一状态都有一个决策集合，在中选定一个决策，状态就转移到新的状态，并且得到效益。我们的目的就是在每一个阶段都在它的决策集合中选择一个决策，使所有阶段的总效益达到最大。我们称之为多阶段决策问题。多阶段决策问题的基本要素：阶段数、状态变量、决策变量、状态转移方程和目标函数。多阶段决策问题的分类阶段数：有限阶段决策问题和无限阶段决策问题；状态变量：连续多阶段决策问题和离散多有限阶段决策问题；阶段个数是否明确：定期多阶段决策问题和不定期多阶段决策问题；参数取值情况：确定多阶段决策问题和不确定多阶段决策问题。第二节最优化原理教学重点：最优化原理。教学难点：无。教学课时：1学时主要教学环节的组织：介绍最优化原理。动态规划最优化原理：一个过程的最优策略具有这样的性质，即无论其初始状态及其初始决策如何，其以后诸决策对以第一个决策所形成的状态作为初始状态而言，必须构成最优策略。动态规划原理还应该包括如下性质：对于多阶段决策的最优策略如果用它的前i步产生的情况来形成一个前i步问题，那么所给最优策略的前i阶段的策略构成这前i步问题的一个最优策略。用动态规划求解多阶段决策问题的一般步骤：第1步明确问题，找出阶段数第2步确定变量，找出状态变量和决策变量第3步找出状态转移方程第4步写出递推关系式第5步求解递推关系式第三节确定性的定期多阶段决策问题教学重点：旅行售货员问题，多阶段资源分配问题，可靠性问题。教学难点：多阶段资源分配问题。教学课时：4学时主要教学环节的组织：用具体的实例计算以上问题。1、旅行售货员问题旅行售货员问题是图论中一个著名问题，就是在网络上找一条从点出发，经过各一次最后返回的最短路线和最短路程。现把它看成一个多阶段决策问题。从出发，经过个阶段，每个阶段的决策是选择下一个点。如果用所在的位置来表示状态，那么状态与阶段数就不能完全决定决策集合了，因为走过的点不需要再走，所以决策集合与以前选的决策有关。用表示状态，是所处的点，是还没有经过的点集合。在状态的决策集合中，取决策，获得的效益是到的距离，转入下一个状态，现在用最优化原理来找递推公式。用表示从点出发，经过中的点各一次，最后回到点的最短路程，是一个顶点集合，是到的弧长，则例5.3.1对图5.3.1求从出发经过，，，又返回的最短路线和最短路径。解：可以用一个矩阵表示到的距离。表示从出发，经过各一次又回到的最短路程。则：同样，现在从最后一个阶段解起：2、多阶段资源分配问题下面讨论有限资源分配问题，它的递推公式是：一般情况下，，是很复杂的函数时，这个问题的解不容易找。当，为凸函数，且时，可以证明在每个阶段上的最优决策总是取其端点的值。引理5.3.1设是凸函数，则对任何固定的，是的凸函数。引理5.3.2设是的凸函数，则也是的凸函数。定理5.3.1设g(y)，g(y)是凸函数，且h(0)=g(0)=0，则n阶段资源分配问题的最优策略y在每个阶段总取0yx的短点的值，并且证明：因为，.由引理5.3.1知对固定的为凸函数，其极大值一定在或点上达到，所以，由引理5.3.2可知，是的凸函数，易证也是的凸函数，所以也是的凸函数，用归纳法可得：例5.3.2在有限资源分配问题中，而且，求第四节定性的不定期多阶段决策问题教学重点：最优线路问题，有限资源分配问题。教学难点：有限资源分配问题。教学课时：2学时主要教学环节的组