动态规划例1求解下列整数规划的最优解要点.pdf

例 1 求解下列整数规划的最优解： 123 123 max456 34510 01,2,3 , jj Zxxx xxx st xjx 为整数 . 解 （1）建立动态规划模型： 阶段变量：将给每一个变量 j x赋值看成一个阶段，划分为3 个阶段，且阶段变量k=1,2,3. 设状态变量 k s表示从第k阶段到第3 阶段约束右端最大值，则10. j s 设决策变量 k x表示第k阶段赋给变量 k x的值(1,2,3)k. 状态转移方程： 211322 3,4.ssx ssx 阶段指标： 111122223333 (,)4,(,)5,(,)6.u s xx usxx usxx 基本方程； 3 11 3,2,10 44 ()max, ()0. s k kkkkkkk k kx a fsusxfs fs 其中 123 3,4,5.aaa （1）用逆序法求解： 当 3k 时， 33 333443 33 00 55 max6max6, ss xx fsxfsx 而 3 0,1,2,3,4,5,6,7,8,9,10.sx表示不超过x的最大整数。 因此，当 3 0,1,2,3, 4s时， 3 0x； 当 3 5 , 6 7 , 8 9s时， 3 x可取 0 或 1； 当 3 10s时， 3 x可取 0， 1， 2， 由此确定 33 .fs 现将有关数据列入表4.1 中 表 4.1 中 . 344 6()xfs 33 ()fs * 3 x 0 1 2 0 1 2 3 4 5 6 0 0 0 0 0 0 0 6 6 0 0 0 0 0 6 6 0 0 0 0 0 1 1 f 3 x 3 s 7 8 9 10 0 0 0 0 6 6 6 6 12 6 6 6 12 1 1 1 2 当2k时，有 22 222332322 22 00 44 max5max54, ss xx fsxfsxfsx 而 2 0,1,2,3,4,5,6,7,8,9,10s。所以当 2 0,1, 2,3s时， 2 0x；当 2 4,5, 6, 7s时， 2 01x或；当 2 8,9,10s时 2 0,1,2x。由此确定 22 fs。现将有关数据列入表4.2 中. 表 4.2 f 2322 5(4)xfsx 33 ()fs * 3 x 3 s 0 1 2 0 1 2 3 4 5 6 7 8 9 10 0+0 0+0 0+0 0+0 0+0 0+6 0+6 0+6 0+6 0+6 0+12 5+0 5+0 5+0 5+0 5+0 5+6 5+6 10+0 10+0 10+0 0 0 0 0 5 6 6 6 10 11 12 0 0 0 0 1 0 0 0 2 1 0 0 1 2 3 0 5 6 7 0 5 10 当1k时,有 11 111221211 11 00 33 max4max43, ss xx fsxfsxfsx 而 1 10,s故 1 x只能取 0,1,2,3,由此确定 11 fs。现将有关数据列入表4.3 中。 表4.3 1211 43xfsx 11 fs * 1 x 2 s 0 1 2 3 10 0+12 4+6 8+5 12+0 13 2 4 按计算顺序反推，由表4.3可知,当 1122 2()13.44.21,xssx 1 时,f取得最大值又由查表得及 2 x 2 s f 1 x 1 s 33 33 0,4.10. 2,1,0,max13. sx xxZ 3 再由表查得因此 ,最优解为 x最优解 例 5 用动态规划方法解下列非线性规划问题 3, 2, 10 max 321 3 2 21 ix cxxx xxxz i 解：解决这一类静态规划问题，需要人为地赋予时间概念，从而将该问题 转化为多阶段决策过程。 按问题的变量个数划分阶段，把它看作一个三阶段决策问题，k=1，2，3 设状态变量为 s1，s2，s3，s4并记 s1c 取问题中的变量x1，x2，x3为决策变量 状态转移方程为：s3=x3s3+x2=s2s2+x1=s1c 允许决策集合为：x3=s30x2s20x1s1 各阶段指标函数为： v1（x1）=x1v2（x2）=x22v3（x3）=x3，各指标函 数以乘积方式结合，最优指标函数fk（sk）表示从第 k 阶段初始状态 sk出发到第 3 阶段所得到的最大值，则动态规划基本方程为： 1)( 1 , ,2, 3)()(max)( 44 11 )( sf ksfxvsf kkkk sDx kk kkk 用逆序解法由后向前依次求解： k=3 时， 334433 )( 33 )(max)()(max)( 33333 sxsfxvsf sxsDx x3 *=s 3 k=2 时， )(max)(max)()(max)( 22 2 2 0 3 2 2 0 3322 )( 22 2222222 xsxsxsfxvsf sxsxsDx 令 h2（s2，x2）=x22（s2x2） 用经典解析法求极值点： 032 2 222 2 2 xsx dx dh 解得： 22 3 2 sxx2=0（舍） 22 2 2 2 2 62xs dx hd 02 3 22 22 2 2 2 2 s sxdx hd 所以 22 3 2 sx是极大值点。 3 222 2 222 27 4 ) 3 2 () 3 2 ()(sssssf 2 * 2 3 2 sx k=1 时， )( 27 4 max) 27 4 (max)()(max)( 3 111 0 3 21 0 2211 )( 11 1111111 xsxsxsfxvsf sxsxsDx 令 3 111111 )( 27 4 ),(xsxxsh 0)1()( 27 12 )( 27 42 111 3 11 1 1 xsxxs dx dh 解得： 11 4 1 sxx1=s1（舍） )2)( 27 24 )( 27 24 )( 27 12 ) 1()( 27 12 1111111 2 11 2 11 2 1 1 2 sxxsxsxxsxs dx hd 0 27 9 4 1 2 1 11 2 1 1 2 s sxdx hd 所以 11 4 1 sx是极大值点。 4 1 3 11111 64 1 ) 4 1 ( 27 4 4 1 )(sssssf 1 * 1 4 1 sx 由于 s1未知，所以对 s1再求极值， ) 64 1 (max)(max 4 1 0 11 0 11 ssf cscs 显然 s1=c 时，f1（s1）取得最大值 4 11 64 1 )(csf 反向追踪得各阶段最优决策及最优值： s1=ccsx 4 1 4 1 1 * 1 4 11 64 1 )(csf cxss 4 3* 112 csx 2 1 3 2 2 * 2 33 222 16 1 27 4 )(cssf cxss 4 1 * 223 csx 4 1 3 * 3 cssf 4 1 )( 333 所以最优解为： 4* 3 * 2 * 1 64 1 , 4 1 , 2 1 , 4 1 czcxcxcx 例 6 用动态规划方法解下列非线性规划问题 3,2, 10 6 max 321 3 32 2 1 jx xxx xxxz j 解：按变量个数将原问题分为三个阶段，阶段变量k=1，2，3； 选择 xk为决策变量； 状态变量 sk表示第 k 阶段至第 3 阶段决策变量之和； 取小区间长度 =1，小区间数目 m=6/1=6，状态变量 sk的取值点为： 6 26, 5, 4, 3, 2, 1 , 0 1 s ksk 状态转移方程： sk+1=skxk； 允许决策集合： Dk（sk）=xk| 0xkskk=1，2，3 xk，sk均在分割点上取值； 阶段指标函数分别为： g1（x1）=x1 2 g2（x2）=x2g3（x3）=x3 3， 最优指标函数 fk（sk）表示从第 k 阶段状态 sk出发到第 3 阶段所得到的最大值， 动态规划的基本方程为： 1)( 1 ,2, 3)()(max)( 44 11 0 sf ksfxgsf kkkk sx kk kk k=3 时， 3 3 3 333 )(max)( 33 sxsf sx s3及 x3取值点较多，计算结果以表格形式给出，见表6.1-6.3 所示。 表 6.1 计算结果 x3 f3(s3) x3 * 0 1 2 3 4 5 6 0 1 2 3 4 5 6 0 1 8 27 64 125 216 0 1 8 27 64 125 216 0 1 2 3 4 5 6 表 6.2 计算结果 x2f3(s2x2) f2(s2) x2 * 0 1 2 3 4 5 6 f x3 s3 f x2 s2 0 1 2 3 4 5 6 0 0 0 0 0 0 0 1×0 1×1 1×8 1×27 1×64 1×125 2×0 2×1 2×8 2×27 2×64 3×0 3×1 3×8 3×27 4×0 4×1 4×8 5×0 5×1 6×0 0 0 1 8 27 64 128 0 0,1 1 1 1 1 2 表 6.3计算结果 x1 2 f2(s1x1) f1(s1) x1 * 0 1 2 3 4 5 6 6 0 1×64 4× 27 9×8 16×1 25×0 36×0 108 2 由表 6.3 知，x1*=2，s1=6，则 s2= s1x1*=62=4，查表 6.2 得：x2*=1，则 s3= s2x2 *=41=3， 查表 6.1 得： x 3 *=3， 所以最优解为：x 1 *=2， x 2 * =1， x3 * =3， f1(s1)=108。 上面讨论的问题仅有一个约束条件。对具有多个约束条件的问题，同样可以 用动态规划方法求解，但这时是一个多维动态规划问题，解法上比较繁琐一些。 例 7 某公司打算在 3 个不同的地区设置4个销售点，根据市场部门估计， 在不同地区设置不同数量的销售点每月可得到的利润如表6.4 所示。试问在各地 区如何设置销售点可使每月总利润最大。 表 6.4利润值 地区 销售点 0 1 2 3 4 1 2 3 0 0 0 16 12 10 25 17 14 30 21 16 32 22 17 解： 如前所述，建立动态规划数学模型： 将问题分为 3 个阶段， k=1，2，3； 决策变量 xk表示分配给第 k 个地区的销售点数； 状态变量为 sk表示分配给第 k 个至第 3 个地区的销售点总数； 状态转移方程： sk+1=skxk，其中 s1=4； 允许决策集合： Dk（sk）=xk| 0xksk 阶段指标函数： gk（xk）表示 xk个销售点分配给第k 个地区所获得的利润； 最优指标函数 fk（sk）表示将数量为sk的销售点分配给第k 个至第 3 个地区 所得到的最大利润，动态规划基本方程为： 0)( 1 ,2, 3)()(max)( 44 1 0 sf kxsfxgsf kkkkk sx kk kk f x1 s1 数值计算如表所示。 表 6.5 k=3时计算结果 g3（x3） f3(s3) x3 * 0 1 2 3 4 0 1 2 3 4 0 10 14 16 17 0 10 14 16 17 0 1 2 3 4 表 6.6 k=2时计算结果 g2(x2)+f3(s2x2) f2(s2) x2* 0 1 2 3 4 0 1 2 3 4 0 0+10 0+14 0+16 0+17 12+0 12+10 12+14 12+16 17+0 17+10 17+14 21+0 21+10 22+0 0 12 22 27 31 0 1 1 2 2,3 表 6.7k=1时计算结果 g1(x1)+f2(s1x1) f1(s1) x1 * 0 1 2 3 4 4 0+31 16+27 25+22 30+12 32+0 47 2 所以最优解为： x1*=2，x2*=1，x3*=1，f1(4)=47，即在第 1 个地区设置 2 个销 售点，第 2 个地区设置 1 个销售点， 第 3 个地区设置 1 个销售点， 每月可获利润 47。 例 9（生产库存问题 ） 某工厂要对一种产品制定今后四个时期的生产计划，据估计在今后四个时期 内，市场对该产品的需求量分别为2，3，2，4 单位，假设每批产品固定成本为 3 千元，若不生产为0，每单位产品成本为1 千元，每个时期最大生产能力不超 过 6 个单位，每期期末未出售产品，每单位需付存贮费0.5 千元，假定第 1 期初 和第 4 期末库存量均为 0，问该厂如何安排生产与库存，可在满足市场需求的前 提下总成本最小。 解: 以每个时期作为一个阶段，该问题分为4 个阶段， k=1，2，3，4； 决策变量 xk表示第 k 阶段生产的产品数； f x3 s3 f x2 s2 f x1 s1 状态变量 sk表示第 k 阶段初的库存量； 以 dk表示第 k 阶段的需求，则状态转移方程：sk+1=sk+xkdk；k=4，3，2，1 由于期初及期末库存为0，所以 s1=0，s5=0； 允许决策集合 Dk（sk）的确定：当 skdk时，xk可以为 0，当 skdk时，至少 应生产 dksk，故 xk的下限为 max（0，dksk）每期最大生产能力为6，xk最大 不超过 6，由于期末库存为0，xk还应小于本期至4 期需求之和减去本期的库存 量， k kj j sd 4 ，所以 xk的上限为 min（ k kj j sd 4 ，6） ，故有： Dk（sk）=xk| max（0，dksk）xkmin（ k kj j sd 4 ，6） 阶段指标函数 rk（sk，xk）表示第 k 期的生产费用与存贮费用之和： 6, 5, 4, 3, 2, 15. 03 05 .0 ),( kkk kk kkk xsx xs xsr 最优指标函数 fk（sk）表示第 k 期库存为 sk到第 4 期末的生产与存贮最低费 用，动态规划基本方程为： 0)( 1 ,2, 3 ,4)(),(min)( 55 11 )( sf ksfxsrsf kkkkk sDx kk kkk 先求出各状态允许状态集合及允许决策集合，如表6.8 所示。 表 6.8 状态允许状态集合及允许决策集合 s1 0 D1(s 1) 2,3,4,5,6 s20 1 2 3 4 D2(s 2) 3,4,5,6 2,3,4,5,6 1,2,3,4,5, 6 0,1,2,3,4,5, 6 0,1,2,3,4, 5 s30 1 2 3 4 5 6 D3(s 3) 2,3,4,5,6 1,2,3,4,5 0,1,2,3,4 0,1,2,30,1,2 0,1 0 s40 1 2 3 4 D4(s 4) 4 3210 由基本方程计算各阶段策略，结果如下表所示。 表 6.9k=4时计算结果 s4x4 05.03 05 .0 ),( 444 44 444 xsx xs xsrs5f5(s5) f4(s4) 0 1 2 4 * 3 * 2 * 7 6.5 6 0 0 0 0 0 0 7 * 6.5 * 6 * 3 4 1 * 0 * 5.5 2 0 0 0 0 5.5 * 2 * 表 6.10 k =3时计算结果 s3x3 05.03 05.0 ),( 333 33 333 xsx xs xsrs4= s3+ x32 f4(s4) f3(s3) 0 2 3 4 5 6 * 5 6 7 8 9 0 1 2 3 4 7 6.5 6 5.5 2 12 12.5 13 13.5 11 * 1 1 2 3 4 5 * 4.5 5.5 6.5 7.5 8.5 0 1 2 3 4 7 6.5 6 5.5 2 11.5 12 12.5 13 10.5 * 2 0 * 1 2 3 4 1 5 6 7 8 0 1 2 3 4 7 6.5 6 5.5 2 8 * 11.5 12 12.5 10 3 0 * 1 2 3 1.5 5.5 6.5 7.5 1 2 3 4 6.5 6 5.5 2 8 * 11.5 12 9.5 4 0 * 1 2 2 6 7 2 3 4 6 5.5 2 8* 11.5 9 5 0 * 1 2.5 6.5 3 4 5.5 2 8 * 8.5 6 0 * 3 4 2 5 * 表 6.11 k =2时计算结果 s2x2 05.03 05 .0 ),( 222 22 222 xsx xs xsrs3= s2+ x23 f3(s3) f2(s2) 0 3 4 5* 6 6 7 8 9 0 1 2 3 11 10.5 8 8 17 17.5 16* 17 1 2 3 4* 5 6 5.5 6.5 7.5 8.5 9.5 0 1 2 3 4 11 10.5 8 8 8 16.5 17 15.5* 16.5 17.5 2 1 2 3* 4 5 5 6 7 8 9 0 1 2 3 4 11 10.5 8 8 8 16 16.5 15* 16 17 6 10 5 8 18 3 0* 1 2 3 4 5 6 1.5 5.5 6.5 7.5 8.5 9.5 10.5 0 1 2 3 4 5 6 11 10.5 8 8 8 8 5 12.5* 16 14.5 15.5 16.5 17.5 15.5 4 0* 1 2 3 4 5 2 6 7 8 9 10 1 2 3 4 5 6 10.5 8 8 8 8 5 12.5* 14 15 16 17 15 表 6.12 k =1 时计算结果 s1x1 05.03 05 .0 ),( 111 11 111 xsx xs xsrs2= x12 f2(s2) f1(s1) 0 2 3 4 5 * 6 5 6 7 8 9 0 1 2 3 4 16 15.5 15 12.5 12.5 21 21.5 22 20.5 * 21.5 逆向追踪可得： x1 *=5，s 2=3，x2 *=0，s 3=0，x3 * =6，s4=4，x4 *=0，即第 1 时期 生产 5 个单位，第 3 时期生产 6 个单位，第 2，4 时期不生产，可使总费用最小， 最小费用为 20.5 千元。 例 10 （库存销售问题 ） 设某公司计划在1 至 4 月份从事某种商品经营。已知仓库最多可存储600 件这种商品， 已知 1 月初存货 200 件，根据预测知 1 至 4 月份各月的单位购货成 本及销售价格如表6.13 所示，每月只能销售本月初的库存，当月进货供以后各 月销售，问如何安排进货量和销售量，使该公司四个月获得利润最大（假设四月 底库存为零）。 表 6.13单位购货成本及销售价格 月份购货成本 C销售价格 P 1 2 3 4 40 38 40 42 45 42 39 44 解: 按月份划分阶段， k=1，2，3，4； 状态变量 sk表示第 k 月初的库存量， s1=200，s5=0； 决策变量：xk表示第 k 月售出的货物数量， yk表示第 k 月购进的货物数量； 状态转移方程： sk+1=sk+ykxk； 允许决策集合： 0xksk，0yk600（skxk） ； 阶段指标函数为： pkxkckyk表示 k 月份的利润，其中pk为第 k 月份的单位 销售价格， ck为第 k 月份的单位购货成本； 最优指标函数 fk（sk）表示第 k 月初库存为 sk时从第 k 月至第 4 月末的最大 利润，则动态规划基本方程为： 0)( 1 ,2, 3, 4)(max)( 55 11 )(6000 0 sf ksfycxpsf kkkkkk xsy sx kk kkk kk k=4 时， 444 )(6000 0 44 44)4244(max)( 444 44 syxsf xsy sx x4 *=s 4y4 *=0 k=3 时， )4544(max )(444039max )(4039max)( 333 )(6000 0 33333 )(6000 0 4433 )(6000 0 33 333 33 333 33 333 33 yxs xysyx sfyxsf xsy sx xsy sx xsy sx 为求出使 44s35x3+4y3最大的 x3，y3，须求解线性规划问题： 0, 600 4544max 33 333 33 333 yx syx sx yxsz 只有两个变量 x3，y3，可用图解法也可用单纯形法求解，取得最优解，x3*=0， y3 * =600s3，f3（s3）=40s3+2400 k=2 时， )24002240(max 2400)(403842max )(3842max)( 222 )(6000 0 22222 )(6000 0 3322 )(6000 0 22 222 22 222 22 222 22 yxs xysyx sfyxsf xsy sx xsy sx xsy sx 类似地求得： x2*=s2，y2*=600，f2（s2）=42s2+3600 k=1 时， )36002342(max 3600)(424045max )(4045max)( 111 )(6000 0 11111 )(6000 0 2211 )(6000 0 11 111 11 111 11 111 11 yxs xysyx sfyxsf xsy sx xsy sx xsy sx 类似地求得： x1*=s1，y1*=600，f1（s1）=45s1+4800=13800 逆向追踪得各月最优购货量及销售量： x1 *=s 1=200 y1 *=600； x2 *=s 2=s1+ y1 *x 1 *=600 y2 *=600； x3 * =0 y3 * =600s3=600（s2+ y2 * x2 * ）=0 x4 *=s 4=（s3+ y3 * x3 *）=600 y4 *=0 即 1 月份销售 200件，进货 600 件，2 月份销售 600 件，进货 600 件，3 月 份销售量及进货量均为0， 4 月份销售 600 件， 不进货，可获得最大总利润13800。 例 11 某鞋店销售一种雪地防潮鞋，以往的销售经历表明，此种鞋的销售季 节是从 10 月 1 日至 3 月 31 日。下个销售季节各月的需求预测值如表6.14所示。 表 6.14 需求预测值(单位：双 ) 月份10 11 12 1 2 3 需求40 20 30 40 30 20 该鞋店的此种鞋完全从外部生产商进货，进货价每双 4 美元。进货批量的基 本单位是箱，每箱10 双。由于存贮空间的限制，每次进货不超过5 箱。对应不 同的订货批量，进价享受一定的数量折扣，具体数值如表6.15 所示。 表 6.15 数量折扣数值表 进货批量1 箱2 箱3 箱4 箱5 箱 数量折扣4% 5% 10% 20% 25% 假设需求是按一定速度均匀发生的，订货不需时间， 但订货只能在月初办理 一次，每次订货的采购费（与采购数量无关）为10 美元。月存贮费按每月月底 鞋的存量计，每双 0.2 美元。由于订货不需时间，所以销售季节外的其他月份的 存贮量为“ 0” 。试确定最佳的进货方案，以使总的销售费用最小。 解：阶段：将销售季节6 个月中的每一个月作为一个阶段，即6 ,2 ,1k； 状态变量：第 k 阶段的状态变量 kS代表第 k 个月初鞋的存量； 决策变量：决策变量 k x代表第 k 个月的采购批量； 状态转移律： kkkk dxSS 1 （ k d是第 k 个月的需求量）； 边界条件： 0 71 SS，0)( 77 Sf； 阶段指标函数：),( kkk xSr代表第 k 个月所发生的全部费用， 即与采购数量无 关的采购费 k C、与采购数量成正比的购置费 k G和存贮费 k Z.其中： 0,10 0,0 k k k x x C； kxk xpG；)(2.0 kkkk dxSZ 最优指标函数：最优指标函数具有如下递推形式 )(min)( 11kkkkk x kk SfZGCSf k )()(2 .0min 1kkkkkkkkk x dxSfdxSGC k 当6k时（3 月） ： 表 6.16 6k时计算结果 S60 10 20 x620 10 0 f6（S6） 86 48 0 当5k时（2 月） ： 表 6.17 5k时计算结果 x5 S5 0 10 20 30 40 50 5 x)( 55 Sf 0 204 188 164 50 164 10 172 168 142 40 142 20 134 136 122 30 122 30 86 98 90 0 86 40 50 52 0 50 50 4 0 4 当4k时（1 月） ： 表 6.18 4k时计算结果 x4 S4 0 10 20 30 40 50 4 x)( 44 Sf 0 302 304 40 302 10 282 282 286 30、40 282 20 250 262 264 252 20 250 30 212 230 244 230 218 10 212 40 164 192 212 210 196 170 0 164 50 144 174 178 176 152 0 144 60 126 140 144 132 0 126 当3k时（12 月） ： 表 6.19 3k时计算结果 x3 S3 0 10 20 30 40 50 3 x)(33Sf 0 420 422 414 50 414 10 388 402 392 384 50 384 20 350 370 372 362 332 50 332 30 302 332 340 342 310 314 0 302 40 284 302 310 290 292 298 0 284 当2k时（11 月） ： 表 6.20 2k时计算结果 x2 S2 0 10 20 30 40 50 2 x)( 22 Sf 0 500 504 474 468 50 468 10 462 472 454 446 452 40 446 当 1k 时（10 月） ： 表 6.21 1k时计算结果 x1 S1 0 10 20 30 40 50 1 x)( 11 Sf 0 606 608 40 606 利用状态转移律，按上述计算的逆序可推算出最优策略：10 月份采购 4 箱 （40双） ，11 月份采购 5 箱（50 双） ，12 月份不采购， 1 月份采购 4 箱（40 双） ， 2 月份采购 5 箱（50 双） ，3 月份不采购；最小的销售费用为606美元。 例 13 某工厂生产三种产品，各产品重量与利润关系如表6.24 所示，现将 此三种产品运往市场销售， 运输能力总重量不超过6 吨，问如何安排运输使总利 润最大？ 表 6.24重量与利润关系表 种类1 2 3 单位重量（吨）2 3 4 单位利润（元）80 130 180 解：设 xi为装载第 i 种货物的件数， i=1，2，3，该问题数学模型为： )3 ,2 , 1(0 6432 18013080max 321 321 ix xxx xxxz i 且为整数 按前述方法建立动态规划模型； k=3 时， )180(max)( 3 4 , 1 ,0 33 3 3 xsf s x 计算结果如表 6.25 所示。 表 6.25 k=3 时计算结果 c3(x3) f3(s3) x3* 0 1 0,1,2,3 4,5,6 0 0 180 0 180 0 1 k=2 时， f x3 s3 )3(130max )(130max)( 2232 3 , 1,0 332 3 , 1 ,0 22 2 2 2 2 xsfx sfxsf s x s x 计算结果如表 6.26 所示。 表 6.26 k=2 时计算结果 c2(x2)+ f3(s23 x2) f2(s2) x2 * 0 1 2 0,1,2 3 4,5 6 0+0 0+0 0+180 0+180 130+0 130+0 130+0 260+0 0 130 180 260 0 1 0 2 k=1 时， )2(80max )(80max)( 1121 3,2, 1 ,0 221 3,2, 1 ,0 11 1 1 xsfx sfxsf x x 计算结果如表 6.27 所示。 表 6.27 k=1 时计算结果 c1(x1)+ f2(s12 x1) f1(s1) x1* 0 1 2 3 6 0+260 80+180 160+0 240+0 260 0,1 反向追踪得最优方案： x1*=0，x2*=2，x3*=0；最优方案： x1*=1，x2*=0， x3 * =1最大总利润为 260元。 f x2 s2 f x1 s1