天然肠衣搭配的优化模型.doc

天然肠衣搭配的优化模型 作者： 日期：17 个人收集整理 勿做商业用途天然肠衣搭配的优化模型与算法设计天然肠衣(以下简称肠衣制作加工是我国的一个传统产业，出口量占世界首位。肠衣经过清洗整理后被分割成长度不等的小段原料，进入组装工序。传统的生产方式依靠人工,边丈量原料长度边心算，将原材料按指定根数和总长度组装出成品捆。原料按长度分档,通常以0.5米为一档，如:3-3.4米按3米计算,3.5米-3.米按3.5米计算，其余的依此类推。表1是几种常见成品的规格，长度单位为米,表示没有上限，但实际长度小于26米。表1 成品规格表最短长度最大长度根数总长度36.508913.891459为了提高生产效率，公司方案改变组装工艺,先丈量所有原料,建立一个原料表。表2为某批次原料描述。表2 原料描述表长度.435-9-4.44.4.9-5.45.5-.96-6.4.5-.9根数43599412728321长度7-7.47.-7.98-.485-.99-9.5-9.10-10.410.-0.9根数2442052122长度11-11.4115-191-12.42.51.913-13413.5-13.914-14.414.-14.9根数31232591253529长度15-1.415.-1.96-6.41.-16917-17.47.5-17918-18.418.51.9根数228424595064长度19-19.192020.420.5-2092-21.21.-21.9222.422.52.9根数56352716122长度2-23.23.5-3.24-.24524.5-25.425.5-25.9根数6001根据以上成品和原料描述，设计一个原料搭配方案,工人根据这个方案“照方抓药进展生产。公司对搭配方案有以下具体要求:1) 对于给定的一批原料，装出的成品捆数越多越好;2)对于成品捆数一样的方案,最短长度最长的成品越多,方案越好;(3) 为提高原料使用率,总长度允许有 .5米的误差,总根数允许比标准少1根;(4)某种规格对应原料如果出现剩余，可以降级使用。如长度为1米的原料可以和长度介于-.5米的进展捆扎，成品属于7-1.5米的规格；(5) 为了食品保鲜,要求在3分钟内产生方案。请建立上述问题的数学模型，给出求解方法，并对表1、表2给出的实际数据进展求解，给出搭配方案。解答：我们将上种类型的成品分别称作规格1、规格2、规格3。其定义见表1。表 成品规格表规格类型最短长度最大长度根数总长度136.20927.8159 由于满足规格3的的原料可以降级作规格2,满足规格2的的原料可以降级作规格1。因此我们先考虑规格3产品的搭配，再考规格2产品的搭配,最后考虑规格产品的搭配。 一、考虑规格3产品的搭配设长度为1,45,1，155，1,165，17，17.,1,185,19,9.5,20,205,21，2.5,22，22.5，23,25.5的种肠衣分成组，设第种长度的原料分到第组为根。设第种长度的原料有根,。其中=3,，30，2，2,42,45,4，50，64，2,63,4,35,27,16,1,2,6，。第种长度的原料分到所有组的根数不能超过根。那么有:每组的根数为5根，由()知也可以为根，因此对每组的根数满足：设第种长度的原料的长度为米。其中=14,14.5，15,1.5，16,165,17,7，18,18.5,19,19.5,2.5,21.5,22,22.,25,2.5。每组的长度为89米,由(3) 知可以 0米的误差，因此每组的总长度满足:为考虑规格利用规格3中的剩余,我们求出规格3中每种长度原料的剩余。设第种长度的原料的剩余根数为。那么有:我们建立目标函数。(1)要求对于给定的一批原料，装出的成品捆数越多越好,因此我们的第一目标为: (2)要求对于成品捆数一样的方案,最短长度最长的成品越多，方案越好。我们设法建立第二目标。令,。该序列表示各列最短长度的序号。令，表示所有组中最短长度的序号最大值。令，表示取得最短长度最大值的序号集。第二目标函为各列最短长度最大的捆数最多，那么有:其中表示集合的元素个数为说明我们的方法,下面采用一个例子说明。如某分配方案如表2,其中为单调增序列。 表2 分配方案例如长度第1组第2组第3组第4组第5组第6组20000600028230055287256553那么有各列最短长度的行序号1,3，3，4，,2, 其最大值，中取得最大值的序号。那么计算出即该分配方案中最短长度最长为,总共有2捆成品。因此总的模型为: 其中=14,14.5,15,5.5,16，16.5，17，1.5，18,18.5,19,19.5,，2.5,1，21.,2,2.，3.,25.5。35,29,0,42，28,42,45，49,0，64，5,63,9,35,7,16,12，2,6,1。 该模型求解困难。在确定第一目标最大时,需要尝试不同的，而在给定进展求解时，利用Lngo12求解极其耗时,通常会小时以上。而在求解第二目标,由于是非线性,求解就更困难,采用Lingo几乎没法求解，即使求解成功,也是局部最优解。鉴于此,我们采用另外的方法建模求解。 先对问题进展分析：1)最大捆数分析：种原材料中长度为1215.5米每捆长度最少为8.5米,因此捆数最多为：20种原材料的总根数为=67根每捆最少为根，因此捆数最多为根。二者取最小值，因此。2)每捆成品的组成模式分析每捆成品可以有不同的构成模式，每种模式由一个向量构成。代表第种材料的根数。那么各取值范围满足： 计算得到各()的最大取值为：5,5,5,5,5,5,4, 4, 4，4, 4, 4, 4，4, 2,，。求出所有模式 如果直接对各从到其最大取值进展完全枚举所有符合条件的模式，计算量为：.7。该结果很难进展枚举。因此我们采用另外的方法得到所有符合条件的模式。根据5=4+3+3+1=2+1=11+11+1+1+1+1 4+1=+22+1+1=11+1+1 因此从根数每捆为4根或5根来看,最多有2种方式。上式的意义解释:如4+,表示第种材料为4根，第种材料为1根，满足长度为8.589米的所有构成方式(不相等)。+2+1,表示第种材料为2根，第种材料为2根,第种材料为1根，满足长度为8.5.5米的所有构成方式互不相等)。由于根或4根某种材料都不可能单独构成长度为88.5或8或.5米，因此这两种模式舍去,只剩下10种模式。其总计算量为： 4+,31,3+方式计算量3n*n 3+11，2+1,2+2+1 nn-) 1+11+1 n(n-1)2(-3 1+1 n(-)(n-2n-(n-4)= 186480 两种不同方式14.00 28.0000 42000 6.0000 .000 14.500 9.0000.0 58.000 72.00 15.00030.000 45.000 0.000 5.000 1550 31.000 6500 2000 7.00 16.00032.00 48.0000 4.0000 0.00 1.500 33.000 4.5000 66.0000 82.000 17.000 34.000 51.0000 68.0000 8500 7500 35.00 5.50 70.0000 87.50 8.0000 6.000 54.0000 72000 0 8500 7000 55.5 74.00 0 19.0 8.00 7000 .000 9.5000 39.000 .500 78.00 0 200000 40.0000 0.0 80.0000 20.50 1.000 61.500 2.0000 2.0000 4.00 3.0000 84.0000 .500 43.000 64.5000 86.000 0 00 4.000 6.000 8800 25000 5.0000 0 0 23.000 47000 70.5000 0 25.000 0 0 0通过计算得到所有的符合条件的构成模式见表a。表 各种模式和种数序号组合方式计算次数模式种数11，1,1162803622，1,17603(2，2)3024(3,)465,1，1,1,1)604010706(2,1,1,3680287(，2，1)76001(,1，)7601739(3,2)40010(4,1)4005总计102139402783模型建立:设共有种模式)，每种模式为一个0维的列向量,代表一种符合条件的组合方式。即根数满足4或根,长度为885米、或8米、或9.5米。设这些模式为：决策变量为第种模式捆，那么成品捆数最多的目标函数为： 设所有组合中最短的最长的模式为。通过分析所有的283种模式，得到最短长度最长的有种模式,一种是模式1，为2根22米和2根22.5米构成；第二种是模式2,为根2米和根22.5米构成；第三种是模式3，为3根22米和1根23米构成。那么第二目标要求最短长度最长的捆数最大,有:满足的约束为各种长度的原料的数量,那么有：那么综合模型为:当求第一目标最大化时,得到3,余料为1米的根。各组最大长度为2米，共2组，其模式为3根2米和1根22.5米构成。当令,求解最大时,得到最优解为各组最大长度为2米，总共 3组.分别为:2组模式为3根22米和1根225米的原材料。1组模式为根22米和1根3.5米的原材料。具体搭配方案为：序号1，长89米,4根, 组,模式:210米1根, 21.5米根,.5米根， 序号 2,长88.米,4根， 3组,模式:.米2根,2.0米根， 23.米1根， 序号3,长89.5米,根, 1组,模式:21.0米1根,.5米1根, 3.米2根, 序号 ,长88.5米,根, 2组,模式：20米3根, 25米1根,序号 5,长89.5米,4根, 1组,模式:.0米3根, 35米1根, 序号 ，长.5米,5根,1组，模式:4米1根, 4.5米1根,8.5米根, 2.0米1根,21.5米1根， 序号 ，长8.米,5根, 组,模式:4.5米1根， 5.0米1根, 18.米1根， 200米根，21.米1根， 序号 8,长88.5米,5根,1组,模式:14.5米1根，1.5米1根, .0米1根, 20.5米1根, 21.0米根, 序号9,长8.米，根， 1组,模式:1.米1根, 55米1根, 18.0米1根, .0米1根,2.5米根, 序号10,长89.米,5根， 1组,模式:145米根,15.5米根， 18.0米1根, 20.5米根,210米1根，序号11,长890米,根， 1组,模式:16米1根, 165米根,17.0米1根,190米1根， 20.5米1根,序号1,长88.5米，根,15组,模式:1.5米2根, .米1根, 1米1根， 2米1根， 序号3,长8.5米,5根, 组，模式:15米1根,10米根, 05米1根, 21米1根， 序号1,长8.5米,5根,组,模式:14.5米1根, 16.米2根， 195米1根, 2.米1根， 序号5,长88.5米,5根,1组,模式:15米1根, 17.5米2根, 18.0米1根, 19.0米1根， 序号16,长85米，5根,18组,模式：60米根, 1.米1根,18.0米2根， 200米1根, 序号17,长88.米,根,10组,模式:4.5米1根， 80米1根， 1米根, 19.米1根， 序号18,长895米，根,14组,模式:5.0米根, 16.5米1根, 5米2根, 1.0米根， 序号19,长89.米,根,组，模式：15.0米1根, 7.0米根,.0米2根,1.5米根， 序号0,长95米,5根, 4组,模式:4.0米根, 5.5米根,19.5米2根, 21.0米1根, 序号2，长8.5米,5根, 7组,模式：150米1根,17.0米1根,.5米根, 19.5米2根,序号2,长895米,5根， 7组,模式：14.米1根, 16米1根,190米1根, 20.0米2根， 序号23,长5米,5根， 2组,模式：14.5米1根， 15.0米1根, 170米根,20米2根, 序号,长8.米，5根,15组,模式:1.米根, 195米1根, 20.米根, 序号2,长88.5米，5根，5组,模式:17.0米2根， 17米2根, 19.5米1根，序号26,长8.5米,5根, 5组,模式:.5米1根， 75米根, 1.0米根,序号27，长88.5米，5根,1组，模式:15.0米2根, 1.5米3根，二、考虑规格2产品的搭配由于规格产品无剩余，类似对规格产品搭配的模型,设长度为7,75，,5,9,5,10,10.5,1,1.5,12,2.,13，13.5米的的1种肠衣分成组，设第种长度的原料分到第组为根。设第种长度的原料有根，。其中=2,2,2,25，21,23,2,1,31，23,22，59,18,5。最大捆数分析:14种原材料中长度为=705.5米每捆长度最少为88.5米，因此捆数最多为:4种原材料的总根数为=35根每捆最少为7根,因此捆数最多为根。二者取最小值,因此。 与一中建立模型的方法相类似，我们可以得到下面求解的模型为: 其中2,20,25,1,3,2,18,31，23，22，59，18,257,75,8.5,9.5,10,0,11,11.5,12，.5,13，13.一) 当求第一目标最大化时，得到=4 ,余料为：长度8米剩余1根，长度.0米剩余1根,长度95米剩余5根,长度12.米剩余1根.。具体搭配方案为:序号 ，长88.米,8根, 2组,模式:9.0米根, 10.5米3根， 1.5米2根, 12.5米2根, 序号 2,长88.米，9根, 2组，模式:8.5米根, 9.米3根, 10米2根， 12.米1根, 序号 3,长88.5米，9根, 4组,模式:8.5米4根,9.0米2根， 12.0米根， 2.5米1根， 序号 4,长8.5米,根, 2组,模式：8.0米1根，1.0米根, 11.5米根, 0米3根,序号5,长88.5米,9根, 组,模式：.0米1根, 9.0米3根, 95米根, 12米根,13.0米1根, 序号 ,长88.5米，根, 组,模式:8.0米根, 8.5米1根， 9.0米1根, 100米1根， 1.0米2根, 1.0米1根, 序号 ,长85米,9根,3组,模式:7.米1根,.0米2根,10米3根, 11.0米3根， 序号8,长8.米,8根， 组，模式:7.5米2根， 11.米根, 12.5米1根,13.0米3根, 序号 9,长88.5米,8根， 组,模式:7.5米2根, 5米根, 105米1根， 130米1根, 5米3根,序号0,长88.5米，根， 组,模式:7.5米2根, 95米根,10.0米2根,12.5米2根, 序号1,长8.5米,9根， 1组，模式:.米3根,8.5米根,100米1根, 11.米3根, 13.米1根, 序号12,长.米,8根,14组，模式：.0米1根, 80米1根, 11.0米1根, 11.5米1根，12米3根， 13.米根, 序号13,长88.5米,9根， 1组，模式：.0米1根, .米4根, 12.0米1根, 125米根,13.5米2根, 序号14，长88.5米,根, 3组,模式:.米3根, 10.5米3根,12.0米3根,二)当令,求解最大时,得到最优解为各组最大长度为1米,总共6组.分别为：组模式为5根1米和根11.5米的原材料。余料为：长度7.5米剩余1根,长度9.0米剩余2根长度9.5米剩余根,长度15米剩余1根.具体搭配方案为：序号 ,长89米，8根, 6组,模式:.0米根, 11.5米3根, 序号 ，长895米，8根,组,模式:10.0米3根， 1.米根,2.0米4根,序号 3,长89.5米,8根, 6组,模式:9.5米3根,10.0米1根,125米3根,135米1根, 序号 4,长89.5米，8根, 3组,模式：8.5米根， 9.米2根, 1米4根, 1.0米1根，序号 5,长85米,9根，2组,模式：85米1根, 9.米根,.5米根, 10.5米根， 12.米2根， 序号 6,长89.0米,9根, 组，模式:8.0米2根, 8.米根, 13.米根, 序号 7,长9.5米,根, 组,模式：8.0米4根, 9.5米1根, 0米4根, 序号8,长85米,9根, 1组,模式:8.0米4根, .5米根,3.5米3根, 序号，长895米,9根， 1组,模式:7.米根， 9.0米5根， 11.0米1根,12.5米1根, 13.5米1根, 序号1,长8.5米,9根, 3组,模式:7.5米根, 8.5米2根， 100米4根, 12.0米2根,序号11,长85米，9根， 组，模式:7.5米3根,1.5米根， 11.米1根，1.5米根,序号2,长95米,根,4组,模式:.0米根, .5米1根， 12.5米根, 序号13,长8.5米,根, 2组,模式:7.0米4根, 80米1根,13.0米3根, 135米1根, 序号4，长88.5米,9根, 组，模式：.0米根,75米根, 12.5米1根, 15米3根， 当不将20米的2根余料做降级处理,最多可分成37组。其解为：=3由第一目标最大得到结果为:。即最大组数为7组。剩余为7米的24根;7.5米的24根；8米的7根,8.5米的3根。求解时可在求出第一目标后,令K=37，然后求第二目标最大。具体求解结果见d.xls。见表。表 规格的搭配方案方案77.58.59.110.51111.51221313.52010200000020210200000000030010000006000040110000060000000410600110000060070010200500000000009001000007000000000200000110000010000001200004020001000041000014000000500030010020001104000160003000004107000310001000180000102001900100033001020000007000002100000100200060101020000050000201041100400101250004100000302600030000040020110010028002100000000290010300000403000001004000003100000043200000050003000041030411100000001040350230000001360000000420100370003000104000380010200000000Max=Z结果 =x(1481)=2;x6239)2；x(68174；(74)=2;x8774)=1;x3758=;x(59)=3；21952)=2;x(2138)=3;x2349)=2;x2157)1;x(31=14;x(39818)=;x(4868)=3；R(4)=;R(5)=1;R=5;R(1)1; axx(1+x)x(x(4)+x(5x(6) 结果z=6x(1)；x326=1；(125)=;4614)3;07=2;x(1281=3；100)=2;(70)=1;x16312；x(17463)=;(24=4;x3421)4;(46327=2;x(434)=3;R(2=1;R()2;()=1;R1)1;剩余.米根；9米2根；95米根；12.米1根三、考虑规格1产品的搭配 由于规格2产品剩余剩余为7米的2根;5米的24根；米的7根,8米的3根。由于其可以降级到规格1产品。因此规格1产品中原料增加米的2根；.5米的2根；8米的7根，8.5米的3根类似对规格1产品搭配的模型,设长度为3，3.,4.5,5,5.5,6,5,75,8，8.米的的12种肠衣分成组，设第种长度的原料分到第组为根。 设第种长度的原料有根，。其中=,59,3,41，27,8,34,21,24,4,7,。最大捆数分析:11种原材料中长度为=16875米每捆长度最少为88.5米,因此捆数最多为：1种原材料的总根数为=34根每捆最少为9根，因此捆数最多为根。二者取最小值,因此。 与一中建立模型的方法相类似，我们可以得到下面求解的模型。的模型为： 其中=3,59,9,41,27,28，34,2,3,6L=3，35,4，4.5，5,5.5,6,65,75,8.当不作降级处理时，最多可分成14组,当将规格2剩余的7米的3根；7.米的3根；8米的根。其解仍然为：K4由第一目标最大得到结果为:。即最大组数为4组。剩余情况：剩余原料序号 ,长度为 3.米,根数为根剩余原料序号 ,长度为 4米,根数为根剩余原料序号 4，长度为 4.5米,根数为根剩余原料序号7,长度为6米,根数为1根剩余原料序号8,长度为 米,根数为16根剩余原料序号9，长度为7米,根数为2根剩余原料序号10，长度为 5米,根数为 24根剩余原料序号11，长度为 8米,根数为 4根求解时可在求出第一目标后,令K=14，然后求第二目标最大。具体求解结果见d1.xls。见表5。表5 规格1的搭配方案方案33.45556577.581601100021201007000011710000004610100000050401500010603011040770091108016200900410120111001100001113112001122111021033802600014112101100新解:不增加成品二的余料.令z1=14，maxZx1+x+.+x得到最优解为各组最大长度为45米，总共3组.分别为：组模式为1根45米和8根5.0米的原材料。1组模式为12根5米和7根5.0米的原材料。余料为：长度3.0米剩余1根.长度米剩余2根.具体搭配方案为：序号 1，长89.5米,19根, 2组,模式:45米11根，5.0米8根,序号 2，长89.0米,根,1组,模式：4.米12根, 5.米7根,序号 3,长89.5米，9根，1组,模式:4.0米4根,45米7根,50米4根, 5.5米4根，序号 4,长89.0米，根,1组,模式：4.0米1根, 5.5米1根，6.5米3根, 序号 5,长89.米,19根， 1组，模式:35米4根, 4.0米6根, 5.米5根, 6米4根,序号 6,长885米,20根, 2组，模式:3.5米10根, 4.0米1根， 5.5米9根, 序号 7,长8.5米,20根,组，模式:3.米13根, 4.米根， 65米根,序号 8,长.米,19根,组,模式:3.0米根， 3.5米8根, 6.米6根, 6.米根,序号 9，长8.0米,20根, 3组,模式:30米5根，3.5米根,4.米3根, 6.米8根, 序号10，长9.米,19根,组,模式:3.0米9根，.0米1根， .5米根,余料的处理:成品一余料为：长度3.米剩余7根，长度.米剩余2根成品二的余料为：剩余7米1根;9米2根;95米根;1.5米根所有余料可组合成一捆,方式有种。可选取组合方式为：4根3米，2根3.米,根9米,1根5米,1根.5米。总根数20根，总长度89米。剩余材料为3根3米，1根.5米。这样,总共可分为5捆。总捆数为15+41+37=13捆。所有剩余材料为3根3米,根7.5米。