天然肠衣一维下料优化问题

1天然肠衣一维下料优化问题（西北工业大学理学院，西安710092）摘要一维下料问题是指在已知原料数量和顾客所需坯料规格、数量等情况下把一维原材料（如线材、管材、棒材等）按一定要求分割加工成不同长度的产品或零部件，使原材料的利用率达到最大的优化问题，此类问题在工程和工业生产中有着广泛而重要的应用。本文着眼于肠衣下料优化问题的解决，但亦可举一反三将解决该问题的思想、算法应用到其他工业生产中所遇到的一维下料优化问题中。本文首先用Matlab软件求解出满足题意的模式，再在当前可行的下料方式中依次按要求通过Lingo软件筛选出最优模式，不断重复此过程，直至所剩余的坯料数量减少至最少为止。经实际操作，本方法产生方案高效快捷，节材效果显著。关键词：一维下料线性优化模式法lingo优化问题matlab1.问题的提出天然肠衣（以下简称肠衣）制作加工是我国的一个传统产业，出口量占世界首位。肠衣经过清洗整理后被分割成长度不等的小段（原料），进入组装工序。原料按长度分档，通常以0.5米为一档，如：3-3.4米按3米计算，3.5米-3.9米按3.5米计算，其余的依此类推。为了提高生产效率，公司计划改变组装工艺，先丈量所有原料，建立一个原料表。最短长度最大长度根数总长度36.52089713.588914∞589表1成品规格表表2为某批次原料描述。长度3-3.43.5-3.94-4.44.5-4.95-5.45.5-5.96-6.46.5-6.9根数4359394127283421长度7-7.47.5-7.98-8.48.5-8.99-9.49.5-9.910-10.410.5-10.9根数2424202521232118长度11-11.411.5-11.912-12.412.5-12.913-13.413.5-13.914-14.414.5-14.9根数3123225918253529长度15-15.415.5-15.916-16.416.5-16.917-17.417.5-17.918-18.418.5-18.9根数3042284245495064长度19-19.419.5-19.920-20.420.5-20.921-21.421.5-21.922-22.422.5-22.9根数5263493527161222长度23-23.423.5-23.924-24.424.5-24.925-25.425.5-25.9根数060001表2原料描述表根据以上成品和原料描述，设计一个原料搭配方案，工人根据这个方案“照方抓药”进行生产。公司对搭配方案有以下具体要求：(1)对于给定的一批原料，装出的成品捆数越多越好；(2)对于成品捆数相同的方案，最短长度最长的成品越多，方案越好；(3)为提高原料使用率，总长度允许有±0.5米的误差，总根数允许比标准少1根；(4)某种规格对应原料如果出现剩余，可以降级使用。如长度为14米的原料可以和长度介于7-13.5米的进行捆扎，成品属于7-13.5米的规格；(5)为了食品保鲜,要求在30分钟内产生方案。2.问题的分析本文主要考虑在满足各种要求的情况下，解决天然肠衣之间的搭配问题，忽略次要因素，如测量误差、原料意外损耗等，主要考虑使天然肠衣的捆数最大且在捆数相同时最短长度最长的成品最多。在考虑到原料利用率的情况下，首先考虑在总长度和总根数都没有误差的情况，建立模型，求出模式。然后再考虑允许误差的情况，在原有的情况下，放松约束条件，求出模式。考虑到原料可以降级使用，就必须先求原料最长的成品的最大捆数，建立最优模型，求出成品三的最大捆数，接着算出该产品原料的余量。最后考虑成品三的余量，建立成品二的最优模型，求出成品二的最大捆数，算出该产品原料的余量。同理，建立成品一的最优模型，计算出成品一的最大捆数及余量。在捆数达到最大的前提下，使得最短长度最长的成品捆数达到最大，只需要在上述最优模型中，固定捆数为最大值，把目标函数改为最短长度最长的成品捆数最大即可。该问题的求解最终可以使公司获得最大利益，同时该问题所用的模型还可以应用到其它广泛领域，所以对该问题的求解，对国民生产具有很重要的实际意义。3.符号的约定)(ix——第i种模式的捆数；ik——模式中所选第i中原料的根数；)(ia——第i种原料的总根数；)(jb——上一级产品的余量被当做该级产品的第j种原料的根数；),(jic——第i种模式中第j种原料的根数；34.模型的假设（1）假设搭配过程中肠衣不会变质以及受到意外损失或损伤；（2）假设在对原料长度的测量中没有人为误差；（3）假设所有坯料均为合格品。5.模型的建立与求解5.1模型的建立5.1.1求解模式本节主要求解符合题意的模式，根据三种成品的不同规格要求分别对这三种产品求出满足题意的模式。（一）决策变量:在成品一中，我们假设从3—3.4米段中选择1k根，从3.5—3.9米段中选择2k根，依此类推，在6.5—6.9米段中选择8k根。在成品二中，我们假设从7—7.4米段中选择1k根，从7.5—7.9米段中选择2k根，依此类推，在13.5—13.9米段中选择14k根。在成品三中，我们假设从14—14.4米段中选择1k根，从14.5—14.9米段中选择2k根，依此类推，在25.5—25.9米段中选择24k根。（二）约束条件在成品一中，由表二知，它的后一种原料均比前一种原料长0.5米，所以第i种原料的长)(il为)8,...,2,1(),1(*5.03)(iiil。考虑到成品总根数可以少一根，总长度可以有5.0米的误差，以及表一，必须满足以下约束条件。,)8,...,2,1(5.89)(5.8820,2019811181ikilkkkkiiiijjiii为整数或4同理，在成品二中，第i种原料长)(il为)14,...,2,1(),1(*5.07)(iiil)14,...,2,1(5.89)(5.888)(,8714111141ikilkkikkiiiijjii为整数或同理，在成品二中，第i种原料长)(il为)24,...,2,1(),1(*5.014)(iiil)24,...,2,1(5.89)(5.885,5424111241ikilkkkkiiiijjiii为整数或5.1.2求解最大捆数本节主要求解在原料可以降级使用的前提下，求解三种成品的最大捆数。考虑到原料可以降级使用，所以我们先求解第三种成品的最大捆数，计算出余量，然后考虑该成品的余量，求解第二种成品的最大捆数，计算出余量，最后考虑这种成品的余量，求解第一种成品的最大捆数。（一）成品三的最大捆数求解:（1）决策变量在成品三中，记)1(x为按照该成品的第一种模式所生产的捆数，)2(x为按照该成品的第二种模式所生产的捆数，依此类推，)(ix为按照该成品的第i种产品生产的捆数。（2）决策目标因为要求的是捆数最大，所以决策目标为)(maxix（3）约束条件记)24,...,2,1)((jja为该成品中第j种原料的根数。),(jic为改成品中第i种模式所用第j种材料的根数。则很显然，所用的该种材料总根数不能超过原来该种材料的总根数。约束条件为为非负整数)()24,...,2,1(),(),()(ixjjajicix5（4）余量求出最优解后，显然第j种原料的余量为,),()()(jicixja)24,...,2,1(j，则总余量b为241)),()()((jjicixja。（二）成品二的最大捆数求解:（1）决策变量在成品二中，记)1(x为按照该成品的第一种模式所生产的捆数，)2(x为按照该成品的第二种模式所生产的捆数，依此类推，)(ix为按照该成品的第i种产品生产的捆数。（2）决策目标因为要求的是捆数最大，所以决策目标为)(maxix（3）约束条件记)14,...,2,1)((jja为该成品中第j种原料的根数。),(jic为第i种模式所用第j种材料的根数。)(jb为上级成品中余量被当做该级成品中第j种原料的根数。则很显然，所用的该种材料总根数不能超过原来该种材料的总根数加上一级被当做该原料的根数。约束条件为为非负整数)()12,...,2,1(),(),()(ixjjajicix（4）余量求出最优解后，显然第j种原料的余量为,),()()()(jicixjbja)12,...,2,1(j，则总余量b为121)),()()()((jjicixjbja。（三）成品一最大捆数求解:由于求成品一最大捆数的模型和求成品二的最大捆数的模型相同，所以这里就略去了求成品一最大捆数的模型。（记得余量是第二级和第三级之和）5.1.3求解最短长度最大的捆数最多本节主要求解在捆数达到最大的情况下，求解最短长度最大的捆数最多的优化方案。由于最短长度最大的这种模式必然属于成品一的模式，所以我们只需考虑成品一即可。由于要直接用程序找出最短长度最大的那些模式有困难，所以我们人为的从成品一的所有模式中进行观察，找出那些最短长度最长的那些模式。（一）决策变量：记)1(y为采用最短长度最长的那些模式中的第1种模式所生产的捆数，)2(y为采用6上述模式中第2种模式所生产的捆数，依此类推，)(iy为采用上述模式中的第i种模式所生产的捆数。（1）决策目标由于要求的是最短长度最长的那些成品的捆数最多，所以目标函数为)(maxiy（2）约束条件记)(ix为采用非最短长度最长的那些模式中的第i个模式所生产的捆数，),(jib为非最短长度最长的那些模式中的第i个模式所用的第j种原料的根数，),(jic为最短长度最长的那些模式中的第i个模式所用的第j种原料的根数，)8,...,2,1)((jja为该成品中第j种原料的根数，)(jb为上一级成品中余量被当做该级成品中第j种原料的根数，d为上一节中计算出的该成品的最大捆数。则显然约束条件为均为非负整数),(),()()()()(),()(),()(iyixdiyixjbjajiciyjibix5.1.4验证模型的合理性假设所有的原料或根数均被用完，先检验第三种成品，记)(ia为该成品中第i种原料的总根数，)(il为第i种原料的长度，s为该成品中一捆的最少总根数，l为该成品中一捆的最短总长度。则最大捆数必须要满足如下条件，如果满足，则证明合理，否则不合理。))(,)()(min()(maxsialiailix然后检验成品二模型的合理性，假设所有的原料或根数均被用完，记)(ia为该成品中第i种原料的总根数，)(il为第i种原料的长度，s为该成品中一捆的最少总根数，l为该成品中一捆的最短总长度，b为上级成品中的总余量。改变该成品中最后一种原料的总根数)(ia为bia)(则最大捆数必须要满足如下条件，如果满足，则证明合理，否则不合理。))(,)()(min()(maxsialiailix成品一的检验模型同成品二的检验模型，故在这里不再赘言。75.2模型求解5.2.1模式求解将上述模式求解的模型用matlab软件编程进行求解，求解程序见附录1，附录2，附录3，运行结果见表3，表4，表5（其中结果均为前面15种结果）。模式原料1原料2原料3原料4原料5原料6原料7原料8100011800020001261003000127000400013420050001350106000135100700013600080001423009000143110100001432001100014400112000144010130001441001400015040015000151210表3成品一的模式以下模式略（共90849种模式）模式12345678910111213141000000000003402000000000004213000000000004304000000000005025000000000