天然肠衣搭配分析(2011D)

2011年高教社杯全国大学生数学建模竞赛赛题解析2011年D题——天然肠衣搭配问题分析吉耀武西安铁路职业技术学院.流程图一.问题提出二.赛题简述三.问题分析四.模型假设五.模型建立与求解六.小结数学教研室吉耀武天然肠衣指的是家畜的大小肠经刮制而成的畜产品，主要用于香肠、灌肠等食品的外衣。我国加工肠衣历史悠久，产量占世界总产量的1/3,其中约80%出口.传统的肠衣加工主要依靠人工来完成，一方面，人工成本高；另一方面，作为食品，不允许将剩余材料留作以后使用，而人工搭配一般不作整体考虑，只是凭经验判断是否可搭配成捆，无法保证原材料的充分利用。一、问题提出数学教研室吉耀武2011年高教社杯全国大学生数学建模竞赛D题——天然肠衣搭配问题。要求解决的问题是根据题目提供的成品规格表和原料描述表，设计一个原料搭配方案，工人根据这个方案“照方抓药”进行生产。公司对搭配方案有以下具体要求：(1)对于给定的一批原料，装出的成品捆数越多越好；(2)对于成品捆数相同的方案，最短长度最长的成品越多，方案越好；(3)为提高原料使用率，总长度允许有±0.5米的误差，总根数允许比标准少1根；(4)某种规格对应原料如果出现剩余，可以降级使用。如长度为14米的原料可以和长度介于7-13.5米的进行捆扎，成品属于7-13.5米的规格；(5)为了食品保鲜,要求在30分钟内产生方案。二、赛题简述数学教研室吉耀武成品规格表表1成品规格表规格最短长度最大长度标准根数/捆总长度/捆短36.52089中713.5889长14∞589数学教研室吉耀武原料描述表表2原料描述表长度3-3.43.5-3.94-4.44.5-4.95-5.45.5-5.96-6.46.5-6.9根数4359394127283421长度7-7.47.5-7.98-8.48.5-8.99-9.49.5-9.910-10.410.5-10.9根数2424202521232118长度11-11.411.5-11.912-12.412.5-12.913-13.413.5-13.914-14.414.5-14.9根数3123225918253529长度15-15.415.5-15.916-16.416.5-16.917-17.417.5-17.918-18.418.5-18.9根数3042284245495064长度19-19.419.5-19.920-20.420.5-20.921-21.421.5-21.922-22.422.5-22.9根数526349352716122长度23-23.423.5-23.924-24.424.5-24.925-25.425.5-25.9根数060001数学教研室吉耀武目标：(1)对于给定的原料，装出的成品捆数越多越好；(2)对于成品捆数相同的方案，最短长度最长的成品越多，方案越好；(3)为了食品保鲜,要求在30分钟内产生方案。三、问题分析条件：(1)总长度允许有±0.5米的误差；(2)总根数允许比标准少1根；(3)剩余原料可以降级使用。数学教研室吉耀武三、问题分析解决方案：将产品规格分成长、中、短三档。其实质是将“最短长度最长的成品最多”转化为“最短长度在某个值以上的成品最多”。1）按照可降级的要求，先从长规格开始，进行求解优化搭配；2）将第1步优化后剩余的原料放入中规格，进行求解优化搭配；3）将第2步优化后剩余的原料放入短规格，进行求解优化搭配；4）如果剩余的原料总长小于88.5米或接近于理论最优值，则认为优化成功。数学教研室吉耀武四、模型假设模型假设：1、原料描述表中提供的原料不能剪裁使用；2、为提高原料使用率，总长度允许有±0.5米的误差，总根数允许比标准少1根；3、某种规格对应的原料如果出现剩余较多时，可以平移降级使用。如长度为7米、7.5米、8米的原料出现剩余，可以向下一规格平移降级为5.5米、6米、6.5米使用，这样可以提高原料的使用率。什么是平移降级?数学教研室吉耀武五、模型建立与求解符号说明：M:一种规格总捆数；N：每捆的标准根数；L：每捆的标准总长度；k：原料的分段数；ia：每段原料的长度；ib：每段原料的根数；ix：每段原料使用的根数；ic：每段原料剩余的根数.方法一：1、将捆数和搭配分开优化（1）最大捆数的优化模型数学教研室吉耀武为分析方便起见，列表如下：原料序号123…i…k原料长度1a2a3a...ia...ka原料使用根数1x2x3x...ix...kx原料提供根数1b2b3b...ib...kb每捆根数范围],-[NN1，其中N是每捆标准根数.每捆长度范围]..5[50LL0,-，其中L是每捆标准长度.数学教研室吉耀武五、模型建立与求解目标函数：Mmax约束条件：取整数.iiiiiikiiixM,k1,2,3,ixbck1,2,3,ibxLMxaLMMNxNM)(-)()(0.5)-(10.51)-(1kiis.t模型建立:数学教研室吉耀武捆数优化程序：model:N=;L=89;sets:yuanliao/1..k/:x,c,a,b;endsetsdata:a=;b=;enddatamax=M;@sum(yuanliao(i):x)=M*(N-1);@sum(yuanliao(i):x)=M*N;@sum(yuanliao(i):a*x)=M*(L-0.5);@sum(yuanliao(i):a*x)=M*(L+0.5);@for(yuanliao(i):x=b);@for(yuanliao(i):c=b-x);!剩余原料;@for(yuanliao(i):@gin(x));@gin(M);end数学教研室吉耀武利用LINGO程序计算：（1）长规格：取k=24，N=5，L=89，计算得最大捆数M=137，原料剩余根（19m长），降级.（2）中规格：取k=14，N=8，L=89，计算得最大捆数M=37，原料剩余，平移降级.（3）短规格：取k=8，N=20，L=89，计算得最大捆数M=18，原料剩余根（6.5m长）.111c1924144321ccccc，，78c数学教研室吉耀武五、模型建立与求解（2）搭配方案（“照方抓药”）设ijy表示第i捆成品中使用的第j段原料的根数，列表如下：123…j…k原料捆序1a2a3a...ja...ka111y21y31y...1jy...1ky221y22y32y...2jy...2ky313y32y33y...j3y...k3y...…………………MM1y2My3My...Mjy...Mky使用根数1x2x3x...jx...kx数学教研室吉耀武•建立搭配模型：数学教研室吉耀武)(k,1,2,jM;,1,2,iyxy0.5Lya0.5LNy1NijjM1iijk1jijjk1jij取整数于选定的根数扎捆中第j段总根数等对每捆长度的约束对每捆根数的约束搭配优化程序：model:N=;L=89;sets:kun/1..M/;yuanliao/1..k/:x,a;link(kun,yuanliao):y;endsetsdata:a=;x=;!x是使用根数;enddata@for(yuanliao(i):@sum(kun(i):y(i,j))=x(j));@for(kun(i):@sum(yuanliao(i):y(i,j))=N-1;@sum(yuanliao(i):y(i,j))=N);@for(kun(i):@sum(yuanliao(i):a(j)*y(i,j))=L-0.5;@sum(yuanliao(i):a(j)*y(i,j))=L+0.5);@for(link(i,j):@gin(y));end数学教研室吉耀武五、模型建立与求解2.将捆数和搭配联合优化模型设ijy表示第i捆成品中使用的第j段原料的根数，列表如下：123…j…k原料捆序1a2a3a...ja...ka111y21y31y...1jy...1ky221y22y32y...2jy...2ky313y32y33y...j3y...k3y...…………………MM1y2My3My...Mjy...Mky原料根数1b2b3b...jb...kb数学教研室吉耀武建立联合优化模型：取整数ijM1ijijk1jijjk1jijyby0.5Lya0.5LNy1NM.s.tmax数学教研室吉耀武方法二：五、模型建立与求解首先预测有多少种扎捆的方式（模式），设),,,(k21rrr为任意一种扎捆方式，它满足如下不等式组：k),1,2,(ibr0.5Lra0.5LNr1Niiik1iik1ii假设不等式组有M个解（每一个解代表一种扎捆方式），列表如下：数学教研室吉耀武五、模型建立与求解设ix表示按第i种模式下所扎的捆数123…j…k扎捆模式捆数1a2a3a...ja...ka11x11r21r31r...1jr...1kr22x21r22r32r...2jr...2kr33x13r32r33r...j3r...k3r......…………………MMxM1r2Mr3Mr...Mjr...Mkr原料根数1b2b3b...jb...kb数学教研室吉耀武•目标函数：•约束条件：•扎捆模式可用MATLAB编程得到•优化程序类似于前面捆数的优化程序M1iixmax取整数ijM1iijixbrxkM)(ijr数学教研室吉耀武六、小结1、模型分析要全面;2、按长、中、短规格顺序建立模型;3、模型的建立应由简单到复杂,重点突出；4、论文写作应条理清晰,最好图、文、表并茂,方法多样化.数学教研室吉耀武陕西赛区组委会及专家的大力支持！谢谢大家！感谢数学教研室吉耀武