钢构件地优化排料问题

1、实用标准文档钢构件的优化排料问题1、 问题的重述1.1背景在当今激烈的市场竞争中, 降低生产成本、 提高生产效率和增强对市场的应变能力 , 是企业保持竞争力的主要实现手段。在钢构件制造产品的生产过程中，依照产品零件尺寸从板料中截取大小适当的零件过程称之为排料，也称之为下料。排料是钢构件制造的第一道工序。在这道工序中， 不同的排料方案具有不同的材料利用率，而原材料的利用率直接影响产品的成本。材料费用是制造企业主要的生产成本 , 一般占总成本的60% 80% ,在大批量生产中 , 材料的利用率即使提高 1% ,所创造的经济效益也相当可观。据调查,优化下料后 ,制造企业材料利用率可平均提高5% 10

2、% 。另外由于切割工艺的要求，切割只能实行“一刀切”的工艺（在整料或余料中，从一边的某点到另外一边某点的连线一次切割，但可以在切割下来的板料中再次切割）。板材的利用率就是所有零件面积之和与在一刀切工艺后继续切割的那部分板材面积的比值。1.2问题对于第一问，对 1 张板料和若干规则形状零件， 求如何在板料中摆放零件使其板料的利用率最高。文案大全规则形状零件即指矩形零件。 其描述一般只需用矩形的长和宽。规则形状零件的排料问题的实质是研究如何组合零件摆放问题，使得在整个原料上摆放大量的不同长和宽的零件产生的废料最少、整料和余料的利用率最高。排放时，其零件间的搭接关系的处理相对容易，只需考虑长、宽两个

3、因素（含预留的损耗量）。板材大小 :2350*900 【1 张】。表 1 是九个规则形状零件的具体规格。表 1零件一二三四五长（ mm ）350350500500500宽（ mm ）300200240210350个数22222零件六七八九长（ mm ）300250500500宽（ mm ）250200400200个数2222对于第二问，对 1 张板料和若干不规则形状零件，如何在板料中摆放零件使其板料的利用率最高。与第一问类似，但是此时需要切割出来的零件不具有矩形般对边平行的条件，切割较为麻烦，同时可能会造成更多边角料的产生，降低板料的利用率。图12和表 2 是题目要求的两种不规则零件的具体形状

4、和规格。板材大小:2380*1630【1 张】。表 2零件一二个数1414图 1零件一零件二对于第三问，考虑到实际的切割过程中， 一张板料并不能满足所有零件的生产需求，故而要求设计对2 张板料和若干规则形状零件， 如何在板料中摆放零件使其板料的利用率最高。 还有一点与问题一不同， 即各零件要求生产的个数有3所改变。板材大小 :4550*1630【2 张】。具体见下表 3 。表 3零件一二三四五个数40566零件六七八九个数42242 、符号规定与模型假设2.1符号规定符号表示意义L板材的长度W板材的宽度?矩形件的长， i=1 ，2，3?w矩形件的宽， i=1 ，2，3?矩形件的数量， i=1

5、， 2， 3?板材利用率?零件的种类， i=1 ，2，3?2.2模型假设1. 切割机垂直切割，不考虑料板的厚度，即将问题转化为二维平面问题；2. 切割不会导致料板的长度或宽度减小，忽略切割损耗；43. 切割方式为一刀切，即在整料或余料中，从一边的某点到另外一边某点的连线一次切割；4. 忽略切割效率，本文着眼点在于料板利用率的提高；5. 对于问题二中的六边形，可看作是矩形一角删去一个150 150 的正方形，而这一步骤利用一刀切不可能实现，故而假设六边形ABCDEF 当作五边形ABCDE 对待（图 2 ），该零件的后续加工后文不予考虑。图 23 、问题分析本题目三个问题所研究的是一刀切下料, 问

6、题一和问题三属于二维规则图形的优化排料问题， 问题二属于二维不规则图形的优化排料问题。排料问题是典型的优化组合问题，具有很高的计算复杂性，属于NP 完全问题。“一刀切”的实际现象给了本问题一个最基础的约束，使得排样有了一个这样一个基础：每次切割都将板材一分为二。图 3 给出了一刀切下料与非一刀切下料的比较。图 35问题一和问题三要求制作的零件规格有9 种, 因此属于多零件下料问题。多种零件 , 需要解决如何选择将零件合理高效的布置在板材上。本文的研究目的是在这些约束条件下实现优化排样, 提高板材利用率。排样目标为: 尽可能提高一块板的利用率。排料需要满足的基本约束条件有：零件之间互不重叠；零件

7、的排布不得超出板材边缘；满足一刀切条件。4 、模型建立4.1模型的准备由于问题一和二要求在一张料板上规划，问题三要求在两张规格相同的料板上规划，故而在料板数量上简化模型， 仅考虑在一张规格已知的料板进行排料规划。对于二维排料问题，排料方式要满足零件长，宽方向上的套裁。将 N 个零件记为 ? 、? 、 ? 合理的排布在板材 A 中，其中满足：12?j=0NSpr *100% ）（1.1）Max （ ）=Max （A且满足：（1）Rr A j =(1,2)N ,6（2）Rj? Rk = ?（jk ， j k = 1,2N ）(1.2)其中 为排料的材料利用率，应满足最大的原则。Sp j 为第 j

8、个板材Rj 的零件面积，A 为第一次一刀切后继续用于一刀切的原料板材的面积，也即布局板材所消耗的原料面积，一般有A= A0 + A 1 + A 2 （其中A0 = Nr= 0 Sp r ，A1 为工艺废料，A 2 为结构废料）。从式（ 1.1 ）中可以看出，理论上若废料（包括工艺废料和结构废料）面积减至0，材料的利用率能够接近1，但该理论值在实际生产中无法达到。工艺废料由行业的工艺要求产生， 如切割损耗和余料， 本题在建模过程中暂不考虑实际生产中的切割损耗。 结构废料由具体板材的结构形状所决定。在生产中结构废料无法控制，要提高材料的利用率只有从减少工艺废料入手，通过采用更合理的排料方案，减少余

9、料（工艺废料） 。4.2模型的建立问题一模型的建立设共有 M 张面积大小都为 A 的板材，N 类目标零件板材。 记板材的集合为：（ X= W i ，H i i M ，零件集合为： Y= w j ，hj j N j 类零件的数量为n j , 板材 i上 j 类零件的数量为n ij ，已知第 k 个 j 类零件在板材上的排列位置可以由其左下角坐标与右上角坐标唯一确定 , 可记第 k 个j 类零件在下料板材 i上的左下角坐标为 (xiiii0jk，y ), 右上角坐标记为 (x1jk，y ) 零件 k 在0jk1jk0 纵排7下料板材 i上的排列方式记为p ijk =，目标是最大化板材的利用率。1

10、横排根据以上分析，将多板材下料问题用数学模型表示为：Max （ ） =Max （j=N0 Sp r *100% ）（1.3 ）Ap r A j =(1,2 2N ,)(1.4 ）p j ? p k = ? （j kj k = 1,2 2N ）（1.5）maxx1jki W i ，（1.6 ）j ，kmax y1jki H i ，（1.7）j ，k1I n ji = n j（1.8 ）式(1.3) 为目标函数，表示最大板材利用效率；式(1.4) 为零件规格约束；式(1.5) 保证零件互不重叠；式 (1.6) 和式 (1.7) 为板材规格约束，式 (8) 为零件数量约束。问题二模型的建立该问属于二

11、维不规则零件排样问题2 ，此类问题的求解主要有两种思路：一种是对这类问题直接在原材料上进行摆放；另一种则是将不规则零件转化为规则矩形件，然后按照矩形件进行优化排样。4如果将不规则零件排放在矩形形状的板材上，其在板材上的位呈由三个参数决定，这三个参数是该零件的一个给定点在板材上的坐标（x,y ）和该零件的排放角度，这三个参数确定后，该零件的其他各顶点参数均可通过这三个参数计算出来。 58首先定义以下参数：pi 排样零件；Gi 排样零件图形；( xi , yi ) 排样零件给定点的坐标。零件在板材上的排样定位过程如下：先将该零件的给定点 ( xi , yi ) 在板材上平移 ( xi , yi )

12、 至 (xi , yi ) ，然后再将该零件以 ( xi , yi ) 为轴作角度为 i 的旋转，这时零件在板材上的方向可表示为 Gi ( xi , yi , i ) 。则零件排样优化的模型为：nzi Simax i 1WL其中 L 为板材的长， W 为板材的宽； N 为排样零件的数目；Si 为排样零件的面积； zi 变量表示零件在板材上的排样状态，如果可以排放则取1 ，不能排放则取 0。排样的约束条件如下：Gi ( xi , yi , i )Gj (x j , y j , j )0xk ( xk , yk , k )L0yk ( xk , yk , k )W其中第一式约束了任意两个零件互不重

13、叠；第二，三式约束了零件中任意点9的坐标都必须在排样材料范围内，不能超出板材之外。我们对于问题二的求解采用第二种方法，由于问题二给出的五边形和六边形并不是特别复杂的多边形，同时五边形具有直角。我们采用穷举法列出了6种较为常见排列方案， 在这里对每种方案的利用率进行讨论，得出最佳矩形件优化方案。矩形面积：277425利用用率：228189.5/277425*100%=82.25%方案一（图 4 ）10矩形面积：=399*617=246183利用效率：=221583/246183*100%=90.01%方案二（图 5 ）矩形面积：=411*558=229338利用效率：=221100/229338

14、*100%=96.41%方案三（图 6）矩形面积：=411*664=272904利用效率：=228050/272904*100%=83.56%11方案四（图 7）矩形面积：=462*519=239778利用效率：=221100/239778*100%=92.21%方案五（图 8 ）矩形面积：=400*350=140000利用效率：=128750/140000*100%=91.96%方案六（图 9 ）经过综合分析，我们拟采用方案三和方案六组合切割。至此，将不规则形状零件的排料问题简化为矩形零件的排料问题，可参照问题一模型来求解。问题三模型的建立与前两问有所不同的是， 问题三要求在两张规格相同的料

15、板上进行排料。经12过计算得知，故而我们在问题一模型的基础上，又可分两种方案进行比较：（ 1）在一张板材上进行排板，看是否可以节省一整张料板；（ 2）在两张板材上进行排版，排板顺序为两张同时进行，以求获得更大的剩余的料板整体面积。4.3 算法模型4.3.1 算法结构框图图10排样算法基本规则：（ 1）插入规则 大边尺寸，指板材或者零件长度和宽度的较大边尺寸。 最大零件，指大边尺寸最大的待处理零件。 最小空穴，指大边尺寸最小的待下料板材。13启发式算法 6 将待下料零件按大边尺寸降序排序，将原料板材按大边尺寸升序排序 , 并规定新一轮的下料排样总是选取待下料零件中的最大零件，搜索空穴列表，从满足

16、零件下料尺寸的空穴中选择最小空穴1 作为下料板材。(2) 放置规则靠左靠下在求解初始排样方案中，对于给定空穴，规定从待排零件中选择高度最低、宽度最大的零件靠左靠下放置。(3) 转向规则整除求余设空穴小边为 x ( x= min( W，L)， W 和L分别为空穴的宽度和长度)，按插入规则和放置规则选定的零件宽度为w 长度为 l ，则 x与w ， l之间满足以下线性关系 : x= aw + l1，x= bh + d2。若 d1 d2 , 则按照 w|x 的方式放置零件，否则按照 l|x 的方式放置。（ 4）切割线替换规则 1对于任意可行解 , 若存在另一条切割线满足第一条切割线的切割条件, 则以这

17、条切割线为第一条切割线所形成的排样方案与原解相同。证明 :如图 11 所示 , 已知区域 O 存在以 x 为第一条切割线的可行解 Ix, 则 O 中存在局部区域 P, 使得 P 中以 x 为第一条切割线的解 ? ?,现已经找到另14外一条满足性质1 的切割线y, 需要证明Iy= Ix。此时切割线y 有两种情况 : 一种为 y 平行于x, 另一种为y 垂直于x。下面分别就这两种情况进行证明。（1） y 平行于 x。x 将 O 划分为 AC 和 B 两部分 , y 将O 划分为 A 和 BC 两部分。易知 ? ? ?且? ?, 同理 ? ? ? 且 ? ? , 根据集合的传递性 , 有 ? ? ?

18、且 ? ? ? 。所以以 y 为第一条切割线所形成的排样方案与?原解相同。（2） y垂直于 x。x将 O 划分为AD和 BC 两部分 , y 将 O 划分为 CD 和 AB 两部分。易知： ? ?且? ?, 同理? ? ? 且? ? ? ? ,? 且 ? , 根据集合的传递性 , 有 ? ? ? ? ? ? ? ? ? ?, ?, ? ?, ? ? ?。所以以 y 为第一条切割线所形成的排样方案与原解相同。?切割线替换定理得证。图1115排样优化思想：采用二叉树的生成过程来描述板材的分割过程，则生成的二叉树就表示一个排样结果，即得到一个全局排样解。用 I=N ，G|N= ?,G= ? ，j=1

19、 ，2 ， 表示一个全局排样解，其中N 表示排样解中各类零件的个数集合；G表示排样解中零件的规格集合。?i = N i ，Gi |N i ? N，G i ? G 是I的局部区域，则称 i是 I的一个局部解。一刀切的切割特点决定了满足一刀切约束的排样解具有以下条件:条件 1排样解中的第一条切割线必须满足：长度等于分割区域中与其平行的那条边的长度，且不影响任意零件的完整性。条件 2设 I为满足一刀切的全局解， 对于 I中的任意局部解 i ，i一定满足一刀切。条件 3对于任意可行解，若存在另一条切割线满足第一条切割线的切割条件，则以这条切割线为第一条切割线所形成的排样方案与原解相同。164.4 下料

20、优化问题的二叉树算法的构造二叉树是一种常用的空间数据结构，因其结构简单， 操作方便、快速而广泛应用于数据的排序和计算内部寻址等方面。本文主要基于VC+6. 0 开发平台，对零件排料涉及到的二叉树算法进行了编写。在排样过程中，由于一刀切的特性，1块矩形区域划分后，可得到2 块小的矩形区域。在这 2块矩形区域继续进行排样，就会得到4 块矩形区域。不断进行下去，这个排样过程就是一种二叉树的结构。本文将二叉树用于矩形物体布局空间状态的表达，具体应用如下 :已知一个布局空间的矩形区域， 按权值从可选布局物体中选择一个相对于该矩形区域来说是最优的布局物体 A，并将其定位于该矩形区域的左下角。这样原布局空间

21、变成了一个? 形区域。将这个? 形区域分12成所图示 2个矩形 A1 和A2 ，分别用根结点的左、右2 个子结点表示。 这样，剩余的布局空间就变成了2 个独立的布局空间，分别对这 2个布局空间重复上述过程，直至没有可选布局物体满足要求时停止分解。图1217其中，每个圆圈和数字代表二叉树的节点， 代表在矩形中进行了一次子排样。根节点 1为板材，进行一次子排样后，会生成2 块空白矩形，相应产生 2 个节点 :节点 2和节点 3。节点 2的空白矩形进行一次子排样后，又会产生2个新的节点 :节点 4和节点 5 。节点之间的关系如图 13 所示：图13二叉树路径中的标号 xi表示空白矩形分割方式。以节点

22、1 为例，定义 X1=0时，对节点 1的进行子排样后的空白区域进行横划分。X1=1 时，对剩余空白区域的划分为竖划分。显然，当x1 取值不同时，生成的节点 2, 3 中的原始空白矩形也不一样，更影响了后面的节点和排样结果。具体步骤如下 :1. 定义零件，二叉树节点的结构体，将板材和零件的长、宽与数量放置到数组中 ,并将零件按照长度从高到低，相同长度按照宽度从宽到窄进行排序。如下所示：/ 定义待排零件18struct ORIGINAL_SQUAREint length;/ 长int width;/ 宽int num;/ 数量 ;/ 定义已排零件struct SQUAREint length;/

23、长int width;/ 宽int num;/ 数量 ;/ 定义二叉树节点struct NODE struct SQUARE blankSquare;/ 排布前的空白矩形struct SQUARE *filledSquare; /空白矩形内排布的一列矩形int fillesSquareNumber;/ 排布的矩形数目int originalIndex;/ 排布的是哪个初始矩形int remainLength;/ 顺着排布方向无法排布的矩形的长int remainWidth;/ 顺着排布方向无法排布的矩形的宽struct NODE *lastNode;/上个节点的地址 ;19/ 构建数组，存储数

24、据，冒泡排序#includeusing namespace std;int main(int argc,char *argv)/ 建立九行三列的二维数组int row,col;int i,n,k;int* p;/p 是一个二维 int 数组row=9;col=3;p = new int*row;/ 创建行指针for(i=1; i=row;i+)pi = new intcol; /为每一行分配空间coutn请按顺序依次输入零件的长,宽与数量 ,并用空格隔开 :n;for(n=1;n=row;n+)for(k=1;kpnk;20coutn您输入的是 :n;coutn长度 t 宽度 t 数量 n;f

25、or(n=1;n=row;n+)for(k=1;k=col;k+)cout pnkt;cout n;cout按照零件长度从高到低 ,相同长度下宽度从宽到窄排序得:n;for(n=1; n=row; n+)/for 循环进行冒泡排序for(int j = n+1;j =row;j+)if(pn1 pj1)int t = pn1;pn1 = pj1;pj1 = t;int r = pn2;pn2 = pj2;pj2 = r;int w = pn3;pn3 = pj3;21pj3 = w;if(pn1 = pj1&pn2 pj2)int t = pn2;pn2 = pj2;pj2 = t;int w

26、 = pn3;pn3 = pj3;pj3 = w;coutn长度 t 宽度 t 数量 n;for(n=1;n=row;n+)for(k=1;k=col;k+)cout pnkt;cout n;cout endl;22return 0;2. 一张板材上的每次下料都优先选择长度最长， 宽度最宽的零件靠左、 靠下排列。此处选择权值法，引入权值公式计算板材的利用率：Int w= 1*u+ 2*t +3*r+4*a其中，u 表示单个待排零件占空白区域比例; t 表示一次子排样下的所有零件面积之和占空白区域比例; r表示剩余区域局部矩形的宽度；a表示剩余区域的面积 ; 1，2 ，3 ，4分别代表 u,t,

27、r,a 的加权系数。以上的加权法直接影响的仅仅是一次排样，但由于全部零件的排样是由各个零件排样完成的，因此，通过调整加权系数，可以改变板材中排样的进程。多次调整权值并横向比较。选取总体排样率最高的权值，就可以得到较优的解。3. 在满足约束条件的情况下建立二叉树并实现遍历、搜索等操作：#include#include#includeusing namespace std;23/ 二叉树链式存储结构的形式定义/ 二叉树结点typedef struct BiTNodechar data;/ 数据struct BiTNode *lchild,*rchild; /左右孩子指针BiTNode,*BiTre

28、e;/ 二叉树的创建/ 按先序序列创建二叉树int CreateBiTree(BiTree &T)char data;/ 按先序次序输入二叉树中结点的值（一个字符） ,# 表示空树cindata;if(data = #)T = NULL;elseT = (BiTree)malloc(sizeof(BiTNode);/ 生成根结点T-data = data;/ 构造左子树CreateBiTree(T-lchild);24/ 构造右子树CreateBiTree(T-rchild);return 0;/ 输出/ 二叉树的遍历/ 递归算法void Visit(BiTree T)if(T-data !=

29、 #)coutdata;/ 先序遍历void PreOrder(BiTree T)if(T != NULL)/ 访问根节点Visit(T);/ 访问左子结点PreOrder(T-lchild);/ 访问右子结点PreOrder(T-rchild);25/ 中序遍历void InOrder(BiTree T)if(T != NULL)/ 访问左子结点InOrder(T-lchild);/ 访问根节点Visit(T);/ 访问右子结点InOrder(T-rchild);/ 后序遍历void PostOrder(BiTree T)if(T != NULL)/ 访问左子结点PostOrder(T-lc

30、hild);/ 访问右子结点PostOrder(T-rchild);/ 访问根节点Visit(T);26int main()BiTree T;CreateBiTree(T);cout”先序遍历： n ”;PreOrder2(T);cout” n ”;cout中序遍历： n;InOrder2(T);cout” n ”;cout后序遍历： n;LevelOrder(T);cout” n ”;return 0;27问题一的输出结果图 14问题二的输出结果图1528问题三的输出结果图16295 、模型求解5.1问题一的求解参考问题一的方法， 画出了近似最优切法图使得利用率较大， 得到具体切法如图 17：图 17剩料为 400 300 的矩形，故?=1?1 ?-= 99 .94%?2500 900 - 300 400余5.2问题二的求解类似问题一，我们画出了近似最优切法图使得利用率较大，得到具体切法如图 18。根据附件二和假设的条件易求得五边形和六边形的面积分别为：110689.5和 128570 。而余料为 411 311 的矩形。可求得：301?1?= 89 .3%?-?2380 1630 - 411 311余图 185.3问题三的求解类似问题一，我们画出了