一维下料优化模型的应用及经济性分析.doc

一维下料优化模型的应用及经济性分析陈 越中核华兴建设有限公司辽宁红沿河项目部摘要：“下料问题”是把相同形状的一些原材料分割加工成若干个不同规格大小的零件的问题，此类问题在工程技术和工业生产中有着重要和广泛的意义。本文首先以材料最省为原则建立下料模型，并结合lingo编制出下料软件，可生成供使用的待加工零件最优组合的报表。最后浅析此模型及软件投入使用后的经济效益并进一步拓展讨论了多维下料问题的解决。关键词：线性规划 下料问题 组合 零件加工引言成本控制是企业赖以生存和发展的基础，而相关数据表明，原材料成本占总生产成本的百分比可以高达45%60%，因此最大限度地节约材料，提高材料的利用率，是实际生产中的一个指导原则，能给企业带来巨大的经济效益。一维下料优化问题是讨论从一种规格的材料中，分切出各种不同长度的坯料，以使材料的利用率最高。下料方案的优劣直接影响原材料的利用率，进而影响原材料成本。这类优化问题在型材、棒材、管材、金属结构材料、建筑材料，甚至布料下料中广泛存在。目前，国内外关于这方面的研究十分活跃，并涌现出了不少近似算法，如Gilmore与Gomory用线性规划建立的一刀切问题的数学模型【1,2】以及Sarker提出的动态规划方法【3】等。本文通过改进目前常用的两种求解方法(常规整数线性规划方法和遗传算法)，结合lingo9.0线性规划软件，编制出一种贴合核电站钢筋下料实际情况且易于操作的下料软件，并对其进行算例对比，提出一种更为合理经济的下料方案，基本杜绝了原料浪费现象。正文1背景目前，红沿河核电站引进的钢筋原材料有光圆钢筋HPB235级（下文统称I级钢）、带肋钢筋HRB335级（下文统称II级钢）、HRB400级（下文统称III级钢），表1对各型号的钢筋不同直径及原料长度做了统计。表1 钢筋原料直径与长度统计表钢筋型号直径（mm）原料长度（mm）I级钢61200081200010120001212000141200016120002012000II级钢1212000141200016120001812000201200022120002512000III级钢1212000141200016120002012000251200032120004012000 实际上，钢筋车间操作人员收到待加工的钢筋料单，会将料单上同种规格和直径的钢筋进行简单组合后使用原材料切割，这种简单组合造成了大量的余料甚至废料。如何找出一种最优的组合方式使得耗材最少以提高材料利用率，本文将采用一种启发式多级序列线性优化模型并求解出最优方案。2问题分析一维下料问题是组合优化中的一个经典问题，如果要得到理论上的严格全局最优下料方案。就要求所有可行下料方式都进入线性规划模型的系数矩阵，从计算的复杂性理论上看，这属于NPC (NP完全)难问题。因此，我们放弃常规的整数规划解法，而在以优化选取下料方式的前提下，寻找建立下料方案的模型。本文要求一个好的下料方案在生产能力允许的条件下要满足两个要求：首先，应该使原材料的利用率最大，即用最少数量的原材料；其次要求所采用的不同下料方式尽可能少。这样，我们可以考虑分层建模：第一阶段，先仅考虑单一原材料的模型，以耗材最少为原则搜寻最优的下料方式；第二阶段解决具体问题时，再进一步考虑将多种原材料并行搜索。改进方案以满足要求。通过计算机编程计算得到我们所需要的最优下料方案。由于原料的种类并不单一，有20种之多，每种原料待加工零件也未确定，导致计算量很大，所以在建立优化模型的基础上，我们需要找到比较合适的算法来解决这类实际问题。作者力图建立一种实用的模型，并提出一种新的优化思想方法启发式多层次逐层优化方法，并结合贪心算法解决此问题。3模型的建立3.1基本假设(1) 假设每个切割点处产生的损耗为5mm，且视为废料不可忽略。(2) 假设车间加工成品速度能够满足交货时间，即忽略交货时间的限制。3.2符号说明符号意义单位原材料的长度第种零件的需求量个第种零件的宽度,且第种零件的长度，且一种下料方式中，切割第种零件的数量个下料方式数种下料方式的使用次数次3.3启发式多级序列线性优化模型该模型的基本思想是在每级求解时，尽可能多的重复使用最优的一种方法进行下料，直到所涉及到的某种零件需求加工完；然后对剩余的零件重复上步的操作，直到所有剩余的零件数目均减小至零为止。原问题的最优解就是各个序列优化问题所求得的最优下料方式的总和。给定种长度的零件，所需的数量分别为，已知原材料长度为。设在最优一种下料方式中，第件零件的加工数量为，由此建立如下模型：优化参数变量：均为非负整数，且不同长度的零件种类有限(即该问题中要求的变量个数有限)，可用分枝定界法来求解。启发式多级序列线性优化计算方法将上述当前最优下料方式计算求解作为多级序列线性优化计算的子程序，在每级求解中重复调用。完整的求解步骤如下：步骤1 将待加工零件中待切割的最长零件作为第一搜索顺序，调用当前最优下料计算子程序，求解得到优化值组成的，此时零件之间种类和数量的组合作为第一级下料方式。步骤2 计算此种下料方式的重复次数，即此种下料方式所需原材料的根数。其中。步骤3 计算去掉根后，余下的每种待切割的零件个数置为： 。步骤4 将作为新一级优化计算的给定值，如果所有的都已减小至零，则优化计算结束；否则转至步骤l，重新用当前最优下料方式计算子程序，求得新一级的下料方式和重复次数。步骤5 各级最优下料方式及其重复次数的集合即为多级序列线性优化的最终结果。一维问题算法流程图4模型求解在确定了模型和算法后，作者使用Lingo9.0线性规划软件编程求解出任意多种原材料加工零件的最优组合方案，为使操作界面窗口化以及使用过程简便易懂，作者将这段程序嵌套在java的运行环境中。以红沿河核电站HDY-9NEF193料单作为一个算例进行操作说明。（所有操作均在安装了java以及Lingo9.0环境下进行）第一步：输入数据。在excel表格中输入料单的基本信息，包括规格、下料长度、数量。图1为HDY-9NEF193料单数据截图。图1其中规格一列316表示III级钢直径16mm的钢筋，108表示I级钢直径8mm的钢筋，以此类推。第二步：处理数据打开红沿河下料优化软件，出现如图2窗口，在光标处依次输入file，run，parse，reset，exit。命令说明：file ：当前需要计算的料单，为料单数据文件所在目录。run：创建当前料单的lingo模型及相关元数据信息文件。parse：分析lingo模型的优化结果，生成Report.txt报表。reset：清空当前记忆的料单。exit：退出。图2 料单信息载入第三步：打开Report.txt报表处理结果对HDY-9NEF193料单处理生成的报表如图3、4（由于篇幅原因只随即挑选两种规格的钢筋进行示意）图3三级钢直径16的结果报表图4三级钢直径32的结果报表如图3第三行表示一根下料长度为2340mm的零件和两根4560mm的零件组合重复5次，每根原料剩余525mm料头。第四行表示一根下料长度为8450mm的零件和一根3350mm的零件组合重复59次，每根原料剩余190mm料头。依次类推。将图3其转换成清晰易懂的最优组合表格如下：表2 三级钢直径16的最优组合切割方案重复次数组合方式余料（mm）52340mm（1根）4560mm（2根）525598450mm（1根）3350mm（1根）19051170mm（1根）8450mm（1根）2340mm（1根）2571170mm（3根）8450mm（1根）20124800mm（1根）7000mm（1根）19024800mm（2根）2340mm（1根）4572050mm（1根）1170mm（1根）8450mm（1根）31582000mm（1根）4800mm（2根）385实际利用率III级钢直径16mm的钢筋为94.36%，III级钢直径32mm的钢筋为97.61%。使用该软件时并不局限于一份料单中的待加工零件之间组合，对于交货时间相近的几份甚至几十份亦可交叉组合，并且会因为组合方式增多效果更好。5模型的评价及经济性分析从本文针对红沿河项目抽取的料单的解决可看出，针对本问题将多目标整数规划模型分解为多层整数线性规划模型和启发式多层次逐层优化方法是十分有效的。且不用担忧随着问题规模的增加，计算量和存储空间的会产生组合爆炸，特别适用于优化目标和约束条件复杂的问题。它在大大降低计算复杂度的同时保持了很高的材料利用率和尚可接受的下料方式数。并且简化后的模型与算法在计算结果稳定性方面均已完美的结果证明，此模型用于任意料单均可得到最高的利用率。 毋庸置疑，该模型投入使用后会给企业节省大笔原材料，其间直接带来的经济效益不可胜数。但生产车间需加派人手，设置专人负责使用该软件生成组合料方案，并且在装车时也增加了难度。但这部分支出远不及节约成本带来的效益，因此具有可行性。6模型的扩展不仅仅是一维下料亟需优化，工业生产中也存在许多二维乃至三维下料浪费的现象。对于二维下料问题，下料方式要满足零件长，宽方向上的套裁，所以远比一维下料复杂且数量大得多。因此，我们希望通过降维启发式方法即通过形成“板条”而把二维下料问题降为一维下料的方法来解决。在此称一维下料的原材料为“条材”，而二维下料的原材料为“板材”。板材与条材的区别在于：条材加工时只考虑长度而板材要同时考虑长、宽。如果能把零件成组看待，板条就是这样一种零件组：其在一个方向上的长度等于或近似于原材料的长(或宽)方向的长度；然后在另一个方向即原材料的宽(或长)方向进行裁剪这样，二维下料问题因“板条”的引入便降为一维下料问题。零件的宽度决定板条的种类，当种类确定后，则要在不超过宽(或长)度的前提下在原材料上进行板条的布局(有若干种)。而布局方式一旦确定，就只剩下每个板条内部零件组的组合问题，这时就可利用一维中求解下料问题的启发式多级序列线性优化的方法来解决。其建模的具体过程类似于一维的分层建模思想。由于篇幅原因，此处不做深入讨论。致谢本文的撰写是在红沿河项目部核岛一队岳雷先队长的循循善诱和悉心指导下完成的。对于这次论文的顺利完成，首先要感谢岳队在论文撰写期间的悉心指导，关心和帮助。另外，贾春荣书记和技术队长陈湘也对论文的相关内容给予了很大的帮助和指导，对这期间所遇到的困难及应注意的问题也给予了关心和建议。岳队和陈队严谨、务实和忘我的工作作风，以及热情和蔼、平易近人的待人作风，给我留下了深刻的印象，并深深的影响着我，使我受益匪浅，在此谨致以最诚挚的谢意。软件编程的完成要特别感谢我大学期间的建模队友潘嘉程。在模型的设计和制作及论文的完成等方面都得到潘嘉程的指导，在此表示真挚的感谢。同时，在红沿河有关钢筋数据方面的提供得到钢筋车间友善的帮助，在此一并表示感谢。最后还要感谢好友朱宏伟、谢警校、胡文杰、王绎咏、李恩平等人的帮助，在设计过程中，和他们一起讨论，共同分析，解决了很多技术上的问题。参考文献1 GILMORE.P.C,GOMORY R E.A linear programming approach to the cutting stock problem (Part I)J.Oper Res,1961,9:849-859.2 GILMORE.P.C,GOMORY R E.A linear programming approach to the cutting stock problem (Part II)J.Oper Res,1963,11:863-887.3 SARKER.B.R, An optimum solution f