钢构件的排料问题

第八届华中地区大学生数学建模邀请赛承诺书我们仔细阅读了第八届华中地区大学生数学建模邀请赛的竞赛细则。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们的参赛报名号为：105141501参赛队员(签名)：队员1：队员2：队员3：武汉工业与应用数学学会第八届华中地区大学生数学建模邀请赛组委会第八届华中地区大学生数学建模邀请赛编号专用页选择的题号：A题参赛的编号：105141501（以下内容参赛队伍不需要填写）竞赛评阅编号：1第八届华中地区大学生数学建模邀请赛题目：钢构件的排料问题摘要排样问题普遍存在于工业生产的许多领域，一个好的排样方案可以有效提高原材料利用率，降低生产成本，直接给企业带来经济效益。由此本文根据单板规则零件、单板不规则零件和双板规则零件的特点提出了基于矩形包络算法与启发式排样算法的一种优化排样布局的数学模型。针对问题一，本文首先制定了一套含有定序规则、定位规则、排放规则的排样布局规则，使得在给定的矩形板材上，尽可能多地排放所需的矩形件，然后根据这一规则提出的启发式排样算法，得出了零件的摆放方式，并且求出其板材的利用率为：11()()maxmaxkkiiiiiiilwnsnfLWCLWC=94.6%，较好地解决了在满足“一刀切”等约束条件下的数控下料二维矩形件优化排样问题。针对问题二，本文运用最小矩形包络算法，将不规则图形转化为规则图形。一方面，本文将不规则的凹边形转化为其凸包，然后直接将所有的凸图形进行矩形包络；另一方面，先对不规则图形进行聚合，然后对聚合后的图像进行矩形包络。比较两种情况下，包络矩形产生的废料大小，得出废料较少的最优包络矩形，最后运用启发式排样优化模型对其进行排样，求出其板材的利用率为99.23%，较好的解决了不规则零件排样问题。针对问题三，本文改动问题一中模型的相关参数，将单板规则零件下料的排料优化模型转化为双板规则零件下料的排料优化模型，最后求出矩形零件的摆放方式，求出其板材的利用率为96.413%，较好的解决了双板规则图形的排样问题。最后由于板材剩余面积较大，本文进行了探究实验，增加零件的数量，最后得出两块板材的平均利用率为97.5%。实践证明，增大板材尺寸，有利于提高材料利用率。因此，在生产中如果实际情况允许，尽量将多个任务合并在一起排样，从而增加零件总数，使下料利用率达到理想水平，同时提高生产效率。关键词：排样布局规则；启发式排样算法；最小矩形包络；零件排样2一、问题重述在钢构件制造产品的生产过程中，依照产品零件尺寸从板料中截取大小适当的零件过程称之为排料，也称之为下料。排料是钢构件制造的第一道工序。在这道工序中，不同的排料方案具有不同的材料利用率，而原材料的利用率直接影响产品的成本。对于一个年消耗大量钢材的生产单位，若能够提高原料利用率的1%，那么其节约的钢材成本是可观的。因此，降低废料率提高原材料利用率是钢构件生产企业追求的目标。根据实际情况，板材排料又可分为两种：一是规则形状的零件排料，一是不规则形状的零件排料。规则形状零件是指矩形零件。其描述一般只需用矩形的长和宽。规则形状零件的排料问题的实质是研究如何组合零件摆放问题，使得在整个原料上摆放大量的不同长和宽的零件产生的废料最少、整料和余料的利用率最高。排放时，其零件间的搭接关系的处理相对容易，只需考虑长、宽两个因素（含预留的损耗量）。不规则零件在这里是指多边形零件（一般的意义是指由直线、圆、弧、孔等的组合形），相对矩形零件排料而言，不规则零件的直接排料要复杂得多。另外由于切割工艺的要求，切割只能实行“一刀切”的工艺（在整料或余料中，从一边的某点到另外一边某点的连线一次切割，但可以在切割下来的板料中再次切割）。板材的利用率就是所有零件面积之和与在一刀切工艺后继续切割的那部分板材面积的比值。问题1:对1张板料和若干规则形状零件（板料和零件参数见附件1），如何在板料中摆放零件使其板料的利用率最高。问题2:对1张板料和若干不规则形状零件（板料和零件参数见附件2），如何在板料中摆放零件使其板料的利用率最高。问题3:对2张板料和若干规则形状零件（板料和零件参数见附件3），如何在板料中摆放零件使其板料的利用率最高。二、问题分析2.1问题一的分析为了在给定长度和宽度的板材上，尽可能多地排放所需的矩形件，使得所需的板材尽可能的少，本文拟制订一种矩形件排样规则。由于在数控下料过程中要满足“一刀切”的工艺要求，且为了操作简单易行，速度快且能够融合各种限制条件和具体目标，使得在整个原料上摆放大量的不同长和宽的零件产生的废料最少、整料和余料的利用率最高，故本文拟采用启发式算法排样模型，摆放出不同大小的矩形零件。2.2问题二的分析二维不规则多边形零件的排料问题的复杂性主要是由多边形的不规则几何形状和不同次序组合引起的。由于零件形状不规则、排料过程中旋转方向多样、排列组合复杂、以及计算量非常大，所以本文准备将不规则形状零件排料问题转化为矩形排料问题。为了使不规则形状较易于转化为规则零件，本文欲将凹边形现转化其凸包，在进行求解。3又由于当不规则形状零件的面积和矩形面积相差很大时，会降低板材的利用率，浪费板材，故本文拟采用最小矩形包络法，使得排料结果较优，增加板材利用率。2.3问题三的分析由于本文拟做的启发式算法排样优化模型，简单易行，速度快且能够融合各种限制条件和具体目标等特点，因此在解决双板规则零件的优化时，本文将改动相关的参数，也将采用该算法模型。三、问题假设（1）假设切割板料刀片厚度忽略不计，不会对切割后板料面积产生影响。（2）假设在切割过程中，板料与零件均无磨损边缘。（3）假设切割时造成板料在被切割中产生的的耗损，而导致原料总面积减少。（4）假设板材厚度与零件厚度一样，两者表面能够无缝接触。（5）假设板料不会因为外界环境高温，受潮等产生形变。四、符号说明L：板材的长W：板材的宽k：板材的数量足以排下所有要排的矩形件数in：第i种矩形件的个数il：第i种矩形件的长度iw：第i种矩形件的宽度is：第i种矩形件的面积，且iilwin：第i类待排矩形件的个数C：余料可利用面积f：板材利用率五、模型的建立与求解5.1问题一的建模与求解：单板规则零件下料的排料优化模型根据如何摆放不同大小的矩形零件，使得在整个原料上摆放大量的不同长和宽的零件产生的废料最少、整料和余料的利用率最高，发现其排样算法主要有：4背包算法、数学规划法、启发式算法、模拟退火和遗传算法等。其中，遗传算法、模拟退火算法在数控下料存在“一刀切”的工艺约束，较难应用，而一般的数学规划法，在大规模排样需求下，也因为计算量太大，计算时间太长无法满足实际生产的需要，又由于本文针对的矩形件的数量、种类较多，不适合采用背包算法，而启发式算法简单易行，速度快且能够融合各种限制条件和具体目标，故本文最后提出了如下的启发式算法排样模型。5.1.1优化排样布局规则在矩形件优化排样中，待排矩形零件的排放顺序、矩形件与矩形件之间的排放方式以及矩形件与板材之间的相对排放位置都是十分重要的。本排样算法应用的相应规则如下：（1）定序规则通过比较待排矩形件的某一项或某几项属性(如长度、面积等)来建立定序规则，它对最终排样结果有着重要的影响。本算法采用的是根据待排矩形件面积递减的顺序进行排样，即先排面积大的矩形件。（2）定位规则确定被选待排矩形件在布局空间中的摆放位置。本算法采用的是占角策略，即将待排矩形件摆放在板材的某一角，采用的是先占左下角的定位规则。（3）排放规则矩形件在板材上有沿板材长度方向的横排和竖排、沿板材宽度方向的横排和竖排共4种方式。本算法优先考虑沿宽度方向的横排和竖排的方式，如图1。通过计算排后板材剩余边界距离大小来决定横排或竖排。宽度方向横排宽度方向竖排图1工作排列示意图5.1.2数控下料优化约束条件（1）矩形件之间不能有相互重叠的区域；（2）矩形件不能排出板材之外；（3）已经排好的零件位置保持不变；（4）符合最左下原则，即第一个排放零件应放置在板材的左下角，其余零件则尽量放置在剩余区域的最左最低位置；（5）满足数控裁板下料的“一刀切”的工艺要求。“一刀切”也可称直线贯通问题，是指在矩形板材上切割的每一刀都平行于矩形板材的一组平行边，端点从矩形板材的一组平行边中的一条延伸到另一条，将矩形板材分为两部分。简单地说，“一刀切”约束条件下的每一刀都会把当前正在锯切的板材一刀两段。如图2a为“一刀切”模式，它可以按图中所标记的切割顺序进行“一刀切”加工；而图2b为非“一刀切”模式，它无法用有“一刀切”工艺要求的设备进行加工。5a为一刀切模式b为非一刀切模式图2锯切模式示意图5.1.3数控下料优化过程矩形件排样优化是指在给定长度和宽度的一定数量的板材上，尽可能多地排放所需的矩形件，使得所需的板材尽可能的少。人造板数控下料优化属于矩形件排样优化问题，实际上是一个二维优化布局问题，从数学计算的复杂理论性上说，该类问题属于NP完全问题(NondeterministicPolynomial)，即为非多项式确定问题，计算复杂性很高，只能用有效的近似算法求解。以下是该问题的数学模型。设板材的长为L，宽为W，且LW，板材的数量足以排下所有要排的k种矩形件。第i种矩形件的个数是(1)inik，其长度为(1)ilik，宽度为(1)iwik，面积为(1)isik，且iilw。于是所有要排的矩形件的总数是1kiinn。并把这k种矩形件元素集合记为12,,......,ikRRRRR，称iR为排样元素。设总共有N张板材，余料可利用面积为C，则优化的目标函数是：11()()maxmaxkkiiiiiiilwnsnfNLWCNLWC即如何排料使板材利用率最大。5.1.4数控下料优化过程的基本描述（1）排序与定序将所有待排矩形件按面积is由大到小进行排序并保存。采用按面积定序的规则，即在R中找到一个未用的且面积最大的排样元素放在已知板材的左下角。（2）确定排放方式优先考虑沿板材宽度方向的横排和竖排。设下列四个判别参数：mod,modiiWWablwint,iiWWcdlw可分为三种情况对这四个参数进行判别：1）如果1,1,cd说明矩形件沿板材宽度方向横排竖排均可放下；如果ba，说明沿板材宽度方向纵排工件后，板材剩余边界距离小于横排工件，则6将零件沿板材宽度方向进行纵排，否则，将零件沿板材宽度方向进行横排。2）如果1,1,cd则只能将矩形件沿板材宽度方向进行横排。3）如果c1，d1，则板材不能排放任何工件。排完上述面积最大的矩形件后，板材被划分为三个部分，即已排区域Ri、未排区域1和区域2，如图3、图4所示。这时区域1和区域2被看作新的待排板材。图3横切图4纵切（3）再次扫描排样元素集合R找出未排的面积最大的矩形件，按照最左最低原则在剩余区域重复上述（2）的方法继续排样，同时考虑横切和竖切，又会相应地产生新的未排区域，并判断剩余区域是否排完；如果未排完，则继续排样；否则，更新矩形件信息，同时将剩余区域作为一定尺寸的板材重新布料，直到任何工件都不能填充为止，即当区域1和区域2的面积小于矩形件的最小面积时为止。（4）按照上述算法，利用MATLAB软件输出排样结果。5.1.5排样算例及分析以问题所给的零件进行下料，应用上述优化算法进行排样。表1为生产所需下料的任务数据列表，人造板板料尺寸为2350×900mm，表中编号代表矩形件的不同种类。表19种排样矩形件列表(单位：mm)编号长宽数量面积135030021050002350200270000350024