天然肠衣搭配问题
2011高教社杯全国大学生数学建模竞赛
承 诺 书
我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.
我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。
我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。
我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。
我们参赛选择的题号是（从A/B/C/D中选择一项填写）： D 我们的参赛报名号为（如果赛区设置报名号的话）：
所属学校（请填写完整的全名）： 重庆教育学院 参赛队员 (打印并签名) ：1. 王平 2. 王静 3. 王鸿玫 指导教师或指导教师组负责人 (打印并签名)： 施成湘
日期： 2011年 9 月11日
赛区评阅编号（由赛区组委会评阅前进行编号）：
天然肠衣搭配问题
2011高教社杯全国大学生数学建模竞赛
编 号 专 用 页
评 阅 人 评 分 备 注 赛区评阅编号（由赛区组委会评阅前进行编号）：
赛区评阅记录（可供赛区评阅时使用）：
全国统一编号（由赛区组委会送交全国前编号）：
全国评阅编号（由全国组委会评阅前进行编号）：
论文题目：天然肠衣搭配问题
摘 要
随着时代的发展，天然肠衣制作加工已经是我国的一个传统产业，在生产中占优很重要的地位。本文就是针对天然肠衣的加工问题展开讨论并建立相应的优化模型，本问题涉及到两方面内容：（一）方案的内容，（二）方案的个数。根据线性规划理论，建立双目标函数模型。从第四个条件肠衣有剩余的角度入题，即剩余的可以降级使用，我们立运筹学中的双目标函数列出了我们最初的模型原型，从而我们可以从中得出的比较合理优化的分配方案577种，在具体解决这个问题的时候，我们从第三种成品开始建立模型，得出初步方案367种，剩余降级使用的数目8根，将剩余的原料归纳到第二种成品中最长的原料中，再利用第二种成品建立模型得出初步方案107种，并得出剩余数目35根，同理降级到第一种成品最长的原料中使用；最终通过筛选得到的最优方案为第一类12种、第二类33种、第三类34种，从捆数上看则是192捆，详见文中总表。对于第三个条件中提出的为了提高利用率而允许有误差，条件是要在30分钟内得出最好的方案，为降低计算复杂度，算法对文中原材料的取定，是要求尽可能的少。通过运行，得出的最优的方案，见下表，
第一类产品 第二类产品 点三类产品 总方案数 367 107 103 剩余方案数 34 33 12 捆数 135 41 16 剩余根数 8 35 ----- 此双目标函数模型很好的解决了天然肠衣的加工分配问题，且方法具有很强的严密性，提高了运算速度，缩短了安排时间，提高效率，能够广泛推广到其他材料的加工安排问题上。
关键词： 肠衣加工 多目标线性规划
(一) 问题的提出
1.问题的重述
天然肠衣（以下简称肠衣）制作加工是我国的一个传统产业，出口量占世界首位。肠衣经过清洗整理后被分割成长度不等的小段（原料），进入组装工序。传统的生产方式依靠人工，边丈量原料长度边心算，将原材料按指定根数和总长度组装出成品（捆）。
原料按长度分档，通常以0.5米为一档，如：3-3.4米按3米计算，3.5米-3.9米按3.5米计算，其余的依此类推。表1是几种常见成品的规格，长度单位为米，∞表示没有上限，但实际长度小于26米。
表1 成品规格表 最短长度 最大长度 根数 总长度 3 6.5 20 89 7 13.5 8 89 14 ∞ 5 89
为了提高生产效率，公司计划改变组装工艺，先丈量所有原料，建立一个原料表。表2为某批次原料描述。
表2 原料描述表 3-3.4 3.5-3.9 4-4.4 4.5-4.9 5-5.4 5.5-5.9 6-6.4 6.5-6.9 43 59 39 41 27 28 34 21 7-7.4 7.5-7.9 8-8.4 8.5-8.9 9-9.4 9.5-9.9 10-10.4 10.5-10.9 24 24 20 25 21 23 21 18 11-11.4 11.5-11.9 12-12.4 12.5-12.9 13-13.4 13.5-13.9 14-14.4 14.5-14.9 31 23 22 59 18 25 35 29 15-15.4 15.5-15.9 16-16.4 16.5-16.9 17-17.4 17.5-17.9 18-18.4 18.5-18.9 30 42 28 42 45 49 50 64 19-19.4 19.5-19.9 20-20.4 20.5-20.9 21-21.4 21.5-21.9 22-22.4 22.5-22.9 52 63 49 35 27 16 12 2 23-23.4 23.5-23.9 24-24.4 24.5-24.9 25-25.4 25.5-25.9 0 6 0 0 0 1 根据以上成品和原料描述，设计一个原料搭配方案，工人根据这个方案“照方抓药”进行生产。
公司对搭配方案有以下具体要求：
(1) 对于给定的一批原料，装出的成品捆数越多越好；
(2) 对于成品捆数相同的方案，最短长度最长的成品越多，方案越好； (3) 为提高原料使用率，总长度允许有± 0.5米的误差，总根数允许比标准少1根；
(4) 某种规格对应原料如果出现剩余，可以降级使用。如长度为14米的原料可以和长度介于7-13.5米的进行捆扎，成品属于7-13.5米的规格；
(5) 为了食品保鲜,要求在30分钟内产生方案。
请建立上述问题的数学模型，给出求解方法，并对表1、表2给出的实际数据进行求解，给出搭配方案。
长度 根数 长度 根数 长度 根数 长度 根数 长度 根数 长度 根数
2．问题的初步分析
这是一个典型的优化问题。本问题最终要求给出一个合理的搭配方案，将涉及到两方面内容：（一）方案的内容，（二）为达到尽可能多的使用原材料，如何选择方案，即方案的个数。这两方面将是问题解决的关键。将通过两次建立数学模型，给予求解。对方案的内容，由于要求（2）提到，对成品捆数相同的方案，最短长度最长的方案优先考虑，因此，在同一捆中尽量避免出现相同长度的原材料，即使出现也用于替代下一级中最短的原材料。基于要求（3）提到其总长度允许有± 0.5米的误差，那么在考虑约束条件时，便考虑成首选总长度89米的，次而考虑88.5米和89.5的总长度的方案。对方案的个数的求解，很显然这是个线性规划问题。满足一定限额内的资源的最大使用。考虑到要求（5），必须在30分钟内形成方案，即要求模型算法的计算复杂度尽可能的小，计算时间尽量短。故，将原材料根据成品规格的要求分成三大类进行逐层优化，并结合要求（3），提高原材料的使用率，长的原材料可以降级使用，算法将考虑对原材料从长到短的讨论。
(二) 模型假设及符号说明
1．模型假设
1) 假设在丈量所有原料时，原料没有任何损坏； 2) 假设原料只有这3种成品规格；
3) 假设原料的各种长度的根数如数据所示，没有差错； 4) 假设在每种方案中，各种肠衣根数的取值范围为[0,1] ； 2．符号说明 符号 表示的意思 表示第j种方案下的捆数 总捆数 第j种方案下第i种产品的根数 第i种原材料的限额 第i种方案下的捆数 x jyaij b it i