cumcm2011D-陆立强-天然肠衣搭配优化问题的模型-数模讲座27

天然肠衣搭配优化问题的模型和计算陆立强复旦大学数学科学学院问题的背景天然肠衣（以下简称：肠衣）指的是家畜的大、小肠经刮制而成的畜产品，主要用于香肠、灌肠等食品的外衣。中国加工肠衣历史悠久，产量占世界总产量的三分之一，其中约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种搭配方式)为(a1j,x2j,…,xNj)T(j=1,…,M)搭配方案表示为(x1,x2,…,xM)xj表示第j种搭配方式对应的捆数(j=1,…,M，模型一最优搭配模型模型：约束条件目标

模型一求解：搭配方式模型自编程序多重循环简单循环层次不变递推方式循环层次可变

复杂模型一求解：最优搭配模型LINGO求解model:sets:rows/1..2862/:x;cols/1..23/:y;table(rows,cols):A;endsetsmax=@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，

原料长度捆数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模型二思路：模仿人工搭配方式，将最优捆数和搭配方式一起作为优化变量进行求解方法：先估计出成品捆数上限，再求出可能的搭配方式；直接求出最优捆数和搭配方式。模型一搭配方式模型记号：

：材料的最短长度

：材料的最大长度

：材料根数

：成品总长度。

种不同长度的材料：各种材料的长度

：材料根数

：成品中各档材料的使用总数模型二捆数上限模型模型：模型二搭配方式模型2设：根据上限模型求得成品捆数的上限为M0

设：第i捆成品中第j种材料的根数为xij

(i=1,…,M0,j=1,…,N)模型二联合优化模型设：成品捆数为M

设：第i捆成品中第j种材料的根数为xij (i=1,…,M,j=1,…,N)maxM模型二分析搭配方式模型2的变量个数为M0*N，比搭配方案优化模型的变量个数M一般要小得多，不会发生因为太大而无法优化的情况。但模型没有目标函数，所以每次只能得到局部最优，而非整体最优。联合优化模型可以直接通过LINGO求解，但因为第一和第三两个约束条件的求和项数也是一个优化变量，因此它是一个非标准的整数规划问题。使用LINGO每次只能得到一个局部最优。模型二分析以上两种模型求搭配方案，一次优化只能得到一种搭配方式的最多捆数。为了得到全部材料的搭配，需要修改剩余原料数据，再次优化，如此逐步进行，直到剩余材料无法成捆为止。人工干预较多，一般不能保证在30分钟内得到搭配方案。模型一对问题的理解比较彻底，是一个标准的整数规划模型，理论上可以得到真正的最优解只要编程得当，基本不需要人工干预，符合企业的最终要求。总结问题可以表达为数学规划问题，对于接受过数学建模训练的大学生而言应该不是一个难题。但是，实际情况没有想象的那样乐观。“肠衣搭配优化问题”是一个源于中国的“土”问题，几乎得不到任何有用的资料，许多参赛同学因此心存怯意，不敢尝试。也有一些同学感觉它和经典的“钢材切割问题”非常相像，后者是化整为零，前者是集零成整，但