运筹学动态规划ppt课件.ppt
第八章 动态规划,多阶段决策过程：是指这样一类决策过程，它可以按时间分为若干阶段（称为时段），每一个阶段都需要做出决策，以便在过程的最终阶段得到最优结局。动态规划的一个重要特点是利用所谓的“最优化原理”，将问题用函数方程来表示（即递推方程），然后利用方程递推地进行计算、求解。,一、最短路线问题,最短路线问题：是指给定始点和终点，并且已知由始点到终点的各种可能的途径，需要找出由始点到终点的最短路线。这里的最短路线可以是通常意义下的距离，也可以是运输的时间或运输费用等等。,例,由A到D地要铺设一条煤气管道。其中须经过两级中间站，第一级中间站分别为B1和B2，第二级中间站分别为C1、C2、C3。两站之间有连线的就表示可铺设管道，没有连线的就表示不能铺设管道。连线中间的数字表示两点间铺设管道的长度，试确定一条由A点到D点的铺设管道的最短路线。,A,B2,B1,C3,C2,C1,D,2,1,2,3,3,1,3,4,3,4,1,符号和概念,A,B2,B1,C3,C2,C1,D,2,1,2,3,3,1,3,4,3,4,1,n：表示由当前的状态到终点之间的阶段数。如由A点到D点n=3；由B2到D点n=2等等。,n=3,n=2,n=1,符号和概念,A,B2,B1,C3,C2,C1,D,2,1,2,3,3,1,3,4,3,4,1,s：表示当前所处的位置，称为状态变量。如s可以是A、B1、B2、C1、C2等等。,符号和概念,A,B2,B1,C3,C2,C1,D,2,1,2,3,3,1,3,4,3,4,1,Xn(s)：称为决策变量，它表示由阶段数为n的某个状态s演变到下一个阶段的某个状态，决策者做出的一种选择。如，X2(B1)表示已处于B1状态，还有2个阶段就到达D点了，此时决策者可选择的地点；X2(B1)可取C1,C2或C3。,符号和概念,A,B2,B1,C3,C2,C1,D,2,1,2,3,3,1,3,4,3,4,1,fn(s)：表示由阶段数为n的某个状态s至终点的最短距离。例如，f2(B1)表示由阶段数为2的状态B1沿最优路线到达终点的距离，即B1到D点的最短距离。显然本例就是要求f3(A)及f3(A)所确定的最短路线。,符号和概念,A,B2,B1,C3,C2,C1,D,2,1,2,3,3,1,3,4,3,4,1,d(s，Xn(s)：表示当前处于状态s时，选取决策变量Xn(s)后，由点s到点Xn(s)的距离。例如，d(B1，C3)=1，d(C2，D)=3,分析,要求出f3(A)的值及相应的策略从起点A开始分析,A,B2,B1,C3,C2,C1,D,2,1,2,3,3,1,3,4,3,4,1,当处于状态A时，有几种可供选择的路线,A,B2,B1,C3,C2,C1,D,2,1,2,3,3,1,3,4,3,4,1,当处于状态A时，有两种可供选择的路线,AB1：表明由A点所选择的下一点是B1由B1状态到终点D的最短距离为f2(B1)若选此条路线，则由A出发到达终点的最短距离可表示为 d(A,B1)+ f2(B1)AB2：表明由A点所选择的下一点是B2由B2状态到终点D的最短距离为f2(B2)若选此条路线，则由A出发到达终点的最短距离可表示为 d(A,B2)+ f2(B2),综合考虑两种情况可知，由状态A出发，到终点D的最优路线应是上述两种最短距离中的最小值，即 可见，要计算f3(A)就得先计算f2(B1)和f2(B2)。,由B1、B2点出发分别有几种可供选择的路线？,A,B2,B1,C3,C2,C1,D,2,1,2,3,3,1,3,4,3,4,1,由B1点出发有三种可供选择的路线,B1C1最短距离为 d(B1,C1)+ f1(C1)B1C2最短距离为 d(B1,C2)+ f1(C2)B1C3最短距离为 d(B1,C3)+ f1(C3),综合考虑三种情况可知，由状态B1出发，到终点D的最优路线应是上述三种最短距离中的最小值，即可见，要计算f2(B1)就得先计算和f1(C1)、f1(C2)、f1(C3)。,由B2点出发有三种可供选择的路线,B2C1最短距离为 d(B2,C1)+ f1(C1)B2C2最短距离为 d(B2,C2)+ f1(C2)B2C3最短距离为 d(B2,C3)+ f1(C3),综合考虑三种情况可知，由状态B2出发，到终点D的最优路线应是上述三种最短距离中的最小值，即可见，要计算f2(B2)就得先计算和f1(C1)、f1(C2)、f1(C3)。,由于由状态C1、C2、C3出发到达终点D只需经过一个阶段，所以,由以上分析可以看出，计算f3(A)的过程实际是一个倒推的过程，即由最后的阶段向前逐级进行计算。,A,B2,B1,C3,C2,C1,D,2,1,2,3,3,1,3,4,3,4,1,当n=1时,图示,A,B2,B1,C3,C2,C1,D,2,1,2,3,3,1,3,4,3,4,1,当n=2时,图示,A,B2,B1,C3,C2,C1,D,2,1,2,3,3,1,3,4,3,4,1,当n=3时,图示,A,B2,B1,C3,C2,C1,D,2,1,2,3,3,1,3,4,3,4,1,所以，铺设管道的最短路线应是AB1C1D。,总结,对于最短路线问题，一般地有如下的递推关系式： 这个递推公式是根据最优化原理得到的,最优化原理,一个过程的最优策略具有这样的性质，即无论其初始状态和初始决策如何，其今后诸决策对第一个决策所形成的状态作为初始状态和过程而言，必须构成最优策略。,二、动态规划的应用,1、“背包”问题/最优装载问题,假设有一个徒步旅行者，它所能承受的旅行背包的总重量式A公斤，今有n种旅行物品供它选择装入背包中，已知，aj：第j种物品的单位重量（公斤）cj：第j种物品的单位使用价值（表明给该旅行者所带来的好处的一种数量指标）我们的问题是：如何确定这n种物品的数量x1、x2、xn，使得该旅行者的背包重量不超过A公斤，而且对旅行者来说总的使用价值最大？,例,假设有以下“背包”问题 （总重量不超过5）,数学模型,思路分析,给待装物品编号：1、2、n分n步装载物品。为与阶段数同一，假设从编号为n的物品开始倒序装载。即先装第n号物品，再装n-1号物品，最后装1号物品。如本例，先装3号物品，再装2号物品，最后装1号物品。,思路分析,当装n号物品时，若决定装xn件， xn 应满足以下条件（ xn为决策变量、A为总重量限制）,递推公式,n种物品的最大价值量= 第n种物品的价值量 + 剩余n-1种物品的最大价值量即：,状态变量的确定,“背包”只有一个约束条件：重量限制。装载阶段不同，“背包”剩余的重量限制会发生变化。因此可确定“重量限制”为状态变量。公式可写成 （n2时）,当n=1时,求解例题,用递推关系式计算：我们的问题是求f3(5),可见要计算f3(5),要先计算f2(5)、f2(0),可见，要计算f2(5)、f2(0) ，要先计算f1(5)、f1(3)、 f1(1)、f1(0),将f1值代入f2中，得到,将f2值代入f3中，得到“背包”问题的最优解为 X1=1, X2=1, X3=0, 最优值为13。,2、投资分配问题/资源分配问题,资源分配问题：设有某种资源（如电力、煤炭等），可用于n种生产，假设资源的总数量为A，用于第j种生产的资源数量为xj时，可以得到收益gj(xj),j=1,2,n，问：对资源A应如何进行分配，使得总的收益最大？投资分配问题：设有总数为A的资金，要分配给n个项目（或工厂、部门等），用于扩大再生产（或其他建设），假设xj：表示分配给第j个项目的资金数；gj(xj):表示第j个项目得到数量为xj的资金后，所提供的利润值；问：如何确定各项目的资金数，使得总的投资利润最大？,分析,不妨假设，分n个阶段考虑分配给n个项目的资金，因为每个阶段的决策不仅影响到该项目得到的资金多少，同时也会影响到今后其他项目所可能得到的资金数（资金总数A已确定），所以可以用动态规划方法来求解，令：fk(x):数量为x的资金分配给前k个项目所得到的最大利润值；xk：分配给第k个项目的资金数，满足条件：0 xkx显然，我们的目标是求fn(A),分析,当n=1时，f1(x)表示将数量为x的资金分配给一个项目的最大利润，因为只有一个项目，所以f1(x)=g1(x)当n=k2时，gk(xk)表示分配给第k个项目资金数为xk时的利润值；(x-xk)表示分配给前k个项目资金数为x，则分配给前k-1个项目的资金数为x-xk；fk-1(x-xk)表示以数量为x-xk的资金分配给k-1个项目所得到的最大利润值。,例：,股东投资30万元给三个工厂进行工厂扩建，每个工厂扩建后的利润与投资额的大小有关，投资后的利润值如下表：问：应如何分配这30万元使得这四个工厂扩建后总利润最大？,解,要计算f3(30)， 要先计算f2(30)，f2(20)，f2(10)，f2(0),要计算f2(30)，f2(20)，f2(10)，f2(0)， 要先计算f1(30)，f1(20)，f1(10)，f1(0),将以上结果代入前面各式,得最优解为 最优值为80,3、多阶段生产安排问题 /多阶段配置问题,设有某种原料，其数量为A吨，用于生产两种不同类型的产品，记为类型、类型，已知投入该原料进行生产后，还可以回收部分原料用于下一阶段的再生产，假设g1(a)：投入数量为a的原料，生产型产品的收益值；g2(a) ：投入数量为a的原料，生产型产品的收益值； r1(a)：生产型产品的回收率（0r11）；r2(a)：生产型产品的回收率（0r21）我们的目标是，对于总数为A的原料进行n个阶段生产，每个阶段应如何分配原料用于生产型产品及型产品，使得经过n个阶段生产之后总收益最大？,分析,由于问题本身就是多阶段的，所以可以用动态规划方法求解，令：fk(a)：初始原料数量为a，进行k个阶段的生产，采取最优分配策略所获得的最大收益；x：进行k个阶段的生产时，在生产的第一个阶段用于生产型产品的原料数量（0 xa）。在进行某阶段生产时，当前阶段的收益为,分析,该阶段生产之后，总的回收原料的数量为 它是在以后将要进行的k-1个阶段生产的状态变量的值，这些原料用于k-1个阶段生产，采取最优分配策略所获得的最大收益为,分析,根据动态规划的最优化原理，当2kn时，有 当k=1时（即只进行一个阶段生产），有 显然，我们的目标是计算fn(A),例,在多阶段生产安排问题中，设收益函数分别为回收率分别为生产阶段数为n=3，现有原料为A=100吨。,解：,先整理一些算式,当k=1时,对于一个阶段生产问题，最大收益为0.6a，最佳生产安排是：全部原料用于生产型产品；,当k=2时,可知，当进行两个阶段生产时，最大收益为0.74a最佳生产安排是：全部原料用于生产型产品；,当k=3时,可知，当进行三个阶段生产时，最大收益为0.796a最佳生产安排是：全部原料用于生产型产品；,将已知数据代入上式得,即投入100吨原料进行三阶段生产时，可获得的最大收益为79.6万元。此时，最佳生产安排是：第一阶段（k=3）全部原料用于生产型产品；第二阶段（k=2）全部原料用于生产型产品；第三阶段（k=1）全部原料用于生产型产品；,第一阶段：把全部原料100吨投入型产品生产 收益=0.5*100=50万元，回收=0.4*100=40吨第二阶段：把全部原料40吨投入型产品生产 收益=0.5*40=20万元，回收=0.4*40=16吨第三阶段：把全部原料16吨投入型产品生产 收益=0.6*16=9.6万元，回收=0.1*16=1.6吨 三个阶段总收益为：50+20+9.6=79.6万元,每个阶段生产安排,4、多阶段存储问题,把一年（或一段时间）分为n个周期（也称阶段），已知仓库的最大容量为w，第i个周期的需求量为ri，单位产品的购进费为ai，单位产品的周期保管费为bi。问：各个周期应订多少货，才能够既满足需求，又使n个周期总存储费最小。假设：1、各个周期的订货在该周期末才能存储，而各周期的需求应在该周期初给予满足，而且不允许缺货。2、第一个周期的初始存储量z1为已知，第n个周期的期末存储量zn+1也为已知。3、期初存储量不低于本期需求量。,例,某个居民区每年四个季度对煤的需求量、该区煤场各个季度购进煤的单价和存储煤的保管费用都列于下表。已知煤场的最大容量为9百吨，每年年底都要求有8百吨煤的存储，现在问，煤场应如何安排各个季度的进煤量，才最合理。假设：1、各个周期的订货在该周期末才能存储，而各周期的需求应在该周期初给予满足，而且不允许缺货。2、第一个周期的初始存储量z1为已知，第n个周期的期末存储量zn+1也为已知。3、期初存储量不低于本期需求量。,分析,存储问题的周期数n为一定数，故定购费在一年内也是一个常数；又因为不允许短缺，所以可以不考虑定购费与短缺费。这样，总存储费就等于购进费与保管费之和。设第i个周期的初始存储量为zi，订货量为qi（i1,2,n），由假设知，有如下关系式成立：,分析,令fk(z)=初始存储量为z，还有k个周期，采取最优策略时的最低总存储费。显然，我们的目标是求fn(z1)。如果设第i个周期的初始存储量为z，进货量为q，由公式（1）（2）可知,分析,再结合公式（3）知令得当i=n时，有 即,分析,由“最优化原理”可得递推公式：,解,这是一个四阶段的存储问题，且z1=z5=8，w=9，由递推公式，得其中,由表可知 从而知,这样，得到煤场每年各季度的购煤量和季初存储量的最优安排如下表，全年总存储费为80400元。,思考题与练习题,
