天然肠衣搭配问题

1天然肠衣搭配问题摘要肠衣的搭配问题就是把给定的若干长度不同的原料进行搭配成捆，使得每捆的总长度，所含原料的根数满足一定条件的情况下，得到的总成品捆数和某些规格的成品捆数越多越好，从而可以最大可能的提高公司肠衣的销售收入。、本文就肠衣的搭配方案问题进行了研究，通过对题目中给定的具体数据进行分析和合理的假设，得到求解该问题最优解的多目标线性整数规划模型。模型中含有较多的决策变量及约束方程。因为问题对食品保鲜有具体的时间要求，为了在有限的时间内得到问题的尽可能合理的搭配方案，使得工人可以按照搭配方案进行捆扎，我们把建立的大规模整数目标规划问题的求解分解成若干个较小规模的整数线性规划问题的求解。运用Lingo软件编程计算每个整数线性规划问题的最优搭配方案及相应的捆数，同时考虑到每捆的总长度要求、根数要求及不同规格的原材料间的可能的降级使用，我们给出了一个求问题可行解的一个算法，从而得到肠衣搭配问题的一个通用的方案。通过把算法运用到问题给定的实际数据中，我们可以得到算法的几个特点。首先，该算法可以在几分钟内产生可行的原料搭配方案，使得每个成品捆都满足相应的总长度要求、每捆的根数要求。其次，方案中也考虑到了规格长的剩余原料可降级使用，以提高原料使用率。最后，也是更重要的是，该算法得到的总捆数和最短长度最长的成品捆数与这两类捆数的上界是非常接近的。关键词：优化肠衣的优化搭配方法多目标线性整数规划单目标线性整数规划运筹lingo软件2目录一、问题重述……………………………………………………………………………………………………….(3)二、模型的基本假设与符号说明……………………………………………………………………(4)2.1、模型的基本假设……………………………………………………………………………….(4)2.2、符号说明……………………………………………………………………………..………...(4)三、问题分析与模型的建立……………………………………………………………………………(4)3.1、问题分析………………………………………………………………………………………….(4)3.2、模型建立…………………………………………………………………………………………..(5)3.3、模型分析……………………………………………………………………………………………(6)四、模型求解…………………………………………………………………………………………………………(7)4.1、求解第三规格的总捆数………………………………………………………………………………(7)4.2、求解第二规格的总捆数………………………………………………………………………………(8)4.3、求解第一规格的总捆数…………………………………………………………………………………(9)五、结果分析……………………………………………………………………………………………………….(11)六、参考文献……………………………………………………………………………………………………….(11)七、附录1-8lingo编程代码…………………………………………………………………………………(12)3一、问题重述天然肠衣（以下简称肠衣）制作加工是我国的一个传统产业，出口量占世界首位。肠衣经过清洗整理后被分割成长度不等的小段（原料），进入组装工序。传统的生产方式依靠人工，边丈量原料长度边心算，将原材料按指定根数和总长度组装出成品（捆）。原料按长度分档，通常以0.5米为一档，如：3-3.4米按3米计算，3.5米-3.9米按3.5米计算，其余的依此类推。表1是几种常见成品的规格，长度单位为米，∞表示没有上限，但实际长度小于26米。表1成品规格表最短长度最大长度根数总长度36.52089713.588914∞589为了提高生产效率，公司计划改变组装工艺，先丈量所有原料，建立一个原料表。表2为某批次原料描述。表2原料描述表长度3-3.43.5-3.94-4.44.5-4.95-5.45.5-5.96-6.46.5-6.9根数4359394127283421长度7-7.47.5-7.98-8.48.5-8.99-9.49.5-9.910-10.410.5-10.9根数2424202521232118长度11-11.411.5-11.912-12.412.5-12.913-13.413.5-13.914-14.414.5-14.9根数3123225918253529长度15-15.415.5-15.916-16.416.5-16.917-17.417.5-17.918-18.418.5-18.9根数3042284245495064长度19-19.419.5-19.920-20.420.5-20.921-21.421.5-21.922-22.422.5-22.9根数526349352716122长度23-23.423.5-23.924-24.424.5-24.925-25.425.5-25.9根数060001根据以上成品和原料描述，设计一个原料搭配方案，工人根据这个方案“照方抓药”进行生产。公司对搭配方案有以下具体要求：(1)对于给定的一批原料，装出的成品捆数越多越好；(2)对于成品捆数相同的方案，最短长度最长的成品越多，方案越好；(3)为提高原料使用率，总长度允许有±0.5米的误差，总根数允许比标准少1根；(4)某种规格对应原料如果出现剩余，可以降级使用。如长度为14米的原料可以和长度介于7-13.5米的进行捆扎，成品属于7-13.5米的规格；(5)为了食品保鲜,要求在30分钟内产生方案。建立上述问题的数学模型，给出求解方法，并对表1、表2给出的实际数据进行求4解，给出搭配方案。二、模型的基本假设和符号说明2.1模型的基本假设（1）假设每类型的原材料不可以再进行分割。（2）在计算长度时，我们按每档的最短长度作为该种类型的原料的长度。（3）在降级时，降级材料的长度必须为原长度。2.2符号说明ijX1：第一规格的成品中一捆的根数为19时，第j捆中所需的第i种类型的原料的根数；ijY1：第一规格的成品中一捆的根数为20时，第j捆中所需的第i种类型的原料的根数；mqX2:第二规格的成品中一捆的根数为7时，第q捆中所需的第m种类型的原料的根数；mqY2:第二规格的成品中一捆的根数为8时，第q捆中所需的第m种类型的原料的根数；nwX3：第三规格的成品中一捆的根数为4时，第w捆中所需的第n种类型的原料的根数；nwY3：第三规格的成品中一捆的根数为5时，第w捆中所需的第n种类型的原料的根数；三、问题分析与模型建立3.1问题分析肠衣的搭配问题就是把给定的若干长度不同的原料进行搭配成捆，使得每捆的总长度，所含原料的根数满足一定条件的情况下，得到的总成品捆数和某些规格的成品捆数越多越好，从而可以最大可能的提高公司肠衣的销售收入。肠衣搭配方案需要满足的具体要求有：装出的成品最多，成品捆数相同的捆选最短长度最长的成品，第二第三规格如出现材料剩余现象要进行降级处理，为了食品保鲜必需在30分钟内完成整个方案。3.2模型建立根据以上的符号说明及对问题的具体分析，我们建立了如下的多目标的线性整数规划模型：24116912411691141501141501811518115135134128127112011191nwnwnwnwmqmqmqmqijijijijYXYXYXMAX（1）24116912411691351341nwnwnwnwYXMAX（2）s.t.55615.89*1*15.8814181jATAXmmmjiiij（3）5615.89*1*15.8814181jATAYmmmjiiij（4）17815.89*2*25.88241141qATAXnnnqmmmq（5）17815.89*2*25.88241141qATAYnnnqmmmq（6）16915.89*35.88241wAXnnnw（7）16915.89*35.88241wAYnnnw（8）81110561561iCYXijijjij（9）81,1411110561561561imTYXjmjjijjij(10),14122017811781mCYXmqmqqmq(11)241,1411220178117811781nmTYXqnqqmqqmq(12)24133016911691nCYXnwnwwnw(13)56101191141)1(81141)1(81jTXorTXmmjiijmmjiij(14)5610120181)2(8181)2(81jTYorTYimjiijimjiij(15)17810272241)1(141241)1(141qTXorTXnnqmmqnnqmmq(16)17810282241)2(141241)2(141qTYorTYnnqmmqnnqmmq(17)034316911691wnwwnwXorX(18)035316911691wnwwnwYorY(19)3.3模型分析由原问题要求(3)和（4）可知，对于剩余原料，不同的规格可以降级使用，并且一捆的总根数允许比一捆标准的总根数少1根。对于第一规格的八种不同类型的原料长度和总根数以及第二规格可降级使用的原料的长度和总根数，可知第一规格的总捆数不超过56捆。对于j=1,...,56,第j捆中第一规格的不同类型的原料根数与相应的长度乘积之和加上第二规格中剩余后降级下来的不同类型的原料根数与相应的长度乘积之和要6满足每捆中总长度介于88.5到89.5之间。本要求由模型中的约束（3）和(4)来表示。同样对于第二规格的14种不同类型的原料长度和总根数以及第三规格可降级使用的原料的长度和总根数，可知第二规格的总捆数不超过178捆，对于q=1,…,178,第q捆中第二规格的不同类型的原料根数与相应的长度乘积之和加上第三规格中剩余后降级下来的不同类型的原料根数与相应的长度乘积之和要满足每捆中总长度介于88.5到89.5之间。本要求由模型中的约束(5)和(6)表示。由于第三规格不存在降级材料，可知第三规格的总捆数不超过169捆。对于w=1,…,169,第w捆中第三规格的不同类型的原料根数与相应的长度乘积之和要满足每捆中总长度介于88.5到89.5之间。本要求由模型中的约束（7）和（8）表示。对于第一种规格的八种类型的原材料，分配给所有捆的第i（i=1,...8)种类型的原料总根数应该不超过给定的原料根数。相应的从第二种规格中降级下来的不同类型的原材料分配给所有捆的总根数也不超过其剩余的总根数。这两项分别由模型中的约束（9）和（10）来体现。同样对于第二种规格的14种类型的原材料，分配给所有捆的第m（m=1,...,14)种类型的原料总根数应该不超过给定的原料根数。相应的从第三种规格中降级下来的不同类型的原材料分配给所有捆的总根数也不超过其剩余的总根数。这两项分别由模型中的约束（11）和（12）来体现。对于第三种规格的24中类型的原材料，分配给所有捆的第n（n=1,…,24）种类型的原材料总根数不超过给定的原料。由于不存在降级下来的原料，则由模型中的约束（13）来体现。由原问题要求(3)可知，各种不同规格每捆的总根数可以比标准少一根。对于第一规格，约束（14）表明第j捆的总根数为19或0。约束（15）表明第j捆的总根数为20或。对于第二规格，约束（16）表明第q捆的总根数为7或0.约束（17）表明第q捆的总根数为8或0。对于第三规格，约束（18）表明第w捆的总根数为4或0.约束（19）表明第w捆的总根数为5