天然肠衣搭配的优化模型

1、天然肠衣搭配的优化模型作者:日期:天然肠衣搭配的优化模型与算法设计天然肠衣（以下简称肠衣制作加工是我国的一个传统产业，出口量占世界 首位。肠衣经过清洗整理后被分割成长度不等的小段原料，进入组装工序。 传统的生产方式依靠人工，边丈量原料长度边心算，将原材料按指定根数和总长 度组装出成品捆。原料按长度分档,通常以0.5米为一档，如:3-3.4米按3米计算,3.5米-3. 9米 按3.5米计算，其余的依此类推。表1是几种常见成品的规格，长度单位为米， 表示没有上限，但实际长度小于26米。表1成品规格表最短长度取大长度根数总长度36.52 089713. 588 914OO58 9为了提高生产效率，公

2、司方案改变组装工艺，先丈量所有原料，建立一个原料 表。表2为某批次原料描述。表2原料描述表长度3 3 .43. 5- 3.94 -4.44. 5 4.95 -5.45.5- 5 .96-6.46 .56 .9根数43593 94127283 42110. 5 -长度7-7.47. 5 -7.98- 8 .48. 5- 8 .99-9. 49 .5-9.910-10.41 0.9根数242 4202 521232 11811 . 5-11 2.5 114. 5长度11-11.41. 91 2 -12.42 .913-13 . 414-14.4-14.9根数31232 2591 825352915

3、-115. 5 -11 6- 11 6 . 5118.5 1长度5 .45 .96.4-16 . 917-17.47.5-17 . 918-18.48 .9根数3 04 22842454 9506419-19.19 . 5 -2 1 -21.21. 522 222.5 2长度419.920 20.420.5-20 . 94-21.92 .42 .9根数5 2634 93 527161222 3 -23.23.5- 2 3.24- 2 4 .24. 5 24.长度49492 5-25.4根数060001根据以上成品和原料描述，设计一个原料搭配方案 ，工人根据这个方案“照 方抓药进展生产。公司对搭

4、配方案有以下具体要求：1）对于给定的一批原料，装出的成品捆数越多越好 ；2)对于成品捆数一样的方案，最短长度最长的成品越多，方案越好；(3) 为提高原料使用率，总长度允许有土 0 .5米的误差，总根数允许比标准 少1根；(4) 某种规格对应原料如果出现剩余，可以降级使用。如长度为14米的原 料可以和长度介于7 - 13 .5米的进展捆扎，成品属于7-13 .5米的规格；(5) 为了食品保鲜，要求在30分钟内产生方案。请建立上述问题的数学模型，给出求解方法，并对表1、表2给出的实际数据 进展求解，给出搭配方案。解答：我们将上种类型的成品分别称作规格1、规格2、规格3。其定义见表1。表1 成品规格

5、表规格类型最短长度最大长度根数总长度136. 5208 92713 . 588 9314OO58 9由于满足规格3的的原料可以降级作规格 2,满足规格2的的原料可以降级作规格1。因此我们先考虑规格3产品的搭配，再考规格2产品的搭配,最后考虑规格1产品的 搭配。一、考虑规格3产品的搭配设长度为 1 4 , 1 4 . 5,1 5，15 .5，1 6 ,16 .5，17，17. 5 ,1 8 ,18 . 5,19,1 9.5,20,20 . 5,21 ，2 1 .5,22，22.5 ，23 . 5 ,25.5 的2 0种肠衣分成K组，设第i种长度的原料分到第j组为Xjj根。设第i种长度的原料有a,

6、根，i 1,2，,24。其中 a =3 5 , 29,30，4 2，2 8 ,42,45,49， 50，64，5 2,63,49 ,35,27,16,12 ,2,6， 1o第i种长度的原料分到所有K组的根数不能超过 ai根。那么有：KXaii 1,2,.,20j 1每组的根数为5根，由(3 )知也可以为4根，因此对每组的根数满足：204Xj5j 1,2,., Ki 1设第i种长度的原料的长度为h米。其中 |=14,14.5,15,15 .5，16,16.5,17,1 7 . 5，18,18.5,19,19.5,2 0 ,2 0 .5,2 1,21.5,22,22.5 ,2 3. 5,2 5 .

7、5。每组的长度为89米，由 知可以±0.5米的误差，因此每组的总长度满足：2088.5 1凶 89.5j 1,2,., Ki 1为考虑规格2利用规格 3中的剩余，我们求出规格3中每种长度原料的剩余。设第i种长度的原料的剩余根数为ri 1,2,.,20。那么有：Kri aiXjj 1我们建立目标函数。要求对于给定的一批原料，装出的成品捆 数越多越好，因此我们的第一目标为：max 乙 K要求对于成品捆数一样的方案，最短长度最长的成品越多，方案越好。 我们设法建立第二目标。令jmini |Xj0,i 1,2，,20 , j 1,2,., K。该序列表示各列最短长度的序号。令u mx j，表

8、示所有组中最短长度的序号最大值。令S j| j u,表示取得最短长度最大值的序号集。第二目标函为各列最短长度最大的捆数最多，那么有 ：maxZ2S其中S表示集合S的元素个数为说明我们的方法，下面采用一个例子说明。如某分配方案如表 2,其中ai为单调增序列。表2 分配方案例如长度第1组第2组第3组第4组第5组第6组a200000600002as823006a4756435287228562553那么有各列最短长度的行序号=1,3 , 3, 4,4 ,2,其最大值u 4 , 中取得最大值的序号S 4,5。那么计算出Z2 S 2即该分配方案中最短长度最长为a4,总共有2捆成品。因此总的模型为：max

9、 Z1 KmaxZ2 SKXj3ii 1,2,., 20j i204 Xj 5 j 1,2,., Ki 12088.5 lixij 89.5j 1,2,., Ki 1StKA axji 1,2,., 20j 1jmini | xij 0, i 1,2,., 20u max ij j5 j| j uXj取整,i1,2,., 20; j 1,2,., K其中丨=14,14.5,15,1 5.5,16, 16.5 , 17 , 1 7 .5 , 18,18.5,19,19.5,2 0, 2 0 .5,2 1 ,21. 5 ,2 2 ,2 2 . 5,2 3. 5 ,25.5。a = 35,29,3

10、0,42 , 28,42,45, 49, 5 0,64 , 5 2 ,63,4 9,35,2 7,16,12, 2,6,1该模型求解困难。 在确定第一目标 K最大时，需要尝试不同的 K,而在给定K进展求 解时，利用 L in go12 求解极其耗时，通常会1小时以上。而在求解第二目标，由于是非线性，求解就更困难，采用Lin go 几乎没法求解，即使求解成功 ，也是局部最优解。鉴于此 ，我们采用 另外的方法建模求解。先对问题进展分析:1）最大捆数分析：202 0种原材料中长度为Lai.li = 1215 9 .5米i 1每捆长度最少为8 8.5米，因此捆数最多为：K 12195.5/88.513

11、7.41372020种原材料的总根数为 T a =6 7 7根i 1每捆最少为4根，因此捆数最多为K 677/4169.25 169根。二者取最小值，因此 K 137。2)每捆成品的组成模式分析每捆成品可以有不同的构成模式，每种模式由一个向量(捲山2,.,乂20)构成。Xj代表第i种材料的根数。那么各xi取值范围满足：89.50 x minq, ,5 i 1,2,.,20li计算得到各x(i 1,2,.,20 )的最大取值为：5,5,5,5 ,5,5, 5 ,5,4,4 , 4, 4,4, 4, 4, 4 ,4, 2, 3,1。3求出所有模式如果直接对各xi从0到其最大取值进展完全枚举所有符合

12、条件的模式，计算量为：(5 1)8(4 1)9(2 1)(3 1)(1 1)7 .8 7 1013。该结果很难进展枚举。因此我们采用另外的方法得到所有符合条件的模式。根据 5=4+ 1 = 3+2 = 3+ 1 +仁2 +2 +1= 2+ 1 + 1+1 = 1 + 1 + 1+1+14=3 +1= 2 +2 = 2+1+ 仁1 + 1 + 1 + 1因此从根数每捆为 4根或5根来看，最多有1 2种方式。上式的意义解释：如4+ 1 ,表示第i种材料为4根，第j种材料为1根，满足长度为8 8 .589.5米的所有构成方式(i,j不相等)。2 +2+1,表示第i种材料为2根，第j种材料为2根，第k

13、种材料为 1根，满足长度为88 .5 8 9 .5米的所有构成方式i, j,k互不相等)。由于5根或4根某种材料都不可能单独构成长度为88.5或8 9或8 9 .5米，因此这两种模式舍去，只剩下10种模式。其总计算量为：4+ 1 ,3+ 1,3+ 2方式计算量 3n*n3+1 + 1， 2+ 1 +1,2+2+13 n n- 1 )1+1 + 1 + 1n(n-1)n 2( n -31+1 + 1 + 1 +1 n( n - 1 )(n-2n- 3(n-4)= 186 0 480两种不同方式14.0 0 0 028.000042.0 0005 6.00007 0 .0 0 0072. 5 0

14、0 015.00 0 030.000 045.00 0 06 0.0 0 007 5.0 00015. 5 0 0 031.000 04 6. 5 0 006 2. 000 07 7 .5 016.00 0032. 0 00 048.00006 4.00008 I0.0 00 01 6 .500 033.00 0 04 9 .500066.000082. 5 00017.0 00034. 0 00051.000068.000085.0 0001 7. 50 0 035. 0 00 052 .5 0 0 070.000087.5 0 0 01 8.00003 6. 0 00054.000072.

15、0 00001 8. 5 0 003 7. 000 055.5 0 0074.0 0 0 019. 0 00 03 8. 0 00 05 7. 0 0 007 6 .00 0 01 9.500039.00 0 05 8 .50 0 078. 0 00 0020. 000040.00006 0.0 0 0 080.0000020.50 0 04 1.000 061.500 08 2.0000021 .00004 2 .0 0 0 06 3.000084.000002 1 .5 0 0043. 0 00064.500086.000 002 2.0 0 0(04 4.000 06 6 .00 0 0

16、88.0 0 0 022. 50004 5.000000023. 5 00047. 00 0070.50000025. 5 000000014.50 0 02 9.00000 0058.000 04 3 . 50000序号组合方式计算次数模式种数11, 1, 1 ,11 1 62803622, 1,1760 03 53(2 , 2)3 8 024(3, 1 )4 0 0651 ,1 , 1,1,1)1 8 604 8 010706(2,1,1, 11 368 0 012 287(2, 2, 1)76001 9 98(3 ,1 , 1 )760 01739(3,2)4001 91 0(4,1)4

17、001 5总计10213 7 9402783通过计算得到所有的符合条件的构成模式见表a。表a各种模式和种数模型建立：设共有n种模式n 2783），每种模式为一个20维的列向量，代表一种符合条件的组合方式。即根数满足 4或5根 长度为88. 5米、或8 9米、或8 9.5米。设这些模式为：1 2 n决策变量为第i种模式Xi捆，那么成品捆数最多的目标函数为：nmaxZ1xii1设所有组合中最短的最长的模式为ki, k2,., kp。通过分析所有的2 7 83种模式，得到最短长度最长的有3种模式，一种是模式1,为2根22米和2根22.5米构成；第二种是模式2,为3根2 2米和1根22.5米构成；第三

18、种是模式3,为3根22米和1根23. 5米构成。那么第二目标要求最短长度最长的捆数最大,有:pmaxZ2xkjj1满足的约束为各种长度的原料的数量,那么有：nxi i ai1那么综合模型为 :nmaxZ1xii1pmaxZ2xkjj1nxi i as.t. i 1Xj为整数,i 1,2,.,n当求第一目标最大化时，得到乙=1 37，余料为1 6米的1根。各组最大长度为22米,共 2 组,其模式为 3 根 22米和 1 根 22.5 米构成。22米,总共 3 组.分别为 :当令Z1137,求解Z2最大时，得到最优解为各组最大长度为2 组模式为 3 根 22 米和 1 根 22. 5 米的原材料。

19、1 组模式为3根 22 米和 1 根2 3.5米的原材料。 具体搭配方案为：序号 1,长 89.5米,4根, 1组,模式:21.0米 1根, 21.5米2根, 25 .5米1根,序号 2,长88.5米,4根, 3组,模式:21.5米 2根, 22.0米1根, 23.5米 1根,序号3,长89.5米,4根,1组，模式:21.0米1根，2 1 .5米1根，2 3. 5米2根,序号4，长88.5米,4根,2组,模式：22. 0米3根,22. 5米1根，序号5,长89.5米,4 根, 1组，模式:2 2 .0米3根，2 3. 5米1根，序号6,长89 .5 米 ,5根,1组，模式：1 4.0米1根,1

20、 4.5米1 根,1 8.5米1根,21.0米1 根,21.5 米 1 根，序号 7,长89 .0米,5根，1组，模式:1 4.5米1根，1 5.0米1根，18.0米1根，20.0米1根， 21. 5米1根，序号8,长88.5米,5根，1组，模式:14.5米1根，1 5 .5米1根，17 .0米1根，20.5米1根，21.0米1 根,序号 9,长88.5米，5根，1 组,模式:14.5米 1 根, 1 5. 5米 1 根, 18.0米 1 根, 20 .0米1 根, 20 .5 米1根 ,序号 10,长 89.5米,5根， 1 组,模式:14. 5米1根 ,15.5米1根， 18.0米 1 根

21、, 20.5米1根,21. 0米 1 根，序号 11,长89. 0米,5根，1 组,模式:16. 0米 1 根, 16. 5米1根 ,17.0米 1 根,19. 0米 1 根， 20.5米 1 根,序号 12,长88.5米，5根 ,15组,模式:15 .5米 2根, 18 .5米 1 根, 19.0米 1 根， 20.0米 1 根， 序号1 3,长8 8.5米,5根, 1组，模式 :14. 5米 1根,16. 0米2根, 2 0. 5米 1 根, 21.5米 1 根，序号 14,长88 .5米,5根, 4组,模式:14.5米 1根, 16.5米 2根， 19. 5米 1 根, 21 .5米 1

22、根， 序号1 5,长88.5米,5根, 1 组,模式:16. 5米 1 根, 17.5米2根, 18.0米 1 根, 19.0米 1 根， 序号 16,长88. 5米， 5根,18组,模式：1 6. 0米1根, 16.5米 1 根,18.0米2 根， 20. 0米 1 根,序号 17,长88.5米,5根,10组,模式:1 4.5 米1 根， 1 8. 0米 1根， 18.5米2根 , 19.0米 1 根， 序号 18,长89. 5米，5根 ,14组,模式:15.0 米1根, 16.5米 1根, 18. 5米 2根, 2 1.0米1根， 序号 19,长89.5米,5根, 4组，模式：15.0米1

23、根,1 7.0米1根,19.0米 2根,19.5米1根，序号2 0,长8 9.5米,5根, 4组,模式:14.0米1根,15.5米1根, 19.5米2根, 21.0米1 根,序号 21，长88.5米,5根, 7组,模式：15. 0米1根,17.0米1 根,17.5米1根 , 19.5米2根,序号2 2,长89.5米,5根， 7组,模式：14.5米1根,16.0米 1 根,19.0米 1 根, 20.0米2根，序号 23,长88. 5米,5根， 2组,模式： 14.5米1 根， 15.0米 1 根, 17. 0米1根, 21. 0米 2根, 序号24 ,长 88.5米， 5根,15组,模式:14

24、 .0米2根 , 19. 5米 1 根, 20.5米2根 , 序号 25 ,长88.5米， 5根，1 5组,模式:17.0米 2根，17.5米 2根, 19.5米 1 根，序号 26,长8 8.5米,5根, 5组,模式:15 .5米 1 根， 1 7. 5米2根 , 19 .0米2根 , 序号 27，长 88.5米， 5根,1组，模式 :15.0米 2根, 19 .5米 3根，二、考虑规格 2 产品的搭配由于规格3产品无剩余，类似对规格3产品搭配的模型，设长度为7,7 .5，8, 8. 5,9, 9. 5,10,10.5,11,1 1.5,12, 12. 5,13 ，13.5 米的的14种肠衣

25、 分成 K 组，设第 i 种长度的原料分到第 j 组为 xij 根。设第i种长度的原料有a,根，i 1,2,.,14。其中 a =2 4,2 4,2 0 ,25 ， 21,23,2 1,1 8,31 ， 23,22 ， 59,18, 25。最大捆数分析1414种原材料中长度为L a=3 705.5米i 1每捆长度最少为 88.5米，因此捆数最多为：K 3705.5/88.541.87141 4种原材料的总根数为 Tai =35 4根i 1每捆最少为7根，因此捆数最多为 K 354/750.650根。二者取最小值，因此K 41 o与一中建立模型的方法相类似，我们可以得到下面求解的模型为:maxZ

26、1 Kmax Z2Si 1,2,.,14j 1,2,., K89.5j 1,2,., Ki 1,2,.,140,i1,2,.,14Kxijaij 1147 Xj 8i 11488.5 liXji 1StKri a xj 1j min i | x0u max jj jS j| j uXjj取整,i 1,2,.,14; j 1,2,., K其中 a = 2 4 , 2 4 ,20,25,2 1, 2 3,2 1 ,18,31,23 , 22 , 59 , 18,25L = 7,7 . 5, 8 ,8.5,9 ,9.5,10,1 0 . 5 ,11,11.5,12,12 .5,13, 13.5.）当

27、求第一目标最大化时，得到乙=4 1 ，余料为:长度& 5米剩余1根，长度9 .0米剩余1根，长度9. 5米剩余5根，长度12. 0米剩余1根.o具体搭配方案为：序号1,长88.5米,8根，2组，模式90米1根，10.5米3根，1 1.5米2 根, 12.5米2根，序号2,长88. 5米，9根，2组，模式:8.5米3根，9.5米3根，11. 0米2根，12.5米1 根,序号3,长88.5米，9根,4组，模式:8.5米4根，9.0米2根，12.0米2根，1 2.5米1根，序号4,长88 .5米8根，2组,模式：8.0米1根，1 0 .0米3根，11.5米1根，13. 0米3根，序号 5,长

28、88.5米,9根，1组，模式：8 .0米1根，9.0米3根，9. 5米3根,12. 0米1根，13.0米1根，序号6，长88.5米，9根，1组，模式:8.0米3根，8.5米1根，9.0米1根,10. 0米1根，1 2 .0米2根，13.0米1根，序号7，长88. 5米,9根，3组，模式:7.5米1根，9 .0米2根，10.0米3根，11.0米3根，序号 8,长8 8.5米,8根，2组，模式:7.5米2根，11.0米2根，12.5米1根，13.0米3根，序号 9，长88.5米，8根，3组，模式:7.5米2根， 9. 5米1根， 10. 5米1根， 13. 0米1根， 13. 5米3根，序号1 0

29、，长88.5米，9根，2组，模式:7.5米2根， 9. 5米3根， 10.0米2根， 12.5米2根，序号1 1，长88.5米，9根， 1组，模式:7.5米3根， 8.5米1根，10. 0米1根， 11.5米3根， 13.0米1根，序号12，长88.5米，8根，14组，模式：7 .0米1根， 8. 0米1根， 11.0米1根， 11.5米1根， 12.5米3根， 13.5米1根， 序号13，长88.5米，9根， 1组，模式：7 .0米1根， 7.5米4根， 12.0米1根， 12. 5米1根，13.5米2根，序号14，长88.5米，9根， 3组，模式:7.0米3根， 10.5米3根，12.0米

30、3根，二）当令Z! 41，求解乙最大时，得到最优解为各组最大长度为1 1米，总共 6组.分别为：6组模式为 5根 11米和3根 11.5米的原材料。余料为：长度 7.5米剩余 1 根，长度 9.0 米剩余 2根长度 9.5米剩余1根 ，长度 12.5米剩余 1 根.具体搭配方案为：序号 1，长 89.5米， 8根， 6组，模式: 11 .0米5根 ， 11.5米 3根，序号 2，长 89.5米，8根， 1组，模式:10.0米3根， 11.5米1根 ， 12.0米4根，序号 3，长 89.5米，8根， 6组，模式:9.5米3根， 10.0米 1根， 12.5米3根， 13.5米 1根，序号 4，

31、长 89.5米，8根， 3组，模式： 8.5米1根， 9.0米 2根， 12.5米 4根， 13.0米 1根，序号5,长8 8 . 5米,9根， 2组模式：8 . 5米1 根, 9. 0米4根，9 .5米1根，10.5米1根，12. 0米2 根，序号 6，长 89.0 米，9 根， 3组，模式 :8.0 米 2 根， 8.5米4根 ， 13.0米3根 ，序号 7，长89.5米，9根， 2组，模式： 8.0米4根， 9.5米1根， 120米4根，序号 8，长895米，9根， 1 组，模式:8.0米4根， 8.5米2根， 13.5米3根，序号 9，长 895米，9根， 1 组，模式:7.5米1根，

32、 9.0米5根， 11.0米1 根， 12.5米1 根， 13.5 米 1 根，序号10，长88.5米，9根， 3组，模式:7.5米1根， 8.5米2根， 100米4根， 12.0米2根，序号11，长895米， 9根， 4组，模式 :7.5米3根， 10.5米4根， 11.5米 1根， 13.5米1根， 序号1 2，长8 95米，8根， 4组，模式:7.0米1根， 7.5米1根， 12.5米6根， 序号13，长88.5米，9根， 2组，模式:7.0米4根， 80米1根，13.0米3根， 135米1 根，序号1 4，长88.5米，9根， 3组，模式：7 .0米4根， 75米1根， 12.5米1根

33、， 135米3根，当不将 20 米的 2 根余料做降级处理 ，最多可分成 37 组。 其解为：K =3 7由第一目标最大得到结果为 : Z1 37。即最大组数为3 7组。剩余为 7米的 24根;7.5米的 24根； 8米的 7根,8.5米的 3根。 求解时可在求出第一目标后 ,令 K=37 ，然后求第二目标最大。具体求解结果见 d 2 .xls。见表4。 表4 规格2的搭配方案1方案77.588.599.51010.51111.512251313.52010012000000202102002000100005000300100000061000040011000000600005000300

34、00000410060011000000600007001020000005000800003000010400090010000007000001000000020500001011000003100004000120010000040210001 300000410000003014000000500000300150002000110040001600030000000410017000031000100030180000000510020001900100000330010020000000007100000210000000600100102200000006001001023000

35、000500002010240011004000100012500000410000003026000030000104000270001010030111002800021000000500029001003000000400300003000010004003100031000000004032000210000005000330000041000000303411100000001004035000023002000001360001000042001003700003000010400038001020000005000Max=Z 1结果 zl = 4 1x(1481)=2;x 623

36、9) = 2; x(6817= 4; x (7 4 4 0 )=2;x 8774)=1;x 1 3758= 1 ;x( 1 58 9 0 )=3 ;x 21952)=2;x(2 2 138)=3;x 2 2 349)=2;x 2 6 157) = 1;x(3 126 1 =14;x(39818)= 1 ;x(4 4868)=3；R(4)= 1 ;R(5)=1;R 6=5;R( 1 1) = 1;m ax= x(1+x2 ) + x( 3+ x(4)+x(5+ x(6)结果 z 2 =6x(1) =6; x 326=1 ; x (12 5 5)= 6 ；x 4614) = 3; x 5 00 7

37、=2;x(128 8 1=3; x 14 02 0)=2; x ( 1 4 2 70)=1;x 16312=1;x(17463)= 3 ;x (2 5 43 9=4;x34 7 21) = 4; x (46327=2;x(4 6 3 3 4)=3;R(2=1;R( 5 ) = 2;R (6 )=1;R 1 2 ) = 1;剩余7 .5米1根;9 米 2 根; 95 米1根; 12.5米 1 根三、考虑规格 1 产品的搭配由于规格 2 产品剩余剩余为 7米的 24根;75米的 24根;8米的 7根,85米的 3 根。由于其可以降级到规格 1 产品。因此规格 1 产品中原料增加7米的 24根;7

38、.5 米 的 24根; 8 米的 7 根， 8.5米的 3根 类似对规格 1 产品搭配的模型 ,设长度为3, 3. 5 , 4 ,4.5,5,5.5,6,6. 5, 7 ,7 . 5,8 , 8. 5 米的的 12 种肠衣分成 K 组，设第 i 种长度的原料分到第 j 组为 xij 根。设第i种长度的原料有a,根，i 1,2，,11。其中 a=43,59,3 9,41 ， 27, 28,34,21,24,24,7, 3。最大捆数分析 :1111种原材料中长度为 La=16875米i1每捆长度最少为 88.5 米,因此捆数最多为： K 1687/88.519.1 191111种原材料的总根数为

39、Tai =344根i1每捆最少为1 9根，因此捆数最多为 K 344/1918.1 18根。二者取最小值，因此K 18 。与一中建立模型的方法相类似，我们可以得到下面求解的模型。的模型为:maxZ1 KmaxZ2 SKxijaii 1,2,.,11j 11219Xj20j 1,2,., Ki 11288.5 lixij 89.5j 1,2,., Ki 1StKr a 为i 1,2,.,12j 1jmini | xij0, i 1,2,.,12u max ij jS j| j uXj取整,i1,2,.,12; j 1,2,., K其中 a= 4 3,59,3 9,41,27,28,34, 2 1 ,2 3 , 2 3,6L=3 , 3. 5,4 , 4.5 , 5,5.5,6,65, 7 ,7 . 5,8.当不作降级处理时，最多可分成14组，当将规格2剩余的7米的2 3根；7.5米的2 3根；8米的6根。其解仍然为：K =1 4由第一目标最大得到结果为:Z114。即最大组数为14组。剩余情况：剩余原料序号2，长度为3. 5米,根数为1根剩余原料序号3，长度为4米,根数为1根剩余原料序号 4,长度为4.5