《2011高教社杯全国大学生数学建模竞赛D题.doc》由会员分享，可在线阅读，更多相关《2011高教社杯全国大学生数学建模竞赛D题.doc（18页珍藏版）》请在三一文库上搜索。
1、2011高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）： D 我们的参赛报名号为（如果赛区设置
2、报名号的话）： 所属学校（请填写完整的全名）： 成都航空职业技术学院 参赛队员 (打印并签名) ：1. 林 亮 2. 吕 迪 3. 崔丁飞 指导教师或指导教师组负责人 (打印并签名)： 日期： 年 月 日赛区评阅编号（由赛区组委会评阅前进行编号）：2011高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：天然肠衣搭配问题摘要 本文针对天然肠衣搭配问题的研究，根据公司对搭配方案的具体要求，建立起最佳搭配模型。首先，在理
3、想情况下建立最优搭配方案，然而，此方案中变量太多，可操作性较低，所以不易实现。在此基础上，我们先简化模型减少变量，用maple编程的方法来确定具体要求下最优的搭配方案。先将三种不同规格的成品进行最优化求解，将规格2（7至13.5）的剩余原料与规格1（3至6.5）的剩余原料进行合理搭配，两种原料搭配后的剩余原料再与规格3（14至）的剩余原料进行合理搭配。如果合理搭配之后规格3（14至）的原料还有剩余则降级成规格2（7至13.5）进行捆扎，如果最终规格1（3至6.5）的原料还有剩余，则不能进行捆扎，因此该剩余规格1（3至6.5）的原料不能进行生产，从而使搭配出的成品捆数较多。按此解决方案代入表2中
4、的数据，得出该批原料搭配出的成品最优捆数为187捆，并在对实际数据进行求解的过程中得出相应的搭配方案（Maple编程得出的三种规格的搭配方案见附录二），并模拟出了产生方案所需总时间大约为22分钟。 按题中具体要求得到的模型搭配方式太多，不适宜工人的实际操作。因此，我们根据表一和表二的描述设计了一个原料搭配方案。关键词：肠衣搭配、maple编程。一、问题重述天然肠衣（以下简称肠衣）制作加工是我国的一个传统产业，出口量占世界首位。肠衣经过清洗整理后被分割成长度不等的小段（原料），进入组装工序。传统的生产方式依靠人工，边丈量原料长度边心算，将原材料按指定根数和总长度组装出成品（捆）。原料按长度分档，
5、通常以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
6、.5-10.9根数2424202521232118长度11-11.411.5-11.912-12.412.5-12.913-13.413.5-13.914-14.414.4-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.
7、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分钟内产生方案。请建立上述问题的数学模型，给出
8、求解方法，并对表1、表2给出的实际数据进行求解，给出搭配方案。二、模型假设1不计丈量肠衣时的误差。2按照表一中三种成品规格进行生产，不考虑其它规格。3不考虑外界因素对产生方案时间的影响。4肠衣原料实际长度小于26米。5优化后的剩余量降级使用，不再考虑长度，可以加到下一种规格的任何一档。6原料按长度分档，以0.5米为一档，3-3.4米按3米计算，3.5-3.9按3.5米计算，其余的以此类推。三、符号说明：成品总捆数；：第种规格产品的捆数；：第种规格成品按第种搭配方式所需第档原料数目；：第种规格分配好以后原料剩余总根数；：产生方案所需时间；：第档原料数目；：第档原料长度；：第种规格按第种方式搭配的
9、捆数；：第规格成品所需根数；：第种规格的组合方式；（注释：=1,2,3，46；=1,2,3；第1种规格为成品（3至6.5），第2种规格为成品（7至13.5），第3种规格为成品（14至）。四、模型的建立 天然肠衣要按照指定的根数和总长度组装出成品，对于给定的一批原料来说，组装出成品的捆数越多越好，我们将成品的捆数作为目标，得出以下整数优目标函数。天然肠衣原料长度不一，以0.5米为一档共被分为46档。为提高原料利用率，总长度允许有0.5米的误差，得到第一个约束条件；第种规格成品按第种搭配方式所需第档原料数目为定值，则由此得到第二至第五个约束条件；第种规格成品按第种方式搭配的捆数不能超过第档原料数目
10、，据此得到第七个约束条件。 目标函数：约束条件：五、模型的求解由总模型可知，变量数目相当庞大，如果用穷举法求解模型，时间将会大大超过30分钟，而且将所有规格的原材料放在一起捆扎势必对工人的工作增大难度。所以为了避免计算困难及企业工人操作上的困难，将模型分为三个优化模型，即针对三种规格的肠衣分别求出最优捆扎方案，再将剩余的原料进行优化组合。由于长度长的原料可以降级处理，长度短的却不能升级，所以先将借用规格2的原料来补充规格1剩下的余料捆扎出最多的成品，如果不够再向规格3借用。类似地，如果规格2借用后还有剩余就借用规格3的余料进行优化捆扎。如果最后只剩规格1的余料，那这些余料将无法再组合，组装结束
11、；如果最后只剩规格2的余料，将其全部降级成规格1进行捆扎；如果最后只剩规格3的余料，将其全部降级成规格2进行捆扎。最后再结合前面得出的，得出成品的最多捆数。各规格优化求解后的剩余量可降级使用，如下示意图：规格1规格3规格2剩余量将规格1中余量补齐剩余量将规格2中余量补齐剩余量将规格1中余量补齐六、实例运算用maple编程（对规格1编程见附录一）对天然肠衣的三种规格分别进行最优化求解,在编程时，将最短长度最长的的成品首先进行运算，使得方案满足最短长度最长的成品越多越好的条件。求得：第1种规格：最优化捆数；剩余原料根数；Maple运行时间为439.5秒；第2种规格：最优化捆数；剩余原料根数；Map
12、le运行时间为232.8秒；第3种规格：最优化捆数；剩余原料根数；Maple运行时间为61.2秒；规格1剩余12根要补成一捆成品需在规格2剩余的145根里拿7根，规格3剩余49根，所以要从规格3里拿出49根补到规格2，现在规格2里的总根数为145-7=138根，余5，所以规格2里的剩余原料为5根不能进行生产。综上所述，得到的成品数捆，总的运行时间分钟。表一为按第三种规格生产的搭配方案，表二为第二种生产的搭配方案，表三为第三种生产的搭配方案。根据此原理搭配方案，工人可根据此方案“照方抓药”进行生产。（表格奇数行表示原料的根数，偶数行表示原料搭配方案）表一表二表三七、模型评价与改进本论文所建立的数
13、学模型有成熟的理论基础，操作较简单。针对条件约束中生产方案的时间不能超过30分钟的问题，我们在对表一、表二中实际数据进行求解过程中，模拟了本次产生方案的时间。Maple运行时间为12.225分钟，手工输入数据花费了5分钟，分配搭配方案用了5分钟，共计22.225分钟，所以在30分钟之内该方案可行，符合保持天然肠衣新鲜的要求。该模型简单易行，运行时间短，可推广到其他需要短时间内得到搭配方案的实例中。该模型中没有考虑降级使用的肠衣是否能被切割的问题，如果可以进行合理切割，那么总捆数将会变大。八、参考文献 1、罗荣桂，新编运筹学题解，武汉，华中科技大学出版社，2002年。附录一 reatrat:k1
14、:=43,59,39,41,27,28,34,21:k1:for nn from 7 to 20 do#nn:=8:num:=0:nn1:=nn:nn2:=nn:nn3:=nn:nn4:=nn:nn5:=nn:nn6:=nn:nn7:=nn:nn8:=nn:k1:=43,59,39,41,27,28,34,21:for i from 0 to nn1 do if(k11nn) then nn1:=nn: elif(k11nn) then nn2:=nn: elif(k12nn) then nn3:=nn: elif(k13nn) then nn4:=nn: elif(k14nn) then n
15、n5:=nn: elif(k15nn) then nn6:=nn: elif(k16nn) then nn7:=nn: elif(k17nn) then nn8:=nn: elif(k18=0 and k12-j=0 and k13-k=0 and k14-l=0 and k15-m=0 and k16-n=0 and k17-o=0 and k18-p=0) then print(i,j,k,l,m,n,o,p,i+j+k+l+m+n+o+p,3*i+3.5*j+4*k+4.5*l+5*m+5.5*n+6*o+6.5*p); k11:=k11-i: k12:=k12-j: k13:=k13-k: k14:=k14-l: k15:=k15-m: k16:=k16-n: k17:=k17-o: k18:=k18-p:num:=num+1:end if:od:od:od:od:od:od:od:od:print(num,k1,nn):printf(/n/n);od:附录二规格1：规格2：规格3：16