天然肠衣搭配问题天然肠衣搭配问题.doc

天然肠衣搭配问题 摘要 肠衣的搭配问题就是把给定的若干长度不同的原料进行搭配成捆，使得每捆的总长度，所含原料的根数满足一定条件的情况下，得到的总成品捆数和某些规格的成品捆数越多越好，从而可以最大可能的提高公司肠衣的销售收入。、 本文就肠衣的搭配方案问题进行了研究，通过对题目中给定的具体数据进行分析和合理的假设，得到求解该问题最优解的多目标线性整数规划模型。模型中含有较多的决策变量及约束方程。因为问题对食品保鲜有具体的时间要求，为了在有限的时间内得到问题的尽可能合理的搭配方案，使得工人可以按照搭配方案进行捆扎，我们把建立的大规模整数目标规划问题的求解分解成若干个较小规模的整数线性规划问题的求解。运用Lingo 软件编程计算每个整数线性规划问题的最优搭配方案及相应的捆数，同时考虑到每捆的总长度要求、根数要求及不同规格的原材料间的可能的降级使用，我们给出了一个求问题可行解的一个算法，从而得到肠衣搭配问题的一个通用的方案。 通过把算法运用到问题给定的实际数据中，我们可以得到算法的几个特点。首先，该算法可以在几分钟内产生可行的原料搭配方案，使得每个成品捆都满足相应的总长度要求、每捆的根数要求。其次，方案中也考虑到了规格长的剩余原料可降级使用，以提高原料使用率。最后，也是更重要的是，该算法得到的总捆数和最短长度最长的成品捆数与这两类捆数的上界是非常接近的。 关键词：优化肠衣的优化搭配方法 多目标线性整数规划 单目标线性整数规划 运筹lingo软件 目录 问题重述 ………………………………………………………………………………………………………. (3) 模型的基本假设与符号说明 …………………………………………………………………… (4) 2.1、模型的基本假设 ………………………………………………………………………………. (4) 2.2、符号说明 ……………………………………………………………………………..………...(4) 问题分析与模型的建立 …………………………………………………………………………… (4) 3.1、问题分析 …………………………………………………………………………………………. (4) 3.2、模型建立 …………………………………………………………………………………………..(5) 3.3、模型分析 …………………………………………………………………………………………… (6) 模型求解 …………………………………………………………………………………………………………(7) 4.1、求解第三规格的总捆数 ………………………………………………………………………………(7) 4.2、求解第二规格的总捆数 ………………………………………………………………………………(8) 4.3、求解第一规格的总捆数 …………………………………………………………………………………(9) 结果分析 ……………………………………………………………………………………………………….(11) 六、参考文献 ……………………………………………………………………………………………………….(11) 七、附录1-8 lingo 编程代码…………………………………………………………………………………(12) 一、问题重述 天然肠衣（以下简称肠衣）制作加工是我国的一个传统产业，出口量占世界首位。肠衣经过清洗整理后被分割成长度不等的小段（原料），进入组装工序。传统的生产方式依靠人工，边丈量原料长度边心算，将原材料按指定根数和总长度组装出成品（捆）。 原料按长度分档，通常以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