2011年高教杯数学建模竞赛D题获奖论文--无锡职业技术学院

1天然肠衣搭配问题黄洁黄兵程理想指导老师杨先伟（无锡职业技术学院）摘要本文针对天然肠衣原料的搭配方案进行设计，充分考虑最优化原则，运用线性规划知识建立模型，并利用LINGO软件计算出结果。本文首先对题目中的五个要求进行分析，将前三个要求综合在一起考虑，建立数学模型解决。充分考虑前三个要求：成品捆数越多越好，在此基础上每捆中最短长度最长的越多越好，并且成品总长度及每捆数量可以有适当误差，确定线性规划中的目标函数为每种规格中的原料组装后所剩肠衣的长度之和最小，并结合题意给出约束条件，在算出每种规格理想的最大捆数的基础上运用LINGO软件求出最佳的搭配方案。其次针对第四个要求，先将规格三和规格二中所剩的肠衣，按照最优化理论建立线性规划模型求解，然后再将规格二和规格一中所剩下的肠衣建立模型求解，并给出最终的设计方案。运用上述模型，再利用LINGO软件计算出最终成品数为191捆，剩余肠衣原料总长为285米。当肠衣的原料表给出后，将数据带入文中模型并运用LINGO软件进行计算，能够在30分钟以内产生最佳搭配方案，满足题目要求。关键词：搭配线性规划模型LINGO一．模型假设1、假设在设计方案中，组装时优先考虑每种规格的肠衣独自组装，之后再将每种规格所剩的肠衣降级进行组装。2、假设肠衣原料降级使用只能降到相邻规格。比如，规格三只能降级到规格二，而不能降级到规格一。3、假设肠衣原料降级使用时，原料长度不降级。比如，将长度为14米的原料与长度介于7-13.米的进行捆扎时，长度仍然按14米计算。2二．符号说明ijx为某一规格中第i捆成品中第j档肠衣原料的根数ija为第i捆成品中第j档次肠衣的长度jb为某一规格中第j档次对应的总根数kd为第k种规格中每捆要求的根数，.3,2,1kkp为第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，得出针对长度的最大捆数；用每种规格肠衣的总根数除以对应规格每捆要求的数量)3,2,1(kdk，得出针对根数的最大捆数；易知，理论最大捆数为两者中较小的一个，具体计算公式为3,1njjkbaL3,2,1},,5.88min{kdNLfkk.．．．．．．①其中kf为理想最大捆数，L为某种规格原料的总长度，N为某种规格原料的总根数，ja为某种规格第j档肠衣的单位长度。以规格一为例，理论最大捆数为：14}20292,5.885.1305min{1f。据此计算三种规格最大捆数如下表1所示：表1总长度根数每捆要求根数每捆要求总长度下限理论最大捆数规格一1305.52922088.514规格二3705.5354888.541规格三12159.5677588.51354.1模型一，分别设计三种规格原料的搭配方案结合要求（1）、（2）可知，题目要求设计的搭配方案满足“给定的一批原料，装出的成品捆数越多越好，且对于成品捆数相同的方案，使得最短长度最长的成品最多”，经过分析可知，该要求等价于“对每种规格的肠衣应用搭配方案后，所剩下的肠衣长度之和最小”。再结合要求（3），总长度允许的0.5误差，总根数允许比标准少一根，应用线性规划建立模型。在求解模型时，将每种规格理想最大捆数依次按从大到小的顺序代入模型求解，直至第一组解求出，相应最优的搭配方案即可确定。具体骤如下：1、根据题目要求将原料描述表进行分档并标号如下表2所示：表2规格一序号12345678长度33.544.555.566.5根数4359394127283421规格二序号12345678长度77.588.599.51010.5根数2424202521232118序号91011121314长度1111.51212.51313.5根数312322591825规格序号12345678长度1414.51515.51616.51717.54三根数3529304228424549序号910111213141516长度1818.51919.52020.52121.5根数5064526349352716序号1718192021222324长度2222.52323.52424.52525.5根数1220600012、建立模型一设,,,2,1;,,2,1,njmiaij表示某一规格中，第i捆成品中第j档次肠衣的长度。某一规格中第j档次对应的总根数为jb，每一种规格的成品捆数为m，每种规格中都用ijx表示第i捆第j档肠衣的根数，kp表示第k种规格中最大成品捆数，kd表示第k种规格中每捆要求的根数，且,5,8,20321ddd用y表示方案搭配剩下的所有肠衣长度之和。根据前面分析可知，我们需要求解的是在题目的要求（1）、（2）、（3）下，y的最小值。易知，当y取得最小值时，m必然取得最大值，此时求出的ijx就是最佳搭配方案。具体的线性规划模型]1[如下：njmiijijjaxby11minS.T..3,2,1,,1kNmpmk且5.895.885.895.885.895.88221122222221211112121111mnmnmmmmnnnnxaxaxaxaxaxaxaxaxa．．．．．．．．．②.,,3,2,1,11midxdkjnjikmininmiimiibxbxbx1122111.,,3、将三种规格的数值分别带入模型并计算结果（ⅰ）针对规格一，将其数据带入到模型②式中可得如下规划模型：5捆数单位长度njmiijijjaxby11minS.T.Nmm,141且5.895.65.335.885.895.65.335.885.895.65.335.88821282221181211mmmxxxxxxxxx.14,,3,2,1,201981ixjjimiimiimiimiixxxx14131211,41,39,59,43.21,34,28,2718171615miimiimiimiixxxx将理想最大捆数14m代入模型，应用LINGO计算]2[模型的最优解5.52miny，即规格一的最大成品捆数为14。具体的搭配方案如下表3所示（求解程序]3[及结果见附录6.1）：表3规格一的搭配方案33.544.555.566.5第一捆001310000第二捆100010153第三捆001207001第四捆100000190第五捆011000026第六捆600001300第七捆28030070第八捆001126001第九捆09050302第十捆330014000第十一捆48100007第十二捆800001100第十三捆0511003016捆数单位长度第十四捆001190000（ⅱ）针对规格二，将其数值带入模型②式中同理可得线性规划模型。限于篇幅，我们在此应用矩阵对模型进行简化。设]5.13135.12125.11115.10105.995.885.77[A，3712]5.89,,5.89,5.89[B3712]5.88,,5.89,5.88['B.141,25,,,24,241421jbbbbj代入数据后具体模型如下：njmiijijjaxby11minNmmjbxixBAXBTSijijjijTTT,411.14,,2,1,.41,,2,1,87'..41114122应用LINGO计算结果，经过验证37m时，模型有最优解428miny，即规格二的最大成品捆数为37，具体搭配方案如下表4（求解程序见附录6.2）：表4规格二的搭配方案77.588.599.51010.51111.51212.51313.5总捆数第一捆000020001140008第二捆001000200041008第三捆000101200110028第四捆000003100020208第五捆000000140003008第六捆001010011004008第七捆000000007100008第八捆002001001000408第九捆000002120001208第十捆000100000700008第十一捆0000201100040087第十二捆001100000204008第十三捆000200001041008第十四捆000310000000048第十五捆000210000005008第十六捆000020003003008第十七捆000020013000028第十八捆001200000102028第十九捆000002110022008第二十捆000004100000038第二十一捆000004000110028第二十二捆000010032000208第二十三捆000013000003018第二十四捆000310000000048第二十五捆000000500001208第二十六捆000001100600008第二十七捆000210002000038第二十八捆000210000005008第二十九捆000210000005008第三十捆000001013020007第三十一捆000011100220108第三十二捆001000040002018第三十三捆000210000005008第三十四捆000010006000018第三十五捆003000000000508第三十六捆000000401003008第三十七捆000210000005008（ⅲ）针对规格三，将数值带入模型②，同样应用矩阵对模型进行简化。设：]5.25255.24245.23235.22225.21215.20205.19195.18185.17175.16165.15155.1414[A13513]5.895.89[B，13513]5.885.88['B.241,1,,29,352421jbbbbj代入数据后具体模型如下：njmiijijjaxby11min8NmmjbxixBAXBTSijijjijTTT,1351.24,,2,1,.135,,2,1,54)'(..135124133应用LINGO计算结果，当135m时，模型有最优解93miny，即规格三的最大成品捆数为135，具体搭配方案如下表5所示（求解程序]3[及结果见附录6.3)：1414.51515.51616.51717.51818.5192020212121.52222.52323.52424.52525.5第一捆212第二捆122第三捆1112第四捆212第五捆41第六捆1112第七捆122