不规则皮件排料方案研究.doc

不规则皮件排料方案研究摘要本文针对牛皮模板的排料问题，建立了排料优化模型和组合排料优化模型，并设计了相应的排料算法，获得了牛皮利用率最大时的排料方案。本文首先将所给牛皮、沙发和餐椅模板的图像比例尺统一化，其次将图像网格化，最后矩阵化图像，得到牛皮模板的换算矩阵和皮件模板的最小包络矩形的换算矩阵。问题一，要求给出N张牛皮模板的排料算法，使牛皮的利用率最大化，考虑到实际生产过程中批量化生产， 本文以2.4的牛皮模板为例，给出制作一套沙发的排料算法。利用Matlab软件，将图像矩阵二值化为0和1的换算矩阵，将牛皮模板划分为可放置和不可放置两个区域，设包络矩形的放置方向为随机量，通过换算矩阵之间的计算，将所有沙发模板安排完全，得到了每张牛皮的利用率。经过多次模拟，得到使牛皮利用率最大的排料方案， 当使用2.4的牛皮模板时，需要3张牛皮，每张利用率分别为87.64%，86.83%，75.52%，牛皮总的利用率为。 问题二，在问题一模型的基础上进行改进，仍然以2.4的牛皮模板为例计算。首先按照问题一的方案裁剪40张牛皮得到13套沙发，剩余1张整牛皮和额外的8张整牛皮裁剪餐椅皮板，然后采用将沙发裁剪余量和完整牛皮模板组合使用和只利用9张完整模板两种方法设计排料方案，通过Matlab软件计算，在两种情况下均可生产27把餐椅，但在余量模板和完整模板配合使用情况下可获得更多规整余量。 本文针对牛皮排料的问题，建立了排料最优化模型，给出了排料算法，得到了牛皮利用率最大时的排料方案，为皮件排料问题提供了可行方案。关键词：排料优化模型 组合优化模型 换算矩阵 模拟仿真 Matlab软件一、问题重述在实际生产生活中裁剪是必不可少的，裁剪的好坏、利用率的高低，直接影响生产厂家的经济利益，首先定义以下三个概念： 1、牛皮：整张，未裁剪的牛皮原料，经过数码取像技术转化成CAD 文件格式的二维区域； 2、皮板：最终产品的模板，一般由硬纸板制成的，用于裁剪。产品设计完后，经过数码取像技术转化成CAD文件格式的二维区域； 3、皮件：由皮革缝制成皮套，再通过其他工艺加工成的最终产品（例如皮包鞋、皮沙发等）。 根据以上定义，本问题研究的对象是数码二维区域。附件提供了牛皮模板、沙发模板和椅子模板，根据制造沙发和椅子的各个部位的皮模板可以制造一把皮沙发和一把餐椅。在实际生产中经常要求最后一张牛皮的利用率要尽可能大，解觉以下两个问题： 1、假设N 张牛皮的模板都和提供的两张一样，试建立数学模型，在厂家皮单确定的情况下，确定针对N 张牛皮的排料算法，要求使牛皮的利用率最大化； 2、在某批沙发订单确认的情况下，在采购了40 张牛皮裁剪结束之后（发现有一定余量），插入一个餐椅皮件订单。利用裁剪的余量，再增加8 张牛皮，计算出增加的餐椅数量。二、基本假设1. 不考虑裁剪牛皮的刀口宽度。2. 裁剪没有失误，牛皮无损坏。3. 所有牛皮原料都完整。4. 假设第二问中的40张牛皮和8张牛皮均为2.4平方米。5. 假设使用相同规格的牛皮制作沙发，不考虑套排。三、符号说明1. 表示与牛皮模板的数量（）；2. 表示牛皮模板的实际面积（）；3. 表示牛皮模板的集合（）；4. 表示沙发模板中第个部件的左上顶点坐标（）；5. 0-1变量，表示沙发模板中第个部件包络矩形的方向等于0表示横放， 等于1表示纵放（）；6. 表示沙发模板中第个部件包络矩形的换长（）；7. 表示沙发模板中第个部件包络矩形的换宽（）；8. 表示沙发模板中第个部件包络矩形的换面积（）；9. 表示沙发模板中第个部件的占用空间集合（）；10. 0-1变量，表示沙发模板中第个部件是否排在当前模板（）；11. 表示牛皮模板的余量部分的面积（）；12. 表示牛皮模板的余量部分占用空间集合（）。四、图像与数据预处理牛皮模板及皮件各部件的几何形状都是二维不规则的,在排料中，要获取模板和各部件的几何信息，本题将信息以图像的形式给出，因此，需要对所给图像进行处理，包括图像的网格化处理和获得图像的数据矩阵。图像处理具体过程见图4-1。图4-1图像处理过程4.1图像网格化(1)离散化处理利用Matlab软件2处理图像如下：Step 1读取灰度图像，获得灰度图像矩阵；Step 2将图像二值化，获得二进制矩阵；Step 3以20mm为网格宽度改变二进制矩阵，将图像网格化，使边界正交化；Step 4获得图像的多边形区域。 (2)网格大小的确定 如以单像素代表长度为网格基准，软件无法完全显示图像，为后续处理带来不便，再考虑到精度的要求，实际20mm的长度为网格的宽度绘制网格。(3)比例尺的统一将图像网格化处理之后， 根据（4.1）确定出每张图像中一单位像素对应的实际距离，进而使实际距离相同，使确定的比例尺统一化。 （4.1）4.2换算数据矩阵 换算数据矩阵是指将图像网格化处理之后，以单位网格的大小作为数据矩阵的元素，数据矩阵为包含0和1的二维矩阵，矩阵中1用来表示该位置包含在图像轮廓内。 4.2.1牛皮模板换算数据矩阵 将牛皮网格化处理之后，通过矩阵可以表示网格化之后图像的信息，矩阵中有1元素的位置则是牛皮模板的内部位置。所有1元素所在点组成牛皮模板的空间集合。4.2.2皮件模板换算数据矩阵(1)最小包络矩形将沙发各部件的边界正交处理之后，各部件的几何信息已改变为多边形，首先将凹多边形转化成凸多边形，进而确定出46个凸多边形。对于确定的46个凸多边形，因为最小包络矩形至少有一条边与该多边形的某一条边重合，具有n个顶点的凸多边形，共有n- 1条边,所以可以作出n-1个外接矩形。依次计算这n-1个外接矩形的面积，之后比较大小，就可以确定所有46个部件的最小包络矩形。计算包络矩形参数的步骤如下：Step 1计算第i条边与x轴的夹角，可以根据连接第i条边两端的顶点坐标求得，然后以顶点i为中心对多边形进行旋转，使第i条边与x轴平行，则第i个最小包络矩形的底边与旋转后的第i条边重合。Step 2多边形旋转后更新所有的顶点坐标，更新方式按式进行，然后在所有已更新坐标值的顶点中搜寻最大和最小的x值以及最大的y值。Step 3计算最小包络矩形的面积，同时记录下矩形的长，短边。依次循环执行上述步骤直到n-1个包络矩形全部求出，再逐个比较面积，最小的就是该多边形的最小包络矩形。同时记录数据，。利用Matlab软件，按照Step 1- Step 3的顺序计算求得沙发各部件包络矩形的参数如表4-1所示。表4-1 沙发各部件包络矩形参数编号原始面积换长换宽编号原始面积换长换宽10.0584275240.2035242120.0584275250.126211530.1033318260.126211540.0398119270.1134261150.0415244280.1134261160.0378119290.1134261170.0387156300.1134261180.0379205310.1134261190.0453186320.11342611100.03842443300225105340.37153229120.0299126350.37153229130.0299126360.47934030140.0378119370.47934030150.0332146380.54114630160.0406166390.54114630170.0731345400.11291915180.0584275410.0731345190.0297204420.0631247200.0297204430.0453186210.21162522440.0387156220.21162522450.0387156230.20352421460.019114说明：1.原始面积单位为平方米。2.换长与换宽的单位是20mm。通过相同的方法，利用Matlab软件求得餐椅各部件的包络矩形参数表如表4-2所示。表4-2 餐椅各部件包络矩形参数编号原始面积换长换宽10.1485231720.02227230.008910240.1159211450.0788171260.0691171070.01517280.0891221090.0371109100.0294145说明：1.原始面积单位为平方米。2. 换长与换宽的单位是20mm。(2)包络矩形的换算矩阵包络矩形的换算矩阵为维的单位矩阵，表示皮件第个部件的轮廓内部空间，该矩阵决定了排料时各部件所要占用的空间。五、问题分析5.1背景概述优化排料通常是指在一组给定尺寸的原始板材上,尽可能多地排放需要的二维零件产品,使得板材利用率最大,以减少废料。排料是优化组合3的一类典型问题,在工业生产中具有较高的实用和推广价值。提高板材利用率将会降低企业的生产成本，会给企业带来经济效益。所以，排料问题的研究具有重要的经济价值。从计算复杂性理论来看，排料问题属于具有较高计算复杂性的一类问题NP完全问题，NP是Nondeterministic Polynomial的缩写，即为非确定型多项式的意思。对于NP完全问题，至今还没有找到多项式时间算法，因而，求其有效的近似解法是必由之路。对于这类问题，以目前已经成熟的计算理论和算法，或者根本无法求解，或者其求解的计算量是爆炸性的。所以，如何找到一种有效的排料算法具有重要的经济价值和理论价值。5.2问题一的分析 本问题为在订单确定的情况下，要求我们针对N张牛皮，建立数学模型，确定皮件的排料算法，使牛皮的总利用率最大，这是寻找平面最优布局的优化问题1。在实际生产中，工厂均是规模化生产，因此本题实际要求我们确定制作单张皮件的排料算法，以利于规模化生产。本题要求牛皮总利用率最大化的前提下，还要求使最后一张牛皮的利用率最大，厂家要求最后一张牛皮剩余的部分尽量规整，利于再利用，则最后一张率用率最大包括剩余牛皮的面积最大即余量最大和剩余部分形状尽可能规则两个部分。因此确定本题为双目标优化问题，使总利用率最大的目标优先于使最后一张牛皮的利用率最高的目标。解决本题性质的双目标问题，可以通过两个阶段，建立不同的模型实现。(1)第一阶段模型 首先明确本阶段的目标是：确定制作单张皮件的排料算法，使牛皮的总利用率最大化。牛皮的利用率为皮件总面积与牛皮总面积和牛皮余量面积之差的比值，表述为： 其次，根据题意的要求，以皮件各部件在牛皮原料上的位置作为决策变量。再次，根据皮件各部件必须在牛皮原料上，并且在排料中不能重叠，以及各部件均要排料一次等限制，确定排料的约束条件。以此建立优化模型，因建立模型中包含集合等元素，普通的算法不能直接求解。考虑将算法进行如下改进：将皮件各部件按照面积大小，从牛皮左上角开始，依次从左至右，从上至下在牛皮上排布，使用模拟仿真4的方法，对问题进行求解。(2)第二阶段模型明确本阶段的目标是使最后一张牛皮的利用率最大，引进余量的面积，使用余量面积的大小描述最后一张牛皮的利用率，余量面积越大，则对应的利用率越大。同样以皮件各部件在牛皮原料上的位置作为决策变量，根据皮件各部件必须在牛皮原料上，各部件在排料中不能重叠，各部件不能与余量部分重叠以及各部件均要排料一次等限制，建立优化模型。该阶段同样对解法进行改进，改进方法与第一阶段相同。通过两阶段模型，确定皮件的排料方式。根据牛皮模板的利用率的定义，计算牛皮模板的利用率。5.3问题二的分析本题是在采购了40 张牛皮裁剪结束之后，利用裁剪的余量，再增加8 张牛皮，要求我们计算出增加的餐椅数量。因第一问模板会有余量存在，所以本问题是在模板数量增加的情况下重新设计排料算法。制作餐椅同样要求模板的利用率最大，本问题是以餐椅模板部件的位置为决策变量，以模板利用率最高为目标的组合优化问题。首先通过面积的分析，可以确定余量模板不能制作所有的餐椅模板部件，则考虑将余量模板与原始模板组合排料。六、问题一模型的建立与求解6.1模型的建立根据问题分析，本问题为双目标规划问题，要通过两个阶段求解。首先根据各部件的面积和牛皮模板的面积，计算出制作一张沙发时所需最少模板数量ZS，则为前（ZS-1）张牛皮原料排料建立第一阶段的优化模型，为最后一张牛皮的排料建立第二阶段的优化模型。6.1.1第一阶段优化模型的建立(1)决策变量的选择根据问题分析，选择沙发模板各部件在前（ZS-1）张牛皮模板上的位置，以及各部件的放置方向为决策变量。(2)优化目标的确定根据问题分析，目标为牛皮模板的利用率，本阶段中牛皮模板余量的面积为零，则，利用率为各部件的面积之和与牛皮的总面积之商，表述为： （6.1）(3)约束条件的表达(1)沙发模板各部件要放置在牛皮模板中，记为第个模板的占用空间集合，为第个模板的集合，则此约束表述为： （6.2）其中。当皮件模板的左上顶点为时，其对角顶点的坐标为，因此集合表示如下：(2)沙发模板中任意两个部件不能有重叠部分，表述为： （6.3）其中。(3)对摆放方式的约束，用0-1变量：其中。(4)模型的建立根据(1)、(2)和 (3)，第一阶段的优化模型表述为： s.t.其中。6.1.2第二阶段模型的建立1)决策变量的选择根据问题分析，选则沙发模板各部件在第ZS张模板上的位置，以及各部件的放置方向为决策变量。2)优化目标的确定根据问题分析，目标为牛皮模板余量面积最大，表述为：max （6.4）3)约束条件的表达(a) 沙发模板各部件要放置在牛皮模板中，记为第个模板的占用空间集合，为第个模板的集合，则此约束表述为： （6.5）其中。(b)沙发模板中任意两个部件不能有重叠部分，表述为： （6.6）其中。(c)牛皮模板余量部分在牛皮模板中，表述为： （6.7）其中。(d)牛皮模板余量部分与沙发任一部件不能有重叠部分，表述为： （6.8）其中。(e)对摆放方式的约束，引进0-1变量：其中。4)模型的建立根据(1)、(2)和 (3)，第二阶段的优化模型表述为其中。6.2模型的求解6.2.1算法介绍因为原问题变量及约束数据为集合形式，使用普通的算法不能对问题进行求解，所以对问题解法进行改进。根据约束条件各个皮件互不重叠，且不超过牛皮的范围等限制，将将皮件模板按照面积从大到小的次序先后进行排序，按照面积的大小安排排料。排料过程中，将皮件部件从左至右，从上至下依次搜索，并将各个皮件的横竖放置作为随机变量，多次重复排放，利于较优解的寻找。算法流程见图6-1。图6-1 算法流程图6.2.2结果及说明 通过Matlab软件，计算出沙发各部件的排料方式如表6-1所示。表6-1沙发排料方式编号第几牛皮模板中横坐标纵坐标是否旋转编号第几牛皮模板中横坐标纵坐标是否旋转11138202433760021625102514160133691612622214043768602721376053771212812217061531912916240073814313025679083158403136149192619003232217010162560333561811117413134246500122721403515660113325110362462001427991037316300151251103811630016187151392163011728615140361751181629204137647119118870422785012021887043285501211166004437728122162180453739502331660146148190注：横纵坐标的单位仍为换算长20cm。由上表可知：1,2,6,10,11,15,16,18,19,21,22,25,28,29,35,38,46等17个部件排在第一张牛皮中；9,12,14,17,20,26,27,30,34,36,39,42,43等13个部件排在第二张牛皮中；3,4,5,7,8,14,23,24,31,32,33,37,40,41,44,45等16个部件排在第三张牛皮中。每张牛皮模板上的排料结果如图6-2、6-3、6-4所示。图6-2 第一张牛皮排料情况图6-3第二张牛皮排料情况图6-4第三张牛皮排料情况通过计算，第一二三张牛皮模板的利用率分别为87.64%，86.83%，75.52%。计算最后一张牛皮模板的剩余面积大小为0.1976，则牛皮的利用率为。七、问题二模型的建立与求解7.1餐椅数量最优化模型的建立 根据问题分析，本问题是在第一问的基础上，增加牛皮模板的数量，在牛皮数量限制的情况下计算能够多生产餐椅的数量。因制作单位餐椅的模板不再固定，存在多种组合模板，因此为组合优化问题。7.1.1余量模板试排料第一问得到三种新的模板，即裁剪沙发皮件后的三种余量。将新增三种模板的矩阵分别使用第一问中的程序进行尝试性排版，发现这三种模板只能排下椅子皮件中最小的两个皮件。而椅子皮件中面积最大的八个无法再原余料的基础上进行排放。已购置40张牛皮可以满足13张沙发的订单，在此情况下仍剩余一张整牛皮模板。因此各模板数量为模板1和1共有9张，模板3,4,5各有13张。7.1.2模型的建立建立以餐椅的位置和放置方向为决策变量，以牛皮利用率最大为目标的优化模型。 s.t.其中。7.2模型的求解7.2.1混合排料 (1)余量的排料 通过Matlab软件计算，余量3种模板共计39张模板共制作餐椅的9,10部件数量为39张。(2)整牛皮的排料通过Matlab软件计算，整牛皮制作27张1-8部件，因1-8的部件的数量小于9,10部件的数量，因此共计制作27张餐椅。余量排料图见图7-1。图7-1余量模板排料情况7.2.2单张整牛皮单独排料在模板1和2上制作整数张餐椅。通过Matlab软件求解，计算制得餐椅数量为27张。排料方案见图7-2。图7-2整牛皮模板排料方案 根据分析，直接用9张也可以做出27张餐椅，比较土7-2和7-1与6-3，结果表明，按照第一问余量排料之后，在制作餐椅之后，剩余的余量部分明显优于原剩余余量。因此选择混合排料方案更优。综合得到排料方案见表7-1。表7-1餐椅在原始模板上排料方案编号横坐标纵坐标是否旋转编号横坐标纵坐标是否旋转椅115330椅655300椅115520椅668701椅138201椅672141椅263960椅830690椅278681椅852430椅279401椅852531椅416691椅968870椅424121椅972310椅438431椅930791椅555180椅1038640椅556751椅1074401椅562531椅1074541八、模型的评价和改进本文首先将图像信息处理成矩阵格式，并通过网格化和换算矩阵的方法，使牛皮和皮件均转化为与其实际尺寸相关的矩阵，使该问题转化为一个与矩阵运算相关的数学问题。以集合和矩阵运算为理论基础，首先凭经验给出一些排放规则（这样利于提高运算效率），并通过计算机模拟仿真实验，比较各皮件随机放置的牛皮利用率，找到一个较优方案，确定各皮件排放。本文模型可以推广到如服装、皮革和机械行业，对实际生产中不规则零件的排料问题提供指导作用。依据本文给出的方法及原理，再根据实际需要，可以提高所选用的精度，并且，可以不必求出最小包络矩形，只需用一个矩阵表示能够放置该皮件的任意一个矩形即可，通过判断矩阵值的匹配与否，进行编程的改进，这样更加切合实际。若需要尽可能提高牛皮利用率，还可以结合遗传算法，模拟退火算法，人工神经网络算法等启发式算法，进行编程求解，这样编程难度虽然有所增加，但是效率更快，利于较优解的搜索。九、参考文献1姜启源，数学模型（第三版），北京：高等教育出版社，20052陈杰，Matlab宝典，北京：电子工业出版社，20073甘应爱，田丰，运筹学（第三版），北京：清华大学出版社，20054韩中庚，数学建模方法及其应用（第二版），北京：高等教育出版社，2009十、附录附录目录：10.1问题一Matlab程序10.2问题二Matlab程序10.1问题一Matlab程序(1)第一张牛皮模板排料程序clear;clc;load b;w=;s=;t=;v=zeros(1,100);D=;F=;v(1)=0.5;%M,N=find(b=1);%a1=min(M);a2=min(N);%b1=max(M);b2=max(N);%o=b1-a1;p=b2-a2;o=sum(sum(b);x1=ones(46,30);x27=ones(27,5);x2=ones(46,30);x28=ones(18,6);x3=ones(40,30);x29=ones(18,6);x4=ones(40,30);x30=ones(20,5);x5=ones(32,29);x31=ones(11,9);x6=ones(32,29);x32=ones(11,9);x7=ones(25,22);x33=ones(11,9);x8=ones(25,22);x34=ones(24,4);x9=ones(24,21);x35=ones(24,4);x10=ones(24,21);x36=ones(16,6);x11=ones(31,13);x37=ones(15,6);x12=ones(21,15);x38=ones(15,6);x13=ones(21,15);x39=ones(15,6);x14=ones(26,11);x40=ones(14,6);x15=ones(26,11);x41=ones(20,4);x16=ones(26,11);x42=ones(20,4);x17=ones(26,11);x43=ones(12,6);x18=ones(26,11);x44=ones(12,6);x19=ones(26,11);x45=ones(5,10);x20=ones(19,15);x46=ones(4,11);x21=ones(31,8);x22=ones(34,5);x23=ones(34,5);x24=ones(24,7);x25=ones(27,5);x26=ones(27,5);A=x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12,x13,x14,x15,x16,x17,x18,x19,x20,x21,x22,x23,x24,x25,x26,x27,x28,x29,x30,x31,x32,x33. x34,x35,x36,x37,x38,x39,x40,x41,x42,x43,x44,x45,x46;for l=2:10for e=1:46 z=rand(1); if z=0.6 Ae=rot90(Ae); m,n=size(Ae); else m,n=size(Ae); endfor i=1:103-m for j=1:117-n r=b(i:i+m-1,j:j+n-1)&Ae; if sum(all(r)=0 b(i:i+m-1,j:j+n-1)=zeros(m,n); s=s;i,j; w=w,m*n; break; else continue end if sum(all(r)=0 break end end if sum(all(r)=0 break; endend if i=103-m&j=117-n t=t,e; else v(l)=sum(w)/(o*p); endendif v(l)v(l-1) Y=v(l); U=b;endenddisp(最大利用率为);disp(Y);(2)第二张牛皮模板排料程序clear;clc;load b;Q=;w=;s=;t=;o=sum(sum(b)%o=b1-a1;p=b2-a2; x1=ones(46,30);x18=ones(18,6);x2=ones(40,30);x19=ones(18,6);x3=ones(40,30);x20=ones(20,5);x4=ones(32,29);x21=ones(11,9); x22=ones(11,9);x5=ones(24,21);x6=ones(24,21);x23=ones(16,6);x7=ones(31,13);x24=ones(15,6); x25=ones(15,6);x8=ones(21,15);x26=ones(15,6);x9=ones(26,11); x27=ones(20,4);x10=ones(26,11);x28=ones(12,6);x11=ones(26,11);x29=ones(12,6);x12=ones(26,11);x13=ones(19,15);x14=ones(31,8);x15=ones(34,5);x16=ones(34,5);x17=ones(24,7);A=x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12,x13,x14,x15,x16,x17,x18,x19,x20,x21,x22,x23,x24,x25,x26,x27,x28,x29;for e=1:29 z=rand(1); E=(z=0.6);Q=Q;E; if z=0.6 Ae=rot90(Ae); m,n=size(Ae); else m,n=size(Ae); endfor i=1:103-m for j=1:117-n r=b(i:i+m-1,j:j+n-1)&Ae; if sum(all(r)=0 b(i:i+m-1,j:j+n-1)=zeros(m,n); s=s;i,j; w=w,m*n; break; else continue end if sum(all(r)=0 break end end if sum(all(r)=0 break; endend if i=103-m&j=117-n t=t,e; else v=sum(w)/o; endenddisp(最大利用率为);disp(v); (3)第三张牛皮模板排料程序clear;clc;load b;Q=;w=;s=;t=;o=sum(sum(b);%o=b1-a1;p=b2-a2; x1=ones(40,30);x10=ones(20,5); x11=ones(11,9)；x2=ones(24,21);x3=ones(24,21);x12=ones(16,6);x4=ones(31,13);x13=ones(15,6);x14=ones(15,6);x15=ones(15,6)； x5=ones(26,11);x16=ones(12,6);x6=ones(26,11);x7=ones(19,15);x8=ones(31,8);x9=ones(34,5);A=x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12,x13,x14,x15,x16;for e=1:16 z=rand(1); E=(z=0.6);Q=Q;E; if z=0.6% Ae=rot90(Ae); m,n=size(Ae); else m,n=size(Ae); endfor i=1:103-m for j=1:117-n r=b(i:i+m-1,j:j+n-1)&Ae; if sum(all(r)=0 % b(i:i+m-1,j:j+n-1)=zer