天然肠衣搭配问题.doc

天然肠衣搭配问题摘要肠衣的搭配问题就是把给定的若干长度不同的原料进行搭配成捆，使得每捆的总长度，所含原料的根数满足一定条件的情况下，得到的总成品捆数和某些规格的成品捆数越多越好，从而可以最大可能的提高公司肠衣的销售收入。、本文就肠衣的搭配方案问题进行了研究，通过对题目中给定的具体数据进行分析和合理的假设，得到求解该问题最优解的多目标线性整数规划模型。模型中含有较多的决策变量及约束方程。因为问题对食品保鲜有具体的时间要求，为了在有限的时间内得到问题的尽可能合理的搭配方案，使得工人可以按照搭配方案进行捆扎，我们把建立的大规模整数目标规划问题的求解分解成若干个较小规模的整数线性规划问题的求解。运用Lingo 软件编程计算每个整数线性规划问题的最优搭配方案及相应的捆数，同时考虑到每捆的总长度要求、根数要求及不同规格的原材料间的可能的降级使用，我们给出了一个求问题可行解的一个算法，从而得到肠衣搭配问题的一个通用的方案。通过把算法运用到问题给定的实际数据中，我们可以得到算法的几个特点。首先，该算法可以在几分钟内产生可行的原料搭配方案，使得每个成品捆都满足相应的总长度要求、每捆的根数要求。其次，方案中也考虑到了规格长的剩余原料可降级使用，以提高原料使用率。最后，也是更重要的是，该算法得到的总捆数和最短长度最长的成品捆数与这两类捆数的上界是非常接近的。关键词：优化肠衣的优化搭配方法 多目标线性整数规划 单目标线性整数规划 运筹lingo软件 目录一、 问题重述 . (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-8 lingo 编程代码(12)一、问题重述天然肠衣（以下简称肠衣）制作加工是我国的一个传统产业，出口量占世界首位。肠衣经过清洗整理后被分割成长度不等的小段（原料），进入组装工序。传统的生产方式依靠人工，边丈量原料长度边心算，将原材料按指定根数和总长度组装出成品（捆）。原料按长度分档，通常以0.5米为一档，如：3-3.4米按3米计算，3.5米-3.9米按3.5米计算，其余的依此类推。表1是几种常见成品的规格，长度单位为米，表示没有上限，但实际长度小于26米。表1 成品规格表最短长度最大长度根数总长度36.52089713.588914589 为了提高生产效率，公司计划改变组装工艺，先丈量所有原料，建立一个原料表。表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给出的实际数据进行求解，给出搭配方案。二、模型的基本假设和符号说明2.1 模型的基本假设（1）假设每类型的原材料不可以再进行分割。（2）在计算长度时，我们按每档的最短长度作为该种类型的原料的长度。（3）在降级时，降级材料的长度必须为原长度。2.2 符号说明：第一规格的成品中一捆的根数为19时，第 j捆中所需的第i种类型的原料的根数；：第一规格的成品中一捆的根数为20时，第 j捆中所需的第i种类型的原料的根数；:第二规格的成品中一捆的根数为7时，第 q捆中所需的第m种类型的原料的根数；: 第二规格的成品中一捆的根数为8时，第 q捆中所需的第m种类型的原料的根数；：第三规格的成品中一捆的根数为4时，第 w捆中所需的第n种类型的原料的根数；：第三规格的成品中一捆的根数为5时，第 w捆中所需的第n种类型的原料的根数； 三、问题分析与模型建立 3.1 问题分析肠衣的搭配问题就是把给定的若干长度不同的原料进行搭配成捆，使得每捆的总长度，所含原料的根数满足一定条件的情况下，得到的总成品捆数和某些规格的成品捆数越多越好，从而可以最大可能的提高公司肠衣的销售收入。肠衣搭配方案需要满足的具体要求有：装出的成品最多，成品捆数相同的捆选最短长度最长的成品，第二第三规格如出现材料剩余现象要进行降级处理，为了食品保鲜必需在30分钟内完成整个方案。3.2 模型建立根据以上的符号说明及对问题的具体分析，我们建立了如下的多目标的线性整数规划模型： （1） （2）s.t. （3） （4） （5） （6） （7） （8） （9） (10) (11) (12) (13) (14) (15) (16) (17) (18) (19)3.3 模型分析由原问题要求(3)和（4）可知，对于剩余原料，不同的规格可以降级使用，并且一捆的总根数允许比一捆标准的总根数少1根。对于第一规格的八种不同类型的原料长度和总根数以及第二规格可降级使用的原料的长度和总根数，可知第一规格的总捆数不超过56捆。对于j=1,.,56,第j捆中第一规格的不同类型的原料根数与相应的长度乘积之和加上第二规格中剩余后降级下来的不同类型的原料根数与相应的长度乘积之和要满足每捆中总长度介于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或0。目标函数中包含两个目标，目标（1）为最大化搭配方案的最大捆数，其中包含三种规格，每种规格的成品捆中两类根数不同的捆的总数。目标（2）为最大化搭配方案的第三种规格的总捆数。1(p125-p153), 5(p10-p13,p76), 4(p92-p101)四、模型的求解 由于以上的多目标整数规划模型中所含的变量个数和满足的约束方程太多，可能导致用matlab,lingo,lindo等数学软件进行计算时间过长而不能满足30分钟内产生方案 模型中含有较多的决策变量及约束方程。因为问题对食品保鲜有具体的时间要求，为了在有限的时间内得到问题的尽可能合理的搭配方案，使得工人可以按照搭配方案进行捆扎，我们把建立的大规模整数目标规划问题的求解分解成若干个较小规模的整数线性规划问题的求解。运用Lingo 软件编程计算每个整数线性规划问题的最优搭配方案及相应的捆数，同时考虑到每捆的总长度要求、根数要求及不同规格的原材料间的可能的降级使用，我们给出了一个求问题可行解的一个算法，从而得到肠衣搭配问题的一个通用的方案。4.1 求解第三规格的总捆数第三规格中原料的总根数为677根，假设所有的捆中每捆都含有5根原材料，可以得到最大可能的捆数为135捆。我们求解如下的整数规划模型:MAX S.t. （20） （21） （22） 其中（20）约束条件表明了每捆的总长度限制，目标函数为第三种规格的原材料全部以5根为一捆得到的总捆数。（21）约束条件表明分配给所有捆的第n（i=1,.24)种类型的原料总根数应该不超过给定的原料根数；（22）约束表明第w捆的总根数为5或0。经过对上述模型进行lingo编程，我们可以如下结果，lingo代码见附录1； 程序产生的搭配方案可得到129捆成品，用时：02:13，剩余的不同类型的根数和对应的长度如下表所示。 长度2020.52121.5数量18185从结果可以看得，原材料有较多剩余，为了使得到的成品捆数尽可能多，由以上方法中剩余的原材料再以4根为一捆进行搭配，共有4种剩余原材料，可以得到最大可能的捆数为8捆，我们求解如下的线性整数规划模型:MAX S.t.模型中的约束条件及目标函数同前一个线性整数规划模型。程序的运行结果发现没有可行解，即剩余的原材料再以4根一捆搭配不可能产生满足条件的成品捆。综合以上步骤，可以得出此种方案最多能产生129捆成品。对于第三规格，我们尝试另外一种方法产生搭配方案，即先假设所有的捆中每捆都含有4根原材料，求解的相应的整数线性规划模型。运行lingo软件，lingo代码见附录2，我们可以得到如下结果，程序产生的搭配方案可得到9捆成品，用时：00:01，剩余的不同类型的根数和对应的长度如下表所示。 长度1414.51515.51616.51717.51818.51919.52020.52121.5数量3529304228424449506452634935262由以上方法中剩余的原材料再以5根为一捆进行搭配，求解的相应的整数线性规划模型，可以得到最大可能的捆数为128捆，运行lingo软件，lingo代码见附录3，用时：2:32，我们可以得到如下结果，程序产生的搭配方案可得到126捆成品，剩余的不同类型的根数和对应的长度如下表所示。 长度1415.51718.5根数7112综合两个数据，可以得出此种最多能有135捆；比较两种最后所得到的最多捆数，可以看出第二种多，因为问题要求产生的最短长度最长的成品越多越好，所以，选用第二种方案，其成品捆数为135捆。然后把剩余原材料成品降级到第二规格中。4.2 求解第二规格的总捆数求解第二规格总捆数的思路是和求解第三规格总捆数的思路大致相同，只是加入了降级处理，但是我们把第三规格剩余的原材料加入到第二规格中，形成新的第二规格原材料分布图，所以思路还是和求解第三规格总捆数的思路相同。根据第三规格最终所选择的方法后的剩余原材料，降级进入第二规格，整理后的第二规格原材料总根数为365根，共有18种原材料，原材料分布如下：长度77.588.599.51010.51111.51212.51313.5根数2424202521232118312322591825长度1415.51718.5根数7112 第二规格中原料的总根数为365根，假设所有的捆中每捆都含有7根原材料，求解的相应的整数线性规划模型。运行lingo软件，lingo代码见附录4，我们可以得到如下结果，程序产生的搭配方案可得到23捆成品，用时：00:02，剩余的不同类型的根数和对应的长度如下表所示。 长度77.588.599.51010.511根数242420252123211828由以上方法中剩余的原材料再以8根为一捆进行搭配，模型中的约束条件及目标函数同前一个线性整数规划模型。程序的运行结果发现没有可行解，即剩余的原材料再以8根一捆搭配不可能产生满足条件的成品捆。综合以上步骤，可以得出此种方案最多能产生23捆成品.对于第二规格，我们尝试另外一种方法产生搭配方案，即先假设所有的捆中每捆都含有8根原材料，求解的相应的整数线性规划模型。运行lingo软件，lingo代码见附录5，我们可以得到如下结果，程序产生的搭配方案可得到40捆成品，用时：02:23，剩余的不同类型的根数和对应的长度如下表所示。 长度 7 7.5 数量 22 23由以上方法中剩余的原材料再以7根为一捆进行搭配，模型中的约束条件及目标函数同前一个线性整数规划模型。程序的运行结果发现没有可行解，即剩余的原材料再以7根一捆搭配不可能产生满足条件的成品捆。综合以上步骤，可以得出此种方案最多能产生40捆成品.比较两种最后所得到的最多捆数，可以看出第二种多，因为问题要求产生的最短长度最长的成品越多越好，所以，选用第二种方案，其成品捆数为40捆。然后把剩余原材料成品降级到第一规格中。4.3 求解第一规格的总捆数求解第一规格总捆数的思路是和求解第二规格总捆数的思路相同，根据第二规格最终所选择的方法后的剩余原材料，降级进入第一规格，整理后的第一规格原材料总根数为337根，共有10种原材料，原材料分布如下：长度 3 3.5 4 4.5 5 5.5 6 6.5 7 7.5 数量 43 59 39 41 27 28 34 21 22 23第一规格中原料的总根数为337根，假设所有的捆中每捆都含有20根原材料，求解的相应的整数线性规划模型。运行lingo软件，lingo代码见附录，我们可以得到如下结果，程序产生的搭配方案可得到14捆成品，用时：00:00，剩余的不同类型的根数和对应的长度如下表所示。 长度 3 5.5 6 6.5 7 7.5 数量 1 2 4 19 17 14 由以上方法中剩余的原材料再以19根为一捆进行搭配，模型中的约束条件及目标函数同前一个线性整数规划模型。程序的运行结果发现没有可行解，即剩余的原材料再以19根一捆搭配不可能产生满足条件的成品捆。综合以上步骤，可以得出此种方案最多能产生14捆成品.对于第一规格，我们尝试另外一种方法产生搭配方案，即先假设所有的捆中每捆都含有19根原材料，求解的相应的整数线性规划模型。运行lingo软件，lingo代码见附录，我们可以得到如下结果，程序产生的搭配方案可得到16捆成品，用时：0:00，剩余的不同类型的根数和对应的长度如下表所示。 长度3.544.555.56.577.5数量233121714由以上方法中剩余的原材料再以20根为一捆进行搭配，模型中的约束条件及目标函数同前一个线性整数规划模型。程序的运行结果发现没有可行解，即剩余的原材料再以20根一捆搭配不可能产生满足条件的成品捆。综合以上步骤，可以得出此种方案最多能产生16捆成品.比较两种最后所得到的最多捆数，可以看出第二种多，因为问题要求产生的最短长度最长的成品越多越好，所以，选用第二种方案，其成品捆数为16捆。综上三种规格最多的捆数，第一规格最多捆数为16捆，第二规格最多捆数为40捆，第三规格最多捆数为135，相加得出最多为191捆，剩余总长度是209，以一捆最短长度88.5计算，最多可以有2.3捆. 2(p322-p333), 1(p125-p153)根据以上解决问题的算法步骤，我们得到如下的算法流程。先计算所有可能的5根一捆的捆数是S1，再计算剩余原料所能产生的4根一捆的捆数S2先计算所有可能的4根一捆的捆数是T1，再计算剩余原料所能产生的5根一捆的捆数T2计算两类捆数之和S=S1+S2计算两类捆数之和T=T1+T2选择S和T中最大的方案作为第三种规格的分配方案，其总捆数记为L1。剩余的材料降级到第二规格第三规格第二规格（包括原有的第二规格和从第三规格中降级的）先计算所有可能的7根一捆的捆数是E1，再计算剩余原料所能产生的8根一捆的捆数E2先计算所有可能的8根一捆的捆数是F1，再计算剩余原料所能产生的7根一捆的捆数F2选择E1+E2和F1+F2中最大的方案作为第二种规格的分配方案，其总捆数记为L2。剩余的材料降级到第一规格第一规格（包括原有的第一规格和从第二规格中降级的）先计算所有可能的20根一捆的捆数是X1，再计算剩余原料所能产生的19根一捆的捆数X2先计算所有可能的19根一捆的捆数是Y1，再计算剩余原料所能产生的20根一捆的捆数Y2选择X1+X2和Y1+Y2中最大的方案作为第一种规格的分配方案，其总捆数记为L3。把三种规格分别的搭配方案组合成一个完整的方案。该方案的总捆数=L1+L2+L3.五、结果分析通过把算法运用到问题给定的实际数据中，我们可以得到算法的几个特点。首先，该算法可以在几分钟内产生可行的原料搭配方案，使得每个成品捆都满足相应的总长度要求、每捆的根数要求。其次，方案中也考虑到了规格长的剩余原料可降级使用，以提高原料使用率。最终要的是，我们要考虑算法的近似程度。从原料总根数和成品捆的根数的角度，设Z1为第三规格每捆有4根的捆数，Z2为第三规格每捆有5根的捆数，Z3为第二规格每捆有7根的捆数，Z4为第二规格每捆有8根的捆数，Z5为第一规格每捆有19根的捆数，Z6为第一规格每捆有20根的捆数；通过计算得到第一规格共有292根；第二规格共有354根，第三规格共有677根，总根数有1323根；三个规格的总根数一定不超过原料总根数，即4*Z1+5*Z2+7*Z3+8*Z4+19*Z5+20*Z6=1323;由于第三规格没有降级，所以，第三规格的总根数一定不超过第三规格原料的总根数，即4*Z1+5*Z2=677;；并且，若四根一捆，每根长度大概在22.25（第三规格总长度除以4），比22.5长的原料至少要有一根，而从原料描述表看，比22.5更长的只有9根，所以，四根一捆的最多9捆，即Z1=9。模型如下MAX Z1+Z2+Z3+Z4+Z5+Z6S.T.4*Z1+5*Z2+7*Z3+8*Z4+19*Z5+20*Z6=13234*Z1+5*Z2=677Z19根据以上推断，通过lingo软件编程，lingo代码见附录8，得到最多可行解为229捆。从原料的总长度和每捆的长度限制的角度出发，每种规格原料长度乘以相应的原材料根数之和除以一捆总长度最小长度（88.5），计算如下：第一捆总长1305.5，第二捆总长3705.5，第三捆总长12159.5，总长度17170.5；所以，三个规格最多能有194捆；而但从第三规格考虑，第三规格最多能有成品137捆；取以上求得的两个总捆数上限的最小值，这也是最大可能的捆数，即194捆。把我们计算得到的总捆数191捆与理论上最大可能的捆数194捆进行比较，接近率为98.4%；由于第三规格没有进行降级，所以可以得到第三规格成品最理想的最大捆数，即上述求的的137捆，而我们计算得出的第三规格的捆数最多为135捆，相比非常接近，接近率为98.5%，所以，此模型的建立与求解的结果是比较合理的；参考文献1陈东彦，李冬梅，王树忠编著数学建模，北京：科学出版社 2007。2谢金星，薛毅编著优化建模与LINDO/LINGO软件，北京：清华大学出版社 2009。3姜启源，谢金星，叶俊编著数学模型第三版，北京：高等教育出版社 2005。4李志林，欧宜贵编著数学建模及典型案例分析，北京:化学工业出版社 2006。5刁在筠，郑汗鼎，刘家壮，刘桂真编著运筹学第二版，北京：高等教育出版社2004 附录附录一：（3-1-5）sets:demand/1.20/:c,a;supply/1.125/;!:u;!,v;link(demand,supply):x;!,y;endsetsdata:c=35 29 30 42 28 42 45 49 50 64 52 63 49 35 27 16 12 2 6 1;a=14 14.5 15 15.5 16 16.5 17 17.5 18 18.5 19 19.5 20 20.5 21 21.5 22 22.5 23.5 25.5;enddatamax=1/5*sum(link(i,j):x(i,j);for(demand(i): sum(supply(j):x(i,j)- c(i)=88.5;);for(supply(j):sum(demand(i):x(i,j)*a(i)=89.5;);for(link(i,j):gin(x(i,j););for(link(i,j):bnd(0,x(i,j),5););end附录 二：（3-1-4）sets:demand/1.20/:c,a;supply/1.9/;link(demand,supply):x;endsetsdata:c=35 29 30 42 28 42 45 49 50 64 52 63 49 35 27 16 12 2 6 1;a=14 14.5 15 15.5 16 16.5 17 17.5 18 18.5 19 19.5 20 20.5 21 21.5 22 22.5 23.5 25.5;enddatamax=1/4*sum(link(i,j):x(i,j);for(demand(i): sum(supply(j):x(i,j)- c(i)=88.5;);for(supply(j):sum(demand(i):x(i,j)*a(i)=89.5;);for(link(i,j):gin(x(i,j););for(link(i,j):bnd(0,x(i,j),4););end附录 三：（3-2-4）sets:demand/1.16/:c,a;supply/1.126/;!:u;!,v;link(demand,supply):x;!,y;endsetsdata:c=35 29 30 42 28 42 45 49 50 64 52 63 49 35 26 2;a=14 14.5 15 15.5 16 16.5 17 17.5 18 18.5 19 19.5 20 20.5 21 21.5;enddatamax=1/5*sum(link(i,j):x(i,j);for(demand(i): sum(supply(j):x(i,j)- c(i)=88.5;);for(supply(j):sum(demand(i):x(i,j)*a(i)=89.5;);for(link(i,j):gin(x(i,j););for(link(i,j):bnd(0,x(i,j),5););end附录 四：（2-1-7）sets:demand/1.18/:c,a;supply/1.23/;!:u;!,v;link(demand,supply):x;!,y;endsetsdata:a= 7 7.5 8 8.5 9 9.5 10 10.5 11 11.5 12 12.5 13 13.5 14 15.5 17 18.5;c= 24 24 20 25 21 23 21 18 31 23 22 59 18 25 7 1 1 2 ;enddatamax=1/7*sum(link(i,j):x(i,j); for(demand(i): sum(supply(j):x(i,j)- c(i) =88.5;);for(supply(j):sum(demand(i):x(i,j)*a(i)=89.5;);for(link(i,j):gin(x(i,j););for(link(i,j):bnd(0,x(i,j),7););end附录 五：（2-1-8）sets:demand/1.18/:c,a;supply/1.40/;!:u;!,v;link(demand,supply):x;!,y;endsetsdat