第五章动态规划125

《第五章动态规划125》由会员分享，可在线阅读，更多相关《第五章动态规划125（68页珍藏版）》请在金锄头文库上搜索。

1、第五章第五章 动态规划（动态规划（DP） 把决策问题按时间时间（即阶段）或空间空间（即层次）划分为若干相互联系的阶段或层次阶段或层次，对每一个阶段或层次都要作决策决策的问题，称为多阶段决策问题多阶段决策问题。1、多阶段决策问题：、多阶段决策问题： 2、动态规划（方法）、动态规划（方法）:解决多阶段决策多阶段决策问题的辅助方法。（美国数学家理查德 贝尔曼提出）可用于:最优路径问题最优路径问题、 资源分配问题资源分配问题、 生产计划与库存生产计划与库存、投资问题投资问题、装载问题装载问题、排序问题排序问题、及生产过程的最优控制生产过程的最优控制等。 3、动态规划模型分类、动态规划模型分类v 根据决

2、策过程的时间参数v根据决策过程的演变分为：离散性 连续性（时间的函数）分为： 确定性（这一阶段到下一阶段确定） 随机性（这一阶段到下一阶段确定）则有离散确定型、离散随机型、连续确定型、连续随机型本章主要研究离散确定型离散确定型。第一节第一节 多阶段决策问题的结构多阶段决策问题的结构一、问题的提出：一、问题的提出：销售策略问题销售策略问题建材商店购进某种屋面防水材料1000千克准备销售。根据市场情况分析，这批材料可以在4个月内销售完。由于每个月的市场需求不同，各月材料的零售价格也不同。经对市场预测，未来4个月的市场价格、没有销售的材料因资金积压和管理费均可折摊成每月的库存费用，如下表。问：该材料

3、店经理应该如何制定销销售售计计划划，才能使这批材料获取的销售利润最大销售利润最大？ 1月3月2月4月设第j月，库存量 ，销售量 ，销售利润材料售价及存储费用表月份1月份2月份3月份4月份售价（元/千克）3456存储费（元/千克）10.51.52则，其整个销售过程为：目标为： 2、生产与存贮问题、生产与存贮问题某工厂每月需供应市场一定数量的产品，并将所有余产品存入仓库。一般某月适当增加产量可降低生产成本，但超产部分存入仓库会增加库存费用。要求确定一个逐逐月月的的生生产产计计划划，在满足需求条件下，使一年的生产与存贮费用之和最小生产与存贮费用之和最小。（每个月为一个阶段，一年分为12个阶段逐次决策

4、决策） 3、投资决策问题、投资决策问题某公司有资金Q万元，在今后5年内考虑给A、B、C、D4个项目投资。这些项目投资的回收期限、回报率均不相同，问该公司应如何确定这些项目每年的投资额每年的投资额，使到第5年未拥有资金的本利总额本利总额最大。（5个阶段）4、设备更新问题、设备更新问题企业在使用设备时，都要考虑设备的更新问题，因为设备越陈旧所需的维修费用越多，但购买新设备则要一次性支出较大的费用。现某企业要决定一台设备未来8年的更新计划，已预测了第j年购买设备的价格为Kj ，设Gj 为设备经过j年后的残值,Cj为设备连续使用j-1年后在第j年的维修费（j=1,2,，8）问应在哪些年更新设备更新设备

5、可使总费用最小总费用最小?（8个阶段决策，是继续使用？还是购买新设备？） 5、多阶段决策问题的特点：、多阶段决策问题的特点： 多个决策阶段是顺序相连，组成一种序列决策系统序列决策系统； 对每个阶段都要进行决策， 且前一阶段决策对后一阶段的决策会产生影响。 反之，后一阶段的决策对前一阶段决策不产生不产生影响。 这一特征：“无后效性无后效性” 、“ 健忘性健忘性” 。 策略是各阶段决策序列. 而最佳策略不一定由各阶段的最佳决策所组成. 二、动态规划的基本概念及多阶段决策问题的结构二、动态规划的基本概念及多阶段决策问题的结构 动态规划要解决的问题是对多阶段决策系统多阶段决策系统进行优化优化的问题。则

6、首先要将实际问题写成动态规划模型动态规划模型，此时要用到以下概念。阶段阶段、状态状态、决策和策略决策和策略、状态转移（变换）状态转移（变换）、指标函数指标函数将系统根据时间、空间的演变过程演变过程，划分为几个相互联系的部分，以便按次序去求每个过程的解，此过程称为阶段阶段或级级。 1、阶段、阶段 ：常用标号：j=1,2,n表示。 这样可以把全过程优化问题转化为的阶段优化问题的阶段优化问题。这些阶段这并不是独立的，而是互相嵌入的。（即后面阶段对前面不产生影响，前面阶段对后面阶段的发展产生影响。） 阶段特征：阶段特征： 必须有顺序性顺序性。 每个阶段的决策，使阶段演变阶段演变。 应具有无后效性无后效

7、性。 2、状态、状态各个阶段开始时的客观条件客观条件（属性）叫做状态状态。描述各阶段状态的变量，称为状态变量状态变量。每阶段可有多个状态变量，状态变量集(向量)表示。前例：库存量 xj ，每年投资资金，设备已用的年限某阶段有几条路， 状态空间：状态变量取值的集合， 可以离散的，也可以为连续的。状态变量的维数：即为各阶段决策问题的维数。2、如果所选定的变量不具备无后效性，就不能作为状态变量来构造动态规划模型。 状态变量应具有的性质：1、当某阶段状态给定以后，在这阶段以后过程的发展不受这段以前各段状态的影响。 也就是说，当前的状态是过去历史的一个完整总结。过程的过去历史只能通过当前状态去影响它未来

8、的发展。 （称为无后效性）3.决策和策略决策和策略当各阶段的状状态态取定以后，就可以做出不同的决决策策（或选择），从而确定下一阶段状态状态。这种在系统的各各级级阶阶段段中，人们为控控制制系系统统的的运运行行发发展展过过程程所采的一种行为，称为决策决策。表示决策的变量，称为决策变量。uj (xj)：j阶段当状态为xj时的决策变量。各阶段决策确定后，整个系统的决策序列决策序列就构成一个策略策略。使整个问题达到最优效果的策略最优效果的策略就是最优策略最优策略。4.状态转移方程（传递函数）状态转移方程（传递函数）动态规划中本阶段的状态本阶段的状态往往是 上一阶段和上一阶段决策的结果。如果给定了第j阶段

9、的状态xj，决策uj，则j+1阶段的状态xj+1也就完全确定，可用关系式表达：xj+1=T(xj,uj(xj)若T为确定性，则为确定性动态问题确定性动态问题；若T为随机性，则为随机性动态问题随机性动态问题5.效益函数（损失函数）效益函数（损失函数）在状态xj，采取uj (xj)决策后，所付出付出或收益收益的部分它取决于系统的状态状态与决策决策。dj（xj，uj）阶段效益函数阶段效益函数6.指标函数指标函数评价评价策略优劣策略优劣的数量标准。动态规划动态规划解决多阶段决策问题多阶段决策问题的基本方法基本方法(1)思路思路:对于一个n段决策过程从1到n阶段，称为原过程原过程。对任意给定的j阶段阶段

10、，从第j阶段到第n阶段的过程 称为原过程的后部子过程后部子过程。（2）1月3月2月4月将全过程阶段决策问题，转化为n个后部子过程决策问题。这些子系统是采用能够逐步嵌入逐步嵌入，阶段数逐步增加逐步增加而形成的。每个子问题都有共同的终止状态共同的终止状态和不同的起始状态不同的起始状态。每个子问题都有自己的子策略集合，即：若j=1: v1,n(x1)为全过程策略全过程策略Vj,n(xj)=uj(xj), uj+1(xj+1), un即求 opt fj(xj,vj,n) (j=1,2, n)以j阶段为起始状态的指标函数，常用fj(xj,vj,n)来表示。动态规划问题动态规划问题是： 在一定的约束条件下

11、，求指标函数指标函数的最优化最优化问题，（3）各阶段的最优最优指标函数指标函数值值为fj*(xj)=opt fj(xj,vj ,n) (j=1,2, n)（4）c.对变量fj+1(xj+1,vj+1, n)来说，严格单调（5）确定指标函数指标函数须具有的条件：a.后部子过程后部子过程或原过程原过程的决策序列决策序列的数量函数b.满足递推关系递推关系fj(xj,vj ,n)=xj,uj, fj+1(xj+1,vj+1, n)（6）经常采用的两种指标函数指标函数a. 总效益函数总效益函数：fj(xj,vj n)=b.累积效益函数累积效益函数：fj(xj,vj n)=第二节第二节 动态规划方法动态规

12、划方法一、最优化原理一、最优化原理1.贝尔曼最优化原理贝尔曼最优化原理作为整个过程的最优化策略，具有这样的性质，即无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优决策。（3）动态规划方法是既把当前一段与未来各段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法。因此，每段的最优决策选取是从全全局局考虑的，与该段的最优选择一般不同。（2）求解时从边界条件开始，逆（顺）过程行进方向，逐段递逐段递推寻优推寻优。每一个子问题求解时，都要使用它前面已求出的都要使用它前面已求出的子问题的最优结果子问题的最优结果。最后一个子问题的最优解，就是整个问题的最优解。2.动态规

13、划方法的基本思想动态规划方法的基本思想（1）对全过程的多多阶阶段段决决策策系系统统的最最优优化化，可以转化为若干个子系统的最优化子系统子系统的最优化子系统： 从当前阶段直至最终阶段的若干阶段组成后部子过程。（4）最优化原理的数学表达式： 即为动态规划的基本方程动态规划的基本方程：是递推逐段求解递推逐段求解 fk*(xk)=optdk(xk,uk)+fk+1*(xk+1) fn+1*(xn+1)=0二、动态规划方法的步骤二、动态规划方法的步骤第一步：建模建模： 确定阶段、状态变量、决策变量、阶段、状态变量、决策变量、 传递函数、效益函数、指标函数传递函数、效益函数、指标函数第二步：逆算法求子问题

14、逆算法求子问题。 建立动态规划的泛函方程。 求解：表格枚举法、线性规划微分法、优选法第三步：确定最优策略确定最优策略。 最优决策是状态变量的函数，确定状态，则才确定决策。例：（连续变量的解法）销售策略问题设第j月，销售量 ，库存量 ，销售利润1月3月2月4月子系统一：4月 Max f4=d4=6u4-2x4 s.t x4=0 0u4x3 u*4 =x3, f*4=6x3子系统二：3、4月Max f3=d3+f*4=5u3-1.5x3+6x3 =4.5x3+5u3=4.5x2+0.5u3 s.t x3=x2-u3 0u3x2 u*3 =x2, f*3=5x21月3月2月4月子系统三：2、3、4月

15、 Max f2=d2+f *3=4u2+4.5x2= 4u2+ 4.5x1-4.5u3=4.5x1-0.5u2 s.t x2=x1-u2 0u2x1 u*2 =0, f*2=4.5x1子系统四：1、2、3、4月 Max f1=d1+f *2=3u1-x1+4.5x1= 3u1+ 3.5x1=-0.5u1+3500 s.t x1=1000-u1 0u11000 u*1=0, f*1=3500最后策略为：最后策略为： u*1=0 u*2=0 u*3=1000 u*4=0 x*1=1000 x*2=1000 x*3=0 x*4=0 v1,4=(0,0,1000,0)f= f*1=3500最短路线问题

16、（分段穷举法）最短路线问题（分段穷举法） 给定一个线路图，要从A地向F地铺设一条输油管道，各点间连线上的数字表示距离，问应选择什么样的路线，可使总距离最短。45236877584AB2B1C1C2C3C4E1D2D3D1E2F534843562134345236877584AB2B1C1C2C3C4E1D2D3D1E2F53484356213431、阶段、阶段 A B C D E F2、状态、状态 第一阶段： x1=A 第二阶段： x2=B1,B2 x2为状态集合，可有个状态 第三阶段： x3=C1,C2,C3,C4 第四阶段： x4=D1,D2,D3 第五阶段： x5=E1,E2 45236

17、877584AB2B1C1C2C3C4E1D2D3D1E2F53484356213433、决策：、决策：因状态不同，决策也不同，构成决策集合4、状态转移方程、状态转移方程 xk+1=uk (xk)5、效益函数、效益函数 d(xk,uk)：由状态xk出发，采用决策 uk到下一阶段xk+1时的两点距离6、指标函数：、指标函数：距离最优 min f45236877584AB2B1C1C2C3C4E1D2D3D1E2F5348435621343对此问题采用分段穷举法1、 可用顺序解法：适用于初始状态给定的问题（A出发点给定） 也可用逆序解法：适用于终止状态给定的问题（F目的点给定） 5阶段阶段 E 4

18、、5 阶段阶段F f5*(E1)=4 f5*(E2)=345236877584AB2B1C1C2C3C4E1D2D3D1E2F53484356213433、4、5阶段2、 3、4、5阶段45236877584AB2B1C1C2C3C4E1D2D3D1E2F53484356213431、 2、 3、4、5阶段第三节第三节 动态规划模型的建立与求解动态规划模型的建立与求解一、动态规划模型的建立一、动态规划模型的建立1. 动态规划是一种辅助的决策方法，并与有关的优化算法相结合起来求解决策问题的最优解决策问题的最优解。如何建立动态规划模型呢？ 建立动态规划的模型就是分析问题并建立问题的动态规划动态规划

19、基本方程基本方程。 成功应用动态规划方法的关键在于识别问题的识别问题的多阶段特征多阶段特征，将问题分解成为可用递推关系递推关系或联系起来的若干子问题若干子问题，或者说正确的建立具体问题的基本方程，这需要经验与技巧。 而正确建立基本递推关系方程的关键在于正确选择状态变状态变量量，保证各阶段的状态变量其有 递推的状态转移关系递推的状态转移关系 xk+1=T(xk,uk) 2. 与时间无明显关系的静态最优化问题，可列出静态模型。为了应用动态规划方法求解，可以人为的赋予它“时段”概念，将投资项目排序：（投资问题中，一般可使用的资金为状态变量）确定阶段、状态变量、决策变量、状态转移方程、指标函数等（可从

20、状态转移图写）P212 例7：3.建立动态规划模型的要点 阶段、状态变量、决策变量(状态方程)、 指标函数二、逆序解法与顺序解法动态规划的求解有两种基本方法： 逆序解法（后向动态规划方法）逆序解法（后向动态规划方法） 顺序解法（前向动态规划方法）顺序解法（前向动态规划方法）逆序解法：逆序解法：寻优的方向与多阶段决策过程的实际行进 方向相反，从最后一段开始计算，逐段前 推，求得全过程的最优策略。顺序解法：顺序解法：寻优方向同于过程的行进方向，计算是从 第一段开始逐段向后递推，计算后一阶段 要用到前一阶段的最优结果，最后一段计 算的结果就是全过程的最优结果。 顺序解法与逆序解法本质上并无区别。 一

21、般地说，当初始状态给定时可用逆序解法， 当终止状态给定时可用顺序解法；若问题给定了一 个初始状态，一个终止状态，则两种方法均可使用； 若初始状态虽已给定，终点状态有多个，须比较到 达不同终点状态的各个路径及最优指标函数值，以 选取总效益最佳的终点状态时，使用顺序解法比较 简便。两种解法的区别： 1.状态转移方程： 逆 xk+1=T(xk,uk) 顺 xk =T(xk +1,uk +1) 2.指标函数定义： 逆 fk(xk):k阶段到终点的后部z过程的 最优效益值 顺 fk(xk +1):第k阶段到起点的前部z过 程的最优效益值3.基本方程形式1kn逆x1 xk xk+1 xn+1 顺 x1 x

22、2 xk xk+1 Xn+1三、基本方程分段求解时的几种常用算法三、基本方程分段求解时的几种常用算法 动态规划模型建立后，对基本方程分段求解对基本方程分段求解，不像线性规划或非线性规划那样有固定解法，必须根据具体问题的特点，结合数学技巧灵活求解。1.离散变量的分段穷举法离散变量的分段穷举法 状态变量与决策变量若被只限定只能取离散值离散值，则可采用分段穷举法分段穷举法。由于每段的状态变量和决策变量离散取值个数较少，所以动态规划的穷举法要比一般的穷举法有效。用分段穷举法求最优指标函数值时，最重要的是正确确定每段状态变量取值范围和允许决策集合的范围。最优路线 2.连续变量的解法连续变量的解法第四节第

23、四节 动态规划在经济管理中的应用动态规划在经济管理中的应用 除了前面讲到的资源分配、最优路径问题外，动态规划在经济管理中还有许多应用，下面举一些典型例子来说明这方面的应用。一、背包问题（分配问题）一、背包问题（分配问题）1.背包问题的一般提法： 一位旅行者携带背包去登山，已知他所能承受的背包重量限度为a千克，现有n种物品可供他选择装入背包，第i种物品的单位重量为ai千克，其价值（可以表明为本物品对登山的重要性重要性的数量指标）是携带数量xi的函数ci(xi)(i=1,2,n)。问旅行者应如何选者携带各种物品的件数，以使总价值最大？背包问题等同于车、船、飞机、潜艇、人造卫星等工具的最优装载问题，

24、还可用于解决机床加工中零件最优加工、下料问题，投资决策等，有广泛实用意义。2.建立模型： 设Xi为装入第i种物品的件数，可归结为如下形式的整数规划模型。3.动态规划逆序解法建模求解动态规划逆序解法建模求解1)阶段k：将可装入物品按1、2、n排序，每一阶段装入一种物品，共划分n阶段，k=1 n。2)状态变量xk：第k段，背包中允许允许装入的总重量3)决策变量uk：第k段，装入第k种物品的件数4)状态转移： 状态转移方程：xk+1=xk-akuk5）决策集合： 6)指标函数：例：有一辆最大货运量为10吨的卡车，用于装载3种货物，每种货物单位重量及相应单位价值如下表，应如何装载可使总价值最大？货物编

25、号123单位重量543单位价值654132分段穷举法（离散、计算机实现）第三阶段：x3取值范围010，f3*=c3u3x3u3f3*(x3)u3*货物编号123单位重量543单位价值654x2u2f2f2*(x2)u2*第2、3阶段：x2取值范围010，f2*=c2u2+f3*货物编号123单位重量543单位价值654当x1=10时，max f*=13,u1*=0 递推得u2*=1,u3*=2若再加个约束条件，如总体积不能超过一定数量，则状态变量是二维的背包问题，其解法与一维相似。X1u1f1*(x3)u1*货物编号123单位重量543单位价值654二、生产经营问题 在生产和经营管理中经常遇到

26、如何合理安排生产计划，采购计划以及仓库的存货计和销售计划，使总效益最高的问题。1、生产与存贮问题，清P199生产与库存问题 教材P1072、采购与销售问题 销售策略问题3、限期采购问题（随机型）例：某部门欲采购一批原料，原料价格在五周内可能有所变动，已预测得该种原料今后五周内不同单价的概率如下表，试确定该部门在五周内购进这批原料的最优策略，使采购价值的期望值最小。本例与前面所讨论的确定型问题不同，状态的转移不能完全确定，而按某种已知的概率分布取值，即属于随机型动态规划问题阶段，按采购期限分为5段，k1，2，3，4，5；状态变量xk，第k周的原料的实际价格，决策变量uk，第k周如采取采购则uk1

27、，若不采购uk0原料单价（元）概率5000.36000.37000.4三、设备更新问题三、设备更新问题 企业中经常会遇到因设备陈旧或损坏需要更新的问题。 从经济上分析，一台设备应该使用多少年更新最合算，这就是设备更新问题。一般来说，一台设备在比较新时，年运转量大，经济收入高，故障少，维修费用少。 但随着使用年限的增加，年运转量减少因而收入减少，故障多，维修费用增加，如果更新可提高不同决策的优劣，常常要在一个较长的时间内考虑更新决策问题。1、设备更新问题一般提法： 在已知一台设备的效益函数效益函数r(t)，维修费用函数维修费用函数p(t)，更新费用函数更新费用函数c(t)条件下，要求在n年内的每

28、年年初做出决策：是继续使用是继续使用旧设备，还是更换一台更换一台新的，使n年总效益最大。rk(t)：在第k年设备已使用过t年（或称役龄为t年），再 使用1年时的效益效益。pk(t)：在第k年设备役龄为t年，再使用1年时的维修费用维修费用。ck(t)：在第k年卖掉一台役龄为t年设备，买进一台新设备 的更新净费用更新净费用。 2、建立动态规划模型阶段k：表示计划使用该设备的年限数。状态变量xk：第k年初，设备已使用过的年数，即役龄。决策变量uk:是决定第k年初更新，还是保留旧设备。状态转移方程: 阶段指标(效益函数)：指标函数： fk(xk)=maxd(xk,uk)+fk+1(xk+1) fn+1

29、(xn+1)=0 rk(xk)-pk(xk) + fk+1(xk+1) 当uk=k rk(0)-pk(0)-ck(xk) + fk+1(1) 当uk=R 即：fk(xk)=maxd(xk,uk)=rk(xk)-pk(xk) 当uk=k rk(0)-pk(0)-ck(xk) 当uk=Rxk+1=xk+1 当uk=K 1 当uk=R 为折扣因子(0 1),表示一年以后的单位收入价值相当于现年的单位。例：设某台新设备的年效益及年均维修费，更新净费用如表示确定今后5年内的更新策略，使总收益最大。（设=1） 役龄 项目012345效益rk(t)54.543.7532.5维修费pk(t)0.511.522

30、.53更新费Ck(t)0.51.52.22.533.5解：五个阶段1）当k=5时 r5(x5)-p5(x5) 当u5=k rk(0)-p5(0)-c5(x5) 当u5=Rx5可取1，2，3，4 r5(1)-p5(1) u5=k rk(0)-p5(0)-c5(1) u5=R 4-0.5 5-0.5-2.2 3.75-2 5-0.5-2.5 3-2.5 5-0.5-3f5(x5)=max*f5(1)=max=maxf5(2)=max*=2.5,u5(2)=k*f5(3)=maxf5(4)=max*=2 , u5(3)= R=1.5,u5(2)= R*4.5-1 u5=k5-0.5-1.5 u5=R

31、=3.5,u*5(1)=k2)当k=4,第四、五年阶段 r4(x4)-p4(x4) + f5(x4+1) 当u4=k r4(0)-p4(0)-c5(1) + f5(1) 当u4=Rx4可取1，2，3 4.5-1+2.5 5-0.5-1.5+3.5 4-1.5+2 5-0.5-1.5+3.5 3.75-2+1.5 5-0.5-2.5+3.5f4(x4)=maxf4(2)=max f4(3)=maxf4(1)=max =3.5,u4(3)= R=5.8,u4(2)= R=6.5,u4(1)=k3)当k=3,第三、四、五年阶段 r3(x3)-p3(x3) + f4(x3+1) 当u3=k r3(0)

32、-p3(0)-c3(x3) + f4(1) 当u3=Rx3可取1,2 4.5-1+5.8 5-0.5-1.5+6.5 4-1.5+5.5 5-0.5-2.2+6.5 f3(x3)=maxf3(1)=maxf3(2)=max=9.5, u3(1)= R=8.8, u3(1)= R*4)当k=2 r2(x2)-p2(x2) + f3(x2+1) 当u2=k r2(0)-p2(0)-c2(x2) + f3(1) 当u2=R x2可取1 4.5-1+8.8 5-0.5-1.5+9.5f2(x2)=maxf2(1)=max=12.5, u2(1)= R5)当k=1 r1(x1)-p1(x1) + f2(

33、x1+1) 当 u1=k r1(0)-p1(0)-c1(x1) + f2(1) 当 u1=Rx1只能取1 5-0.5+12.5 5-0.5-0.5+12.5递推算回去，当u1(0)= k时，x1=0 x1+1 当u1=k 知 x2=1, 查 f2=(1), 得u2 (1) =R 1 当u1=R x2+1 当u2=k 知 x3=1, 查 f3=(1), 得u3 (1) =R 1 当u2=R x4=1, u4 (1) =R x5=1, u5 (1) =k最优策略为K,R,R,R,K 总效益：f = 17f1(x1)=maxf1(0)=max=17, u1(0)= k*x2=X3=*四、货郎担问题货

34、郎担问题一般提法： 一个货郎从某城镇出发，经过若干个城镇一次，且仅一次，最后人回到原出发的城镇，问应如何选择行走路线可是总行程最短。 这是运筹学的一个著名问题，实际问题很多问题可以归结为这类问题。设v1,v2,vn是一致的n个城镇，vi到vj的距离dij。求从v1 出发，经各城镇一次且仅一次，再返回v1的最短路程。对n个城镇进行排列，有(n-1)！/2种方案，穷举法不现实。 下面采用动态规划方法求解。 货郎担问题也是求最短路径问题，但与前面的最短路径问题有很大不同，建立动态规划模型时，虽然也可按城镇数目n将问题分为n个阶段，但状态变量不好选择，不容易满足无后效性。 设状态S表示从v1到 vi中

35、间所能经过的城市集合， S实际上是包含除v1与 vi两个点之外其余点的集合，但S中的点的个数点的个数要随阶段数改变。（点的个数为阶段数）第K阶段的状态变量（状态变量（i,S）表示从v1点出发，经过S集合中K个所有点一次，最后到达vi 点。最优指标函数最优指标函数fk (i,S)为从v1点出发，经由k个城镇的S集合到vi的最短距离。决策变量决策变量Pk (i,S)表示从v1经k个中间城镇的S集合到vi城镇的最短路线上邻接邻接vi的前一个城镇的前一个城镇。则递推关系为：fk(i,s)=minfk-1(j,si)+dij F0(i,=d1i 为空集 (k=1,2,n-1;i=2,3 n)例：已知4个

36、城市间距离如表。求从v1出发经其余城市一次且仅一次，最后返回v1的最短路径与距离。解: 1）k=0,即中间无经过的城市，s= f0(2,)=d12=6, f0(3,)=d13=7, f0(4,)=d14=9 2) k=1,从v1出发，经过一个城市，到vi的最短距离 f1(2,3)= f0(3,)+ d32=7+8=15 f1(2,4)= f0(4,)+ d42=9+5=14 f1(3,2)= f0(2,)+ d23=6+9=15 f1(3,4)= f0(4,)+ d43=9+5=15 f1(4,2)= f0(2,)+ d24=6+7=13 f1(4,3)= f0(3,)+ d34=7+8=15

37、vi12341067928097358084655013241324vi1234106792809735808465503) k=2,计算从城市v1出发，中间经过2个城市，到vi的最短距离f2(2,3,4)= minf1(4,3) + d42, f1(3,4) + d32 =min15+5,14+8=20 p2(2,3,4)=4 由1出发要经过3、4到2时,先经过3再到4,最后到2f2(3,2,4)= minf1(2,4) + d23, f1(4,2) + d43 =min14+9,13+5=18 p2(3,2,4)=4 由1出发要经过2、4到3时，先经过2再到4 ,最后到3f2(4,2,3)

38、= min15+7,15+8=22 p2(4,2,3)=24) k=3,即从v1出发，中间经过3个城市，再回到v1的最短距离f3(1,2,3,4)= minf2(2,3,4) + d21, f2(3,2,4) + d31, f2(4,2,3) + d41 =min20+8,18+5,22+6=23 p3(1,2,3,4)=3 13421最短距离：23 当当n较大时，用此法解计算量太大，较大时，用此法解计算量太大， 只适合于只适合于n 较小的情况较小的情况1324五、某公司资金10万元,若投资于项目 i(i=1,2,3)的投资额为 xi 时,其收益分别为 g1(x1)=4x1, g2(x2)=9

39、x22 , g3(x3)=2x32 ,问应如何分配投资数额才能使总收益最大?132用逆序解法132132132六、某商店在未来四个月里,利用一个仓库经销某种商品，该仓库的最大容量为1000件，每月中旬订购商品，并于下月初取到订货。据估计：今后四个月这种商品的购价 pk 和售价qk 如表所示。假定商店在1月初开始经销时仓库已存有该种商品500件，每月市场需求不限，问应如何计划每月的订购与销售数量，使这四个月的总利润最大？(不考虑仓库的存储费用。)月份 k购价 pk 售价 qk110122993111341517设状态变量 sk 表示第 k 个月的库存量；决策变量 xk 和 yk 分别表示第 k 个月的订货量和销售量；H=1000为仓库的最大库容，则状态转移图:第 k 个月的状态转移方程：sk+1 = sk + xk yk第 k 个月的效益函数：dk (sk ，xk，yk) = qk yk pk xk第 k 个月的最优指标函数：1月3月2月4月月份 k购价 pk 售价 qk110122993111341517显然，y4*=s4，x4*=0 为最优决策，这时 f4* (s4)=17s41月3月2月4月1月3月2月4月