5月1日数学建模华中赛

1、第八届华中地区大学生数学建模邀请赛承 诺 书我们仔细阅读了第八届华中地区大学生数学建模邀请赛的竞赛细则。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们的参赛报名号为： 参赛队员 (签名) ：队员1： 队员2： 队员3： 武汉工业与应

2、用数学学会第八届华中地区大学生数学建模邀请赛组委会第八届华中地区大学生数学建模邀请赛编 号 专 用 页选择的题号： A 参赛的编号： （以下内容参赛队伍不需要填写） 竞赛评阅编号： 钢构件的排料问题摘 要本文针对三种不同的约束条件下的板料布局切割问题，根据底部填充原则，即采用优化后的BL算法模型来求解问题。问题一，只考虑板料在以宽度为基准的条件下，针对矩形零件以宽度在下为原则来布局。首先，根据矩形零件特征，依据其长度长短宽度大小的顺序提取，其次，将排好的零件依次摆置在板料宽度中，并每一次加以判断剩余宽度并根据与数组中元素对应的宽度比较进行撤出和撤入选择，最后不断撤出撤入对板料填充，最终得到优化

3、算法后的板料摆放格局。问题二，考虑不规则的零件摆放，采用最小包络矩形的方式将不规则零件规则化，且既有零件的宽度为底摆置也有零件的长度为底摆置。首先，进行单个不规则零件的最小包络矩形化，采用问题一中的方式对最小矩形进行摆放，由于最小包络矩形误差大，无法在一板料下摆放，否定此种做法，其次，采用不规则零件各自两两拼接再进行最小包络矩形化，并对问题一中的算法进一步优化，运用0-1整数规划的方式对零件的长宽组合和与板料宽度差值分别筛选并运用底部填充和剩余宽度最小原则摆放，进行简单人工干预，最终得到进一步优化算法的板料摆放格局。问题三，在问题二的优化算法后，考虑变化为规定零件在两板料摆放。首先，在问题二中

4、的长宽组合和与板料宽差值方式基础上采用底部填充，剩余宽度最小以及高度差最小原则对在单个板料先进行摆放，其次，在对板料宽已填充满的那部分矩形组合上的阶梯状矩形按利用率最大的原则重复组合摆放，进行简单的人工干预，最终得到推广的优化算法的板料摆放格局。为了提高对模型求解准确性和明了性，本文采用Matlab算法对摆放布局一步一步动态摆放规定矩形。本文的优点在于运用以简单的算法并采用不断优化的方式，针对零件的多样性和复杂性优化摆放格局，不同的问题求解不同之处仅仅是其所规定的零件规格不同。关键词： BL算法 矩形件优化排样 底部填充1问题重述1.1背景在钢构件制造产品的生产过程中，依照产品零件尺寸从板料中

5、截取大小适当的零件过程称之为排料，也称之为下料。排料是钢构件制造的第一道工序。在这道工序中，不同的排料方案具有不同的材料利用率，而原材料的利用率直接影响产品的成本。对于一个年消耗大量钢材的生产单位，若能够提高原料利用率的1%，那么其节约的钢材成本是可观的。因此，降低废料率提高原材料利用率是钢构件生产企业追求的目标。根据实际情况，板材排料又可分为两种：一是规则形状的零件排料，一是不规则形状的零件排料。规则形状零件是指矩形零件。其描述一般只需用矩形的长和宽。规则形状零件的排料问题的实质是研究如何组合零件摆放问题，使得在整个原料上摆放大量的不同长和宽的零件产生的废料最少、整料和余料的利用率最高。排放

6、时，其零件间的搭接关系的处理相对容易，只需考虑长、宽两个因素（含预留的损耗量）。不规则零件在这里是指多边形零件（一般的意义是指由直线、圆、弧、孔等的组合形），相对矩形零件排料而言，不规则零件的直接排料要复杂得多。另外由于切割工艺的要求，切割只能实行“一刀切”的工艺（在整料或余料中，从一边的某点到另外一边某点的连线一次切割，但可以在切割下来的板料中再次切割）。板材的利用率就是所有零件面积之和与在一刀切工艺后继续切割的那部分板材面积的比值。(即所有零件的面积为S1，在对板材进行多次一刀切工艺，不能再进行一刀切的板料的面积为S2，利用率=S1/S2)1.2所需要解决的问题(1) 对1张板料和若干规则

7、形状零件（板料和零件参数见附件1），如何在板料中摆放零件使其板料的利用率最高。(2) 对1张板料和若干不规则形状零件（板料和零件参数见附件2），如何在板料中摆放零件使其板料的利用率最高。(3) 对2张板料和若干规则形状零件（板料和零件参数见附件3），如何在板料中摆放零件使其板料的利用率最高。 2.问题分析在制造工业需要大量钢构件制造产品，工厂要生产产品零件，就要从板料中截取大小适当排料来生产零件，在生产中其原材料的利用率与生产企业的成本是密切相关的，故生产企业的目的就是要提供高质量的排料方案来节约材料，降低成本来提高经济效益与社会效益。故要解决的就是优化板材的使用效率。另外由于切割工艺的要求，

8、切割只能实行“一刀切”的工艺（在整料或余料中，从一边的某点到另外一边某点的连线一次切割，但可以在切割下来的板料中再次切割）。如下图所示：2.1针对问题一的分析鉴于题目所定义的板材的利用率就是所有零件面积之和与在一刀切工艺后继续切割的那部分板材面积的比值。针对一张板料是固定的，故要考虑到让规则的矩形零件尽量合理紧密的排列，让矩形零件尽量无间隙的排列在一起。故可以利用BL算法来进行排列，但是有缺陷,有些最优排样图是无法得到的，故要对BL算法进行改进可以根据矩形的长度与宽度对矩形进行排序，在对其进行有规律的排序即可得出。2.2针对问题二的分析由于题目所提供的是五边形与六边形，故在问题一的基础之上，可

9、以用矩形来包络五边形与六边形，可以设计算法来找到最小的矩形来包络该五边形与六边形。后通过对其运算后在板料上是无法排列出来的。故对之前的最小矩形包络进行优化，得出对五边形与六边形各自进行两两拼接，设计算法找到最小的矩形来包络拼接后的图形。2.3针对问题三的分析由于题目提供了两块大小一致的板材，所提供的零件是规则的矩形，在此问题中比问题一板材增加了一块板，故在问题一的基础上还应考虑到零件如何更加合理的分配到两块板材上，使得零件分布在两块板材上的利用率比在一块板材上分布的利用率更高，故这里要涉及到分配的问题，不同的分配方式会有不同的利用率结果。基于问题一要应用运筹学中的0-1规划来考虑分配。3.模型

10、假设1、鉴于附件中所提供的零件数据值较大，以及数据的差值接近整百值，假设将数据进行整数化对布局影响不大。2、假设板料只有长宽尺寸上的差别，不考虑厚度的因素影响。3、假设一刀切工艺后只有其中一部分允许再次一刀切切割。4、假设一刀切工艺后形成的不能再一刀切的那部分允许其他非一刀切切割方式。4.符号说明符号定义5.模型的建立与求解5.1问题一的建模与求解5.1.1问题分析通过对板材与零件尺寸大小的分析，寻找一种算法让这些零件与板材更加契合故可以对这些零件根据其尺寸大小进行编号，故下述为改进后的BL算法。5.1.2模型的建立与求解此模型基于BL算法来建立。(1)将板料按宽边，底部填充原则设置初始最高轮

11、廓线T为板材的最下面的边，先根据已有数据进行筛选工作，按照长度从长到短，宽度从大到小原则进行排序，即先以长度优先为准则，若长度一致的，再使用以宽度优先排入为准则，以此类推对应地将其编号：1-16；形成一数组P=P1,P2,P16。(2)先将P1放在板料的左下角，宽度与原板料的宽度 贴合，长度与原板料的长度在最左侧贴合，(3)：再排入P2，使P2宽度在下，按照(1)中所要求的原则，每当要排入一个零件Pi(i=2，3，4.),就在最高轮廓线T集中选取最低的一段水平线,如有数段,则选取最左边的一段,测试该段线的宽度是否大于或等于要排零件的宽度 。i:如果该段线的宽度大于要排入零件的宽度,则将该零件在

12、此位置排放,并判断排放后整体排样高度的变化,如果排样后高度增加了(甚至超出了板材边界),那么就从前面已排的零件中寻找宽度合适的零件(零件宽度和该段水平线的宽度均合适):a.如果没有,则按照原排样序列进行排,更新最高轮廓线后转至第(2)步;b.如有数个这样满足条件的零件,则先选取下标最小 的一个,并判断交换前后的整体排样高度，然后,依次选取另外的几个零件,进行相同的操作:如果其中部分改变操作降低了整体排样高度 ,则选取整体排样高度最低的进行交换,并更新排样序列和零件最高轮廓线T,删除对应的Pi，其他已排样的零件位置不变;如果改变都没有降低整体排样高度,则不改变排样位置,按原序列进行排样.ii:如

13、果该段线的宽度小于要排入零件的宽度,则从零件所在位置起向后搜索后面可以放下的零件:a.如果有零件的宽度恰好等于该段水平线的宽度,优先排入此零件,并更新零件最高轮廓线L（更新即为提高至去除原定最低高度后的最低高度）;b.如果没有宽度相等的零件,则从该零件所在位置起向后搜索第一个可以放下的零件,同时将这个零件调到待排零件的位置并排入;c.如果在这短线上没有任意可以排放的零件,就将原来排的依次反顺序撤出，并在依次撤出过程中后面的零件中搜索宽度之和有无和为板材最下边的宽度，如有就提前排入，若都没出现情况就更新最低水平线T 第二低的一段齐平,更新零件最高轮廓线L.重复步骤(2),直至将零件排入;重复上述

14、过程,直至所有零件都排放完毕. 流程由下图（1）所示： （图1）图一表示的是：先优先选择矩形件的长度排列，排列后可发现板料的底部还有100的间隙，而没有矩形件的宽度是小于或者等于100的，故要将矩形件2退出，以此类推出下列的排料过程为图（2）： 图（2）流程图二中最后的一张图就是矩形零件在板料上的摆放布局，由图可知黑色那条线是第一次一刀切后，红色的为第二次一刀切，最后所得到的板料就是不能再进行一刀切的部分，其面积为S1。所有的零件面积之和为S2.通过使用MATLAB编程可以得出最后可算出板料利用率5.1.3模型的结果分析 由上述可知板料的利用率为94.15%，说明用底部填充算法所得到的结果还是

15、较优的，说明底部填充算法还是有具有一定可行性的。因为该算法可以将板材的底部尽可能充分填充，故可让板材的内部尽量不出现间隙。可充分提高板材内部使用率。5.2问题二的建模与求解5.2.1问题分析问题二是基于问题一的基础之上，题目给出了两类不规则图形，为五边形与六边形（如图3，图4）首先会考虑将问题二转化为问题一来处理，相对矩形零件排料而言，多边形零件的直接排料要复杂得多。如何提高板材利用率,降低生产成本,从而带来显著的经济效益,是我们的研究重点。因此提出了一种简单的求取不规则零件的最小包络矩形的方法，此方法通过假设将复杂多变的多边形近似的看作在一个面积和其最接近的矩阵（即为包络的最小面积矩形）当中

16、，再根据第一问中的改进后的BL方法和底部填充原则将板料进行布局并排料。 图(3) 图（4）由于由于题目中所给出的零件一规格数据值较大，以及数据的差值接近整百值，故将零件一数据进行调整，得到下表新的数据，如图（5） 对零件一改进后的数据040050400504004101204101203600360000000400 图（5） 5.2.2模型的建立建立最小包络矩形具体步骤如下：(1) 先根据叉乘的判断方法判断多边形的凹凸性，如果为凸变形就保持原来的形状不变，如果为凹边形就将原多边形凸化（具体凸化方法见附录）；(2) 通过比较得出多边形的各个端点的距离间隔最远的两个点，记为A，B；我们近似的看线

17、AB为所求的矩形的对角线，(3) 由 A、B 两点与临近的点组合可以得出 4 条边；(4) 将这四条边中的其中一条旋转至x轴,读出旋转过后的各个端点的值，比较得到xmax、xmin、ymax、ymax，则包络矩形的面积为S=xmax-xmin（ymax-ymin） (5)：选下一条边，重复步骤(4)。(6)比较所得到的四个矩形的面积大小，选择最小面积的矩形即为最小包络矩阵。该算法的流程图如下图（6）所示： 图（6）通过以上办法，我们先采用用最小包络矩形包络单个图形形成一系列矩形，S140035014=1960000,S241028014=1607200,同时S总=23801630=387940

18、0，a=S总-(S1+S2)S总=0.080,由于在矩形切割过程中根据底部填充原则必然出现大于S总-(S1+S2）的面积值，所以该模型无法使用，由于在用最小包络矩形时与原来的多边形之间产生的面积差过于大，我们通过将图形的拼接使得产生的最小包络矩形与拼接过后的多边形的平均面积差比单个多边形的包络小，优于原来的包络方式使得产生的剩余面积可以相对变大可供切割的灵活性相对就变大，我们采用了将五边形和六边形分别两两组合的方式产生最小包络矩形，如图（7）图（8）所示图(7)图（8)图中所示矩形拼接根据拼接理论，即在多边形两两拼接后所形成的最小矩形必可以在以多边形边上的某一点为圆心旋转一定角度 后就可得到另

19、一个拼接上的多边形。图（9）表格中我们以取计算出六边形各个边的中点进行旋转形成的拼接六边形的最小包络矩形为例比较各个产生的面积LengthWidthSquart70055038500700400280000800500400000800350280000650400260000550500275000 图（9）由于用标准方法求得的最小包络矩阵与图中将五边形延长形成对角线的方法形成的误差远小于总面积而言，故在此题中我们用延长对角线的方法来近似看做最小包络矩形。我们对第一问中所依据的算法进行优化，类似与第一问的算法，其具体算法类似于问题一中的算法如下：第一步：设置初始最高轮廓线L为板材的最下面的边

20、，先根据已有数据进行筛选工作，按照长度长短，宽度大小原则进行排序，并对应地将其编号：1-14；形成一数组P=P1,P2,P14。第二步：将Pi(i=1,2.14)分别根据i的不同性以及它们的长宽L,W以多种方式组合并且求出并它们的各自的值，储蓄于数组sum中第三步：将最高轮廓线T的长度 与数组sum中各个值进行比较，其中的最小值min(sum(j)-b)所对应的Pi以及对应的长宽相加形式，如果最高轮廓线的宽度L大于得出的最小值,则在各个的出的差值中搜索后面可以放下的零件:a.如果差值恰好等于该段水平线的宽度,优先排入求得该差值对应的零件组合方法的此组零件,删去在数组P中对应的元素，并更新数组s

21、um以及零件最高轮廓线L;b.如果无a中的情况,则得出从所有差值中与水平线L宽度绝对值最小的那个差值对应的Pi以及对应的长宽相加形式,同时将相对应Pi以及其对应的长宽方式调到待排零件的位置并排入;删除排入后在数组P中的Pi, 更新数组sum以及零件最高轮廓线L;如果最高轮廓线的宽度小于得出的最小值，更新零件最高轮廓线L;重复第二，第三步，,直至将零件排入;重复上述过程,直至所有零件都排放完毕.通过MATLAB来求解在上述步骤（4）中的最小包络矩形的求解，可以得到两个五边形拼接后得到的最小面积为两个六边形拼接后得到的最小面积为 最后可得到最小的包络矩形在板料上的摆放方式为图(10 ) 图 ( 1

22、0) 最后所得到的板料就是不能再进行一刀切的部分，其面积为S1。所有的零件面积之和为S2.计算可得利用率87.23%5.2.3模型的分析 由上述得出的利用率为87.23%可知，利用率比问题一中的利用率小，造成此结果的原因是：对五边形与六边形进行两两各自拼接后，再找到最小面积的矩形来包络拼接后的多边形，在此期间会产生一定的废料，由于拼接后所得到的最小包络矩形，在板料中进行排料时会产生较多的废料，故要对问题一中的模型进行改造，对最小包络矩形的长与宽的摆放可以多种进行组合。此模型可将板料的底部充分填充。故可以得到一个较优的结果。5.3问题三的建模与求解5.3.1问题分析在此问题中板材增加了一块板，故

23、在问题一的基础上还应考虑到零件如何更加合理的分配到两块板材上，采用合理的分配方式使得零件分布在两块板材上的利用率比在一块板材上分布的利用率更高，故这里要涉及到分配的问题，不同的分配方式会有不同的利用率结果。5.3.2问题的建模与求解建模的具体算法步骤如下：1、此类问题中的核心方法：以底部填充原则法对板料的宽度, 用问题二的方法对底部能被完全填充的先进行填充，若 ，其中,只能取0或1，表示是否选择第i种零件，=1表示选了第i种零件后用它的长去填充，=0表示选了第i种零件后用它的宽去填充,若出现多组数据都能被完全填充，则按照其组合形成的高度差 最小 先放置的原则对板料进行左边高右边低的阶梯状放置，

24、同时在长宽数组L，W中删去已填充的元素值，将删除过后的数组形成一新的长宽数组，更新零件最高轮廓线L;重复循环步骤直至无法在进行填充为止，形成一新的长宽数组；2、再将长宽各自的新形成的数组运用底部填充原则组合成的值与原板料宽度差最小的先填充,若出现多组差值都一样的，则按照其组合形成的高度差 最小先放置的原则对板料进行左边高右边低的阶梯状放置重复步骤2，直至将一块板料填充完全，更新零件最高轮廓线L;3、题中要求可选择性填充两块板料，先按第2步方式填满其中一块板料，填充完整的因其不会对利用率产生影响故放置在一块板料上不动，在形成阶梯状的未被填充完整的另外一部分按照利用率最大的原则将阶梯状的整体“台阶

25、”在两块板上进行挪动，重复挪动“阶梯”，分别求所得利用率，直至使求得阶梯状在两块板料中适当的分布，使所求利用率最高。(1)通过MATLAB画图可得到若只在一个板料上排料，可得下图11的排料方案：图(11)(2)以下为在两块板料上，对矩形在两块板料上的合理分布得到的排料方案，鉴于矩形在板料上是基于以板料的宽先摆满的原则，若能把板料的宽上摆满后，再进行摆放的过程中，要以从左到右以高度优先为准则，依次呈阶梯状排样方案可得到以下几种不同的排样方案：方案一的排料方案如下图11，12： 图(12) 图(13)方案二的排料方案如下图14.15图(14) 图（15）最后可以得到若只在一张板材上进行排料可得到利

26、用率为92.21%方案一得到的利用率为97.99%方案二得到的利用率为98.60%模型的分析由模型的求解过程可以得到板材的最优的利用率为98.60% ，建立此模型的思想为：先在一块板料上对所有零件进行排料，可得到一个摆放的方案。可由一块板料上的摆放可以优化得出，因为在一块板料上每一次的段线上都有可能出现,因此得到的排料方案是呈多样性的，故通过多次组合尝试可得出一个较优的排料方案。使得利用率较高。6模型的优缺点与改进6.1模型的优缺点优点：(1) BL算法在实际的开发与研究过程中能较为广泛的运用,其策略思想较易理解,实现较为简单,适用范围广。(2)问题二中对问题一中的底部填充对矩形的限制变小，可

27、对矩形的长度与宽度进行自由地组合，使得模型的应用范围更加广泛。(3)底部填充法则可以让零件分布在板材的下部，使得矩形零件较紧密地排列。(4)该算法能很好的满足贯通要求。缺点：对于矩形排样的零件个数只能为有限个。只适用与矩形零件的一刀切问题，不规则零件通过最小包络矩形的方法对板 材的浪费可能造成损失会变大，使利用率变化幅度强烈。底部填充的算法还是带有主观性的，在编程中具有局限性。6.2模型的改进 (1)在求解问题二时是通过最小包络矩形对其中两个相同规格的多边形即为五边形、 六边形包络，其对板料的浪费率还是较高，要更好的提高利用率，要求我们用更优化的拼接方式，五边形和六边形的拼接，形成一个临界多边

28、形，不同的临界多边形决定了不同的摆放方式，例如：我们用三个五边形拼接，示例如图(16)所示拼接而形成一临界六边形。 图(16 )以此类推可以得到：利用4个或5个五边形进行拼接，其拼接的可能性是多种方式的，上述的建模过程没有进行对多种拼接进行讨论，故该模型不够完善，故可按此方向对模型进行改进。（2）对问题三中附件中出现的数据零件二（0个） 零件二的规格00350035003502003502000200020000 图（17）我们将其中的0个视为零件二不限个数，我们采用问题三中方式，并制定规定的分配标准，目标为：生产完附件三中所要求的其余零件能摆放零件二的最大个数。这个可以视为模型改进的一个方向

29、(3)在求解问题二时是通过最小矩形包络，由于其对板料的浪费率较高，还可用临界多变形整体逼近来求解问题。(4)在对矩形选取的过程中，MATLAB只能对矩形的长度进行筛选，只能在一维的条件下进行选取。6.3模型的推广改进后的BL算法不仅仅可以使用在刚构建排料中使用，还可以应用在以下领域： 服装制造业生产过程的布匹材料的分割过程塑料制品中塑料板材、型材的分割家具制造业木质家具胶合板的分割7参考文献1 姜启源等.数学模型M.北京：高等教育出版社，2003.2叶晓光.纲结构排样优化问题研究D. 浙江.浙江大学，2008.5:21-293刘月明.二维不规则零件排样算法及系统的研究D.广东.华南理工大学，2

30、012.11：15-194卢齐飞.二维不规则图形下料排样优化算法研究D.广东.广东工业大学，2013.6：10-175王正东等.数学软件与数学实验第二版M.北京：科学出版社，2010.86井振毅等.MATLAB实用宝典M.北京.中国铁道出版社，2008.127张军等.一刀切下料的数学模型N.吉林.延边大学，2001.38郭瑞峰.基于病毒进化遗传算法的二维不规则图形排样D.广东.广东工业大学，2014.058.附录BL算法的具体步骤如下：对于一个给定的排样序列Pj(j=l,2,n),规定横放为正,竖放为负.(l)将零件P1放在板材的左下角,若P1为负值,则将其旋转90度后再排放,并求出排放后所占

31、板材的最大高度;(2)将零件Pi(i=l,2,n)置于板材右边最大高度处后,交替向下左移动尸i,首先尽可能地向下移动,然后再尽可能地向左移动,直至无法再向下向左移动为止(即接触到其它零件或板材边界),并求出此时的最大高度.重复上述过程,直至所有零件排放完毕,最后所得到的最大高度即为所需板材的高度根据参考文献（二维不规则图形下料排样优化算法研究_卢齐飞）对二维不规则零件的凹凸性判断：用叉积法:绕多边形的周长计算相邻边向量的叉乘,如各叉积均同号,则为凸多边形;如果有正有负,则为凹多边形。凸化方法：用上面所述方式对所要求的零件每个点进行凹凸性判断，如果出现凹点，就将凹点附近的两个点相连代替原来的多边形%此程序目的是填充满长度或宽度为n的板料忽略其高度是否变化和宽度长度的组合排列，以填充三种零件为例进行填充function s=baifang(l1,n1,l2,n2,l3,n3,n)%li，ni分别代表第i种零件的长度（或宽度）和要求数量，n为板料长度（或