运筹学74动态规划应用举例

第七章第七章 动态规划动态规划 n多阶段决策过程的最优化多阶段决策过程的最优化n动态规划的基本概念和基本原理动态规划的基本概念和基本原理 n动态规划模型的建立与求解动态规划模型的建立与求解n动态规划在经济管理中的应用动态规划在经济管理中的应用 第四节第四节 动态规划在经济管理中的应用动态规划在经济管理中的应用 连续变量的离散化解法连续变量的离散化解法 先介绍连续变量离散化的概念。如投资分配问题先介绍连续变量离散化的概念。如投资分配问题的一般静态模型为：的一般静态模型为：niiixgz1)(max),2,1(01nixaxinii模型中：阶段数、总投资、各阶段投资数、各阶段收益、决策变量、状模型中：阶段数、总投资、各阶段投资数、各阶段收益、决策变量、状态变量态变量 状态转移方程、基本方程、指标函数、最优指标函数状态转移方程、基本方程、指标函数、最优指标函数建立它的动态规划模型，其基本方程为：建立它的动态规划模型，其基本方程为：0)(1,2,1,)()(max)(11110nnkkkksxkksfnnksfxgsfkk其状态转移方程为其状态转移方程为:kkkxss1 由于由于 与与 都是连续变量，当各阶段指标都是连续变量，当各阶段指标 没没有特殊性而较为复杂时，有特殊性而较为复杂时，要求出要求出 会比较困难，因而求会比较困难，因而求全过程的最优策略也就相当不容易，这时常常采用把连续变量全过程的最优策略也就相当不容易，这时常常采用把连续变量离散化的办法求其数值解。具体做法如下：离散化的办法求其数值解。具体做法如下：kskx)(kkxg)(kksf（1 1）令令 ，把区间把区间 0 0，aa进行分割，进行分割，的大小可的大小可依据问题所要求的精度以及计算机的容依据问题所要求的精度以及计算机的容量来定。量来定。amsk,2,0(2)(2)规定状态变量规定状态变量 及决策变量及决策变量 只在离散点只在离散点 上取值，相应的指标上取值，相应的指标函数函数 就被定义在这些离散值上，于是递推方就被定义在这些离散值上，于是递推方程就变为：程就变为：kskxam,2,0)(kksf0)()()(max)(111,2,1,0nnkkkqpkksfpsfpgsf其中其中 pxsqkk,作为离散化例子，在例作为离散化例子，在例5 5中规定状态变量和决中规定状态变量和决策变量只在给出的离散点上取值，见例策变量只在给出的离散点上取值，见例6 6。（3 3）按 逆 序 方 法，逐 步 递 推 求按 逆 序 方 法，逐 步 递 推 求出出 ，最后求出最，最后求出最优资金分配方案。优资金分配方案。)(,),(11sfsfnn问如何分配投资数额才能使总效益最大问如何分配投资数额才能使总效益最大?23332221112)(,9)(,4)(xxgxxgxxg例例5 5 某公司有资金某公司有资金1010万元，若投资于项目万元，若投资于项目i(i=1,2,3)i(i=1,2,3)的投资额为的投资额为x xi i时，其效益分别为：时，其效益分别为：例例6 6 连续变量的离散化解法连续变量的离散化解法)3,2,1(,010.294max3212321ixxxxtsxxxZi解解 令令 ，将区间，将区间00，1010分割成分割成0 0，2 2，4 4，6 6，8 8，1010六个点，即状态变量六个点，即状态变量 集合为集合为 2ks10,8,6,4,2,0允许允许决策集合为决策集合为 ，与与 均在分割点上取值。均在分割点上取值。kksx0kxks动态规划基本方程为：动态规划基本方程为：0)(1,2,3)()(max)(4410sfkxsfxgsfkkkkksxkkkk当当k=3k=3时，时，230332max)(33xsxsf式中式中 与与 的集合均为：的集合均为：计算结果见表计算结果见表7-17-1。3s3x10,8,6,4,2,03s)(33sf*3x02468100832721282000246810当当k=3时，时，表表7-1 230332max)(33xsxsf当当k=2时，时，)(9max)(223202222xsfxsfsx0)(1,2,3)()(max)(4410sfkxsfxgsfkkkkksxkkkk计算结果见表计算结果见表7-27-2。2s2x32fg 2f*2x024681000 20 2 40 2 4 60 2 4 6 80 2 4 6 8 1008 1832 26 3672 50 44 54128 90 68 62 72200 146 108 86 80 900 18 36 72 128 2000 24 0 0 0表表7-2 7-2 当当k=1时，时，0)(1,2,3)()(max)(4410sfkxsfxgsfkkkkksxkkkk计算结果见表计算结果见表7-37-3。表表7-3)(4max)(1121100111xsfxsfx1s1x21fg 1f*1x 10 101010 10100246810200136886050402000最大收益为最大收益为 ，与例，与例5 5结论完全相同。结论完全相同。10,0,0*3*2*1xxx200)10(1f计算结果表明，最优决策为：计算结果表明，最优决策为：应指出的是：这种方法有可能丢失最优解，应指出的是：这种方法有可能丢失最优解，一般得到原问题的近似解。一般得到原问题的近似解。一、背包问题一、背包问题 一位旅行者携带背包去登山，已知他所能承受的背包重一位旅行者携带背包去登山，已知他所能承受的背包重量限度为量限度为a kg，现有，现有n种物品可供他选择装入背包，第种物品可供他选择装入背包，第i种种物品的单件重量为物品的单件重量为ai kg，其价值是携带数量，其价值是携带数量xi的函数的函数ci(xi)(i=1,2,n)，问旅行者应如何选择携带各种物品的件，问旅行者应如何选择携带各种物品的件数，以使总价值最大？数，以使总价值最大？),2,1(0)(max11nixaxaxcziniiiniii且为整数例例1 有一辆最大货运量为有一辆最大货运量为10t的卡车，用以装载的卡车，用以装载3种货物，种货物，每种货物的单位重量及相应单位价值见下表，应如何装载可每种货物的单位重量及相应单位价值见下表，应如何装载可使总价值最大？使总价值最大？)3,2,1(010543654max321321ixxxxxxxzi且为整数货物编号i123单位重量(t)345单位价值ci456逆序解法：逆序解法：阶段阶段k：k=1,2,3状态变量状态变量sk:第第k阶段可以装载第阶段可以装载第k种到第种到第3种货物的重量。种货物的重量。决策变量决策变量xk:决定装载第决定装载第k种货物的数量。种货物的数量。状态转移方程状态转移方程:sk+1=sk-akxk最优指标函数最优指标函数fk(sk):当可装载重量为当可装载重量为sk,装载第装载第k种到第种到第3种货物所获得的种货物所获得的最大价值。最大价值。基本方程：基本方程：0)(1,2,3)()(max)(4411/,1,0sfksfxcsfkkkkasxkkkkk当阶段当阶段k=3时，有时，有6max)(35/,03333xsfsxs3012345678910 x3000000 10 10 10 10 10 1 2c3+f4000000 60 60 60 60 60 6 12f3000006666612x3*00000111112当阶段当阶段k=2时，有时，有)(5max)(3324/,02222sfxsfsx s2012345678910 x200000 10 10 10 10 1 20 1 20 1 2c2+f300000 5+06 56 56 56 5 106 5+6 1012 5+6 10f200005666101112x2*000010002102234xss当阶段当阶段k=1时，有时，有)(3max)(2213/10,0111sfxsfx s110 x10 1 2 3c1+f312 4+6 8+5 12f213x1*21123xss二、生产经营问题二、生产经营问题 在生产和经营管理中，经常遇到如何合在生产和经营管理中，经常遇到如何合理地安排生产计划、采购计划以及仓库的存理地安排生产计划、采购计划以及仓库的存货计划和销售计划，使总效益最高的问题。货计划和销售计划，使总效益最高的问题。下面通过例子来说明对不同特点问题的不同下面通过例子来说明对不同特点问题的不同处理技巧处理技巧。例例2 生产与存贮问题生产与存贮问题 某工厂生产并销售某种产品，已知今后四个月市场需求预测如表，又每月某工厂生产并销售某种产品，已知今后四个月市场需求预测如表，又每月生产生产j单位产品费用为：单位产品费用为：)()6,2,1(3)0(0)(千元jjjjC 每月库存每月库存j j单位产品的费用为单位产品的费用为 ，该厂最大库存容量为该厂最大库存容量为3 3单单位，每月最大生产能力为位，每月最大生产能力为6 6单位，计划开始和计划期末库存量都是单位，计划开始和计划期末库存量都是零零。试制定试制定四个月四个月的生产计划，在满足用户需求条件下总费用最小。假设第的生产计划，在满足用户需求条件下总费用最小。假设第i+1i+1个月的库个月的库存量是第存量是第i i个月个月可销售量可销售量与该月用户需求量之差；而第与该月用户需求量之差；而第i i个月的可销售量是本个月的可销售量是本月初库存量与产量之和。月初库存量与产量之和。)(5.0)(千元jjE)(月i)(需求ig12342324用动态规划方法求解时，对有关概念作如下分析：用动态规划方法求解时，对有关概念作如下分析：(1)(1)阶段：每个月为一个阶段，阶段：每个月为一个阶段，k k1 1，2 2，3 3，4 4。(2)(2)状态变量：状态变量：为第为第k k个月初的库存量。个月初的库存量。ks(3)(3)决策变量：决策变量：为第为第k k个月的生产量。个月的生产量。ku(4)(4)状态转移方程：状态转移方程：kkkkguss1(5)(5)最优指标函数：最优指标函数：表示第表示第k k月状态为月状态为 时，采取时，采取最佳策略生产，从本月到计划结束最佳策略生产，从本月到计划结束(第第4 4月末月末)的生产与存贮最的生产与存贮最低费用。低费用。（6 6）基本方程：）基本方程：)(kksfks0)(1,2,3,4)()()(min)(5511sfksfsEuCsfkkkkukkk k4，s5=s4+u4-g4=0，所以，所以u4=g4-s4=4-s4，s4可取可取0，1，2，3。0)()(min)(443,2,1,0444sEuCsfus40123u44321C+E+f576+0.55+14+1.5f476.565.5u4*4321 k3，s4=s3+u3-g3，所以，所以u3=s4+g3-s3，s3可取可取0，1，2，3。s30123u32 3 4 51 2 3 40 1 2 30 1 2C+E+f45+7 6+6.5 7+6 8+5.5 4.5+7 5.5+6.5 6.5+6 7.5+5.51+7 5+6.5 6+6 7+5.5 1.5+6.5 5.5+6 6.5+5.5f31211.588u3*2100 k2，s3=s2+u2-g2，所以，所以u2=s3+g2-s2，s2可取可取0，1，2，3。s20123u23 4 5 62 3 4 51 2 3 40 1 2 3C+E+f36+12 7+11.5 8+8 9+85.5+12 6.5+11.5 7.5+8 8.5+85+12 6+11.5 7+8 8+8 1.5+12 5.5+11.5 6.5+8 7.5+8 f21615.51513.5u2*5430 k1，s2=s1+u1-g1，所以，所以u1=s2+g1-s1，s1可取可取0。s10u12 3 4 5C+E+f25+16 6+15.5 7+15 8+13.5f121u1*2反推回去，反推回去，u1*=2，u2*=5，u3*=0，u4*=4。例例3 3 采购与销售问题采购与销售问题 某商店在未来的某商店在未来的4 4个月里，准备利用它的一个仓库来专门经销某种商个月里，准备利用它的一个仓库来专门经销某种商品，仓库最大容量能贮存这种商品品，仓库最大容量能贮存这种商品l000l000单位。假定该商店每月只能出卖仓单位。假定该商店每月只能出卖仓库现有的货。当商店在某月购货时，下月初才能到货。预测该商品未来四库现有的货。当商店在某月购货时，下月初才能到货。预测该商品未来四个月的买卖价格如表个月的买卖价格如表7 7_12_12所示，假定商店在所示，假定商店在1 1月开始经销时，仓库贮有该月开始经销时，仓库贮有该商品商品500500单位。试问若不计库存费用，该商店应如何制定单位。试问若不计库存费用，该商店应如何制定1 1月至月至4 4月的订购月的订购与销售计划，使预期获利最大。与销售计划，使预期获利最大。月份（月份（k）购买单价（购买单价（ck）销售单价（销售单价（pk）110122983111341517解解 按月份划分为按月份划分为4个阶段，个阶段，k=l，2，3，4状态变量状态变量 ：第：第k月初时仓库中的存货量月初时仓库中的存货量(含上月订货含上月订货)。决策变量决策变量 ：第：第k月卖出的货物数量。月卖出的货物数量。：第：第k月订购的货物数量。月订购的货物数量。状态转移方程：状态转移方程：kskxky最优指标函数最优指标函数 ：第：第k k月初存货量为月初存货量为 时，从第时，从第k k月到月到4 4月末所获最大月末所获最大利润。利润。则则有逆序递推关系式为：有逆序递推关系式为：kkkkxyss1)(kksfks0)(1,2,3,4)(max)(5511)(100000sfksfycxpsfkkkkkkxsysxkkkkkkk当当k=4时时 显然，决策应取显然，决策应取 时才有最大值时才有最大值1517max)(44)(1000004444444yxsfxsysx0,*44*4ysx44417)(ssf0)(1,2,3,4)(max)(5511)(100000sfksfycxpsfkkkkkkxsysxkkkkkkk当当k=3时时 这个阶段需解一个线性规划问题：这个阶段需解一个线性规划问题：1764max)(171113max)(1113max)(333)(10000033333)(1000004433)(10000033333333333333333syxxysyxsfyxsfxsysxxsysxxsysx因为只有两个变量因为只有两个变量x3,y3，可以用图解法，也可以用单纯形法，求解得到：，可以用图解法，也可以用单纯形法，求解得到：时有最大值时有最大值 0,10001764max3333333333yxsxysxsyxz1000,*33*3ysx333136000)(ssf当当k=2时时 求解线性规划问题：求解线性规划问题：得得45136000max)(13600098max)(98max)(222)(10000022222)(100000222322)(10000022222222222222222yxsxysyxxysfyxsfxsysxxsysxxsysx0,100045136000max2222222222yxsxysxyxsz2222291000044000136000)(ssssf2*2*21000,0syx当当k=1时时 求解一个线性规划问题：求解一个线性规划问题：得得)(1012max)(111211)(1000001111111xysfyxsfxsysx 5001s145003max)(9100001012max)500(115000500011111500050001111111yxxysyxfxyxxyx0,500500314500max1111111yxxyxyxz16000500314500)500(,0,5001*1*1fyx最优策略见下表。最大利润为最优策略见下表。最大利润为1600016000。月份月份期前存货期前存货售出量售出量购进量购进量15005000200100031000100010004100010000例例4 4 限期采购问题限期采购问题(随机型随机型)某部门欲采购一批原料，原料价格在五周内可能有某部门欲采购一批原料，原料价格在五周内可能有所变动，已预测得该种原料今后五周内取不同单价的概所变动，已预测得该种原料今后五周内取不同单价的概率如表率如表7-147-14所示。试确定该部门在五周内购进这批原料所示。试确定该部门在五周内购进这批原料的最优策略，使采购价格的的最优策略，使采购价格的期望值期望值最小。最小。原材料单价（元）原材料单价（元）概率概率5006007000.30.30.4表表7-14 阶段阶段k k：可按采购期限可按采购期限(周周)分为分为5 5段，段，k k1 1，2 2，3 3，4 4，5 5。状态变量状态变量 ：第：第k k周的原料实际价格。周的原料实际价格。kx 决策变量决策变量 ：第：第k周如采购周如采购 则则 1，若不采购，若不采购 则则 =0 =0。另外用另外用 表示：当第表示：当第k周决定等待，而在以后采购时的采购价格期望值。周决定等待，而在以后采购时的采购价格期望值。最优指标函数最优指标函数 ：第：第k周实际价格为周实际价格为 时，从第时，从第k周至第周至第5周采取最周采取最优策略所花费的最低期望价格。优策略所花费的最低期望价格。则则有逆序递推关系式为：有逆序递推关系式为：)(kksfks解解 本例与前面所讨论的确定型问题不同，状态的转移不能完全确定，而本例与前面所讨论的确定型问题不同，状态的转移不能完全确定，而按某种已知的按某种已知的概率分布概率分布取值，即属于取值，即属于随机型随机型动态规划问题。动态规划问题。kskxkxkES)17.7()()17.7(1,2,3,4,min)(55555bDsssfakDsSssfkkkEkkkkD为状态集合为状态集合500，600，700。当当k=5时时 因为若前四周尚未购买，则无论本周价格如何，该部门都因为若前四周尚未购买，则无论本周价格如何，该部门都必须购买，所以必须购买，所以)(1700700)(1600600)(1500500)5(5*55*55*55采购当采购当采购当xsxsxssf当当k=4时时 由于由于 所以所以 6107004.06003.05003.0)700(4.0)600(3.0)500(3.05554fffSE610,min,min)(4444444sSssfEDs)(0700610)(1600600)(1500500*44*44*44等待当采购当采购当xsxsxs当当k=3时时 由于由于 所以所以 5746104.06003.05003.0)700(4.0)600(3.0)500(3.04443fffSE574,min,min)(3333333sSssfEDs07006005741500500*33*33xsxs或当当当当k=2时时 同理同理 8.551,min,min)(22222sSssfE07006008.5511500500*22*22xsxs或当当当当k=1时时 26.536,min,min)(11111sSssfE070060026.5361500500*11*11xsxs或当当 所以，最优采购策略为：若第一、二、三周原料价格所以，最优采购策略为：若第一、二、三周原料价格为为500500，则立即采购，否则在以后的几周内再采购。若第四，则立即采购，否则在以后的几周内再采购。若第四周价格为周价格为500500或或600600，则立即采购，否则等第五周再采购。，则立即采购，否则等第五周再采购。而第五周时无论当时价格为多少都必须采购。而第五周时无论当时价格为多少都必须采购。按照以上策略进行采购，期望价格为：按照以上策略进行采购，期望价格为：525382.52526.5364.026.5363.05003.0)700(4.0)600(3.0)500(3.0)(11111fffsf三、设备更新问题三、设备更新问题 从经济上分析，一台设备应该从经济上分析，一台设备应该 使用多少年更新最使用多少年更新最合算，这就是设备更新问题。一般来说，一台设备在比合算，这就是设备更新问题。一般来说，一台设备在比较新时，年运转量大，经济收入高，故障少，维修费用较新时，年运转量大，经济收入高，故障少，维修费用少，但随着使用年限的增加，年运转量减少因而收入减少，但随着使用年限的增加，年运转量减少因而收入减少，故障变多少，故障变多,维修费用增加。如果更新可提高年净收维修费用增加。如果更新可提高年净收入，但是当年要支出一笔数额较大的购买费，为了比较入，但是当年要支出一笔数额较大的购买费，为了比较不同决策的优劣，常常要在一个较长的时间内考虑更新不同决策的优劣，常常要在一个较长的时间内考虑更新决策问题。决策问题。设备更新问题一般提法：在已知一台设备的效益函数设备更新问题一般提法：在已知一台设备的效益函数r(t)，维修费用函数维修费用函数u(t)及更新费用函数及更新费用函数c(t)条件下，要求在条件下，要求在n年内的年内的每年年初作出决策，是继续使用旧设备还是更换一台新的，使每年年初作出决策，是继续使用旧设备还是更换一台新的，使n年总效益最大。年总效益最大。rk(t)：在第：在第k年设备已使用过年设备已使用过t年年(或称役龄为或称役龄为t年年)，再使用，再使用1年时的年时的效益。效益。uk(t)：在第：在第k年设备役龄为年设备役龄为t年，再使用一年的维修费用。年，再使用一年的维修费用。ck(t)：在第：在第k年卖掉年卖掉台役龄为台役龄为t年的设备，买进一台新设备的更年的设备，买进一台新设备的更新净费用。新净费用。为折扣因子为折扣因子(01)，表示一年以后的单位收入价值相当于现，表示一年以后的单位收入价值相当于现年的年的 单位。单位。动态规划模型动态规划模型阶段变量阶段变量k：k=1,2,n，表示计划使用该设备的年限数。，表示计划使用该设备的年限数。状态变量状态变量sk:第第k年初，设备年初，设备已使用过已使用过的年数，即役龄。的年数，即役龄。决策变量决策变量xk:是第是第k年初更新（年初更新（Replacement），还是保留使用（，还是保留使用（keep）旧设备，分别用旧设备，分别用R与与K表示。表示。状态转移方程为：状态转移方程为：阶段指标为：阶段指标为：111kkssRxKxkk当当指标函数为：指标函数为：)()0()0()()(),(kkkkkkkkkkjscursusrxsvRxKxkk当当),2,1(),(,nkxsvVnkjkkjnk 最优指标函数最优指标函数fk(sk)表示第表示第k年初，使用一台已用了年初，使用一台已用了sk年的设备，到第年的设备，到第n年年末的最大收益，则可得如下的逆序动态规划方程：末的最大收益，则可得如下的逆序动态规划方程：实际上实际上，0)()(),(max)(1111nnkkkkRKkkksfsfxsvxsfk或)18.7()18.7(ba)()()0()0()()()(max)(1111kkkkkkkkkkkkkksfscursfsusrsfRxKxkk当当例例5 5 设某台新设备的年效益及年均维修费、更新净费用如表设某台新设备的年效益及年均维修费、更新净费用如表7-7-1515所示。试确定今后所示。试确定今后5 5年内的更新策略，使总收益最大。年内的更新策略，使总收益最大。（设（设 ）1)(trk)(tuk)(tck役龄役龄项目项目012345效益效益54.543.7532.5维修费维修费0.5 11.522.53更新费更新费0.51.52.22.533.5解解 如前述建立动态规划模型，如前述建立动态规划模型，n=5 当当k=5时时，)()0()0()()(max)(5555555555scursusrsfRxKx55当当状态变量状态变量s5可取可取1，2，3，4。)1()0()0()1()1(max)1(555555cururfRxKx55当当5.35.15.0515.4maxK)1(x5当=2.52.25.055.14max)2(5fK)2(x5当=25.25.05275.3max)3(5fR)3(x5当=1.535.055.23max)4(5fR)2(x5当 役龄役龄项目项目012345效益效益54.543.7532.5维修费维修费0.5 11.522.53更新费更新费0.51.52.22.533.5当当k=4时时，状态变量状态变量s4可取可取1，2，3。=6.5 役龄役龄项目项目012345效益效益54.543.7532.5维修费维修费0.5 11.522.53更新费更新费0.51.52.22.533.5)1()()0()0()1()()(max)(5444445444444fscursfsusrsfRxKx44当当)1(4f5.35.15.055.215.4maxR)1(x4当)2(4f=5.32.25.05215.4max=5.8R)2(x4当)3(4f=5.35.25.055.1275.3max=5.5R)3(x4当当当k=3时时，状态变量状态变量s3可取可取1，2。=9.5 役龄役龄项目项目012345效益效益54.543.7532.5维修费维修费0.5 11.522.53更新费更新费0.51.52.22.533.5)1()()0()0()1()()(max)(4333334333333fscursfsusrsfRxKx33当当)1(3f5.65.15.058.515.4maxR)1(x3当)2(3f=5.62.25.055.515.4max=8.8R)2(x3当当当k=2时时，状态变量状态变量s2只能取只能取1 役龄役龄项目项目012345效益效益54.543.7532.5维修费维修费0.5 11.522.53更新费更新费0.51.52.22.533.5=12.5)1()()0()0()1()()(max)(3222223222222fscursfsusrsfRxKx22当当)1(2f5.95.15.058.815.4maxR)1(x2当当当k=1时时，状态变量状态变量s1只能取只能取0 役龄役龄项目项目012345效益效益54.543.7532.5维修费维修费0.5 11.522.53更新费更新费0.51.52.22.533.5=17)1()()0()0()1()()(max)(2111112111111fscursfsusrsfRxKx11当当5.125.05.055.125.05max)0(1fKx)0(1 上述计算递推回去，当上述计算递推回去，当 时，由状态转移方程，时，由状态转移方程，则则 则查则查 得：得：状态状态 ，查：，查：Kx)0(1RxRxfsKxss1*2221121)1(11得，查知RxsKxss23223111推出)1(3fRx*3推出推出 ，查，查 14s)1(4fRx*415s)1(5fKx*5最优策略为：最优策略为：，即第一年初购买的设备到第二、三、四年初，即第一年初购买的设备到第二、三、四年初各更新一次，用到第各更新一次，用到第5年末，其总效益为年末，其总效益为17万元。万元。KRRRK,k5，s5可取可取1,2,3,4。s51234u5K RK RK RK Rv5+f64.5-1 5-0.5-1.54-1.5 5-0.5-2.23.75-2 5-0.5-2.53-2.5 5-0.5-3f53.52.521.5u5*KKRR k4,s4可取可取1,2,3。s4123u4K RK RK Rv4+f54.5-1+2.5 5-0.5-1.5+3.54-1.5+2 5-0.5-2.2+3.53.75-2+1.5 5-0.5-2.5+3.5f46.55.85.5u4*RRR k3，s3可取可取1,2。s312u3K RK Rv3+f44.5-1+5.8 5-0.5-1.5+6.54-1.5+5.5 5-0.5-2.2+6.5f49.58.8u4*RR k2,s2可取可取1。s21u2K Rv3+f24.5-1+8.8 5-0.5-1.5+9.5f212.5u2*R k1,s2可取可取0。s10u1K Rv1+f25-0.5+12.5 5-0.5-0.5+12.5f117u1*K 货郎担问题一般提法为：一个货郎从某货郎担问题一般提法为：一个货郎从某城镇出发，经过若干个城镇一次，且仅一次，城镇出发，经过若干个城镇一次，且仅一次，最后仍回到原出发的城镇，问应如何选择行最后仍回到原出发的城镇，问应如何选择行走路线可使总行程最短，这是运筹学的一个走路线可使总行程最短，这是运筹学的一个著名问题，实际中有很多问题可以归结为这著名问题，实际中有很多问题可以归结为这类问题。类问题。四、货郎担问题四、货郎担问题 设设 是已知的是已知的n n个城镇，城镇个城镇，城镇 到城镇到城镇 的距离为的距离为 ，现求从，现求从 出发，经各城镇一次且仅一次出发，经各城镇一次且仅一次返回返回 的最短路程。若对的最短路程。若对n n个城镇进行排列，有个城镇进行排列，有 (n(n一一1)!1)!2 2种方案，所以穷举法是不现实的，这里介绍一种方案，所以穷举法是不现实的，这里介绍一种动态规划方法。种动态规划方法。货郎担问题也是求最短路径问题，但与例货郎担问题也是求最短路径问题，但与例4 4的最短路的最短路问题有很大不同，建动态规划模型时，虽然也可按城镇数问题有很大不同，建动态规划模型时，虽然也可按城镇数目目n n将问题分为将问题分为n n个阶段。但是状态变量不好选择，不容易个阶段。但是状态变量不好选择，不容易满足无后效性。为保持状态间相互独立，可按以下方法建满足无后效性。为保持状态间相互独立，可按以下方法建模：模：nvvv,21jvijd1viv1v 设设S S表示从表示从 到到 中间所有可能经过的城中间所有可能经过的城市集合，市集合，S S实际上是包含除实际上是包含除 与与 两个点之外其余两个点之外其余点的集合，但点的集合，但S S中的点的个数要随阶段数改变。中的点的个数要随阶段数改变。状态变量状态变量 表示：从表示：从 点出发经过点出发经过S S集集合中所有点一次最后到达合中所有点一次最后到达 。最优指标函数最优指标函数 为从为从 出发经由出发经由k k个城个城镇的镇的S S集合到集合到V Vi i的最短距离。的最短距离。1viv1viv),(Si1viv),(Sifk1v 决策变量决策变量 表示：从表示：从 经经k k个中间城镇个中间城镇的的S S集合到集合到 城镇的最短路线上邻接城镇的最短路线上邻接 的前一个的前一个城镇，则动态规划的顺序递推关系为城镇，则动态规划的顺序递推关系为：),(SiPk1viviv)21.7(),3,2,1,2,1(),()21.7(),(min),(101bninkdifadjSjfSifijikSjk为空集例例6 6 已知已知4 4个城市间距离如表个城市间距离如表716716，求从，求从v1v1出发，经其余城出发，经其余城市一次且仅一次最后返回市一次且仅一次最后返回v1v1的最短路径与距离。的最短路径与距离。表表7 16 vj 距 离 vi 1 2 3 4 1 0 6 7 9 2 8 0 9 7 3 5 8 0 8 4 6 5 5 0 解解 由边界条件（由边界条件（7.21b7.21b）知：）知：当当k=1k=1时，从城市时，从城市v v1 1出发，经过出发，经过1 1个城镇到达个城镇到达v vi i的的最短距离为：最短距离为：9),4(7),3(6),2(140130120dfdfdf 1587),3()3,4(1376),2()2,4(1459),4()4,3(1596),2()2,3(1459),4()4,2(1587),3()3,2(340124014301230142013201dffdffdffdffdffdff 当当k=2k=2时，从城市时，从城市v v1 1出发，经过出发，经过2 2个城镇到达个城镇到达v vi i的最短距离为：的最短距离为：20515,814min)3,4(,)4,3(min)4,3,2(4213212dfdff18513,914min)4,2,3(4)4,3,2(22fP22815,715min)3,2,4(4)4,3,2(22fP2)3,2,4(2P所以所以所以所以所以所以 当当k=3k=3时，从城市时，从城市v v1 1出发，经过出发，经过3 3个城镇到达个城镇到达v vi i的最短距离为：的最短距离为：,)4,2,3(,)4,3,2(min)4,3,2,1(3122123dfdff23622,518,820min)3,2,4(412 df3)4,3,2,1(3P所以所以 逆推回去，货郎的最短路线是逆推回去，货郎的最短路线是l2431l2431最短距离为最短距离为2323。货郎担问题当城市数目增加时，用动态规划货郎担问题当城市数目增加时，用动态规划方法求解，无论是计算量还是存贮量都会大大增方法求解，无论是计算量还是存贮量都会大大增加，所以本方法只适合于加，所以本方法只适合于n n较小情况。较小情况。个人观点供参考，欢迎讨论