2.2天然肠衣问题

天然肠衣问题天然肠衣制作加工是我国的一个传统产业，出口量占世界首位。肠衣经过清洗整理后被分割成长度不等的小段（原料），进入组装工序。传统的生产方式依靠人工，边丈量原料长度边心算，将原材料按指定根数和总长度组装出成品（捆）。原料按长度分档，通常以0.5米为一档，如：14-14.4米按14米计算，14.5米-14.9米按14.5米计算，其余的依此类推。为了提高生产效率，公司计划改变组装工艺，先丈量所有原料，建立一个原料表。表1某批次原料描述。表1原料描述表长度14-14.414.5-14.915-15.415.5-15.916-16.416.5-16.917-17.417.5-17.9根数3529304228424549长度18-18.418.5-18.919-19.419.5-19.920-20.420.5-20.921-21.421.5-21.9根数5064526349352716长度22-22.422.5-22.923-23.423.5-23.924-24.424.5-24.925-25.425.5-25.9根数122060001根据以上成品和原料描述，设计一个原料搭配方案，工人根据这个方案“照方抓药”进行生产。每捆标准长度为89米，根数为5根。公司对搭配方案有以下具体要求：(1)对于给定的一批原料，装出的成品捆数越多越好；(2)对于成品捆数相同的方案，最短长度最长的成品越多，方案越好；(3)为提高原料使用率，总长度允许有±0.5米的误差，总根数允许比标准少1根；(4）为减少组装的复杂性，要求组装的模式尽可能最少。这里一种模式表示各种长度的肠衣构成情况相同。请建立上述问题的数学模型，给出求解方法，并对表1给出的实际数据进行求解，给出搭配方案。(该题根据全国数模竞赛2011D改编)问题求解：首先求出20种肠衣根据原料可搭配成捆的所有模式，然后建立线性规划模型求解。利用编制Matlab程序求出20种肠衣根据原料可搭配成捆的所有模式，然后在模式中选择最佳的搭配。先对问题进行分析：1）最大捆数分析：将材料根数为0的去掉，这样总共有20种原材料。设第i种原材料的长度为il，根数为ia，1,2,...,20i。其中l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.5,25.5a35,29,30,42,28,42,45,49,50,64,52,63,49,35,27,16,12,2,6,1。则20种原材料中长度为201.iiiLal=12159.5米每捆长度最少为88.5米，因此捆数最多为：12195.5/88.5137.4137K其中[.]表示取整。20种原材料的总根数为201iiTa=677根每捆最少为4根，因此捆数最多为677/4169.25169K根。二者取最小值，因此137K。2）每捆成品的组成模式分析每捆成品可以有不同的构成模式，每种模式由一个向量1220(,,...,)xxx构成。ix代表第i种材料的根数。则各ix取值的最大整数值为：89.5min,,5iiiMal1,2,...,20i计算得到各ix(1,2,...,20i)的最大取值iM为：5,5,5,5,5,5,5,5,4,4,4,4,4,4,4,4,4,2,3,1。如果直接对各ix从0到iM进行完全枚举所有符合条件的模式，计算量为：20891(1)(51)(41)(21)(31)(11)iiTM7.871310如此巨大的计算量很难进行枚举。我们通过剪枝计算，可大大减少计算量，采用Matlab编程，可在不到1秒钟内计算出所有模式，其总数为2783种。实现的Matlab程序见附录1程序changyi.m图1部分模式向量示意图3）模型建立设共有n种模式(这里2783n)，每种模式为一个20维的列向量，代表一种符合条件的模式。即根数满足4或5根，长度为88.5米、或89米、或89.5米的一捆。所有些模式用矩阵207320B表示。ijb表示第i种模式中第j种长度的肠衣的根数。1,2,...,2783;i1,2,...,20j。所有模式向量由前面计算得到。决策变量为第i种模式ix捆，则成品捆数最多的目标函数为：278311maxiiZx现设法找到所有模式中最短长度最长的模式。在Matlab中通过编程，进行剪枝计算，得到在所有的2783种模式中，每捆最短长度最长的有3种模式，第一种是模式1，为2根22米和2根22.5米构成；第二种是模式2，为3根22米和1根22.5米构成；第三种是模式3，为3根22米和1根23.5米构成。则第二目标要求最短长度最长的捆数最大，有：2123maxZxxx满足的约束为各种长度的原料的数量，则有：278311,2,...,20iijjixbajja第j种长度的原料的根数。更进一步，从实际问题出发，当模式数比较多时，会增加搭配操作的复杂性，导致花费更多的搭配组装时间，因此我们尽量使搭配的模式尽量少。因此我们在前面两个目标情况下，考虑使搭配模式最少的方案。建立决策变量10iiyi第种模式选中第种模式未选中(1,2,...,2783)i我们建立的第三目标为总模式数最小，即278331miniiZy需要满足的约束有：当第i种模式未被选中时，则不能选取该种模式，且选中时不影响ix的取值，则有：.iixMy(1,2,...,2783)i其中M为一个足够大整数，如可取200M当第i种模式被选中时，则该种模式下一定有成品，因此有：iixy(1,2,...,2783)i则总的模型为：278311maxiiZx2123maxZxxx278331miniiZy278311,2,...,20.1,2,...,2783..1,2,...,2783,011,2,...,2783iijjiiiiiiixbajxMyistxyixyi为整数或；其中a=35,29,30,42,28,42,45,49,50,64,52,63,49,35,27,16,12,2,6,1实现的LINGO程序见附录程序changyi.lg4。令第一目标1Z最大化，利用LINGO得到1Z=137，最短长度为22米的有2捆，其模式为3根22米和1根23.5米构成。该结果还不是最优解。将1137Z变为约束，令2Z最大，利用LINGO求解。得到23Z的最优解。该解情况下材料无剩余，但使用模式有32种。再将12137,3ZZ作为约束，对目标3Z最小，利用LINGO得到总模式为16种的搭配方案。具体搭配方案见下表2。该结果由附录的Matlab程序result.m生成。表2最优搭配方案表(粗体为最短长度最长的方案)序号模式长度(米)根数捆数122.0米2根,22.5米2根8941222.0米3根,23.5米1根89.542321.5米2根,22.0米1根,23.5米1根88.544421.0米1根,21.5米2根,25.5米1根89.541516.5米1根,17.0米1根,18.0米1根,18.5米1根,19.5米1根89.555616.5米1根,17.0米1根,17.5米1根,18.5米1根,19.5米1根89515716.5米2根,17.0米2根,21.5米1根88.551815.5米1根,17.5米1根,18.0米1根,18.5米1根,19.0米1根88.5534915.5米1根,16.5米1根,18.0米1根,19.0米1根,19.5米1根88.5581015.0米1根,16.0米1根,16.5米1根,19.5米1根,21.5米1根88.5521114.5米1根,18.0米1根,18.5米1根,19.0米1根,19.5米1根89.5531214.5米1根,16.0米1根,17.0米1根,20.0米1根,21.0米1根88.55231314.5米1根,16.0米1根,16.5米1根,21.0米1根,21.5米1根89.5531414.0米1根,16.5米1根,18.5米1根,19.0米1根,20.5米1根88.5571514.0米1根,15.0米1根,19.5米1根,20.0米1根,20.5米1根895261614.0米1根,15.0米1根,19.5米2根,20.5米1根88.552总计137在该方案中，总捆数为137捆，达到最大，总共使用模式为16种，达到最小。最短长度为22米的有3捆.分别为：1捆模式为2根22米和2根22.5米的原材料。2捆模式为3根22米和1根23.5米的原材料。总共使用原材料677根，总长度为12159.5米，恰好将原材料用完无剩余。该搭配方案达到最优。注意该结果中具体的方案不是唯一的。序号1,模式:22.0米2根,22.5米2根,长度89.0米,4根,1捆.序号2,模式:22.0米3根,23.5米1根,长度89.5米,4根,2捆.序号3,模式:21.5米2根,22.0米1根,23.5米1根,长度88.5米,4根,4捆.序号4,模式:21.0米1根,21.5米2根,25.5米1根,长度89.5米,4根,1捆.序号5,模式:16.5米1根,17.0米1根,18.0米1根,18.5米1根,19.5米1根,长度89.5米,5根,5捆.序号6,模式:16.5米1根,17.0米1根,17.5米1根,18.5米1根,19.5米1根,长度89.0米,5根,15捆.序号7,模式:16.5米2根,17.0米2根,21.5米1根,长度88.5米,5根,1捆.序号8,模式:15.5米1根,17.5米1根,18.0米1根,18.5米1根,19.0米1根,长度88.5米,5根,34捆.序号9,模式:15.5米1根,16.5米1根,18.0米1根,19.0米1根,19.5米1根,长度88.5米,5根,8捆.序号10,模式:15.0米1根,16.0米1根,16.5米1根,19.5米1根,21.5米1根,长度88.5米,5根,2捆.序号11,模式:14.5米1根,18.0米1根,18.5米1根,19.0米1根,19.5米1根,长度89.5米,5根,3捆.序号12,模式:14.5米1根,16.0米1根,17.0米1根,20.0米1根,21.0米1根,长度88.5米,5根,23捆.序号13,模式:14.5米1根,16.0米1根,16.5米1根,21.0米1根,21.5米1根,长度89.5米,5根,3捆.序号14,模式:14.0米1根,16.5米1根,18.5米1根,19.0米1根,20.5米1根,长度88.5米,5根,7捆.序号15,模式:14.0米1根,15.0米1根,19.5米1根,20.0米1根,20.5米1根,长度89.0米,5根,26捆.序号16,模式:14.0米1根,15.0米1根,19.5米2根,20.5米1根,长度88.5米,5根,2捆.附录1程序：changyi.m输出所有模式的Matlab程序，该程序采用剪枝法进行枚举所有模式。输出文件为changyi.txt，该文件按行存储所有模式。方便后面的LINGO程序调用该数据文件。%20种长度l=[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.5,25.5];a=[35,29,30,42,28,42,45,49,50,64,52,63,49,35,27,16,12,2,6,1];%20种原料的根数L=l*a';%总长度Total=floor(L/88.5);%最多根数fprintf('最大捆数:%2d\n',Total);n=length(l);g=zeros(1,n);fori=1:nt=min(5,floor(89.5/l(i)));g(i)=min(t,a(i));%获得各种长度的类型肠衣的最多根数endModel=z