肠衣搭配问题之求解

童宁江

（台州科技职业学院机电与模具工程学院，浙江 台州318020）

0 问题重述

天然肠衣（以下简称肠衣）制作加工是我国的一个传统产业，出口量占世界首位。肠衣经过清洗整理后被分割成长度不等的小段 （原料），进入组装工序。传统的生产方式依靠人工，边丈量原料长度边心算，将原材料按指定根数和总长度组装出成品（捆）。

原料按长度分档，通常以0.5米为一档，如：3-3.4米按3米计算，3.5米-3.9米按3.5米计算，其余的依此类推。为了提高生产效率，公司计划改变组装工艺，先丈量所有原料，建立一个原料描述。根据成品规格和原料描述，现需要我们通过数学模型方法为公司设计一个原料搭配方案，工人根据这个方案“照方抓药”进行生产。

公司对搭配方案有以下具体要求[1]：

（1）对于给定的一批原料，装出的成品捆数越多越好；

（2）对于成品捆数相同的方案，最短长度最长的成品越多，方案越好；

（3）为提高原料使用率，总长度允许有±0.5米的误差，总根数允许比标准少1根；

（4）某种规格对应原料如果出现剩余，可以降级使用。如长度为14米的原料可以和长度介于7-13.5米的进行捆扎，成品属于7-13.5米的规格；

（5）为了食品保鲜,要求在30分钟内产生方案。

1 符号说明

原料描述为长度档位mj米有nj根。最大根数是G。第i类组合的次数是yi。第i类组合的第j长度档位根数是aij。

2 解题思路

本问题的解题思路为：先求第一种规格的成品方案、第二种规格的成品方案、第三种规格的成品方案，再求这三种方案剩余肠衣的成品方案。

3 模型一的建立与求解

3.1 模型一的建立

模型一是单目标非线性规划模型，用于优化原料搭配组合（及组合次数）。对于每种规格，模型一不仅可以求得最大成品捆数，而且可以求得原料搭配组合及其次数。

目标：求各种原料搭配组合次数之和的最大值。

约束：

（1）对于每种组合，长度下界≤该组合的各档原料长度之和；

（2）对于每种组合，该组合的各档原料长度之和≤长度上界；

（3）对于每种组合，根数下界≤该组合的各档原料根数之和；

（4）对于每种组合，该组合的各档原料根数之和≤根数上界；

（5）对于每档原料，各种组合的该原料根数之和≤可用根数；

（6）对于每种组合每档原料，使用根数是自然数；

（7）对于每种组合，组合次数是正整数。

下面是模型一的数学描述。

目标函数：max Σyi。

约束条件：每个 i有 88.5≤Σ(mj×aij)≤89.5,G-1≤Σaij≤G+1;每个j有 Σ(aij×yi)≤nj;aij是自然数,yi是正整数。

3.2 模型一的求解

实践表明，在软件LINGO[2]上，模型一的求解时间主要决定于原料档位数。原料档位数越大，求解时间也越长。当原料档位不多时，在普通电脑上1个小时内产生方案是非常轻松。当原料档位很多时，在普通电脑上1个小时内产生方案是有些勉强。

当原料档位很多时，为了在普通电脑上1个小时内产生方案，比较有效的解决办法是减少组合数和采用中断技术。因为，减少组合数可以让软件LINGO缩短求解时间，采用中断技术可以让软件LINGO立即返回局部最优解。特别，为了减少组合数，可以限制组合的使用原料档位个数。

现在，利用模型一，通过软件Lingo求得：第一种、第二种规格和第三种规格的最大成品捆数为分别为14、35和120。

4 模型二的建立与求解

4.1 模型二的建立

为了解决剩余问题，提出了模型二：先第三种规格的剩余合并到第二种规格的剩余，在第二种规格的剩余中求解成品的搭配与捆数；再第二种规格的剩余合并到第一种规格的剩余，在第一种规格的剩余中求解成品的搭配与捆数。

4.2 模型二的求解

首先，第三种的剩余合并到第二种的剩余，建立新的原料描述。利用模型一，通过软件Lingo求得最大成品捆数为19。

然后，第二种的剩余合并到第一种的剩余，建立新的原料描述。利用模型一，通过软件Lingo求得最大成品捆数为0。

综上所述，剩余的原料最多可以搭配为成品19捆。

5 结论

通过模型一和模型二的求解，得出总捆数为188。

［1］2011高教社杯全国大学生数学建模竞赛D题[Z].

［2］LINGO 12.0 用户手册[Z].