天然肠衣搭配问题.doc

2010高教社杯全国大学生数学建模竞赛 承 诺 书 我们仔细阅读了中国大学生数学建模竞赛的竞赛规则. 我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。 我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。 我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。 我们参赛选择的题号是（从A/B/C/D中选择一项填写）： 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）： 参赛队员 (打印并签名) ：1. 2. 3. 指导教师或指导教师组负责人 (打印并签名)： 日期： 年 月 日 天然肠衣搭配问题 摘 要 本文主要是对天然肠衣搭配问题进行探讨与研究，建立线性规划数学模型，利用编程，得到符合实际的最优方案。文章以成品规格表和原料描述表为参考依据，采用整数规划，分别从“最大捆数、最优方案和时间限制”三个方面建立优化模型，利用编程最优求解，最终制作出了一套科学、合理和实用的搭配方案。 本文分三步解决问题，具体如下： 首先，通过分析题设，按照要求（1）、（3）和（4），建立“最大捆数”的优化模型。根据文中给出的三种成品规格，我们建立了三个求最大捆数的整数规划模型。考虑到剩余原料可以降级规格使用，我们采用“倒序”原则，利用编程，先算出第三种规格的最大捆数，接着把剩余原料23.5-23.9米的6根和25.5-25.9米的1根降级到第二种规格搭配使用，以此类推，运行得到三种规格的最大捆数，分别为134捆,41捆和16捆。 其次，根据最大捆数，本文得到两个具体的搭配方案。方案一是根据材料使用情况建立最大损失函数模型，通过编程得到搭配方案（表）。方案二是按照原料的最大利用原则建立优化模型，利用编程得到搭配方案（表）， 按照要求（2），比较两个方案的剩余原料（表），档次低的原料越多，搭配方案越好。我们最终选择方案二。对剩余原料再次替代，得到优化方案（表）。 最后，考虑到食品保鲜，要求30分钟内产生方案，而第三规格原料数据太多，给程序运行带来困难，我们对模型改进。把第三规格原料分成5个批次（表、），对每个批次分别建模，求出的最大捆数分别32,32,32,18,19。然后通过编程分别求出各个批次的搭配方案（表、、）。 最后剩余的5根，利用替代原则，再优化1捆，得到最终的搭配方案（表）。 关键词： 整数规划 搭配方案 最优求解 天然肠衣 1 问题重述 天然肠衣的制作加工首先要经过清洗整理后被分割成长度不等的小段（原料），然后进入组装工序。传统的生产方式就是人工边丈量原料长度边心算，将 原材料按指定根数和总长度组装出成品（捆）。 原料按长度分档，以0.5米为一档，附表是几种常见成品的规格，长度单位为米，表示没有上限，但实际长度小于米。 为了提高生产效率，公司计划改变组装工艺，先丈量所有原料，建立一个原料表。附表为某批次原料描述。 根据以上成品和原料描述，设计一个原料搭配方案，工人根据这个方案“照方抓药”进行生产。 公司对搭配方案有以下具体要求： （1）对于给定的一批原料，装出的成品捆数越多越好； （2）对于成品捆数相同的方案，最短长度最长的成品越多，方案越好； （3）为提高原料使用率，总长度允许有米的误差，总根数允许比标准少根； （4）某种规格对应原料如果出现剩余，可以降级规格使用。如长度为米的原料可以和长度介于米的进行捆扎，成品属于米的规格； （5）为了食品保鲜,要求在分钟内产生方案。 根据上述问题建立数学模型，给出求解方法，并对附表、附表给出的实际数据进行求解，给出搭配方案。 2 问题分析 问题中要求根据成品规格和原料描述，以及公司对搭配方案的具体要求，设计一个原料的最优搭配方案。 2.1对最大捆数的分析 制作原