天然肠衣搭配优化问题的模型(厦门1)

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