第八届华中地区大学生数学建模邀请赛

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

2、 君队员三：王 江 武汉工业与应用数学学会第八届华中地区大学生数学建模邀请赛组委会第八届华中地区大学生数学建模邀请赛编 号 专 用 页选择的题号： 题A 参赛的编号： 105141519第八届华中地区大学生数学建模邀请赛题目： 钢构件的排料问题【摘 要】随着钢结构产品的广泛应用,提高原材料板材的利用效率是钢结构企业迫切需要解决的问题，计算机辅助排样优化的目的在于提供高质,以便节约原材料,降低产品成本、提高企业经济效益和社会效益。增强企业竞争力。 本文在理论和实践中的主要研究工作如下: （1）针对二维规则钢结构排样，采用构造性的递归结构，每完成一个排样基本单元排样后，假定将板材切建立二维矩形件排

3、样问题的几何模型，之后采用启发式算法进行求解割，完成零件的下料，并形成新的更小的板材。对新的更小的板材递归进行排样，直到完成所有零件的排样。为避免陷入局部最优解，为算法设置了回溯机制。 （2）针对二维不规则钢构件(异形件)排样,在综合利用计算几何、计算机图形学、优化组合的知识的基础上,采用最小包络法建立模型，并用启发式算法和动态规划法求解。 （3）针对问题一,二,三的分析，总结出了模型的优点和不足之处。知道了启发式算法只能求出可行解而不能确定最优解。 关键词：排料；递归算法；最小包络法；启发式算法目录第八届华中地区大学生数学建模邀请赛 承 诺 书1第八届华中地区大学生数学建模邀请赛 编 号 专

4、 用 页2第八届华中地区大学生数学建模邀请赛31.问题的重述42.分析问题52.1问题一52.2问题二62.3问题三63.模型假设64.符号说明65.模型的建立75.1问题一75.1.1模型的建立75.1.2模型的求解95.2问题二105.2.1 排料预处理105.2.2 建立数学模型135.2.3模型的求解145.3问题三145.3.1建立模型145.3.2模型求解：166.评价176.1 模型的优点176.2 模型的缺点171.问题的重述在钢构件制造产品的生产过程中，依照产品零件尺寸从板料中截取大小适当的零件过程称之为排料，也称之为下料。排料是钢构件制造的第一道工序。在这道工序中，不同的排

5、料方案具有不同的材料利用率，而原材料的利用率直接影响产品的成本。对于一个年消耗大量钢材的生产单位，若能够提高原料利用率的1%，那么其节约的钢材成本是可观的。因此，降低废料率提高原材料利用率是钢构件生产企业追求的目标。根据实际情况，板材排料又可分为两种：一是规则形状的零件排料，一是不规则形状的零件排料。规则形状零件是指矩形零件。其描述一般只需用矩形的长和宽。规则形状零件的排料问题的实质是研究如何组合零件摆放问题，使得在整个原料上摆放大量的不同长和宽的零件产生的废料最少、整料和余料的利用率最高。排放时，其零件间的搭接关系的处理相对容易，只需考虑长、宽两个因素（含预留的损耗量）。不规则零件在这里是指

6、多边形零件（一般的意义是指由直线、圆、弧、孔等的组合形），相对矩形零件排料而言，不规则零件的直接排料要复杂得多。另外由于切割工艺的要求，切割只能实行“一刀切”的工艺（在整料或余料中，从一边的某点到另外一边某点的连线一次切割，但可以在切割下来的板料中再次切割）。板材的利用率就是所有零件面积之和与在一刀切工艺后继续切割的那部分板材面积的比值。问题1: 对1张板料和若干规则形状零件（板料和零件参数见附件1），如何在板料中摆放零件使其板料的利用率最高。问题2: 对1张板料和若干不规则形状零件（板料和零件参数见附件2），如何在板料中摆放零件使其板料的利用率最高。问题3: 对2张板料和若干规则形状零件（板

7、料和零件参数见附件3），如何在板料中摆放零件使其板料的利用率最高。2.分析问题2.1问题一：需要建立二维矩形件排样问题的几何模型，之后采用启发式算法进行求解。算法采用构造性的递归结构，每完成一个排样基本单元排样后，假定将板材切割，完成零件的下料，并形成新的更小的板材。对新的更小的板材递归进行排样，直到完成所有零件的排样。为避免陷入局部最优解，为算法设置了回溯机制，当后面的零件无法完成排样时，算法返回修改之前的排样，再尝试完成后续零件的排样。当所有零件完成排样后，算法终止，记录各个零件的位置坐标，得出排样结果。2.2问题二： 根据问题一的求解，本文对不规则的零件先进行规则化处理，如：最小包络矩形

8、法，通过对零件外轮廓多边形进行操作，分别求得与多边形平行或重合的最小包络矩形，找出其中的最小者即为零件最小包络矩形。为得到最小包络矩形，通过聚合矩形法，将不规则的零件，进行旋转，由文献研究可的，当两个零件的边界相差180度时，能够产生最小包络矩形。最终问题归结为规则的零件排料问题。2.3问题三： 通过对一二两个问题的研究，本文对问题三作如问题的处理方式。问题三中，原材料数量增加了一倍，但原理与问题一类似，运用启发式算法求解问题。3.模型假设（1） 每个零件与板块原件的厚度都是一样的。（2） 在满足尺寸约束的条件下，每一块矩形原件上都可以排放不同的零件，每个不同零件都可以在不同的原件上摆放。（3

9、） 各个原件完成排样后，再根据各个原件上余料的情况进行多原件之间的零件的相互调整，减少余料提高排样利用。（4） 假设零件可旋转二维矩形件排样。4.符号说明L：原件的长度；W：原件的宽；：第j类零件；：第i类零件的长度；：第i类零件的宽；：第i类零件的数量；：第i个原件排布的第j类零件的数量；：第i个原件；：第i张原件的长；：第i个原件的宽；：第k个j类零件；：的坐标；：第k 个j类零件在第i个原件上的坐标；：条料i的单位宽度；:条料i的面积；：第i个零件的条料数；：第i个零件最大条数；G（i，x）:最大面积值；：从k阶段到n阶段的最大收益；S:初始状态；：状态所确定的第n阶段的允许决策集合；：

10、第n阶段的最优解；：第n阶段的最优值；5.模型的建立5.1问题一模型的建立 在二维矩形件排样问题中，假设一次排样中使用了1张矩形原件，1张原件的长为，宽为。待排样矩形零件种类数为9，第(=1，2，9)类零件的长度为，宽度，数量为。排样完成后，原件上排布的类零件的数为；第k个j类零件在原件上的位置由零件左下角点在原件上的坐标(，）及零件的长宽确定。同一类型的不同类零件坐标位置不同。零件的各边与原件的对应边保持平行。根据排样实际需要，在满足约束条件的前提下，零件可以旋转90度，交换零件的长宽后再排到原件上。那么，为了最大化排样的利用率，目标函数为： (1) 排样各约束条件表示如下:(2) + +(

11、3) 切片不能超过原件的边缘： + +(4) 所有零件全部排完: 通过上述数学模型可知，二维矩形件排样问题属于带复杂约束条件的单目标优化问题。问题的难点是怎样合理协调各工件之间及零件与原件之间的位置关系，使得排样布局在满足约束条件的前提下，具有较高的材料利用率。 这里先建立二维矩形件排样的模型。在某个原件上进行排样时，我们用矩形表示该原件，以左下角点为原点建立笛卡尔直角标系；水平方向向右为X轴正方向向上为Y轴正向。坐标系中的矩形表示排放在该原件上的不同的切片，各形的边必须跟水平方向的x轴平行或者跟竖直方向的Y轴平行，各个零件相对的位置可以由零件左下角点在坐标系中的坐标、零件的宽width、零件

12、的高height一确定。在满足约束的前提下，零件可以在原件上旋转90度得到新的布局。几何模型中代表各个零件的矩形必须满足以下约束条件：(1)矩形之间不能有重叠的区域；(2)矩形不能超出原件的边缘；(3)矩形满足“一刀切”工艺约束；如图21所示为排样结果满足“一刀切”约束与不满足“一刀切”约束的比较。yyxx a)满足“一刀切”约束 b)不满足“一刀切”约束图2-1 “一刀切”约束示例模型的求解1.启发式算法1）排样定位方法，每排放一个零件组时，该切片组怎样定位在原件上。 2）切片排样次序，确定零件组排放的先后顺序。 在算法计算时先假设该任务具有100利用率的最优解，用零件总面积除以原片的宽度，

13、得到最短需要的原件长度。使用该长度的原件进行排样计算，尝试求得具有100利用率的最优解，并将找到一个具有100利用率的排样图作为算法的终止条件。并且排样图满足“一刀切”等约束存在一个能排放完所有零件的解，那么该排样解中的余料面积和等于原片的面积减去所有零件的面积。我们将原片的面积减去所有零件的面积所得的值作为余料的面积阈值，将零件的面积和与原片面积的百分比作为利用率阈值。在排样计算过程中，我们实时记录当前排样方案产生的余料面积，当余料面积和大于该原片余料面积阈值时，该排样方案的排样利用率低于利用率阈值，不可能在完成所有零件的排放，该排样方案失败，需要修改该排样方案中前期排放的零件，以获得新的排

14、样方案，直到找出解为止。2.算法求解 用启发式算法进行求解。算法采用构造性的递归结构，完成零件的下料，并形成新的更小的板材。对新的更小的板材递归进行排样，直到完成所有零件的排样，当所有零件完成排样后算法终止，记录各个零件的位置坐标，得出排样结果。运用<极致下料>板材企业版V14.0求得结果如下：小结建立二维矩形件排样问题的数学模型，明确了此类排样问题的目标函数、排样布局必须满足的约束条件；为排样优化算法的设计提供了思路。设计了排样过程及排样结果的几何模型，将排样约束转化为计算机可以识别的几何模型。5.2问题二 排料预处理1.最小包络矩形的求取求取零件的最小包络矩形是排料算法的要求。

15、所谓最络矩形就是能够包含零件的所有矩形中面积最小者。资料表明：只有当零件的包络矩形与零件的外轮廓多边形中的一条边平行或重合时，此包络矩形才有可能是最小包围络形。据此，我们得到了求零件最小包络矩形的方法：对零件外轮廓多边形进行操作，分别求得与多边形平行或重合的最小包络矩形，找出其中的最小者即为零件最小包络矩形，如图1所示，此后，在排料时还需恢复零件原形。350400250150200150 图1 最小包络矩形的求取2.聚合矩形的求取为了提高板材利用率，需要对零件进行一定程度的聚合然后求取聚合后零件的最小包络矩形，称之为聚合矩形。零件的聚合就是使零件相互接触，但不重叠，以达到包络矩形的面积最小。在

16、排料过程中由于零件可以任意方向旋转，两个零件的聚合问题就较为复杂，但根据文献中的研究结果1，两个相同的零件进行聚合，只有当两个零件相差180。时，才能产生最小包络矩形，因此，在零件聚合过程中，可以只考虑相差180。时的情况。图2表示了零件聚合过程，其聚合过程如下：(1)求零件的最小包络矩形，图中虚线所示矩形即为零件的最小包络矩形；(2)将原零件复制一个，翻转180。，按其最小包络矩形移到零件的左上角，如图所示；(3)将原零件的总长度从左到右按一定精度等分，将复制件依次移动到每个位置后，依据碰撞算法心1分别与原零件碰撞，每次碰撞后，均求一次最小包络矩形，记录下该矩形的面积。图中实线所示的是其中一

17、个位置上复制件与原零件进行碰撞的结果；(4) 将复制件沿原零件的上、下、左、右四个方向分别与原零件进行碰撞试验，最后面积最小的矩形即为零件聚合体的最小包络矩形，记下此时的位置和碰撞距离值。图中所求得聚合矩形是将原零件经翻转后从左边靠近的结果。如果聚合后的聚合矩形的面积小于两个零件的最小包容矩形面积之和，则聚合成功；反之则自动放弃聚合。对于聚合成功的零件图形都可以提高其局部的材料利用率。36254.89945650聚合后的图形如下： 362549945650（1）3625499456 （2）50图2 零件的聚合3.不规则零件的排料过程 经过零件预处理求得了最小包络矩形、聚合矩形和多个的包络矩形，

18、这样就把不规则零件的排放问题转化为预后的矩形区域在板材上的自动排放问题。这里采用矩、启发式技术与动态规划法相结合方法解决不规则零件问题，不规则零件排料的过程是： (1)利用矩形法，分别求取两个相同零件的聚合矩形，两个零件的最小包容矩形面积之和相比较，若大于，保合结果；若小于，求其最小包络矩形，将其转化为矩形件； (2)将相同或近似零件的聚合矩形或最小包络矩形组成“条料”； (3)决定使用所形成的候选条料直接填充板材，还是通垂直方向上划分板材，用两个子区域代替原来的矩形； (4)在当前的子区域上排放这些称作条料的成组零件，过程中应用动态规划分块实时补充的方法解决“子区中条料的填充问题。该方法的规

19、则是：每次只排放矩形块；长边尺寸大的矩形块具有优先排放权；材图形长边按x方向放置，排放的零件按照最左、最下则放人；排放过程中按照板材的可用区域尺寸和待形块的尺寸和数量来动态地划分排放区域；每排放零件。已划分的区域大都会产生一定的空白区域，对于区域仍按照上述规则用待排矩形块进行补充，这一过程进行下去。直到排放完所有零件。其排料流程见图3所示：开始应用排料过程解是否满意？产生子区间产生最优定位条件获取板材输入与初始化否是结束是否有余料？否板材是否排满？空白区是否可利用？是是否否是图3 自动排料系统流程图 建立数学模型 在将不规则零件转化为条料后，就要研究条料排料过程。既已知：=条料i的单位宽度；=

20、条料的面积,需解决的问题是：确定出可排放条料的数量，使得各个候选条料的宽度之和不能超过当前矩形板材区域的宽度形，而且板材的利用面积最大。根据优化理论，可以建立的排料的数学模型如下：，其状态转移方程为：排料数学模型的允许决策集合为：bi为由零件i所组成的条料的最大数目bi。 因而可写出矩形排料模型动态规划的递推关系式为：其中，G(i，x)是从r个候选条料中选择前I各条料在宽度为的子区域上排放获得最大面积值。函数G(i，x)被初始化为零，即对于任意x，有G(0，x)=0。模型的求解 采用动态规划法。运用这种方法大大的减少了计算量，而且随着阶段数增加，减少程度更为显著。动态规划法有逆序解法和顺序解法

21、两种。却已知初始状态，因此采用逆推法。动态规划中。k阶段与k+1阶段的递推关系式可写为：,K=n,n-1,，1 设已知初始状态为s，第k阶段的初始状态位。最优值函数表示从k阶段到n阶段所得到的最大收益。从第n阶段开始，则有： ,其中是由状态所确定的第n阶段的允许决策集合。借此一维极值问题，就得到最优解和最优值。且若只有一个决策时，则就已被更改写成。在第，n-l阶段，有，其中 ，一维极值问题，得到最优解和最优值。如此类推，直到第一阶段，由于初始状态s1已知，故x1=x1(s1)和是确定的，从而也可以确定，照上述递推过程相反的顺序推算下去，就可逐步确定出每阶段的决策及效益。5.3问题三建立模型同问题一构思类似，如大化排样的利用率，在二维矩形件排样问题中，假设一次排样中使用了2张矩形原片，第i(i=1，2)张原片的长为，宽为。待排样矩形切片种类数为9，第j(j=1，29)类零件的长度为，宽度为，数量为。排样完成后，原片上排布的类零件的数量为。第k个j类零件在原片上的位置由切片左下角点在原片上的坐标（）及零件的长宽确定。同一类型的不同切片坐标位置不同。切片的各边与原件的对应边保持平行。根据排样实际需要，