1、1天然肠衣搭配问题摘要本文针对天然肠衣原料的搭配方案进行设计，充分考虑最优化原则，运用线性规划知识建立模型，并利用 LINGO 软件计算出结果。本文首先对题目中的五个要求进行分析，将前三个要求综合在一起考虑，建立数学模型解决。充分考虑前三个要求：成品捆数越多越好，在此基础上每捆中最短长度最长的越多越好，并且成品总长度及每捆数量可以有适当误差，确定线性规划中的目标函数为每种规格中的原料组装后所剩肠衣的长度之和最小，并结合题意给出约束条件，在算出每种规格理想的最大捆数的基础上运用LINGO 软件求出最佳的搭配方案。其次针对第四个要求，先将规格三和规格二中所剩的肠衣，按照最优化理论建立线性规划模型求
2、解，然后再将规格二和规格一中所剩下的肠衣建立模型求解，并给出最终的设计方案。运用上述模型，再利用 LINGO 软件计算出最终成品数为 191 捆，剩余肠衣原料总长为 285 米。当肠衣的原料表给出后，将数据带入文中模型并运用 LINGO 软件进行计算，能够在 30 分钟以内产生最佳搭配方案，满足题目要求。关键词： 搭配 线性规划模型 LINGO 一模型假设1、假设在设计方案中，组装时优先考虑每种规格的肠衣独自组装，之后再将每种规格所剩的肠衣降级进行组装。2、假设肠衣原料降级使用只能降到相邻规格。比如，规格三只能降级到规格二，而不能降级到规格一。3、假设肠衣原料降级使用时，原料长度不降级。比如，
3、将长度为 14 米的原料与长度介于 7-13.米的进行捆扎时，长度仍然按 14 米计算。2符号说明为某一规格中第 捆成品中第 档肠衣原料的根数ijxij为第 捆成品中第 档次肠衣的长度ijaij2为某一规格中第 档次对应的总根数jbj为第 种规格中每捆要求的根数，kd .3,21k为第 种规格中最大成品捆数p三模型分析结合题目要求，我们将设计的搭配方案分为两个模型。其中模型一的设计方案先将每种规格的肠衣分别进行搭配；模型二将模型一中每种规格所剩肠衣按照要求（4）降级进行搭配。最终得出最后的设计方案。模型一主要针对要求（1） 、 （2） 、 （3）建立。具体步骤如下：1、计算每种规格理想的最大捆
4、数；2、可以分析出如果方案中所剩下的肠衣总长度最小就可以同时满足要求（1）和（2） ，即捆数最多的情况下，每捆成品最短长度最长。再结合要求（3） ，应用线性规划建立模型设计搭配方案；3、应用 LINGO 软件计算出结果。模型二针对要求（4）建立，具体步骤如下：1、将模型一中规格三所剩原料降级同规格二所剩原料进行组装。应用模型一中的原理建立线性规划模型，并应用 LINGO 软件计算结果；2、将上面步骤中所剩规格二的原料降级同模型一中规格一所剩原料进行组装。同样应用模型一中的原理建立线性规划模型，并应用 LINGO 软件计算结果。四模型的建立与求解4.0 计算三种规格成品的理想最大捆数 根据题目要
5、求（1） ，对于给定的原料，成品捆数越多越好；要求（3）每捆成品总长度允许有 0.5 的误差。我们据此计算三种规格对应的理论最大捆数。用每种规格肠衣的总长度除以每捆成品总长度的下限 88.5，得出针对长度的最大捆数；用每种规格肠衣的总根数除以对应规格每捆要求的数量，得出针对根数的最大捆数；易知，理论最大捆数为两者中较小的)3,21(kd一个，具体计算公式为. ,1njkbaL3,21,5.8minkdNLfk其中 为理想最大捆数， 为某种规格原料的总长度， 为某种规格原料的总kf3根数， 为某种规格第 档肠衣的单位长度。以规格一为例，理论最大捆数为：jaj。14209,5.813min1f据此
6、计算三种规格最大捆数如下表 1 所示：表 1 总长度 根数 每捆要求根数 每捆要求总长度下限 理论最大捆数规格一 1305.5 292 20 88.5 14规格二 3705.5 354 8 88.5 41规格三 12159.5 677 5 88.5 1354.1 模型一，分别设计三种规格原料的搭配方案结合要求（1） 、 （2）可知，题目要求设计的搭配方案满足“给定的一批原料，装出的成品捆数越多越好，且对于成品捆数相同的方案，使得最短长度最长的成品最多” ，经过分析可知，该要求等价于“对每种规格的肠衣应用搭配方案后，所剩下的肠衣长度之和最小” 。再结合要求（3） ，总长度允许的 0.5 误差，总
7、根数允许比标准少一根，应用线性规划建立模型。在求解模型时，将每种规格理想最大捆数依次按从大到小的顺序代入模型求解，直至第一组解求出，相应最优的搭配方案即可确定。具体骤如下：1、根据题目要求将原料描述表进行分档并标号如下表 2 所示：表 2序号 1 2 3 4 5 6 7 8长度 3 3.5 4 4.5 5 5.5 6 6.5规格一 根数43 59 39 41 27 28 34 21序号 1 2 3 4 5 6 7 8长度 7 7.5 8 8.5 9 9.5 10 10.5根数 24 24 20 25 21 23 21 18序号 9 10 11 12 13 14长度 11 11.5 12 12.
8、5 13 13.5规格二根数 31 23 22 59 18 25序号 1 2 3 4 5 6 7 8长度 14 14.5 15 15.5 16 16.5 17 17.5根数 35 29 30 42 28 42 45 49序号 9 10 11 12 13 14 15 16规格三长度 18 18.5 19 19.5 20 20.5 21 21.54根数 50 64 52 63 49 35 27 16序号 17 18 19 20 21 22 23 24长度 22 22.5 23 23.5 24 24.5 25 25.5根数 12 2 0 6 0 0 0 12、建立模型一设 表示某一规格中，第 捆成品
9、中第 档次肠衣,1;,1, njmiaj ij的长度。某一规格中第 档次对应的总根数为 ，每一种规格的成品捆数为 ，jbm每种规格中都用 表示第 捆第 档肠衣的根数， 表示第 种规格中最大成ijxijkp品捆数， 表示第 种规格中每捆要求的根数，且 用 表kd ,5,8,2031ddy示方案搭配剩下的所有肠衣长度之和。根据前面分析可知，我们需要求解的是在题目的要求（1） 、 （2） 、 （3）下， 的最小值。易知，当 取得最小值时，yy必然取得最大值，此时求出的 就是最佳搭配方案。具体的线性规划模型mijx如下： nj miij ijjaxby11miS.T. .3,2,kNpk且 5.895
10、.8.2122211mnmmnxaxa .,3,1iddkjnjik minmimi bxbx1121 .,3、将三种规格的数值分别带入模型并计算结果（）针对规格一，将其数据带入到模型式中可得如下规划模型： nj miij ijjaxby11miS.T. N,4且5捆数单位长度5.89.65.3.8.212218121 mmxx .14,091ijji mimimimi xxxx 1413121 ,9,5,43.2,8,718171615 iiii将理想最大捆数 代入模型，应用 LINGO 计算 模型的最优解4m2，即规格一的最大成品捆数为 14。具体的搭配方案如下表 3 所示5.2miny（
11、求解程序 及结果见附录 6.1）：3表 3 规格一的搭配方案3 3.5 4 4.5 5 5.5 6 6.5第一捆 0 0 13 1 0 0 0 0第二捆 10 0 0 1 0 1 5 3第三捆 0 0 12 0 7 0 0 1第四捆 10 0 0 0 0 1 9 0第五捆 0 11 0 0 0 0 2 6第六捆 6 0 0 0 0 13 0 0第七捆 2 8 0 3 0 0 7 0第八捆 0 0 11 2 6 0 0 1第九捆 0 9 0 5 0 3 0 2第十捆 3 3 0 0 14 0 0 0第十一捆 4 8 1 0 0 0 0 7第十二捆 8 0 0 0 0 1 10 0第十三捆 0 5
12、 1 10 0 3 0 1第十四捆 0 0 1 19 0 0 0 0（）针对规格二，将其数值带入模型式中同理可得线性规划模型。限于篇幅，我们在此应用矩阵对模型进行简化。设 ，.135.21.5.10.95.8.7A6捆数单位长度3712 5.89,.,589B .14,2,4,1421 jbbj代入数据后具体模型如下：nj miij ijjaxby11miNmjbxiBAXTSijjiTT,41.4,2.,87.4122 应用 LINGO 计算结果，经过验证 时，模型有最优解 ，即37428miny规格二的最大成品捆数为 37，具体搭配方案如下表 4（求解程序见附录 6.2）：表 4 规格二的
13、搭配方案7 7.58 8.5 9 9.510 10.5 11 11.512 12.513 13.5总捆数第一捆 0 0 0 0 2 0 0 0 1 1 4 0 0 0 8第二捆 0 0 1 0 0 0 2 0 0 0 4 1 0 0 8第三捆 0 0 0 1 0 1 2 0 0 1 1 0 0 2 8第四捆 0 0 0 0 0 3 1 0 0 0 2 0 2 0 8第五捆 0 0 0 0 0 0 1 4 0 0 0 3 0 0 8第六捆 0 0 1 0 1 0 0 1 1 0 0 4 0 0 8第七捆 0 0 0 0 0 0 0 0 7 1 0 0 0 0 8第八捆 0 0 2 0 0 1 0
14、 0 1 0 0 0 4 0 8第九捆 0 0 0 0 0 2 1 2 0 0 0 1 2 0 8第十捆 0 0 0 1 0 0 0 0 0 7 0 0 0 0 8第十一捆 0 0 0 0 2 0 1 1 0 0 0 4 0 0 8第十二捆 0 0 1 1 0 0 0 0 0 2 0 4 0 0 8第十三捆 0 0 0 2 0 0 0 0 1 0 4 1 0 0 8第十四捆 0 0 0 3 1 0 0 0 0 0 0 0 0 4 8第十五捆 0 0 0 2 1 0 0 0 0 0 0 5 0 0 8第十六捆 0 0 0 0 2 0 0 0 3 0 0 3 0 0 8第十七捆 0 0 0 0 2
15、 0 0 1 3 0 0 0 0 2 87第十八捆 0 0 1 2 0 0 0 0 0 1 0 2 0 2 8第十九捆 0 0 0 0 0 2 1 1 0 0 2 2 0 0 8第二十捆 0 0 0 0 0 4 1 0 0 0 0 0 0 3 8第二十一捆 0 0 0 0 0 4 0 0 0 1 1 0 0 2 8第二十二捆 0 0 0 0 1 0 0 3 2 0 0 0 2 0 8第二十三捆 0 0 0 0 1 3 0 0 0 0 0 3 0 1 8第二十四捆 0 0 0 3 1 0 0 0 0 0 0 0 0 4 8第二十五捆 0 0 0 0 0 0 5 0 0 0 0 1 2 0 8第二
16、十六捆 0 0 0 0 0 1 1 0 0 6 0 0 0 0 8第二十七捆 0 0 0 2 1 0 0 0 2 0 0 0 0 3 8第二十八捆 0 0 0 2 1 0 0 0 0 0 0 5 0 0 8第二十九捆 0 0 0 2 1 0 0 0 0 0 0 5 0 0 8第三十捆 0 0 0 0 0 1 0 1 3 0 2 0 0 0 7第三十一捆 0 0 0 0 1 1 1 0 0 2 2 0 1 0 8第三十二捆 0 0 1 0 0 0 0 4 0 0 0 2 0 1 8第三十三捆 0 0 0 2 1 0 0 0 0 0 0 5 0 0 8第三十四捆 0 0 0 0 1 0 0 0 6
17、 0 0 0 0 1 8第三十五捆 0 0 3 0 0 0 0 0 0 0 0 0 5 0 8第三十六捆 0 0 0 0 0 0 4 0 1 0 0 3 0 0 8第三十七捆 0 0 0 2 1 0 0 0 0 0 0 5 0 0 8（）针对规格三，将数值带入模型，同样应用矩阵对模型进行简化。设： 5.2.425.3.25.12.0 19817164A，3389B18 B.,52421 jbbj代入数据后具体模型如下：nj miij ijjaxby11miNmjbxiBAXTSijjiTT,135.24,.35,54)(.13523 应用 LINGO 计算结果， 当 时，模型有最优解 ，即规格
18、三的最93miny表 5 规格三搭配方案8大成品捆数为 135，具体搭配方案如下表 5 所示（求解程序 及结果见附录 6.3)：31414.51515.51616.51717.51818.5192020212121.52222.52323.52424.52525.5第一捆 2 1 2第二捆 1 2 2第三捆 1 1 1 2第四捆 2 1 2第五捆 4 1第六捆 1 1 1 2第七捆 1 2 2第八捆 1 2 2第九捆 1 3 1第十捆 1 1 3第十一捆 1 1 3第十二捆 1 3 1第十三捆 1 2 2第十四捆 1 4第十五捆 2 3第十六捆 1 1 3第十七捆 1 1 1 2第十八捆 1
19、1 1 2第十九捆 1 1 3第二十捆 2 2 1第二十一捆 1 1 3第二十二捆 1 1 1 1 1第二十三捆 2 3第二十四捆 1 1 3第二十五捆 1 2 2第二十六捆 1 3 1第二十七捆 1 2 1 1第二十八捆 2 2 1第二十九捆 2 2 1第三十捆 3 2第三十一捆 2 2 1第三十二捆 1 2 19第三十三捆 2 1 1 1第三十四捆 1 1 1 2第三十五捆 1 2 1第三十六捆 3 1第三十七捆 1 3 1第三十八捆 2 3第三十九捆 3 2第四十捆 2 2 1第四十一捆 4 1第四十二捆 2 1 2第四十三捆 1 2 2第四十四捆 1 2 2第四十五捆 4 1第四十六捆
20、 2 2 1第四十七捆 2 3第四十八捆 1 1 3第四十九捆 1 2 1 1第五十捆 1 2 2第五十一捆 2 1 1 1第五十二捆 2 1 2第五十三捆 1 4第五十四捆 2 3第五十五捆 1 2 2第五十六捆 2 3第五十七捆 1 1 3第五十八捆 2 2 1第五十九捆 2 1 2第六十捆 2 3第六十一捆 1 1 1 2第六十二捆 1 1 1 2第六十三捆 1 3 1第六十四捆 1 2 1第六十五捆 2 1 1 1第六十六捆 1 1 3第六十七捆 1 4第六十八捆 3 2第六十九捆 2 3第七十捆 3 1 1第七十一捆 1 4第七十二捆 3 2第七十三捆 1 4第七十四捆 1 2 1第
21、七十五捆 1 1 310第七十六捆 3 2第七十七捆 2 3第七十八捆 2 2 1第七十九捆 4 1第八十捆 2 3第八十一捆 2 1 1 1第八十二捆 1 1 3第八十三捆 2 2 1第八十四捆 2 1 2第八十五捆 1 2 2第八十六捆 1 1 3第八十七捆 4 1第八十九捆 1 1 3第八十九捆 2 3第九十捆 2 2 1第九十一捆 3 2第九十二捆 4 1第九十三捆 1 4第九十四捆 1 1 3第九十五捆 1 1 3第九十六捆 3 2第九十七捆 1 1 1 2第九十八捆 1 1 3第九十九捆 2 2 1第一百捆 2 3第一百零一捆 1 4第一百零二捆 1 1 1 2第一百零三捆 1 2 2第一百零四捆 1 3 1第一百零五捆 1 1 2 1第一百零六捆 1 1 3第一百零七捆 1 3 1第一百零八捆 2 1 1第一百零九捆 1 1 3第一百一捆 2 3第一百一十一捆 4 1第一百一十二捆 3 1 1第一百一十三捆 2 2 1第一百一十四捆 1 1 3第一百一十五捆 2 2 1第一百一十六捆 1 1 1 2第一百一十七捆 1 2 2第一百一十八捆 2 2 1
