[临床医学]天然肠衣的论文.doc

天然肠衣搭配问题摘要本文针对天然肠衣搭配方案的设计以及最优原则，在满足题意要求的情况下，采用建立整数线性规划模型，利用数学知识联系实际，并借助LINGO软件，得到肠衣最多捆数和及肠衣最优搭配方案。由题中表1、表2知，批次的原料按照成品表格里面指定的“根数”和“总长度”组装成“捆”，在36.5、713.5、1425.5长度规格中依次构造目标函数和约束条件，然后建立初步整数规划模型，利用LINGO软件，分别得到各种规格搭配的最大捆数为14+36+130=180。题中要求为提高原料使用率，总长度允许有 0.5米的误差，总根数允许比标准少1根；又可建立附加约束条件后的整数线性规划模型。当某种规格对应原料如果出现剩余，可以降级使用。如长度为14米的原料可以和长度介于7-13.5米的进行捆扎，成品属于7-13.5米的规格；按降级后的区段计算长度，对余料降级使用，最后得出各规格每捆的方案，对于成品捆数相同的方案，即每捆里面单根肠衣在选择时在一个区段里面越长的越好，组合最优化方案，故可让工人按方抓药。关键词：整数线性规划、LINGO软件、组合最优化、搭配问题问题重述 天然肠衣（以下简称肠衣）制作加工是我国的一个传统产业，出口量占世界首位。肠衣经过清洗整理后被分割成长度不等的小段（原料），进入组装工序。传统的生产方式依靠人工，边丈量原料长度边心算，将原材料按指定根数和总长度组装出成品（捆）。原料按长度分档，通常以0.5米为一档，如：3-3.4米按3米计算，3.5米-3.9米按3.5米计算，其余的依此类推。表1是几种常见成品的规格，长度单位为米，表示没有上限，但实际长度小于26米。 成品规格表最短长度最大长度根数总长度36.52089713.588914589表1为了提高生产效率，公司计划改变组装工艺，先丈量所有原料，建立一个原料表。表2为某批次原料描述。第一种规格档次12345678长度3-3.43.5-3.94-4.44.5-4.95-5.45.5-5.96-6.46.5-6.9根数4359394127283421第二种规格档次1234567长度7-7.47.5-7.98-8.48.5-8.99-9.49.5-9.910-10.4根数24242025212321档次891011121314长度10.5-10.911-11.411.5-11.912-12.412.5-12.913-13.413.5-13.9根数18312322591825第三种规格档次12345678长度14-14.414.5-14.915-15.415.5-15.916-16.416.5-16.917-17.417.5-17.9根数3529304228424549档次910111213141516长度18-18.418.5-18.919-19.419.5-19.920-20.420.5-20.921-21.421.5-21.9根数5064526349352716档次1718192021222324长度22-22.422.5-22.923-23.423.5-23.924-24.424.5-24.925-25.425.5-25.9根数122060001表2根据以上成品和原料描述，设计一个原料搭配方案，工人根据这个方案“照方抓药”进行生产。公司对搭配方案有以下具体要求：(1) 对于给定的一批原料，装出的成品捆数越多越好；(2) 对于成品捆数相同的方案，最短长度最长的成品越多，方案越好；(3) 为提高原料使用率，总长度允许有 0.5米的误差，总根数允许比标准少1 根；(4) 某种规格对应原料如果出现剩余，可以降级使用。如长度为14米的原料可以和长度介于7-13.5米的进行捆扎，成品属于7-13.5米的规格；(5) 为了食品保鲜,要求在30分钟内产生方案。请建立上述问题的数学模型，给出求解方法，并对表1、表2给出的实际数据进行求解，给出搭配方案。问题分析由题意可知，目的就是为了建立一种模型，通过计算，按照成品规格表，获得原料的一种最佳搭配方案而使工人能够根据这个方案“按方抓药”进行生产，提高生产效率，实现生产数据化和最大产出率。由问题重述表1中可我们可把肠衣分为三类规格第一类规格长度（36.9），分为8个档次即：3-3.43.5-3.944.44.5-4.95-5.45.5-5.96-6.46.5-6.9第二类规格长度（713.9），分为14个档次即：7-7.47.5-7.98-8.48.5-8.99-9.49.5-9.910-10.410.5-10.911-11.411.5-11.912-12.412.5-12.913-13.413.5-13.9第三类规格长度（1425.9），分为24个档次即：14-14.414.5-14.915-15.415.5-15.916-16.416.5-16.917-17.417.5-17.918-18.418.5-18.919-19.419.5-19.920-20.420.5-20.921-21.421.5-21.922-22.422.5-22.923-23.423.5-23.924-24.424.5-24.925-25.425.5-25.9我们对要求一做出初步整数数学模型（即没有每捆总长度和每捆总根数误差），在36.5、713.5、1425.5长度规格中依次构造目标函数和约束条件，利用LINGO软件，分别得到各种规格搭配的最大捆数：14+36+130=180。要求二对于成品捆数相同的方案，即每捆里面单根肠衣在选择时在一个区段里面越长的越好，故可知规格一中用（6.56.9）长度的肠衣越多越好，规格二中用（13.5-13.9）长度的肠衣越多越好，规格三中用（25.5-25.9）长度的肠衣越多越好，其中14-26米之间（表示没有上限，但实际长度小于26米）。考虑到要求三中的误差每规格总长度允许有 0.5米的误差，每规格总根数允许比标准少1根；把附加约束条件添加到数学线性规划模型中，对比初步整数数学模型得到最优解。原料表格里面的材料出现剩余时，可降级使用，不浪费，按降级后的区段计算长度，求算规格二有原料剩余，降级到规格一使用，最后的得到各种规格搭配方案的最大捆数：16+37+137=190。再考虑到要求五中，为了食品保鲜,要求在30分钟内产生方案，我们可求算各个规格中所采取的不同方案，使工人根据这个方案进行“照方抓药”进行生产。模型假设1 视33.4米为3米，3.54米为3.5米，以下长度类推；2 忽略在生产过程中对肠衣长度的损耗；3 总长度、总根数许可误差情况下对结果不会产生影响；4 工人在肠衣捆绑的过程中不受外界因素干扰，且对肠衣的保鲜度不受影响；5丈量所有原料时，丈量误差都在误差允许范围之内；6. 某种规格对应原料如果出现剩余，可以降级使用符号定义i天然肠衣的规格J天然肠衣的档次Y天然肠衣的捆数n天然肠衣的使用根数K天然肠衣原始根数X单根天然肠衣的长度模型建立与求解整数线性规划：当线性规划问题的部分或所有的变量局限于整数值时，我们称这一类问题为整数线性规划问题。建立初步整数线性最优化模型：方案一：由题中给出的成品规格表1的数据，在有任何误差以及满足要求一的情况下，我们设计出方案一，求得每一种规格的成品的最大捆数。规格：目标函数：约束条件： 运用LINGO程序得到36.5规格最大捆数=14捆，每一档使用情况如下表1：没有误差36.5规格的数据档次12345678长度33.544.555.566.5原始根数4359394127283421使用根数4359394117283420剩余根数000010001表1规格：目标函数： 约束条件： 运用LINGO程序得到713.5规格最大捆数=36捆，每一档使用情况如下表2没有误差713.5规格的数据档次1234567长度7-7.47.5-7.98-8.48.5-8.99-9.49.5-9.910-10.4原始根数24242025212321使用根数00625212121剩余根数2424140020档次891011121314长度10.5-10.911-11.411.5-11.912-12.412.5-12.913-13.413.5-13.9原始根数18312322591825使用根数18302222591825剩余根数0110000表2规格：目标函数：约束条件： 运用LINGO程序得到1425.5规格的最大捆数=130捆，每一档使用情况如下表3：没有误差1425.5规格的数据档次12 345678长度14-14.414.5-14.915-15.415.5-15.916-16.416.5-16.917-17.417.5-17.9原始根数3529304228424549使用根数3529304228424549剩余根数00000000档次910111213141516长度18-18.418.5-18.919-19.419.5-19.920-20.420.5-20.921-21.421.5-21.9原始根数5064526349352716使用根数5064526349352714剩余根数00000002档次1718192021222324长度22-22.422.5-22.923-23.423.5-23.924-24.424.5-24.925-25.425.5-25.9原始根数122060001使用根数00000000剩余根数122060001表3三种规格的成品最大捆数总和：捆方案二：针对要求三，为提高原料使用率，总长度允许有 0.5米的误差，总根数允许比标准少1根的情况下，由题中表1、表2的数据，我们设计方案二，求得每一种规格的成品的最大捆数。规格：目标函数：约束条件： 运用LINGO程序得到36.5规格最大捆数=14捆，每一档使用情况如下表4：有误差36.5规格的数据档次12345678长度33.544.555.566.5原始根数4359394127283421使用根数4359254127283421剩余根数00000000表4规格：目标函数：约束条件： 运用LINGO程序得到713.5规格最大捆数=37捆，每一档使用情况如下表5：有误差713.5规格的数据档次1234567长度7-7.47.5-7.98-8.48.5-8.99-9.49.5-9.910-10.4原始根数24242025212321使用根数12923212321剩余根数2322112000档次891011121314长度10.5-10.911-11.411.5-11.912-12.412.5-12.913-13.413.5-13.9原始根数18312322591825使用根数18312322591825剩余根数0000000表5规格：目标函数：约束条件： 运用LINGO程序得到1425.5规格最大捆数=137捆，每一档使用情况见表6：有误差1425.5规格的数据档次12345678长度14-14.414.5-14.915-15.415.5-15.916-16.416.5-16.917-17.417.5-17.9原始根数3529304228424549使用根数3529304228424549剩余根数00000000档次910111213141516长度18-18.418.5-18.919-19.419.5-19.920-20.420.5-20.921-21.421.5-21.9原始根数5064526349352716使用根数5064526349352716剩余根数00000000档次1718192021222324长度22-22.422.5-22.923-23.423.5-23.924-24.424.5-24.925-25.425.5-25.9原始根数122060001使用根数122060001剩余根数00000000表6在允许的误差范围内，三种规格的成品最大捆数捆 方案三：由方案一、方案二得到：为了最优原则，考虑成品捆数越多越好，我们可以采取方案二，但是我们还要考虑余料降级。在方案二的基础上我们考虑余料降级，由表6中1425.5规格没有余料，表5知713.5规格在77.4、7.58、88.4、8.58.9、有余料，将此余料降级到36.5规格中。如表7：规格二的原料剩余量长度使用根数原始根数剩余根数7124237.5224228920118.5232529212109.523230102121010.518180113131011.523230122222012.559590131818013.525250表7-1规格一的数据档次123456长度33.544.555.5原始根数435939412728使用根数435925412728剩余根数000000档次789101112长度66.577.588.5原始根数342124242025使用根数34210000剩余根数0024242025表7-2表7可见规格增加四个档次，我们设计方案三，只对增加档次后的规格重新建立目标函数、约束条件运用LINGO程序求得最大捆数，规格规格没有任何改变，最大捆数不变。规格：目标函数：约束条件： 运用LINGO程序得到38.9最大捆数=16捆。见表8规格一的原料剩余量长度利用总共剩余3434303.5595904393904.5414105272705.5272816343406.5021217223217.5212218101118.5220表8规格、不变，允许误差范围内，考虑降级后三种规格总捆数：捆 。方案四：在满足所有的要求：捆数越多越好；每捆里面单根肠衣在选择时，在一个区段里面越长越好；允许误差范围内；余料降解；节省时间，我们设计方案三，运用LINGO软件得到每种规格的最佳搭配方案。规格目标函数：约束条件： 运用LINGO程序得到1425.5规格的搭配方案见表9：规格三的搭配方式130000100000013.500000000000140000000000014.501101000000153201020000015.500000130000160000000030016.500000001100170003000400017.500400000000180000000000018.500010000000191000302000019.500000200001200200000010020.510000000000210000000003121.500000000000220000000000022.500000000012230000000000023.500000000000240000000000024.500000000000捆数39664234216表9规格：目标函数：约束条件： 运用LINGO程序得到713.5规格的搭配方案见表10：规格二搭配方案长度77.588.599.51010.51111.51212.51313.5捆数 规格二的分配方案 000003000050002000011200004001000110200003011001100000060001000310000000041000000034000101010000005000201001000000700001000210000005004000100300004001000000320003001100000030004001000013000003012000002102003001000310000000041000000007100001000021100003011000004100000031000031000000401000112000002021002000102000031000030101000031000000201500001000000007100001001200000100401000000401100201000000051002001012000000000501000300000030021001000000700001000000050030001001020000005001表10规格：目标函数：约束条件： 运用LINGO程序得到36.5规格的搭配方案见表11：规格一搭配方案长度规格一搭配方案3728001100901104003.525000008131429690431012101100010000104.5104200310009120185060000010150500005.50023900800011300604100060600080906.50000000000000000700000000100001007.56030070000500000801120001200003008.50000000000010001捆数1111111111111111表11模型的评价与推广本文通过对问题的充分分析，用了整数规划模型，使问题的思路清晰明了。创造性的把问题的要求转化为用LINGO数学软件解决的线性规划问题。大大简化了问题讨论过程的复杂程度。分析原料数据的时候，从整体大方面开始处理，然后再一步步细化，这种讨论问题的方法简洁易懂，具有很高的可读性。建立整数线性规划模型，在理论上有一定的基础，在实际操作中具有一定的可行性。优点：在使用LINGO软件求解的整数线性规划的过程中，有些最优解可能是分数或小数，不符合本文的要求。故模型的结果有一定的误差，但考虑到本问题可以降级使用原料，按需可以获得不同规格的成品，在允许的误差范围内是可以接受的。因所需设计的搭配方案需要从原料处在不同的长度区段来获取一定长度的成品，决策变量是原料的根数，所求的解必须是整数，为满足整数的要求，化整后的数趋近于最优解。整数规划的主要缺点是：没有统一的标准模型，也没有构造模型的通用方法，甚至还没有判断一个问题能否构造动态规划模型的准则。这样就只能对每类问题进行具体分析，构造具体的模型。对于较复杂的问题在选择状态、决策、确定状态转移规律等方面需要丰富的想象力和灵活的技巧性，这就带来了应用上的局限性。模型的改进组合最优化通常都可表述为整数规划问题。两者都是在有限个可供选择的方案中，寻找满足一定约束的最好方案。有许多典型的问题反映整数规划的广泛背景。例如，背袋（或装载）问题、超市分配员工问题、旅行推销员问题, 车辆路径问题、选修课程问题、公司的人员安排问题等。因此整数规划的应用范围也是极其广泛的。它不仅在工业和工程设计和科学研究方面有许多应用，而且在计算机设计、系统可靠性、编码和经济分析等方面也有新的应用。参考案例钢管下料问题公司的人员安排问题参考文献1 袁新生，邵大宏，郁时炼.LINGO和Excel在数学建模中的应用。北京：科学出版社，20082 韩中庚，陆宜清，周素静.数学建模实用教程。北京：高等教育出版社，2012附录程序1 model: max=y1; 3*x11+3.5*x12+4*x13+4.5*x14+5*x15+5.5*x16+6*x17+6.5*x18-89*y1=0; x11+x12+x13+x14+x15+x16+x17+x18-20*y1=0; x11=43;x12=59;x13=39;x14=41;x15=27;x16=28;x17=34;x18=0; 3*x11+3.5*x12+4*x13+4.5*x14+5*x15+5.5*x16+6*x17+6.5*x18-89.5*y1=0; x11+x12+x13+x14+x15+x16+x17+x18-20*y1=0; x11=43;x12=59;x13=39;x14=41;x15=27;x16=28;x17=34;x18=21; gin(x11);gin(x12);gin(x13);gin(x14);gin(x15);gin(x16);gin(x17);gin(x18);gin(y1); 结果 Global optimal solution found. Objective value: 14.00000 Extended solver steps: 0 Total solver iterations: 3 Variable Value Reduced Cost Y1 14.00000 -1.000000 X11 43.00000 0.000000 X12 59.00000 0.000000 X13 25.00000 0.000000 X14 41.00000 0.000000 X15 27.00000 0.000000 X16 28.00000 0.000000 X17 34.00000 0.000000 X18 21.00000 0.000000 Row Slack or Surplus Dual Price 1 14.00000 1.0000002 10.50000 0.0000003 3.500000 0.0000004 12.00000 0.0000005 2.000000 0.0000006 0.000000 0.0000007 0.000000 0.0000008 14.00000 0.0000009 0.000000 0.000000 10 0.000000 0.000000 11 0.000000 0.000000 12 0.000000 0.000000 13 0.000000 0.000000 程序3 model: max=y2; 7*x9+7.5*x10+8*x11+8.5*x12+9*x13+9.5*x14+10*x15+10.5*x16+11*x17+11.5*x1 8+12*x19+12.5*x20+13*x21+13.5*x22-89*y2=0; x9+x10+x11+x12+x13+x14+x15+x16+x17+x18+x19+x20+x21+x22-8*y2=0; x9=24;x10=24;x11=20;x12=25;x13=21;x14=23;x15=21;x16=18;x17=31; x18=23;x19=22;x20=59;x21=18;x22=25; gin(x9);gin(x10);gin(x11);gin(x12);gin(x13);gin(x14);gin(x15);gin(x16);gin(x17);gin(x18);gin(x19);gin(x20);gin(x21);gin(x22); 结果 Global optimal solution found. Objective value: 36.00000 Extended solver steps: 6969 Total solver iterations: 9911 Variable Value Reduced Cost Y2 36.00000 0.000000 X9 0.000000 -0.7865169E-01 X10 0.000000 -0.8426966E-01 X11 6.000000 -0.8988764E-01 X12 25.00000 -0.9550562E-01 X13 21.00000 -0.1011236 X14 21.00000 -0.1067416 X15 21.00000 -0.1123596 X16 18.00000 -0.1179775 X17 30.00000 -0.1235955 X18 22.00000 -0.1292135 X19 22.00000 -0.1348315 X20 59.00000 -0.1404494 X21 18.00000 -0.1460674 X22 25.00000 -0.1516854 Row Slack or Surplus Dual Price 1 36.00000 1.0000002 0.000000 -0.1123596E-013 0.000000 0.0000004 24.00000 0.0000005 24.00000 0.0000006 14.00000 0.0000007 0.000000 0.000000程序4 model: max=y2; 7*x9+7.5*x10+8*x11+8.5*x12+9*x13+9.5*x14+10*x15+10.5*x16+11*x17+11.5*x1 8+12*x19+12.5*x20+13*x21+13.5*x22-89.5*y2=0; x9+x10+x11+x12+x13+x14+x15+x16+x17+x18+x19+x20+x21+x22-8*y2=0; x9=24;x10=24;x11=20;x12=25;x13=21;x14=23;x15=21;x16=18;x17=31; x18=23;x19=22;x20=59;x21=18;x22=25; gin(x9);gin(x10);gin(x11);gin(x12);gin(x13);gin(x14);gin(x15);gin(x16);gin(x17);gin(x18);gin(x19);gin(x20);gin(x21);gin(x22); 结果 Global optimal solution found. Objective value: 37.00000 Extended solver steps: 0 Total solver iterations: 16 Variable Value Reduced Cost Y2 37.00000 0.000000 X9 0.000000 -0.7909605E-01 X10 0.000000 -0.8474576E-01 X11 11.00000 -0.9039548E-01 X12 25.00000 -0.9604520E-01 X13 21.00000 -0.1016949 X14 23.0000