第三节 背包装载问题及旅行推销员问题一、 背包装载问题问题：有一人带一背包旅行，其可携带物品重量限度为。现有编号为 1，2， 的 种物品供他选择。Mnn已知第 种物品每件重量为，价值携带数量的函数iiwix。问此人应如何选择携带物品，以使装货的价值)(iixc最大？ 动态规划求解方法首先建立模型设为第种物品的装入件数，则问题的数学模型ixi为nixMxwxcfiniiiniii, 2 , 1, 0)(max11L且为整数，这是整数规划问题，若，即变量取值仅为1ix，则称为“01”背包问题。现在我们用动态规划方法来求解背包问题。1按物品的个种类分为个阶段；nn2状态变量：表示用于装第 1 种至第种物品的ksk总重量；3决策变量：表示装入第种物品的件数；kxk4状态转移方程：kkkkwxss15允许决策集合： 0 )(kk kkkksxxsD式中的表示不超过的最大整数；kk wskk ws6最优指标函数：表示总重量不超过时，)(kksfks背包中可装入第 1 种至第种物品的最大价值，即k kixxcsfikiii sxwkkkikii, 2 , 1, 0)(max)(1 1 L且为整数，7递推关系：)(max)(2 , )()(max)(11/, 1 , 0111/, 1 , 01111 xcsfnkxwsfxcsfwsxkkkkkkwsxkk kkLL要求：)(Mfn求解过程：逐步计算及)(,),(),(2211nnsfsfsfL，最后得到和相应的最优策略。)(kksx)(Mfn例 用动态规划方法求解3 , 2 , 1, 010543654max321321ixxxxxxxfi且为整数，解：，问题就是求，递推关系10, 3Mn)10(3f为： )0(12),5(6),10(0max)510(6max)10(222323510, 1 , 033fffxfxfx L因此，求，需先计算。)10(3f)0(),5(),10(222fff )2(10),6(5),10(0max)410(5max)10(111212410, 1 , 022fffxfxfx L) 1 (5),5(0max)45(5max)5(1121245, 1 , 022ffxfxfx L)0()40(5max)0(121240, 1 , 022fxfxfx L为计算，又需先计算：)0(),5(),10(222fff)0(),1 (),2(),5(),6(),10(111111ffffff对我们有：1f 34)4(max)(13, 1 , 011sxsf sxL对应的最优决策为，因此得到： 31sx0 004)0(0 004) 1 (0 004)2(1 414)5(2 824)6(3 1234)10(111111111111xfxfxfxfxfxf从而有 0, 0 0)0()0(1, 0 505 , 4max ) 1 (5),5(max)5(1, 2 13010, 85 ,12max )2(10),6(5),10(max)10(211221112211112xxffxxfffxxffff最后得到： 0, 1, 213012, 56 ,13max)10(12),5(6),10(max)10(3212223 xxxffff即最优方案为，最大价值为 13。0, 1, 2* 3* 2* 1xxx多维背包问题“二维背包问题”的数学模型为：nixLxMxwxcfiniiiniiiniii, 2 , 1, 0)(max111L最优指标函数：表示当总重量不超过，),(wfkw总体积不超过时，背包中装入第一种到第种物品的k最大使用价值。则有：kixxwxwxcwfikiiikiiiniiikL, 2 , 1, 0)(max),(111递推关系为： 0),(1 ,),( )(max),(01),min(0wfnkxxwwfxcwfkkkkkkkwwxkkkk按上面递推关系求出，即为所求的最大价值，),(LMfn对应的策就是最佳携带方案。二、旅行推销员问题问题：设有个城市，以 1，2，表示。表nnijd示从城到城的距离。一个推销员从城 1 出发到ij其它每个城市一次且仅去一次，然后回到城 1。问应如何选择行走路线，才能使总的路程最短。动态规划解法1设推销员从城 1 开始，最终走到城,记i , 1, 1, 3 , 2niiNiLL表示由城 1 到城 的中间城市集合，i：到达城 之前中途所经过的城市集合，则Si有；SiN2状态变量：；),( Si3决策：一个城市走到另一个城市；4最优的指标函数：从城 1 出发经由 个中),( Sifkk间城市的集到城 的最短距离；Si5递推关系： iijiksjkdSifNSninkdjSjfSif101),(, 3 , 2 , 1, 2 , 1),(min),(LL6最优决策函数：表示从城 1 开始经个中),( Sipkk间城市的集到 城的最短路线上紧挨着城 前面的那个Sii城市。按上面递推关系可逐步求出最后求出，即,),( ),(21LSifSif), 3 , 2, 1 (1nfnL为最短距离。同时，由即可确定最优路线。),( Sipk例：求解四个城市的旅行推销员问题，各城之间的距离同例。设推销员从城 1 出发，经过每个城市一次且仅一次，最后回到城 1。问应如何选择行走路线，才能使总的行程距离最短？各城之间的距离城i1234城i1234025401121045140解：显然4), 2(120 df2), 3(130 df5), 4(140 df由递推关系知当时，即从城 1 出发，中间经过一个城市到城1k的最短距离是：i 642), 3()3, 4(514), 2()2, 4(514), 2()2, 4(945), 4()4, 3(514), 2()2, 3(615), 4()4, 2(312), 3()3, 2(3401240124014301230142013201dffdffdffdffdffdffdff当时，即从城 1 出,发，中间经过二个城市到达2k城的最短距离是：i 7 16 , 19min )3, 4(,)4, 3(min)4 , 3, 2(4213212 dfdff所以 4)4 , 3, 2(2p对应的走法为：1342同理 445 , 13min)3 , 2, 4(745 , 16min)4 , 2, 3(22 ff1423 2)4 , 2, 3(2p1324 2)3 , 2, 4(2p当时，即从城 1 出发，中间经过三个城市回到3k城 1 最短距离为： 954 , 27 , 47min )3 , 2, 4( ,)4 , 2, 3( ,)4 , 3, 2(min)4 , 3 , 2, 1 (4123122123dfdfdff相应地得： 43)4 , 3 , 2, 1 (3或p由此可知，推销员的最短旅行路线为：13241或14231最短总距离为 9。还有哪些问题可以归结为旅行推销员问题？如运输路线中，怎样安排运输工具的行走路线才能使总行程距离最短；城市里在这一些地方铺设管道时，管子应走怎样的路线才能使所用管子最少等。第四节 动态规划在电力系统中的应用示例一、设备更新问题在实际问题中，经常会遇到设备陈旧或部分损坏后何时需要更新的问题。现以一台机器为例，随着使用时间的增加，机器的故障率增加，收入减少，维修、运行费用增加。而且机器使用年限越长，它本身的剩余价值就越小，因而更新时所需的净支出费用就越多。1：在第 年、役龄为 年的一台机器运行所)(tIjjt得到的收入；2：在第 年、役龄为 年的一台机器运行时)(tOjjt所需要的运行费用；3：在第年、役龄为 年的一台机器更新时)(tCjjt的净更新费用；4：折扣因子表示一年以后的单位收入a) 10( a价值相当现年的单位；a5：在第一年开始时，正在使用的机器的役龄；T6：计划的年限数；n7：在年开始使用一个役龄为 年的机器，)(tgjjt从第 年至第年末的最大收入；jn8：决策变量，表示在第年开始时，对一台)(txjj役龄为 年的机器保留还是更新。t8寻找递推关系若在第 年开始时购买了新机器，则从第 年至第jj年得到的总收入应等于在第 年由新机器获得的收入，nj减去第 年中的运行费用，减去在第 年开始时役龄为jj年的机器的净更新费用，加上在第年开始使用役t1k龄为 1 年的机器从第年至第 年的最大收入；若在第1jn年开始时继续使用役龄为 年的机器，则从第 年至第jtj年的总收入应等于在第 年由役龄为 年的机器得到的njt收入，减去它的运行费用，加上在第年开始使用役1j龄为年的机器从第年至第 年的最大收入。然后，1t1jn比较它们的大小，选取大的，从而得出是更新还是保留的决策。递推关系为1 , 1, 2 , 1 , 2 , 1 ) 1()()(:) 1 ()()0()0(:max)(11TjjtnjtagtOtIKagtCOIRtgjjjjjjjjLL式中：表示保留；表示更新。KR对年的计划，可要求：n0)(1tgn按上面递推关系可逆推求解，确定相应的最优策略。例 1 设某电厂有一台已工作了 10 年的发电机，不考虑资金的贴现问题，即。试制订五年中的设备1a更新策略，使五年内的总收入达到最大，各有关数据见下表。已 知 数 据产品年代第一年第二年第三年第四年第五年10 年前机器役龄（年）01234012 30120101011121314收入（万元）2221201816272524222926243028321816161414运行费用（万元）668810568 9556454889910更新费用（万元）2729323437293134363132333233343234363638解：1清楚各个符号的含义，及相应的费用、收入。如：第年开始机龄为 年的机器，其制造时间为jt第年或 10 年前，从而各种费用、收入应第年或tj tj 10 年前产品计算。如为第五年新发电机的收入，故)0(5I，为第