运筹学动态规划

第八章动态规划多阶段决策过程：是指这样一类决策过程，它可以按时间分为若干阶段（称为时段），每一个阶段都需要做出决策，以便在过程的最终阶段得到最优结局。动态规划的一个重要特点是利用所谓的“最优化原理”，将问题用函数方程来表示（即递推方程），然后利用方程递推地进行计算、求解。运筹学动态规划一、最短路线问题最短路线问题：是指给定始点和终点，并且已知由始点到终点的各种可能的途径，需要找出由始点到终点的最短路线。这里的最短路线可以是通常意义下的距离，也可以是运输的时间或运输费用等等。运筹学动态规划例由A到D地要铺设一条煤气管道。其中须经过两级中间站，第一级中间站分别为B1和B2，第二级中间站分别为C1、C2、C3。两站之间有连线的就表示可铺设管道，没有连线的就表示不能铺设管道。连线中间的数字表示两点间铺设管道的长度，试确定一条由A点到D点的铺设管道的最短路线。AB2B1C3C2C1D21233134341运筹学动态规划符号和概念AB2B1C3C2C1D21233134341n：表示由当前的状态到终点之间的阶段数。如由A点到D点n=3；由B2到D点n=2等等。n=3n=2n=1运筹学动态规划符号和概念AB2B1C3C2C1D21233134341s：表示当前所处的位置，称为状态变量。如s可以是A、B1、B2、C1、C2等等。运筹学动态规划符号和概念AB2B1C3C2C1D21233134341Xn(s)：称为决策变量，它表示由阶段数为n的某个状态s演变到下一个阶段的某个状态，决策者做出的一种选择。如，X2(B1)表示已处于B1状态，还有2个阶段就到达D点了，此时决策者可选择的地点；X2(B1)可取C1,C2或C3。运筹学动态规划符号和概念AB2B1C3C2C1D21233134341fn(s)：表示由阶段数为n的某个状态s至终点的最短距离。例如，f2(B1)表示由阶段数为2的状态B1沿最优路线到达终点的距离，即B1到D点的最短距离。显然本例就是要求f3(A)及f3(A)所确定的最短路线。运筹学动态规划符号和概念AB2B1C3C2C1D21233134341d(s，Xn(s))：表示当前处于状态s时，选取决策变量Xn(s)后，由点s到点Xn(s)的距离。例如，d(B1，C3)=1，d(C2，D)=3运筹学动态规划分析要求出f3(A)的值及相应的策略从起点A开始分析AB2B1C3C2C1D21233134341运筹学动态规划当处于状态A时，

有几种可供选择的路线

AB2B1C3C2C1D21233134341运筹学动态规划当处于状态A时，

有两种可供选择的路线①A→B1：表明由A点所选择的下一点是B1由B1状态到终点D的最短距离为f2(B1)∴若选此条路线，则由A出发到达终点的最短距离可表示为

d(A,B1)+f2(B1)②A→B2：表明由A点所选择的下一点是B2由B2状态到终点D的最短距离为f2(B2)∴若选此条路线，则由A出发到达终点的最短距离可表示为

d(A,B2)+f2(B2)运筹学动态规划综合考虑两种情况可知，由状态A出发，到终点D的最优路线应是上述两种最短距离中的最小值，即可见，要计算f3(A)就得先计算f2(B1)和f2(B2)。运筹学动态规划由B1、B2点出发

分别有几种可供选择的路线？AB2B1C3C2C1D21233134341运筹学动态规划由B1点出发

有三种可供选择的路线①B1→C1最短距离为d(B1,C1)+f1(C1)②B1→C2最短距离为d(B1,C2)+f1(C2)③B1→C3最短距离为d(B1,C3)+f1(C3)运筹学动态规划综合考虑三种情况可知，由状态B1出发，到终点D的最优路线应是上述三种最短距离中的最小值，即可见，要计算f2(B1)就得先计算和f1(C1)、f1(C2)、f1(C3)。运筹学动态规划由B2点出发

有三种可供选择的路线①B2→C1最短距离为d(B2,C1)+f1(C1)②B2→C2最短距离为d(B2,C2)+f1(C2)③B2→C3最短距离为d(B2,C3)+f1(C3)运筹学动态规划综合考虑三种情况可知，由状态B2出发，到终点D的最优路线应是上述三种最短距离中的最小值，即可见，要计算f2(B2)就得先计算和f1(C1)、f1(C2)、f1(C3)。运筹学动态规划由于由状态C1、C2、C3出发到达终点D只需经过一个阶段，所以运筹学动态规划由以上分析可以看出，计算f3(A)的过程实际是一个倒推的过程，即由最后的阶段向前逐级进行计算。AB2B1C3C2C1D21233134341运筹学动态规划当n=1时运筹学动态规划图示AB2B1C3C2C1D21233134341运筹学动态规划当n=2时运筹学动态规划图示AB2B1C3C2C1D21233134341运筹学动态规划当n=3时运筹学动态规划图示AB2B1C3C2C1D21233134341所以，铺设管道的最短路线应是A→B1→C1→D。运筹学动态规划总结对于最短路线问题，一般地有如下的递推关系式：

这个递推公式是根据最优化原理得到的运筹学动态规划最优化原理一个过程的最优策略具有这样的性质，即无论其初始状态和初始决策如何，其今后诸决策对第一个决策所形成的状态作为初始状态和过程而言，必须构成最优策略。运筹学动态规划二、动态规划的应用运筹学动态规划1、“背包”问题/最优装载问题假设有一个徒步旅行者，它所能承受的旅行背包的总重量式A公斤，今有n种旅行物品供它选择装入背包中，已知，aj：第j种物品的单位重量（公斤）cj：第j种物品的单位使用价值（表明给该旅行者所带来的好处的一种数量指标）我们的问题是：如何确定这n种物品的数量x1、x2、…、xn，使得该旅行者的背包重量不超过A公斤，而且对旅行者来说总的使用价值最大？运筹学动态规划例假设有以下“背包”问题（总重量不超过5）物品编号123单位重量aj325每件使用价值量cj8512物品件数xjx1x2x3运筹学动态规划数学模型运筹学动态规划思路分析给待装物品编号：1、2、……、n分n步装载物品。为与阶段数同一，假设从编号为n的物品开始倒序装载。即先装第n号物品，再装n-1号物品，……，最后装1号物品。如本例，先装3号物品，再装2号物品，最后装1号物品。运筹学动态规划思路分析当装n号物品时，若决定装xn件，

xn

应满足以下条件（xn为决策变量、A为总重量限制）运筹学动态规划递推公式n种物品的最大价值量=

第n种物品的价值量+剩余n-1种物品的最大价值量即：运筹学动态规划状态变量的确定“背包”只有一个约束条件：重量限制。装载阶段不同，“背包”剩余的重量限制会发生变化。因此可确定“重量限制”为状态变量。公式可写成（n≥2时）运筹学动态规划当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≤xk≤x显然，我们的目标是求fn(A)运筹学动态规划分析当n=1时，f1(x)表示将数量为x的资金分配给一个项目的最大利润，因为只有一个项目，所以f1(x)=g1(x)当n=k≥2时，gk(xk)表示分配给第k个项目资金数为xk时的利润值；(x-xk)表示分配给前k个项目资金数为x，则分配给前k-1个项目的资金数为x-xk；fk-1(x-xk)表示以数量为x-xk的资金分配给k-1个项目所得到的最大利润值。运筹学动态规划例：股东投资30万元给三个工厂进行工厂扩建，每个工厂扩建后的利润与投资额的大小有关，投资后的利润值如下表：问：应如何分配这30万元使得这四个工厂扩建后总利润最大？

投资x利润0102030g1(x)0205065g2(x)0204050g3(x)0256075运筹学动态规划解∴要计算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)：生产Ⅰ型产品的回收率（0≤r1≤1）；r2(a)：生产Ⅱ型产品的回收率（0≤r2≤1）我们的目标是，对于总数为A的原料进行n个阶段生产，每个阶段应如何分配原料用于生产Ⅰ型产品及Ⅱ型产品，使得经过n个阶段生产之后总收益最大？运筹学动态规划分析由于问题本身就是多阶段的，所以可以用动态规划方法求解，令：fk(a)：初始原料数量为a，进行k个阶段的生产，采取最优分配策略所获得的最大收益；x：进行k个阶段的生产时，在生产的第一个阶段用于生产Ⅰ型产品的原料数量（0≤x≤a）。在进行某阶段生产时，当前阶段的收益为运筹学动态规划分析该阶段生产之后，总的回收原料的数量为它是在以后将要进行的k-1个阶段生产的状态变量的值，这些原料用于k-1个阶段生产，采取最优分配策略所获得的最大收益为运筹学动态规划分析根据动态规划的最优化原理，当2≤k≤n时，有当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为