天然肠衣搭配问题一、摘要肠衣加工企业对原材料应制定合理有效的方式来搭配，使得企业的收益最大化，同时基于保鲜的需要，也要求搭配方案能够尽可能快速。因此肠衣的搭配问题是个很有实际意义的研究课题。在本问题中，给出了 2 组数据，我们需要根据这 2 组数据设计搭配的方案。显然，肠衣分配问题是一个整数规划问题。所以本文都采用 Lingo 软件进行编程求解，求解这个整数规划问题本文都选择单纯形法。对于每一个题设的要求，我们都单独考虑。对于第一个问题：我们将问题分为 3 个小块，对于长度在［3,6.5］的长度，由于题设限制了一捆要求满足 20 根肠衣并且一捆最短要 89 米，所以我们通过构建线性方程组，来找到满足条件的结果；对于其他长度的肠衣，我们也是类似于［3,6.5］的方式进行。对于第二个问题，题设要求最短长度的尽量多，所以我们在第一问的基础上，给较短长度的肠衣较大的权系数，最后通过 Lingo 软件求得全局最优解。关于第三个问题的求解，我们参照求解问题一的方法使用不等式约束。对于问题四，我们运用贪心算法来求解，即对于剩余的肠衣，我们通过贪心准则来进行降级，使得每次的贪心选择都是当时的最佳选择。由于原材料已定，按照题设，分别讨论每个要求，解得第一问中肠衣最多只能做出 130捆；第二问中对剩余的肠衣加权，也得到了比较理想的结果；第三问最多可以生产 183 捆合格成品；第四问中我们通过贪心算法对降级问题进行处理，最终得到剩下的肠衣可以组成 183 捆。对于第五问，我们每个程序的时间都仔分钟内就可以得到结果，所以能够在 30 分钟内得到分配方案。关键词：搭配问题、LINGO 软件、整数规划、全局最优、加权二、问题重述天然肠衣(以下简称肠衣)制作加工就是我国的一个传统产业，已有百余年的历史，出口量占世界首位，为我国创造了可观的经济价值。肠衣经过清洗整理后被分割成长度不等的小段(原料)，进入组装工序。传统的生产方式依靠人工，边丈量原料长度边心算，将原材料按指定根数和总长度组装出成品(捆)。原料按长度分档，通常以 0.5 米为一档，如：3-3.4 米按 3 米计算，3.5 米-3.9 米按 3.5 米计算，其余的依此类推。表 1 是几种常见成品的规格，长度单位为米，表示没有上限，但实际长度小于 26 米。为了提高生产效率，提高产品的市场竞争力，公司计划改变组装工艺，先丈量所有原料，建立一个原料表。并按照公司对原料搭配的具体要求，设计一个原料搭配方案，使工...
VIP
