基于动态规划的肠衣搭配模型与软件设计

《基于动态规划的肠衣搭配模型与软件设计》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2011年全国大学生数学建模竞赛一等奖论文2011高教社杯全国大学生数学建模竞赛承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理

2、。我们参赛选择的题号是（从A/B/C/D中选择一项填写）：D我们的参赛报名号为（如果赛区设置报名号的话）：所属学校（请填写完整的全名）：内江职业技术学院参赛队员(打印并签名)：1.李辉2.黄凯3.徐微指导教师或指导教师组负责人(打印并签名)：魏齐日期：2011年9月12日赛区评阅编号（由赛区组委会评阅前进行编号）：2011年全国大学生数学建模竞赛一等奖论文2011高教社杯全国大学生数学建模竞赛编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号

3、）：全国评阅编号（由全国组委会评阅前进行编号）：2011年全国大学生数学建模竞赛一等奖论文基于动态规划的肠衣搭配模型与软件设计摘要我国是肠衣加工大国，出口量占世界首位。在肠衣加工的一个重要工序——组装工序中，传统生产往往依靠工人心算来确定如何搭配成成品（捆）。这不仅影响肠衣生产的速度，还制约着规模化生产。如何快速的将原料搭配成“药方”，方便工人“照方抓药”，同时保持肠衣的新鲜度，是一个值得研究的问题。肠衣搭配问题的原理虽是一个简单线性规划模型，但其求解的运算量巨大，如果采用穷举的办法，对第三类规格的肠衣组装运算量将达到的数量级，即使是

4、用我国的“天河一号”超级计算机以每秒2566万亿次的运算速度进行计算，也需要四千多年，显然是不合理的。本文采用动态规划的方法，逐步求出搭配方案。即每次运算产生10捆搭配方案，缩小原料根数，直到原料已经不能再组合成成品为止。按上述方法，对于给定的已分档的原料，建立线性规划模型，从符合第三类成品规格的原料中开始搭配，得到134捆成品3。将该种规格剩余原料做降级处理，按对半分割的方式进行，加入到符合第2类成品规格的原料中，再次进行计算，得到36捆成品2。按同样的方法，得到14捆成品1，合计得到成品184捆。根据提供数据，原材料总长为1717

5、0.5米，理论上可以组装成192.93捆，实际利用率为95.37%。为方便工厂使用，根据以上思路，开发了肠衣搭配方案的管理软件：在excel中设计界面，运用VBA和宏进行数据处理；在LINGO中使用excel数据进行优化计算，并将运算结果返回至excel中。在该系统的支持下，用户仅需要在excel界面中输入数据，并进行一些简单的操作，就能得到分配方案。按当前普通办公电脑测试，得到上述分配方案需要10分钟左右，其中调用LINGO软件的运算时间累计约30秒左右。此系统运算速度快，可以实现不同批次、不同数量的原料的搭配问题，操作简单，不需要

6、具备数学模型的相关知识即可操作，易推广。关键词：动态规划LINGOExcelVBA202011年全国大学生数学建模竞赛一等奖论文一、问题的重述天然肠衣（以下简称肠衣）制作加工是我国的一个传统产业，出口量占世界首位。肠衣经过清洗整理后被分割成长度不等的小段（原料），进入组装工序。传统的生产方式依靠人工，边丈量原料长度边心算，将原材料按指定根数和总长度组装出成品（捆）。原料按长度分档，通常以0.5米为一档，如：3-3.4米按3米计算，3.5米-3.9米按3.5米计算，其余的依此类推。表1是几种常见成品的规格，长度单位为米，∞表示没有上限，

7、但实际长度小于26米。为了提高生产效率，公司计划改变组装工艺，先丈量所有原料，建立一个原料表。根据以上成品和原料描述，设计一个原料搭配方案，工人根据这个方案“照方抓药”进行生产。公司对搭配方案有以下具体要求：(1)对于给定的一批原料，装出的成品捆数越多越好；(2)对于成品捆数相同的方案，最短长度最长的成品越多，方案越好；(3)为提高原料使用率，总长度允许有±0.5米的误差，总根数允许比标准少1根；(4)某种规格对应原料如果出现剩余，可以降级使用。如长度为14米的原料可以和长度介于7-13.5米的进行捆扎，成品属于7-13.5米的规格；

8、(5)为了食品保鲜,要求在30分钟内产生方案。请建立上述问题的数学模型，给出求解方法，并对表1、表2给出的实际数据进行求解，给出搭配方案。二、问题分析原问题的本质，是对肠衣原料按成品规格进行组装的问题。由于所生产的成品有