天然肠衣搭配优化问题的模型和计算

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,天然肠衣搭配优化问题的模型和,计算,陆立,强,复旦大学数学科学学院,问题的背景,天然肠衣（以下简称：肠衣）指的是家畜的大、小肠经刮制而成的畜产品，主要用于香肠、灌肠等食品的外衣,。,中国,加工肠衣历史悠久,，产量,占世界总产量的,三分之一,，其中约,80%,出口，年出口量达,30,多万,桶,我国,现有肠衣出口注册企业,200,家左右，其中对欧盟注册的就有,119,家,左右。,近几年,，国内市场对肠衣的需求也呈递增趋势,，机会,越来越多,，竞争,也更加激烈。,问题的背景,传统,肠衣加工,工艺,清洗,整理,捆扎,丈量,搭配,肠衣加工主要依靠,人工,，,其中,捆扎,环节,要求,工人,眼明手快,，,人力成本高,原料,长短不一,成品中肠衣的,总长度,和,总,根数,固定,问题的背景,作为一种食品,，不,允许将剩余的原材料留作以后使用，因此对于原料的,使用率,有比较高的要求,。,人工搭配一般,不作整体考虑，,只是凭,经验,和,简单的计算,判断,是否可以搭配成一捆成品,，,无法,保证原材料的充分利用,。,问题的提出,肠衣加工企业,希望开发,一套计算机软件,，只需,一线工人将测量所得,原料数据输入,电脑，就能,自动生成,经过优化后的满足成品规格要求的,搭配方案,，这样既可以,减少劳动强度,、又能,提高原料使用率,。,问题的提出,原料,信息,：,企业,的测量以,0.5,米为一档，如：,3.1-3.5米按3米计算，3.6米-4米按3.5米计算，,其余的依此类推,；,成品,描述：,一般,分成三种,规格,每,种规格,用,（,最短原料长度，最长原料长度，原料根数，总长度,）,加以描述,问题的提出,目标,对于,给定的一批原料，装出的成品捆数越,多,，方案,越,好,。,对于,成品捆数相同的方案，最短长度最长的成品越多，方案越好,。,要在,30,分钟内产生方案,。,问题的提出,条件,总长度,允许误差范围为,-0.5,，,0.5,，总根数允许误差范围为,-1,，,0,。,剩余原料可以,降级使用,。,问题,的,分析,目标,2,是,难点,最小,最大,问题解决难,度高,和,目标,1,可能是相互矛盾,的,办法,把,成品规格分成大、中、小三挡,，其,实质是将“,最短长度最长的成品最多,”的要求转化为“,最短长度在某个值以上的成品最多,”,将,一个从,理论上,完,美但,难以,实现,的,最优目标转化,为,可行,的,优化目标。,问题,的,分析,受,目标,2,的限制,，无法,依据,目标,1,建立,关于全部原料的优化装配,模型,办法,结合,条件,1,按照三种不同规格分步进行优化,。,结合,条件,2,，扩大每种规格最大长度的,上限,，提高原料使用率,。,问题,的,分析,总体方案,根据,大规格要求，求最优解；,将第,1,步优化后多余的原料纳入中规格，求最优解；,将第,2,步优化后多余的原料纳入小规格求最优解。,如果多余的原料总长小于,88.5,米,或者接近于理论最优值,，,则优化成功。,模型一,搭配方式模型,记号：,：,材料,的最短长,度,：,材料,的,最大长度,：,材料,根,数,：,成品,总,长度。,种,不同长度,的材料,：各种材料,的长度,：材,料,根,数,：某种,搭配方式,中各档材料的根数,模型一,搭配方式模型,模型,上述不等式组的解表示,所有可能的搭配方式,模型一,最优搭配,模型,记号：,不等式,组,解的个数,为,M,，,第,j,个,解,(,第,j,种搭配方式,),为,(a,1j,x,2j,x,Nj,),T,(j=1,M),搭配方案,表示为,(x,1,x,2,x,M,),x,j,表示第,j,种,搭配,方式,对应的捆数,(j=1,M,，,模型一,最优搭配,模型,模型：,约束条件,目标,模型一,求解：,搭配方式模型,自编程序,多重循环,简单,循环层次不变,递推,方式,循环层次可变,复杂,模型一,求解：,最优搭配模型,LINGO,求解,model:,sets:,rows/1.2862/:x;,cols/1.23/:y;,table(rows,cols):A;,endsets,max=sum(rows(i):x(i);,for(cols(j):,sum(rows(i):A(i,j)*x(i)=y(j);,for(rows(i):gin(x(i);,end,模型一,求解：,最优搭配模型,结果分析,大规格：捆扎方式,=2862,种,，最多捆数,=137,，,原料长度,捆数,14,14.5,15,15.5,16,16.5,17,17.5,18,18.5,19,19.5,20,20.5,21,21.5,22,22.5,23,23.5,24,24.5,25,25.5,搭配方式,1,1,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,4,1,0,0,0,1,0,0,0,1,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,1,1,0,0,0,0,1,1,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,2,1,0,0,0,0,1,0,0,0,0,2,0,1,0,0,0,0,0,0,0,0,0,0,0,7,1,0,0,0,0,0,0,1,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,8,0,1,0,0,0,0,0,1,1,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,15,0,1,0,0,0,0,0,0,0,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,10,剩余,18,米一根,模型一,求解：,最优搭配模型,结果分析,中规格,：,M=19635,种,，,最优捆,数,=37,捆,原料长度,捆数,7,7.5,8,8.5,9,9.5,10,10.5,11,11.5,12,12.5,13,13.5,18,捆扎方式,0,0,1,1,0,0,0,0,3,0,0,0,3,0,0,2,0,0,1,1,0,0,0,0,0,3,0,3,0,0,0,2,0,0,1,0,3,0,0,0,0,0,0,0,1,3,0,3,0,0,1,0,0,0,4,0,0,0,0,0,0,3,0,1,0,0,1,0,0,0,0,1,2,0,4,0,0,0,0,4,0,0,0,2,1,0,0,0,0,0,2,2,0,1,0,2,0,0,0,1,1,0,0,2,0,2,0,0,0,2,0,5,0,0,0,1,0,2,0,0,1,0,0,4,0,0,0,11,0,0,0,0,4,0,0,0,0,3,0,0,0,0,1,1,0,0,0,0,1,0,0,4,0,0,0,3,0,0,0,1,0,0,0,0,0,0,4,0,1,1,0,0,2,0,0,4,0,0,0,1,0,0,1,0,2,0,2,2,0,0,0,1,长度,7,7.5,8,9.5,13,13.5,根数,24,24,8,1,1,1,模型一,求解：,最优搭配模型,结果分析,小,规格,：只考虑等式约束，,M,接近,500,万,思路：,减少,搜索空间的维数,代价：,近似最优解,方法一：,M,个搭配方式中选取,LINGGO,所允许的最大,个数,结果：,M=24564,种，,最,优捆数,=16,。,模型一,求解：,最优搭配模型,结果分析,原料长度,捆数,3,3.5,4,4.5,5,5.5,6,6.5,7,7.5,8,9.5,13,13.5,搭配方式,4,0,1,1,4,4,1,0,1,3,0,0,1,0,1,3,4,4,1,0,2,0,4,0,0,1,1,0,0,1,2,4,3,0,4,0,0,4,1,1,1,0,0,0,1,2,3,2,4,2,0,0,4,3,0,0,0,0,0,1,2,3,1,0,2,3,4,0,3,1,1,0,0,0,2,1,3,7,0,1,3,2,0,1,0,1,0,0,1,1,0,7,2,3,3,0,3,1,0,1,0,0,0,0,3,0,4,3,8,1,1,1,1,0,0,1,0,0,0,3,0,4,0,0,0,8,0,1,6,1,0,0,0,0,1,0,1,4,1,0,0,4,2,0,8,0,0,0,0,1,0,0,1,1,0,0,7,0,5,6,0,0,0,0,1,长度,3,3.5,5.5,7,根数,27,1,2,1,模型二,思路：,模仿人工搭配方式，将最优捆数和搭配方式一起作为优化变量进行求解,方法：,先估计出成品,捆数,上限，再求出可能的搭配方式；,直接求出最优捆数和搭配方式。,模型一,搭配方式模型,记号：,：,材料,的最短长,度,：,材料,的,最大长度,：,材料,根,数,：,成品,总,长度。,种,不同长度,的材料,：各种材料,的长度,：材,料,根,数,：成品中各档材料的使用总数,模型二,捆数上限,模型,模型：,模型二,搭配方式,模型,2,设：根据上限模型求得成品捆数的上限为,M,0,设,：,第,i,捆成品中第,j,种,材料,的根数,为,x,ij,(i=1,M,0,j=1,N),模型二,联合优化,模型,设：成品捆数为,M,设,：,第,i,捆成品中第,j,种,材料,的根数,为,x,ij,(i=1,M,j=1,N),max M,模型二,分析,搭配方式,模型,2,的变量个数为,M,0,*N,，比,搭配方案优化,模型的变量个数,M,一般,要小得多，不会发生因为太大而无法优化的情况。但,模型,没有目标函数，所以每次只能得到局部最优，而非整体最优。,联合优化模型,可以直接通过,LINGO,求解，但因为第,一和第,三,两个,约束条件的求和项数也是一个优化变量，因此它是一个,非标准的整数规划,问题,。,使用,LINGO,每次只能得到一个局部最优。,模型二,分析,以上两种模型,求搭配方案，一次优化只能得到一种搭配方式的最多捆数,。,为了得到全部材料的搭配，需要修改剩余原料数据，再次优化，如此逐步进行，直到剩余材料无法成捆为止。人工干预较多，一般不能保证在,30,分钟内得到搭配方案。,模型一对问题的理解比较彻底，是一个标准的整数规划模型，理论上可以得到真正的最优解,只要编程得当，基本不需要人工干预，符合企业的最终要求。,总结,问题可以表达为数学规划问题，对于接受过数学建模训练的大学生而言应该不是一个难题。但是，实际情况没有想象的那样乐观。,“肠衣搭配优化问题”是一个源于中国的“土”问题，几乎得不到任何有用的资料，许多参赛同学因此心存怯意，不敢尝试。,也有一些同学感觉它和经典的“钢材切割问题”非常相像，后者是化整为零，前者是集零成整，但是，这表面的稍微差别却导致问题的本质发生了变化，使变量个数成倍增加，以致无法在规定时间内用现有的软件完成计算,，,因此而放弃了努力。,总结,数学建模竞赛过程中，模型固然是一个核心，,求解也十分重要,。,实际问题会出现计算规模超过计算机能力的情况，一种可行的解决办法就是将漂亮的理论最优解代之以实用的局部最优解。,从此次阅卷的情况来看，获奖的参赛队，或多或少地应用了这个思想。,在教学过程中应该适当增加,这方面,的内容。,感谢谭永基、叶其孝、蔡志杰等教授,感谢全国大学生数学建模竞赛组委会及其专家组,