天然肠衣搭配问题.doc

2011高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）： 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）： 参赛队员 (打印并签名) ：1. 2. 3. 指导教师或指导教师组负责人 (打印并签名)： 日期： 年 月 日赛区评阅编号（由赛区组委会评阅前进行编号）：2011高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：关于天然肠衣搭配的最优模型摘要本文主要解决的是天然肠衣的原料搭配方案问题。我们用线性规划模型解决了该问题。由题意知若某种规格对应原料出现剩余，可以降级使用。我们解决本题时，首先计算第三种成品的最大捆数，进而求出它的剩余原料，然后把第三种成品的剩余原料用到第二种成品的原料中，计算出第二种成品的最大捆数和剩余原料。用同样的方法计算第一种成品的最大捆数和总原料的剩余量。对于该问题我们综合考虑该公司对搭配方案的具体要求，做出以下解决方案：1：估算最大捆数我们根据题中材料的要求得出了平衡式；根据题中提供的原料计算出各个成品规格的原料总长度；根据各种成品的总长度为89米和原料的总长度和，估算出了各种成品的最大捆数，根据我们估算出的各种成品的最大捆数估算出了原料的剩余量。2：用MATLAB和LINGO验证估算出的结果是否合理 我们根据题意，在不考虑为了提高使用率，允许误差的情况下，列出了求最优方案的MATLAB编程式，得出最优方案。根据最优方案我们求出了原料的剩余量，与此同时我们根据最优方案编出求最大捆数的LINGO编程，用LINGO方程求出了在允许误差的情况下的最大捆数。而后将剩余量在考虑误差的情况下算出了剩余量的最大捆数。最后对和求和得到了最终的最大捆数；又根据计算的结果算出了原料的剩余量，同理得出其他各类成品的最大捆数。 根据我们计算的结果，和估算值相近，可以确定方案的正确性。 关键词 搭配方案 线性规划 MATLAB LINGO1.问题重述天然肠衣（以下简称肠衣）制作加工是我国的一个传统产业，出口量占世界首位。肠衣经过清洗整理后被分割成不等的小段（原料），进入组装工序。传统的生产方式依靠人工，边丈量原料长度边心算，将原材料按指定根数和总长度组装出成品（捆）。原料按长度分档，通常以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可知，成品规格有3种：第一种成品由最短长度=3米，以0.5米为一档，最大长度=6米，之间长度的组成，且20根为一捆，总长度为89米；第二种成品由最短长度=7米，以0.5米为一档，最大长度为=13.5米，之间的长度组成，且8根为一捆，总长度为89米；第三种成品为最短长度=14米，以0.5米为一档，最大长度没有上限，但实际长度应小于26米，的长度组成，以20根为一捆，总长度为89米。根据表2的已知条件可设计出原料搭配方案。根据该公司的要求：（1）对于数量一定的一批原料，装出的成品捆数越多越好，即剩余原料越少，方案越好；（2）对于成品捆数相同的方案，最短长度最长的成品越多，方案越好，即假若有两种方案，装出的成品捆数都是若方案1的最短长度是,方案2的最短长度是,则取方案1；（3）某种规格对应原料如果出现剩余，可以降级使用，如长度为14米的原料可以和长度介于7-13.5米的进行捆绑，成品属于7-13.5米的规格；在满足题意的要求下，我们对此设计出最优分配方案，建立最优化模型。根据表1，2的数据以及各种成品的长度和根数列出含有未知数的等式，利用MATLAB和LINGO软件求出其解，最大值及分配方案。3.模型的假设（1）假设题中所给的数据完全真实可靠；（2）假设测量肠衣时的误差可以忽略不计；（3）假设由于肠衣的弹性造成的误差忽略不计；（4）假设所有肠衣的质量，弹性都一样；（5）假设原料降级使用时不能剪断.4.符号说明：长度：根数：总长度()：第种成品原料的总长度5.模型的建立与求解按题意要求，如果想要提高原料使用率，允许有正负0.5的误差，总根数允许比标准少一根；当原料出现剩余时可以降级使用。因为可以降级使用，所以我们先算出第三种成品的最大捆数，计算出第三种成品的余量,按此模型依次算出第二种成品的最大捆数，第二种成品的余量；及第一种产品的最大捆数；和总原料最后的剩余量。为了更好的找到原料搭配方案，所以我们先估算出了最大捆数和剩余量，下面是我们估算的过程：根据我们理解的题意我们，得到了一个模型：依据模型列出公式（1） （2） （3）当=3， =24时将表1,2的数据代入（1）（2）（3）式，得出 即分别为第三种成品的最大捆数，剩余量。如图（1）乘积和长度1414.51515.51616.517根数35293042284245乘积490420.54506514486937653917.5长度17.51818.51919.52020.5根数49506452634935乘积857.590011849881228.5960717.56835.5长度2121.52222.525.523.50根数2716122160乘积5671292644525.514101171.5乘积和000000011924.5当时将表1,2的数据代入（1）（2）（3）式，得出 运用相同的方法我们分别计算出了：1.第二种成品的最大捆数，剩余量。如图（2）乘积和长度77.588.599.510根数24242025212321乘积168180240212.5189218.52101418长度10.51111.51212.51313.5根数18312322591825乘积189341264.5264737.5234337.52367.5乘积和3785.5当时将表1,2的数据代入（1）（2）（3）式，得出 和2.第一种成品的最大捆数，剩余量。如图（3）乘积和长度33.544.555.56根数43593941272834乘积129206.5156184.5135154204长度6.5根数21000000乘积136.51305.5由最大捆数得出 即这批原料可以组装191捆。以上结果是用逻辑推理而得，并不是根据实际的最优的分配方案得到的最大捆数，和最少的剩余量，若要用最优分配方案去得到最大捆数和最少的剩余量，且最大程度的利用原料。必须最大程度的利用各成品的最大长度，故根据要求列出以下等式： （4） （5）公式（4）中表示各档次所取的根数；公式（5）中表示各成品一捆中的根数；运用MATLAB与LINGO得出各成品的最优分配方案、在最优分配方案下的最大的捆数和最小的剩余量：第三种成品的分配方案如下表所示（程序见附录1）：长度取得根数1403100011000000000002014.50002000000000000002001500202000100000000200015.53000020010000000300001600011100020000020000016.50000000000020030000001710000020002012000000017.50000000200002000000001800000000001202000000018.50000000000202002000001900000000030001000001019.50000000030000001002022000000002000100011010020.50000002000000000000202100000200000000000100021.50000200000000000010002300020000000000000000123.500200000000000000000025.5120000000000000000000用MATLAB计算得出的最大捆数为：125又根据题中（3）为提高原料使用率，总长度允许有0.5米的误差，总根数允许比标准少一根我们得到了五组数据，如下表：长度1414.5151616.51717.51818.519.520.523.5根数000130000301误差0101000000（误差0.5）0长度000000001（误差1根）03根数10000110002（误差0.5）误差01100001002（误差0.5）总计得最大捆数：130通过计算得出剩余原料如下表：原料18.5192020.52121.522.5余量12231542因为剩余的原料可以降级使用所以：第二种成品的分配方案如下表（程序见附表2）：长度取得根数72210000000000020000047.540034000000000010001080450000000000200001008.500030600000020002100090000000301020000220009.50000206000000000000201000000002004001000000010.50000000060000100000001100000000050020000000011.50000000000050000006001200000000002000060010012.50000000002204500050521300000000200000500000013.500000013000100004000018.5000000100000000000000190000020000000000000002000002000000000000000020.50002000000000000000002100200000000000000000021.502000000000000000000022.5200000000000000000000用MATLAB计算得出的最大捆数为：41又根据题中（3）为提高原料手机用率，总长度允许有正负0.5米的误差，总根数允许比标准少一根我们又得到了七组数据，如下表：长度77.588.599.5101111.51212.521根数42251211（差0.5）3215（少1根0.5）111（少1根0.5）4111（少1根0.5）141111（差0.5）41总计得最大捆数：48通过计算得出剩余原料如下表原料8.5111313.520.5余量12221同理：我们得到的第一种成品的分配方案如下表（程序见附录3）：原料435939412728342112221长度33.544.555.566.58.5111313.520.5方案14004000010001216000000000209090000000200010800000020000016003001000009070004000009020009000000800021000000000604100000000001019000000000010400070000000401000500000016001300000000余量171671410581700221用MATLAB计算得出的最大捆数为：10又根据题中（3）为提高原料手机用率，总长度允许有正负0.5米的误差，总根数允许比标准少一根我们又得到了四组数据，如下表：长度33.544.555.5678.511131420.5根数1162(误差0.5)11444277(误差0.5)558总计得最大捆数为：14通过计算得出剩余原料余料如下表：剩余原料66.5132172由最大捆数得出即运用程序求得的最大捆数是192总结以上我们的最终方案为：第一种成品的分配方案如下表：长度每捆所取的根数3142900098000003.50161009061011640098160200011004.50000070041900050000000210090135.500003001000000600000090000906.500000400000008.5100010000000011002000000000013000200000000013.5020000000000020.51000000000000第二种成品的分配方案如下表：长度每捆取得根数72210000000000020000047.540034000000000010001080450000000000200001008.500030600000020002100090000000301020000220009.50000206000000000000201000000002004001000000010.50000000060000100000001100000000050020000000011.50000000000050000006001200000000002000060010012.50000000002204500050521300000000200000500000013.500000013000100004000018.5000000100000000000000190000020000000000000002000002000000000000000020.50002000000000000000002100200000000000000000021.502000000000000000000022.5200000000000000000000第三种成品的分配方案：长度每一捆取的根数1403100011000000000002014.5002000000000000002001500202000100000000200015.53000020010000000300001600011100020000020000016.50000000000020030000001710000020002000000000017.50000000200000000000001800000000001000000000018.50000000000200000000001900000000030000000001019.50000000030000000000022000000002000100011010020.5000000200000000000020210000020000000000100021.50000200000000000010002300020000000000000000123.500200000000000000000025.5120000000000000000000余料的方案：第一种成品的余料如下表：长度33.54555.5678.511131420.5根数1162(误差0.5)000011442776(误差0.5)558第二种成品的余料如下表：长度77.588.599.5101111.51212.521根数42251211（差0.5）3215（少1根0.5）111（少1根0.5）4111（少1根0.5）141111（差0.5）41第三种成品的余料如下表：长度1414.5151616.51717.51818.519.520.523.5根数131113（误差0.5）1（误差1根）31112（误差0.5）1112（误差0.5）6.模型结果的分析由第五步得出的结果可知：用逻辑方法得出的结果与用线性规划得出的结果有误差，其原因是：（1）逻辑方法只是把各个产品的原料整合成一根来求解，而没考虑到当某种规格的原料有剩余时的可以降级使用这一方面。（2）用逻辑方法并不能完全满足题目要求使捆数达到最多。（3）用逻辑方法得出的结果，不容易看出表1中所要求的每捆中给出的根数。也看不出用了什么方案，和最后剩余的原料是那个长度的；（4）在求解的过程中，运用MATLAB与LINGO软件求得最大捆；很容易看出最优的分配方案是什么样的，也很清晰的得到剩余原料。对于接下来剩余原料的降级求解，利用很方便。7.模型的推广与改进方向7.1模型的推广（1）本模型还适合于计算下料问题，如某公司需制作工架，每套工架需要不同长度的圆钢，而原材料的长度已知，建立一个模型使该公司下料使用的原材料最省，成本费用最低。对此可建立线性规划模型，得到多种组合下料方案；（2）还可用于调度员在满足物资需求和装载条件下，安排从各供应点到各个需求点的运量和路线；（3）销售商根据市场需求和生产成本，确定产品价格使得利润最高；。7.2模型的改进方向由于软件局限性的问题，我们不能很容易的得出最优解。所以我们需要对当前的模型进行改进，找到刚好的方法来解决实际问题。8.模型的优缺点8.1模型的优点：该方案形式简单，通俗易懂，以表格的形式呈现出数据，便于工人操作。方案数据直接显示所用原料，可算出剩余原料，工人可根据原料的使用与剩料为制作各类产品做好准备，提高了操作速度。该方案公式简单明了，编程简单。8.2模型的缺点由于对数学软件并不精通，所用MATLAB计算得出的结果精确度不太高，得出的最优方案只是根据平衡估算出的一个最优解。参考文献1薛山.MATLAB基础教程M. 北京：清华大学出版社, 2011.2韩中庚.数学建模使用教材M. 北京：高等教育出版社， 2012.3编写组.运筹学M. 北京：清华大学出版社， 2005.附件附件1MATLABfor a1=14:0.5:23.5for a2=14:0.5:23.5for x1=0:1:3for x2=0:1:3j=(1+x1+x2)-5;m=(23.5*2+a1*x1+a2*x2)-89;if j=0&m=0 A= x1 x2 B= a1 a2endendendendend其他与此类似LINGOmax=x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14+x15+x16+x17+x18+x19+x20;3*x2+x3+x7+x8+2*x20=35;2*x4+2*x19=29;2*x3+2*x5+x9+2*x18=30;3*x1+2*x6+x9+3*x17=42;x4+x5+x6+2*x10+2*x16=28;2*x12+3*x15=42;x1+2*x7+2*x11+x13+2*x14=45;2*x8+2*x13=49;x11+2*x12+2*x14=50;2*x11+2*x13+2*x16=64;3*x10+x14+x19=52;3*x9+x15+2*x18+2*x20=63;2*x8+x12+x15+x16+x18=49;2*x7+2*x19=35;2*x6+x17=27;2*x5+x17=16;2*x4+x20=12;2*x3=2;2*x2=6;x1=1;第二种成品的分配方案 附录2MATLABfor x1=0:1:8for x2=0:1:8for x3=0:1:3j=(3+x1+x2+x3)-8;m=(13.5*3+a1*x1+a2*x2+a3*x3)-89;if j=0&m=0 A= x1 x2 x3 B=