《运筹学》教学课件 第5章 动态规划.ppt

运 筹 帷 幄 之 中;综 述 ;综 述 ;§5.1 多阶段决策问题 §5.2 最优化原理 §5.3 确定性的定期多阶段决策问题 §5.4 确定性的不定期多阶段决策问题 ;§5.1 多阶段决策问题;例1、最短线路问题 最短路问题就是从某地出发，途经假设干中间点最后到达目的地，要求找出路程或费用最小的路线。一般的最短路问题将在下一章讨论，这里只讨论分层的最短路问题。下面的管道设计问题(例5.1.1)就是其中之一。;从A点到E点要铺设一条天然气管道， 中间必须经过三个中间站， 第一站可在B1、B2、B3中选择， 第二站可在C1、C2、C3中选择， 第三站可在D1、D2、D3中选择， 要求选择一条由A 到E的铺管路线，使总长度最短。 其中两点连线上的数字表示两点间管线的长度。;从A点到E点铺设管道，可以按其地理特点自然地分成四个阶段：〔如以下图所示〕 从A到B是第一阶段，从B到C是第二阶段， 从C到D是第三阶段，从D到E是第四阶段，;在阶段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 多阶段资源分配问题 ;例2 多阶段资源分配问题-续(1) ; 因此，我们的问题就变成：求y,y1,y2,…,yn-1，以使g(y)+h(x-y)+ g(y1)+h(x1-y1)+ …+g(yn-1)+h(xn-1-yn-1) 到达最大，且满足条件 x1=ay+b(x-y) x2=ay1+b(x1-y1) … … … xn-1=ayn-2+b(xn-2-yn-2) yi与xi均非负,i=1,2, …,n-1 ;例3 生产和库存问题; 假设这个工厂根据需要可以日夜两班生产或只是日班生产，当开足日班时，每一个生产周期能生产商品15个单位，每生产一个单位商品的本钱为100元。当开足夜班时，每一生产周期能生产的商品也是15个，但是由于增加了辅助性生产设备和生产辅助费用，每生产一单位商品的本钱为120元。由于生产能力的限制，可以在需求淡季多生产一些商品储存起来以备需求旺季使用，但存储商品是需要存储费用的，假设每单位商品存储一周期需要16元，开始时存储为零，年终也不存储商品备下年使用，问应该如何作生产和存储方案，才能使总的生产和存储费用最小？; 设第i个周期的生产量为xi，周期末的存储量为ui，那 么这个问题用式子写出来就是：求x1,x2,…,x6，满足条件： x1=5+u1， x2+u1=5+u2， x3+u2=10+u3 x4+u3=30+u4 ， x5+u4=50+u5， x6+u5=8 0 xi 30, 0 uj, i=1,2,…,6; j=1,2, …,5 使S= = 为最小，其中 ; ;例5 多阶段决策问题 ;多阶段决策问题的根本要素：阶段数、状态变量、决策变量、状态转移方程和目标函数。; 最优化原理;最优化原理的性质：对于多阶段决策问题的最优策略，如果用它的前步策略产生的情况〔加上原有的约束条件〕来形成一个前步问题，那么所给最优策略的前阶段的策略构成这前步问题的一个最优策略。 ;动态规划的最优化定理的数学表述; 下面以以下图所示的网络中确定A—E最短路(例1)为例，来说明应用动态规划最优化定理解决问题的步骤。; 由最优化定理可知，一条 A-