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

第五章 动态规划
教学重点：用递推的方法求解最短路线问题，有限资源分配问题，旅行售货员问题，最优线路问题等。
教学难点：有限资源分配问题。
教学课时：10学时
主要教学环节的组织：将最优化原理应用于几种典型多阶段问题当中，结合实例给第五章 动态规划
教学重点：用递推的方法求解最短路线问题，有限资源分配问题，旅行售货员问题，最优线路问题等。
教学难点：有限资源分配问题。
教学课时：10学时
主要教学环节的组织：将最优化原理应用于几种典型多阶段问题当中，结合实例给学生以具体的认识，通过习题加以巩固。
第一节 多阶段决策问题
教学重点：通过具体实例得多阶段决策问题的模型，讨论多阶段决策问题的解决方法。
教学难点：多阶段决策问题的解法。
教学课时：1学时
主要教学环节的组织：给出具体的多阶段决策问题，讨论多阶段决策问题的算法—递推法。
实例
最短路问题---例1
最短路问题就是从某地出发，途经若干中间点最后到达目的地，要求找出路程或费用最小的路线。一般的最短路问题将在下一章讨论，这里只讨论分层的最短路问题。下面的管道设计问题()就是其中之一。
5
4
2
6
3
4
6
5
6
1
2
2
2
3
3
2
3
4
E
D3
D1
D2
C1
C3
C2
A
B3
B2
B1
从A点到E点要铺设一条煤气管道，中间必须经过三个中间站，第一站可在B1、B2、B3中选择，第二站可在C1、C2、C3中选择，第三站可在D1、D2、D3中选择，要求选择一条由A 到E的铺管路线，使总长度最短。其中两点连线上的数字表示两点间管线的长度。
从A点到E点铺设管道，可以按其地理特点自然地分成四个阶段：（如下图所示）
从A到B是第一阶段，从B到C是第二阶段，从C到D是第三阶段，从D到E是第四阶段。
A
B
C
D
E
阶段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 生产-库存问题（略）
一般多阶段决策问题
有一个系统，可以分成若干个阶段，任意一个阶段，系统的状态 可以用表示（可以是数量、向量、集合等）。在每一阶段的每一 状态都有一个决策集合，在中选定一个决策，状态就转移到新的状态，并且得到效益。我们的目的就是在每一个阶段都在它的决策集合中选择一个决策，使所有阶段的总效益达到最大。我们称