《天然肠衣搭配问题论文定稿》由会员分享，可在线阅读，更多相关《天然肠衣搭配问题论文定稿（25页珍藏版）》请在金锄头文库上搜索。
1、2011高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）： D 我们的参赛报名号为（如果赛区设置
2、报名号的话）： 所属学校（请填写完整的全名）： 重庆教育学院 参赛队员 (打印并签名) ：1. 王平 2. 王静 3. 王鸿玫 指导教师或指导教师组负责人 (打印并签名)： 施成湘 日期： 2011年 9 月11日赛区评阅编号（由赛区组委会评阅前进行编号）：2011高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：论文题目：天然肠衣搭配问题摘 要随着时代的发展，天然肠衣制作加工已经是我国的一个传统产业，在生产中占优很
3、重要的地位。本文就是针对天然肠衣的加工问题展开讨论并建立相应的优化模型，本问题涉及到两方面内容：（一）方案的内容，（二）方案的个数。根据线性规划理论，建立双目标函数模型。从第四个条件肠衣有剩余的角度入题，即剩余的可以降级使用，我们立运筹学中的双目标函数列出了我们最初的模型原型，从而我们可以从中得出的比较合理优化的分配方案577种，在具体解决这个问题的时候，我们从第三种成品开始建立模型，得出初步方案367种，剩余降级使用的数目8根，将剩余的原料归纳到第二种成品中最长的原料中，再利用第二种成品建立模型得出初步方案107种，并得出剩余数目35根，同理降级到第一种成品最长的原料中使用；最终通过筛选得到
4、的最优方案为第一类12种、第二类33种、第三类34种，从捆数上看则是192捆，详见文中总表。对于第三个条件中提出的为了提高利用率而允许有误差，条件是要在30分钟内得出最好的方案，为降低计算复杂度，算法对文中原材料的取定，是要求尽可能的少。通过运行，得出的最优的方案，见下表，总方案数剩余方案数捆数剩余根数第一类产品367341358第二类产品107334135点三类产品1031216-此双目标函数模型很好的解决了天然肠衣的加工分配问题，且方法具有很强的严密性，提高了运算速度，缩短了安排时间，提高效率，能够广泛推广到其他材料的加工安排问题上。关键词： 肠衣加工 多目标线性规划 (一) 问题的提出1
5、.问题的重述天然肠衣（以下简称肠衣）制作加工是我国的一个传统产业，出口量占世界首位。肠衣经过清洗整理后被分割成长度不等的小段（原料），进入组装工序。传统的生产方式依靠人工，边丈量原料长度边心算，将原材料按指定根数和总长度组装出成品（捆）。原料按长度分档，通常以0.5米为一档，如：3-3.4米按3米计算，3.5米-3.9米按3.5米计算，其余的依此类推。表1是几种常见成品的规格，长度单位为米，表示没有上限，但实际长度小于26米。表1 成品规格表最短长度最大长度根数总长度36.52089713.588914589为了提高生产效率，公司计划改变组装工艺，先丈量所有原料，建立一个原料表。表2为某批次原
6、料描述。表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
7、.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
8、米的误差，总根数允许比标准少1根；(4) 某种规格对应原料如果出现剩余，可以降级使用。如长度为14米的原料可以和长度介于7-13.5米的进行捆扎，成品属于7-13.5米的规格；(5) 为了食品保鲜,要求在30分钟内产生方案。请建立上述问题的数学模型，给出求解方法，并对表1、表2给出的实际数据进行求解，给出搭配方案。2问题的初步分析这是一个典型的优化问题。本问题最终要求给出一个合理的搭配方案，将涉及到两方面内容：（一）方案的内容，（二）为达到尽可能多的使用原材料，如何选择方案，即方案的个数。这两方面将是问题解决的关键。将通过两次建立数学模型，给予求解。对方案的内容，由于要求（2）提到，对成品捆数
9、相同的方案，最短长度最长的方案优先考虑，因此，在同一捆中尽量避免出现相同长度的原材料，即使出现也用于替代下一级中最短的原材料。基于要求（3）提到其总长度允许有 0.5米的误差，那么在考虑约束条件时，便考虑成首选总长度89米的，次而考虑88.5米和89.5的总长度的方案。对方案的个数的求解，很显然这是个线性规划问题。满足一定限额内的资源的最大使用。考虑到要求（5），必须在30分钟内形成方案，即要求模型算法的计算复杂度尽可能的小，计算时间尽量短。故，将原材料根据成品规格的要求分成三大类进行逐层优化，并结合要求（3），提高原材料的使用率，长的原材料可以降级使用，算法将考虑对原材料从长到短的讨论。(二
10、) 模型假设及符号说明1 模型假设1) 假设在丈量所有原料时，原料没有任何损坏；2) 假设原料只有这3种成品规格；3) 假设原料的各种长度的根数如数据所示，没有差错；4) 假设在每种方案中，各种肠衣根数的取值范围为0,1 ；2 符号说明符号表示的意思表示第j种方案下的捆数总捆数第种方案下第种产品的根数第种原材料的限额第种方案下的捆数 (三) 模型建立与求解本问题在求解的过程中要解决两方面内容：（一）方案的内容，（二）方案的个数。为降级计算复杂度，减少计算量，算法首先将原材料按照成品的方案分成三大类，逐类进行计算优化。并且剩余的原材料将遗留到下一类中再次使用。方案内容将由枚举法产生。对方案的个数
11、的求解，根据线性规划理论求解。1 理论线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法。它是运筹学的一个重要分支，广泛应用于军事作战、经济分析、经营管理和工程技术等方面。为合理地利用有限的人力、物力、财力等资源作出的最优决策，提供科学的依据。在企业的各项管理活动中,例如计划、生产、运输、技术等问题,线性规划是指从各种限制条件的组合中,选择出最为合理的计算方法,建立线性规划模型从而求得最佳结果。线性规划是运筹学的重要分支，它是一门实用性很强的应用数学学科。随着计算机技术的发展和普及，线性规划的应用越来越广泛。它已成为人们为合理利用有
12、限资源制订最佳决策的有力工具。一般地，求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题。满足线性约束条件的解叫做可行解，由所有可行解组成的集合叫做可行域。决策变量、约束条件、目标函数是线性规划的三要素.从实际问题中建立数学模型一般有以下三个步骤； 1.根据影响所要达到目的的因素找到决策变量； 2.由决策变量和所在达到目的之间的函数关系确定目标函数； 3.由决策变量所受的限制条件确定决策变量所要满足的约束条件。 所建立的数学模型具有以下特点： 1、每个模型都有若干个决策变量（），其中为决策变量个数。决策变量的一组值表示一种方案，同时决策变量一般是非负的。 2、目标函数是决策变量的线性函数，根据具体问题可以是最大化（）或最小化（），二者统称为最优化（opt）。 3、约束条件也是决策变量的线性函数。 当我们得到的数学模型的目标函数为线性函数，约束条件为线性等式或不等式时称此数学模型为线性规划模型。线性规划问题建立的最终数学模型包括：决策变量、约束条件和目标函数。建立线性规划问题的方法：设决策变量；列出约束条件；分析目标，列出目标函数。线性规划数学模型的简写： 线性规划的矩阵表示方式： 线性规划的标准形式：目标函数： 约束条件：
