天然肠衣搭配问题
黄洁 黄兵 程理想 指导老师 杨先伟 （无锡职业技术学院）
摘要
本文针对天然肠衣原料的搭配方案进行设计，充分考虑最优化原则，运用线性规划知识建立模型，并利用LINGO软件计算出结果。
本文首先对题目中的五个要求进行分析，将前三个要求综合在一起考虑，建立数学模型解决。充分考虑前三个要求：成品捆数越多越好，在此基础上每捆中最短长度最长的越多越好，并且成品总长度及每捆数量可以有适当误差，确定线性规划中的目标函数为每种规格中的原料组装后所剩肠衣的长度之和最小，并结合题意给出约束条件，在算出每种规格理想的最大捆数的基础上运用LINGO软件求出最佳的搭配方案。
其次针对第四个要求，先将规格三和规格二中所剩的肠衣，按照最优化理论建立线性规划模型求解，然后再将规格二和规格一中所剩下的肠衣建立模型求解，并给出最终的设计方案。
运用上述模型，再利用LINGO软件计算出最终成品数为191捆，剩余肠衣原料总长为285米。
当肠衣的原料表给出后，将数据带入文中模型并运用LINGO软件进行计算，能够在30分钟以内产生最佳搭配方案，满足题目要求。
关键词： 搭配 线性规划模型 LINGO
一．模型假设
1、假设在设计方案中，组装时优先考虑每种规格的肠衣独自组装，之后再将每种规格所剩的肠衣降级进行组装。
2、假设肠衣原料降级使用只能降到相邻规格。比如，规格三只能降级到规格二，而不能降级到规格一。
3、假设肠衣原料降级使用时，原料长度不降级。比如，将长度为14米的原料与长度介于7-13.米的进行捆扎时，长度仍然按14米计算。
二．符号说明
xij 为某一规格中第i捆成品中第j档肠衣原料的根数 aij 为第i捆成品中第j档次肠衣的长度 bj 为某一规格中第j档次对应的总根数
dk 为第k种规格中每捆要求的根数，k?1,2,3. pk 为第k种规格中最大成品捆数
三．模型分析
结合题目要求，我们将设计的搭配方案分为两个模型。其中模型一的设计方
案先将每种规格的肠衣分别进行搭配；模型二将模型一中每种规格所剩肠衣按照要求（4）降级进行搭配。最终得出最后的设计方案。
模型一主要针对要求（1）、（2）、（3）建立。具体步骤如下： 1、计算每种规格理想的最大捆数； 2、可以分析出如果方案中所剩下的肠衣总长度最小就可以同时满足要求（1）和（2），即捆数最多的情况下，每捆成品最短长度最长。再结合要求（3），应用线性规划建立模型设计搭配方案；
3、应用LINGO软件计算出结果。
模型二针对要求（4）建立，具体步骤如下：
1、将模型一中规格三所剩原料降级同规格二所剩原料进行组装。应用模型一中的原理建立线性规划模型，并应用LINGO软件计算结果；
2、将上面步骤中所剩规格二的原料降级同模型一中规格一所剩原料进行组装。同样应用模型一中的原理建立线性规划模型，并应用LINGO软件计算结果。
四．模型的建立与求解
4.0计算三种规格成品的理想最大捆数
根据题目要求（1），对于给定的原料，成品捆数越多越好；要求（3）每捆成品总长度允许有?0.5的误差。我们据此计算三种规格对应的理论最大捆数。
用每种规格肠衣的总长度除以每捆成品总长度的下限88.5，得出针对长度的最大捆数；用每种规格肠衣的总根数除以对应规格每捆要求的数量dk(k?1,2,3)，得出针对根数的最大捆数；易知，理论最大捆数为两者中较小的一个，具体计算公式为
L??ajbk, fk?min{j?1nLN,},k?1,2,3. ．．．．．． ① 88.5dk其中fk为理想最大捆数，L为某种规格原料的总长度，N为某种规格原料的总根数，aj为某种规格第j档肠衣的单位长度。以规格一为例，理论最大捆数为：
1305.5292f1?min{,}?14。
88.520据此计算三种规格最大捆数如下表1所示：
表1 规格一 规格二 规格三 总长度 1305.5 3705.5 12159.5 根数 292 354 677 每捆要求根数 20 8 5 每捆要求总长度下限 88.5 88.5 88.5 理论最大捆数 14 41 135 4.1模型一，分别设计三种规格原料的搭配方案
结合要求（1）、（2）可知，题目要求设计的搭配方案满足“给定的一批原料，
装出的成品捆数越多越好，且对于成品捆数相同的方案，使得最短长度最长的成品最多”，经过分析可知，该要求等价于“对每种规格的肠衣应用搭配方案后，所剩下的肠衣长度之和最小”。再结合要求（3），总长度允许的?0.5误差，总根数允许比标准少一根，应用线性规划建立模型。在求解模型时，将每种规格理想最大捆数依次按从大到小的顺序代入模型求解，直至第一组解求出，相应最优的搭配方案即可确定。具体骤如下：
1、根据题目要求将原料描述表进行分档并标号如下表2所示：
表2 规格一 序号 长度 根数 序号 规格二 长度 根数 序号 长度 根数 规格序号 长度 1 3 43 1 7 24 9 11 31 1 14 2 3.5 59 2 7.5 24 10 11.5 23 2 14.5 3 4 39 3 8 20 11 12 22 3 15 4 4.5 41 4 8.5 25 12 12.5 59 4 15.5 5 5 27 5 9 21 13 13 18 5 16 6 5.5 28 6 9.5 23 14 13.5 25 6 16.5 7 6 34 7 10 21 7 17 8 6.5 21 8 10.5 18 8 17.5
高教杯数学建模竞赛D题一等奖论文
