钢构件的排料问题.doc

第八届华中地区大学生数学建模邀请赛承 诺 书我们仔细阅读了第八届华中地区大学生数学建模邀请赛的竞赛细则。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们的参赛报名号为： 105141501 参赛队员 (签名) ：队员1： 队员2： 队员3： 武汉工业与应用数学学会第八届华中地区大学生数学建模邀请赛组委会17第八届华中地区大学生数学建模邀请赛编 号 专 用 页选择的题号： A题 参赛的编号： 105141501 （以下内容参赛队伍不需要填写） 竞赛评阅编号： 第八届华中地区大学生数学建模邀请赛题目： 钢构件的排料问题 摘 要排样问题普遍存在于工业生产的许多领域，一个好的排样方案可以有效提高原材料利用率，降低生产成本，直接给企业带来经济效益。由此本文根据单板规则零件、单板不规则零件和双板规则零件的特点提出了基于矩形包络算法与启发式排样算法的一种优化排样布局的数学模型。针对问题一，本文首先制定了一套含有定序规则、定位规则、排放规则的排样布局规则，使得在给定的矩形板材上，尽可能多地排放所需的矩形件，然后根据这一规则提出的启发式排样算法，得出了零件的摆放方式，并且求出其板材的利用率为：=94.6%，较好地解决了在满足“一刀切”等约束条件下的数控下料二维矩形件优化排样问题。针对问题二，本文运用最小矩形包络算法，将不规则图形转化为规则图形。一方面，本文将不规则的凹边形转化为其凸包，然后直接将所有的凸图形进行矩形包络；另一方面，先对不规则图形进行聚合，然后对聚合后的图像进行矩形包络。比较两种情况下，包络矩形产生的废料大小，得出废料较少的最优包络矩形，最后运用启发式排样优化模型对其进行排样，求出其板材的利用率为99.23%，较好的解决了不规则零件排样问题。针对问题三， 本文改动问题一中模型的相关参数，将单板规则零件下料的排料优化模型转化为双板规则零件下料的排料优化模型，最后求出矩形零件的摆放方式，求出其板材的利用率为96.413%，较好的解决了双板规则图形的排样问题。最后由于板材剩余面积较大，本文进行了探究实验，增加零件的数量，最后得出两块板材的平均利用率为97.5%。实践证明，增大板材尺寸，有利于提高材料利用率。因此，在生产中如果实际情况允许，尽量将多个任务合并在一起排样，从而增加零件总数，使下料利用率达到理想水平，同时提高生产效率。关键词：排样布局规则；启发式排样算法；最小矩形包络；零件排样一、 问题重述在钢构件制造产品的生产过程中，依照产品零件尺寸从板料中截取大小适当的零件过程称之为排料，也称之为下料。排料是钢构件制造的第一道工序。在这道工序中，不同的排料方案具有不同的材料利用率，而原材料的利用率直接影响产品的成本。对于一个年消耗大量钢材的生产单位，若能够提高原料利用率的1%，那么其节约的钢材成本是可观的。因此，降低废料率提高原材料利用率是钢构件生产企业追求的目标。根据实际情况，板材排料又可分为两种：一是规则形状的零件排料，一是不规则形状的零件排料。规则形状零件是指矩形零件。其描述一般只需用矩形的长和宽。规则形状零件的排料问题的实质是研究如何组合零件摆放问题，使得在整个原料上摆放大量的不同长和宽的零件产生的废料最少、整料和余料的利用率最高。排放时，其零件间的搭接关系的处理相对容易，只需考虑长、宽两个因素（含预留的损耗量）。不规则零件在这里是指多边形零件（一般的意义是指由直线、圆、弧、孔等的组合形），相对矩形零件排料而言，不规则零件的直接排料要复杂得多。另外由于切割工艺的要求，切割只能实行“一刀切”的工艺（在整料或余料中，从一边的某点到另外一边某点的连线一次切割，但可以在切割下来的板料中再次切割）。板材的利用率就是所有零件面积之和与在一刀切工艺后继续切割的那部分板材面积的比值。问题1: 对1张板料和若干规则形状零件（板料和零件参数见附件1），如何在板料中摆放零件使其板料的利用率最高。问题2: 对1张板料和若干不规则形状零件（板料和零件参数见附件2），如何在板料中摆放零件使其板料的利用率最高。问题3: 对2张板料和若干规则形状零件（板料和零件参数见附件3），如何在板料中摆放零件使其板料的利用率最高。二、 问题分析2.1问题一的分析为了在给定长度和宽度的板材上，尽可能多地排放所需的矩形件，使得所需的板材尽可能的少，本文拟制订一种矩形件排样规则。由于在数控下料过程中要满足“一刀切”的工艺要求，且为了操作简单易行，速度快且能够融合各种限制条件和具体目标，使得在整个原料上摆放大量的不同长和宽的零件产生的废料最少、整料和余料的利用率最高，故本文拟采用启发式算法排样模型，摆放出不同大小的矩形零件。2.2问题二的分析二维不规则多边形零件的排料问题的复杂性主要是由多边形的不规则几何形状和不同次序组合引起的。由于零件形状不规则、排料过程中旋转方向多样、排列组合复杂、以及计算量非常大，所以本文准备将不规则形状零件排料问题转化为矩形排料问题。为了使不规则形状较易于转化为规则零件，本文欲将凹边形现转化其凸包，在进行求解。又由于当不规则形状零件的面积和矩形面积相差很大时，会降低板材的利用率，浪费板材，故本文拟采用最小矩形包络法，使得排料结果较优，增加板材利用率。 2.3问题三的分析由于本文拟做的启发式算法排样优化模型，简单易行，速度快且能够融合各种限制条件和具体目标等特点，因此在解决双板规则零件的优化时，本文将改动相关的参数，也将采用该算法模型。三、 问题假设（1）假设切割板料刀片厚度忽略不计，不会对切割后板料面积产生影响。（2）假设在切割过程中，板料与零件均无磨损边缘。（3）假设切割时造成板料在被切割中产生的的耗损，而导致原料总面积减少。（4）假设板材厚度与零件厚度一样，两者表面能够无缝接触。（5）假设板料不会因为外界环境高温，受潮等产生形变。四、 符号说明：板材的长：板材的宽：板材的数量足以排下所有要排的矩形件数：第i种矩形件的个数：第i种矩形件的长度：第i种矩形件的宽度：第i种矩形件的面积，且：第类待排矩形件的个数：余料可利用面积：板材利用率五、 模型的建立与求解5.1 问题一的建模与求解：单板规则零件下料的排料优化模型根据如何摆放不同大小的矩形零件，使得在整个原料上摆放大量的不同长和宽的零件产生的废料最少、整料和余料的利用率最高，发现其排样算法主要有：背包算法、数学规划法、启发式算法、模拟退火和遗传算法等。其中，遗传算法、模拟退火算法在数控下料存在“一刀切”的工艺约束，较难应用，而一般的数学规划法，在大规模排样需求下，也因为计算量太大，计算时间太长无法满足实际生产的需要，又由于本文针对的矩形件的数量、种类较多，不适合采用背包算法，而启发式算法简单易行，速度快且能够融合各种限制条件和具体目标，故本文最后提出了如下的启发式算法排样模型。5.1.1 优化排样布局规则在矩形件优化排样中，待排矩形零件的排放顺序、矩形件与矩形件之间的排放方式以及矩形件与板材之间的相对排放位置都是十分重要的。本排样算法应用的相应规则如下：（1）定序规则通过比较待排矩形件的某一项或某几项属性(如长度、面积等)来建立定序规则，它对最终排样结果有着重要的影响。本算法采用的是根据待排矩形件面积递减的顺序进行排样，即先排面积大的矩形件。（2）定位规则确定被选待排矩形件在布局空间中的摆放位置。本算法采用的是占角策略，即将待排矩形件摆放在板材的某一角，采用的是先占左下角的定位规则。（3）排放规则矩形件在板材上有沿板材长度方向的横排和竖排、沿板材宽度方向的横排和竖排共4种方式。本算法优先考虑沿宽度方向的横排和竖排的方式，如图1。通过计算排后板材剩余边界距离大小来决定横排或竖排。 宽度方向横排 宽度方向竖排图1 工作排列示意图5.1.2数控下料优化约束条件（1）矩形件之间不能有相互重叠的区域；（2）矩形件不能排出板材之外；（3）已经排好的零件位置保持不变；（4）符合最左下原则，即第一个排放零件应放置在板材的左下角，其余零件则尽量放置在剩余区域的最左最低位置；（5）满足数控裁板下料的“一刀切”的工艺要求。“一刀切”也可称直线贯通问题，是指在矩形板材上切割的每一刀都平行于矩形板材的一组平行边，端点从矩形板材的一组平行边中的一条延伸到另一条，将矩形板材分为两部分。简单地说，“一刀切”约束条件下的每一刀都会把当前正在锯切的板材一刀两段。如图2a为“一刀切”模式，它可以按图中所标记的切割顺序进行“一刀切”加工；而图2b为非“一刀切”模式，它无法用有“一刀切”工艺要求的设备进行加工。 a为一刀切模式 b为非一刀切模式图2 锯切模式示意图5.1.3数控下料优化过程矩形件排样优化是指在给定长度和宽度的一定数量的板材上，尽可能多地排放所需的矩形件，使得所需的板材尽可能的少。人造板数控下料优化属于矩形件排样优化问题，实际上是一个二维优化布局问题，从数学计算的复杂理论性上说，该类问题属于NP完全问题(Nondeterministic Polynomial )，即为非多项式确定问题，计算复杂性很高，只能用有效的近似算法求解。以下是该问题的数学模型。设板材的长为L，宽为W，且LW，板材的数量足以排下所有要排的k种矩形件。第i种矩形件的个数是，其长度为，宽度为，面积为，且 。于是所有要排的矩形件的总数是。并把这k种矩形件元素集合记为 ，称 为排样元素。设总共有N张板材，余料可利用面积为C，则优化的目标函数是：即如何排料使板材利用率最大。5.1.4数控下料优化过程的基本描述（1）排序与定序将所有待排矩形件按面积 由大到小进行排序并保存。采用按面积定序的规则，即在R中找到一个未用的且面积最大的排样元素放在已知板材的左下角。（2）确定排放方式优先考虑沿板材宽度方向的横排和竖排。设下列四个判别参数： 可分为三种情况对这四个参数进行判别：1）如果说明矩形件沿板材宽度方向横排竖排均可放下；如果，说明沿板材宽度方向纵排工件后，板材剩余边界距离小于横排工件，则将零件沿板材宽度方向进行纵排，否则，将零件沿板材宽度方向进行横排。2）如果则只能将矩形件沿板材宽度方向进行横排。3）如果c1，则板材不能排放任何工件。排完上述面积最大的矩形件后，板材被划分为三个部分，即已排区域Ri、未排区域1和区域2，如图3、图4所示。这时区域1和区域2被看作新的待排板材。 图3 横切 图4 纵切（3）再次扫描排样元素集合R找出未排的面积最大的矩形件，按照最左最低原则在剩余区域重复上述（2）的方法继续排样，同时考虑横切和竖切，又会相应地产生新的未排区域，并判断剩余区域是否排完；如果未排完，则继续排样；否则，更新矩形件信息，同时将剩余区域作为一定尺寸的板材重新布料，直到任何工件都不能填充为止，即当区域1和区域2的面积小于矩形件的最小面积时为止。（4）按照上述算法，利用MATLAB软件输出排样结果。5.1.5 排样算例及分析以问题所给的零件进行下料，应用上述优化算法进行排样。表1为生产所需下料的任务数据列表，人造板板料尺寸为2350900mm，表中编号代表矩形件的不同种类。表1 9种排样矩形件列表 (单位：mm)编号长宽数量面积135030021050002350200270000350024021200004500210210500055003502175000630025027500072502002500008500400220000095002002100000应用上述算法对表1元素进行排样，共需一张人造板材，排样结果如下图所示：图5 表1排样结果算法结果分析：通过计算，板材的利用率=94.6%，考虑到板材剩余废料面积较小，即不可利用面积较小，使得板材的平均利用率与理论值较接近。实践证明，参与排样的矩形件种数、板材尺寸对材料的利用率影响很大。零件种数越多，材料利用率越高。另外，增大板材尺寸，也有利于提高材料利用率。模型结论本文提出的启发式排样算法较好地解决了人造板“一刀切”数控下料的二维矩形件优化排样问题，应用在数控裁板下料中能够获得较高的板材利用率，可为家具制造企业节约成本，增加效益。其排样思想对其他行业的排料问题也具有一定的指导意义。5.2单板不规则零件下料的排样优化模型二维不规则多边形零件的排料问题的复杂性主要是由多边形的不规则几何形状和不同次序组合引起的。由于零件形状不规则、排料过程中旋转方向多样、排列组合复杂、以及计算量非常大，所以将不规则形状零件排料问题转化为矩形排料问题，可以有效的求解不规则形状零件排料问题。但是当不规则形状零件的面积和矩形面积相差很大时，会降低板材的利用率，浪费板材，故本文采用最小矩形包络法，使得排料结果更优，增加板材利用率。 5.2.1排料样品分析为了确保排料布局的合理性，满足工艺上的一刀切要求，本文对于不规则多边形即凸五边形、凹六边形（如图6）采用组合规则和邻接规则来合成矩形块。即采用矩形包络法将这些不规则形排料问题转化成比较简单、算法成熟的矩形件排料问题来实现。这样做还可减少废料碎片、降低算法复杂度、提高板材利用率。 图6 待摆放的零件类型5.2.2最小包络矩形的求取求取零件的最小包络矩形是排料算法的要求。所谓最小包络矩形就是能够包含零件的所有矩形中面积最小者。因为只有当零件的包络矩形与零件的外轮廓多边形中的一条边平行或重合时，此包络矩形才有可能是最小包围络形。而最小包络矩形的确定将会影响到板材的利用率。据此,本文得到了求零件最小包络矩形的方法，其算法如下：(1)判断不规则图形的凹凸性首先，按逆时针对多边形顶点进行编号。然后,将待判别的点前后相邻点进行连接构成一个三角形S，则三角形的面积表示为：，如果，则i点为凸顶点，如果，则i点为凹顶点;如果 ,则i点与i-1与i+1三点共线。(2)求凹多边形的凸包判断出凹点以后将该凹点去掉，并将该点前后相邻的点进行连接，重新进行顶点编号，继续判断，直至多边形中不存在凹点。这样就会将凹多边形转化为它的凸包，而凹多边形和它凸包的最小包络矩形是相同的。图7、8表示凹多边形和它的凸包有着相同的最小包络矩形。 图7 凹六边形包络 图8 凹六边形凸包的包络(3)最小包络矩形的求解经过凹凸性判别后，得到一个凸多边形。设该凸多边形有n个顶点n-1条边。首先计算出第i条边与X坐标轴的夹角，然后以第i个顶点为中心，对多边形进行旋转，使第i条边与X轴平行，则第i个包络矩形的底边与旋转后的第i条边重合。多边形旋转后更新了所有的顶点坐标，更新方式按下式进行，然后在所有的已更新坐标值的顶点中搜寻最大和最小的X值和Y值。计算包络矩形的面积：同时记录下矩形的长边和短边的尺寸，依次循环上述步骤直到n-1个包络矩形全部求出，再逐个比较面积，最小的就是该多边形的最小包络矩形。但是这样无法保证单个板件的包络矩形有较为理想的利用率。因此我们提出了一种基于单件包络矩形面积利用率的处理方案。首先，设置一判定阀值ratio。然后，分别计算每个板件包络矩形的板材利用率：判断若ratioratio i则表明该板件包络矩形的板材利用率较低,存在较大的空白区域。这就需要对已经求出的包络矩形进行再处理。处理的方法是将面积小于包络矩形i的其他包络矩形按面积由大到小进行排列,依次填入第i个包络矩形,以获得较高的板材利用率。对零件外轮廓多边形进行上述算法操作,分别求得与多边形平行或重合的最小包络矩形,找出其中的最小者即为零件最小包络矩形,如下图所示： 图9 五边形的最小包络图 图10六边形的最小包络图此后,在排料时还需恢复零件原形。(4)聚合矩形的求取为了提高板材利用率,需要对零件进行一定程度的聚合,然后求取聚合后零件的最小包络矩形,称之为聚合矩形。零件的聚合就是使零件相互接触,但不重叠,以达到包络矩形的面积最小。在排料过程中,由于零件可以任意方向旋转,两个零件的聚合问题就显得尤为复杂,两个相同的零件进行聚合,只有当两个零件相差180o时,才能产生最小包络矩形,因此,在零件聚合过程中,可以只考虑相差180o时的情况。图11、12表示了零件聚合结构,其聚合过程如下:1)求零件的最小包络矩形;2)将原零件复制一个,翻转180o,按其最小包络矩形移到零件的左上角;3)将原零件的总长度从左到右按一定精度等分,将复制件依次移动到每个位置后,每次移动后,均求一次最小包络矩形,记录下该矩形的面积。4)将复制件沿原零件的上、下、左、右四个方向分别与原零件进行组合试验,最后面积最小的矩形即为零件聚合体的最小包络矩形,记下此时的位置和碰撞距离值。如果聚合后的聚合矩形的面积小于两个零件的最小包络矩形面积之和,则聚合成功;反之则自动放弃聚合。对于聚合成功的零件图形都可以提高其局部的材料利用率。聚合矩形算法结果：对于凹六边形来说，本文利用上述算法进行聚合（组合），聚合后将凹边形转变为凸边形，最后对其进行最小矩形包络，如图11所示，使得空白面积最小，利用率最高； 图11 组合六边形的包络图但对于五边形来说，利用上述算法，本文得出了两组矩形包络图，且他们的空白部分的面积相等，如图12、13所示，由图我们可以发现，当对包络矩形恢复零件原形时，图12所需要的切割次数较多，且不能实行一刀切，导致成本增加，所以本文采用第二种聚合方法。 图12 组合五边形的包络图（1） 图13组合五边形的包络图（2）模型结论:通过以上的两种包络发现，单一的对多边形进行包络图形中，空白部分的面积的两倍要比组合包络图形中空白部分的面积要大，所以说，对于本问题中所给的零件，本文采用聚合矩形包络使得利用率更大。5.2.3不规则件排样求解根据问题中所给的不规则零件，本文进行了上述的最小包络矩形近似处理，将二维不规则图形排样转化为规则的矩形排样，得到了下表的包络矩形数据，以这些矩形零件进行下料，应用上述启发式优化算法进行排样。表2为近似替代后生产所需下料的任务数据列表，人造板板料尺寸为23801630mm，表中编号代表包络矩形件的不同种类。表2 两种零件近似包络矩形数据列表 (单位：mm)零件处理后编号长宽数量面积组合五边形矩形包络16163997245784组合六边形矩形包络26004007240000将上表的包络矩形零件运用模型一中的矩形件排样的算法，得到了二维不规则图形的排样。下图给出了一般不规则构件排样效果图.图14 不规则构件排样效果图算法结果分析：通过计算，得出材料利用率为：=99.23%，排样效果比较理想。构件的排样系统分别分析了矩形构件和不规则构件排样的特点,将最小矩形包络算法与启发式排样算法相结合。实现了矩形构件和不规则构件的排样优化,取得了较为理想的排样效果。5.3 问题三的建模与求解5.3.1双板规则零件的排样优化模型由于本文给出的启发式算法排样优化模型，简单易行，速度快且能够融合各种限制条件和具体目标，因此在解决双板规则零件的优化时，本问题也采用该算法模型，只是相关的参数不同。以问题所给的零件进行下料，应用启发式优化算法进行排样。表3为生产所需下料的任务数据列表，人造板板料尺寸为45501630mm，表中编号代表矩形件的不同种类。表3 9种排样矩形件列表 (单位：mm)编号长宽数量面积135030041050002350200070000350024051200004500210610500055003506175000630025047500072502002500008500400220000095002004100000由于本问题所给的板材数量是2，而生产的零件所需要的板材数量一块足以，根据本文模型的特点，剩余的可以利用的板材面积在分母中都减掉了，故只考虑一块板材中的排样情况，应用启发式优化排样算法对表3元素进行排样，排样结果如下图所示：图15 表3排样结果算法结果分析：通过计算，板材的利用率=96.412%，利用率较高，较好的解决了双板规则图形的排样问题。5.3.2 模型探究考虑到板材剩余面积较大，可再次使用，所以本文尝试优先考虑增加面积较大的零件数量的原则，看能否提高板材利用率；探究发现：增加零件总数，能够使下料利用率达到理想水平，提高了生产效率，探究最终得到零件的总数如下表4所示：表4 9种排样矩形件列表 (单位：mm)编号长宽数量面积135030014105000235020011700003500240151200004500210161050005500350161750006300250157500072502001550000850040018200000950020016100000根据上表的零件数目，运用启发式优化排样模型，最终得到排样结果如下图所示：图16 板料1的排样示意图图17 板料2的排样示意图探究结果：通过计算，本文得出第一快板材的利用率为98.2%，第二块板材的利用率为：96.8%，最后得出两块板的平均利用率为97.5%。故本文推出增大板材尺寸，有利于提高材料利用率。因此，在生产中如果实际情况允许，尽量将多个任务合并在一起排样，从而增加零件总数，使下料利用率达到理想水平，同时提高生产效率。六、 模型评价与应用6.1模型优点（1）本文提出的启发式排样算法较好地解决了人造板“一刀切”数控下料的二维矩形件优化排样问题，应用在数控板材下料中能够获得较高的板材利用率，可为板材制造企业节约成本，增加效益。其排样思想可以广泛的应用在金属制品业、木材制品业、家具制造业等其他行业中，对于工业生产具有重要的经济价值。（2）本文在解决问题二的二维不规则零件的自动排料问题时，设计了凸包和合成多边形的图形学算法，将矩形法、启发式算法相结合来解决二维不规则零件的排料。模型特色在于它深入研究了不同切割方式的特点，找出了若干优化准则，运用这些准则找到很好的切割方案，大大提高了计算效率，克服了传统排料计算时间长、编码过于复杂的缺点，显著提高了材料利用率和生产效率，提高了运算速度。从而提高生产利用率，具有很高的实用性和有效性。而且可以将之扩大应用于多个板料的下料问题。6.2不足之处本文在解决问题二中凹六边形下料时，虽然摆放零件使其板料的利用率较高，但在凹处不符合一刀切的工艺要求，而且启发式算法缺乏统一、完整的理论体系，求出的解只是问题的近似最优解，与最优解有一定差距。对于这个问题，还有待继续研究。6.3 模型的应用及推广目前，中小家具制造企业板材排料基本上采用手工试算或凭经验，板材利用率不高，工作效率低。特别是在大批量生产时，手工试算排料几乎不可能。所以在优化下料时结合数控操作，可以大大提高生产率，增加经济效益。在工程实践中，优化排样的应用范围非常广泛：服装制造时的面料分割；家具制造中的人造板分割；机械制造业的金属型材、板材、管材的分割；建筑行业玻璃、装饰材料的分割等。七、 参考文献1 刘嘉敏，张胜男，黄有群等，二维不规则形状自动排料算法的研究与实现N，计算机辅助设计与图形学学报，2007-7-12(7)。2 彭文利，陈淑茹，张定华等，优化排料算法的研究现状与趋势J，模具工业，2006，32（8）：16-17。3 王华昌, 陶献伟, 李志刚等，一种矩形件优化排样综合算法，华中科技大学学报(自然科学版), 2003,31(6): 9-12。4 张英杰，二维不规则零件自动排料的优化算法J，机械设计与研究，2009（10）：70-80。 5 贾志欣，排样问题的研究现状与趋势，计算机辅助设计与图形学学报, 2004, 16(7): 890-897。6 崔耀东，矩形毛坯下料排样的一种优化算法J，机械工程师, 2003,(4): 32-34。7 计华，一种基于四叉树结构的排料算法J, Computer Engineering，2003，9。8 陶献伟，王华昌, 李志刚等，基于填充算法的矩形件排样求解J，中国机械工程, 2003, 14(13):1104-1108。 9 李满江，孟祥旭，王志强等，矩形件和任意多边形排样问题的算法及应用J，贵州工业大学学报（自然科学版），2002,(31):126-130。10 曾凤华，剩余矩形匹配算法在矩形件排样中的应用J，机电工程技术，2006,(35):64-65。八、 附录clear;x=1804