运筹学动态规划

第八章动态规划•多阶段决策过程：是指这样一类决策过程，它可以按时间分为若干阶段（称为时段），每一个阶段都需要做出决策，以便在过程的最终阶段得到最优结局。•动态规划的一个重要特点是利用所谓的“最优化原理”，将问题用函数方程来表示（即递推方程），然后利用方程递推地进行计算、求解。一、最短路线问题•最短路线问题：是指给定始点和终点，并且已知由始点到终点的各种可能的途径，需要找出由始点到终点的最短路线。•这里的最短路线可以是通常意义下的距离，也可以是运输的时间或运输费用等等。例•由A到D地要铺设一条煤气管道。其中须经过两级中间站，第一级中间站分别为B1和B2，第二级中间站分别为C1、C2、C3。两站之间有连线的就表示可铺设管道，没有连线的就表示不能铺设管道。连线中间的数字表示两点间铺设管道的长度，试确定一条由A点到D点的铺设管道的最短路线。AB2B1C3C2C1D21233134341符号和概念AB2B1C3C2C1D21233134341•n：表示由当前的状态到终点之间的阶段数。–如由A点到D点n=3；由B2到D点n=2等等。n=3n=2n=1符号和概念AB2B1C3C2C1D21233134341•s：表示当前所处的位置，称为状态变量。–如s可以是A、B1、B2、C1、C2等等。符号和概念AB2B1C3C2C1D21233134341•Xn(s)：称为决策变量，它表示由阶段数为n的某个状态s演变到下一个阶段的某个状态，决策者做出的一种选择。–如，X2(B1)表示已处于B1状态，还有2个阶段就到达D点了，此时决策者可选择的地点；X2(B1)可取C1,C2或C3。符号和概念AB2B1C3C2C1D21233134341•fn(s)：表示由阶段数为n的某个状态s至终点的最短距离。–例如，f2(B1)表示由阶段数为2的状态B1沿最优路线到达终点的距离，即B1到D点的最短距离。–显然本例就是要求f3(A)及f3(A)所确定的最短路线。符号和概念AB2B1C3C2C1D21233134341•d(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)。2221213,,minBfBAdBfBAdAf由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)。31312121111112,,,minCfCBdCfCBdCfCBdBf由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)。31322122111222,,,minCfCBdCfCBdCfCBdBf•由于由状态C1、C2、C3出发到达终点D只需经过一个阶段，所以DCdCfDCdCfDCdCf,,,331221111•由以上分析可以看出，计算f3(A)的过程实际是一个倒推的过程，即由最后的阶段向前逐级进行计算。AB2B1C3C2C1D21233134341当n=1时DCDCdCfDCDCdCfDCDCdCf3331222111114,3,1,相应的最短路线为相应的最短路线为相应的最短路线为图示AB2B1C3C2C1D21233134341当n=2时DCBCfCBdCfCBdCfCBdBf11313121211111124564413313,,,min相应的最短路线为DCBCfCBdCfCBdCfCBdBf12313221221112223563413312,,,min相应的最短路线为图示AB2B1C3C2C1D21233134341当n=3时DCBABfBAdBfBAdAf1122212136763442min,,min相应的最短路线为图示AB2B1C3C2C1D21233134341•所以，铺设管道的最短路线应是A→B1→C1→D。总结•对于最短路线问题，一般地有如下的递推关系式：•这个递推公式是根据最优化原理得到的为终点状态其中：E,2,min11Esdsfnsxfsxsdsfnnnn最优化原理•一个过程的最优策略具有这样的性质，即无论其初始状态和初始决策如何，其今后诸决策对第一个决策所形成的状态作为初始状态和过程而言，必须构成最优策略。二、动态规划的应用1、“背包”问题/最优装载问题•假设有一个徒步旅行者，它所能承受的旅行背包的总重量式A公斤，今有n种旅行物品供它选择装入背包中，已知，•aj：第j种物品的单位重量（公斤）•cj：第j种物品的单位使用价值（表明给该旅行者所带来的好处的一种数量指标）•我们的问题是：如何确定这n种物品的数量x1、x2、…、xn，使得该旅行者的背包重量不超过A公斤，而且对旅行者来说总的使用价值最大？例•假设有以下“背包”问题（总重量不超过5）物品编号123单位重量aj325每件使用价值量cj8512物品件数xjx1x2x3数学模型3,2,105523..1258max321321jxxxxtsxxxfj且全为整数，思路分析•给待装物品编号：1、2、……、n•分n步装载物品。–为与阶段数同一，假设从编号为n的物品开始倒序装载。即先装第n号物品，再装n-1号物品，……，最后装1号物品。–如本例，先装3号物品，再装2号物品，最后装1号物品。思路分析•当装n号物品时，若决定装xn件，xn应满足以下条件（xn为决策变量、A为总重量限制）nnnnnA,0,Aaxxxa整数递推公式•n种物品的最大价值量=第n种物品的价值量+剩余n-1种物品的最大价值量即：'ymax1nnnnfxcyf状态变量的确定•“背包”只有一个约束条件：重量限制。•装载阶段不同，“背包”剩余的重量限制会发生变化。•因此可确定“重量限制”为状态变量。•公式可写成（n≥2时）nn1nnn,aAxnAmaxAnnxafxcf且为整数•当n=1时1111,01111maxaycxcyfxyxa为整数求解例题•用递推关系式计算：我们的问题是求f3(5)012,5max5512max5512max5max5221,0323,55032333233,503333333ffxfxxfxxafxcfxxxxax为整数为整数可见要计算f3(5),要先计算f2(5)、f2(0)110,35,5max255max255max5max51112,1,0213,25021222122,502222222fffxfxxfxxafxcfxxxxax为整数为整数002f•可见，要计算f2(5)、f2(0)，•要先计算f1(5)、f1(3)、f1(1)、f1(0)1583585511111axacf1383383311111axacf0103181111111axacf0003080011111axacf•将f1值代入f2中，得到)0,0(000)1,1(,1310138max010858max52112212xxffxx，，，，f•将f2值代入f3中，得到•∴“背包”问题的最优解为X1=1,X2=1,X3=0,最优值为13。0,1,113012,13max53213xxxf2、投资分配问题/资源分配问题•资源分配问题：设有某种资源（如电力、煤炭等），可用于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个项目所得到的最大利润值。kkkkxxkxxfxgxfk10max例：•股东投资30万元给三个工厂进行工厂扩建，每个工厂扩建后的利润与投资额的大小有关，投资后的利润值如下表：问：应如何分配这30万元使得这四个工厂扩建后总利润最大？投资x利润0102030g1(x)0205065g2(x)0204050g3(x)0256075解03010202010300max30max302323232330,20,10