不规则皮件排料方案研究

1、不规则皮件排料方案研究摘要本文针对牛皮模板的排料问题，建立了排料优化模型和组合排料优化模型，并设计 了相应的排料算法，获得了牛皮利用率最大时的排料方案。本文首先将所给牛皮、沙发和餐椅模板的图像比例尺统一化，其次将图像网格化， 最后矩阵化图像，得到牛皮模板的换算矩阵和皮件模板的最小包络矩形的换算矩阵。问题一，要求给出n张牛皮模板的排料算法，使牛皮的利用率最大化，考虑到实际 生产过程中批量化生产，本文以2am2的牛皮模板为例，给出制作一套沙发的排料算 法。利用matlab软件，将图像矩阵二值化为0和1的换算矩阵，将牛皮模板划分为可 放置和不可放置两个区域，设包络矩形的放置方向为随机量，通过换算矩阵

2、z间的计算, 将所有沙发模板安排完全，得到了每张牛皮的利用率。经过多次模拟，得到使牛皮利用 率最大的排料方案，当使用2.4加$的牛皮模板时，需要3张牛皮，每张利用率分别为 87.64%, 86.83%, 75.52%,牛皮总的利用率为帀二85.68%。问题二，在问题一模型的基础上进行改进，仍然以2.4加彳的牛皮模板为例计算。首 先按照问题一的方案裁剪40张牛皮得到13套沙发，剩余1张整牛皮和额外的8张整牛 皮裁剪餐椅皮板，然后采用将沙发裁剪余量和完整牛皮模板组合使用和只利用9张完整 模板两种方法设计排料方案，通过matlab软件计算，在两种情况下均可生产27把餐椅, 但在余量模板和完整模板配合

3、使用情况下可获得更多规整余量。木文针对牛皮排料的问题，建立了排料最优化模型，给出了排料算法，得到了牛皮 利用率最大时的排料方案，为皮件排料问题提供了可行方案。关键词：排料优化模型组合优化模型换算矩阵模拟仿真matlab软件一. 问题重述在实际生产生活小裁剪是必不可少的，裁剪的好坏、利用率的高低，直接影响生产 厂家的经济利益，首先定义以下三个概念：1、牛皮：整张，未裁剪的牛皮原料，经过数码取像技术转化成cad文件格式的 二维区域；2、皮板：最终产品的模板，一般由硕纸板制成的，用于裁剪。产品设计完后，经 过数码取像技术转化成cad文件格式的二维区域；3、皮件：由皮革缝制成皮套，再通过其他工艺加工成

4、的最终产品（例如皮包鞋、 皮沙发等）。根据以上定义，本问题研究的对象是数码二维区域。附件提供了牛皮模板、沙发模 板和椅子模板，根据制造沙发和椅子的各个部位的皮模板可以制造一把皮沙发和一把餐 椅。在实际生产中经常要求最后一张牛皮的利用率要尽可能大，解觉以卜两个问题：1、假设n张牛皮的模板都和提供的两张一样，试建立数学模型，在厂家皮单确定 的情况下，确定针对n张牛皮的排料算法，要求使牛皮的利用率最大化；2、在某批沙发订单确认的情况下，在采购了 40张牛皮裁剪结束之后（发现有一定 余量），插入一个餐椅皮件订单。利用裁剪的余量，再增加8张牛皮，计算出增加的餐 椅数量。二、基本假设1. 不考虑裁剪牛皮的

5、刀口宽度。2. 裁剪没有失误，牛皮无损坏。3. 所有牛皮原料都完整。4. 假设第二问中的40张牛皮和8张牛皮均为2.4平方米。5假设使用相同规格的牛皮制作沙发，不考虑套排。三、符号说明1. nj一表示与牛皮模板j的数量（）= 1,2）；2. q表示牛皮模板丿的实际而积（j = l,2）；3. 一表示牛皮模板）的集合（）= 1,2）；4. （兀,）表示沙发模板中第i个部件的左上顶点坐标（i=l,2,3,46 ）；5. r-0-l变量，表示沙发模板中第i个部件包络矩形的方向等于0表示横放，等于1 表示纵放（i=l,2,3,：46 ）；6. 厶一表示沙发模板中第i个部件包络矩形的换长（i=l,2,3

6、,：46）；7. 比一表示沙发模板屮第i个部件包络矩形的换宽（i=l,2,3,46）；& s,表示沙发模板中第i个部件包络矩形的换面积(i=l,2,3,46)；9. 色一表示沙发模板屮第i个部件的占用空间集合(i=l,2,3,46)；10. p-0-l变量，表示沙发模板中第i个部件是否排在当前模板(i=l,2,3,46)；11. gj一表示牛皮模板丿的余量部分的而积()= 1,2)；12. °表示牛皮模板/的余量部分占用空间集合(j = l,2) o四. 图像与数据预处理牛皮模板及皮件齐部件的几何形状都是二维不规则的，在排料中，耍获取模板和各 部件的几何信息，本题将信息以图像

7、的形式给出，因此，需要对所给图像进行处理，包 括图像的网格化处理和获得图像的数据矩阵。图像处理具体过程见图4-1 o络矩形矩阵图41图像处理过程4.1图像网格化(1) 离散化处理 利用matlab软件处理图像如下：step 1读取灰度图像，获得灰度图像矩阵；step 2将图像二值化，获得二进制矩阵；step 3以20mm为网格宽度改变二进制矩阵，将图像网格化，使边界正交化； step 4获得图像的多边形区域。(2) 网格大小的确定 如以单像素代表长度为网格基准，软件无法完全显示图像，为后续处理带来不便, 再考虑到精度的要求，实际20mm的长度为网格的宽度绘制网格。(3) 比例尺的统一将图像网格

8、化处理z后，根据(4.1)确定出每张图像中一单位像素对应的实际距 离，进而使实际距离相同，使确定的比例尺统一化。换算面积二换算长度)2实际而积实际长度(4.1)4.2换算数据矩阵换算数据矩阵是指将图像网格化处理z后，以单位网格的大小作为数据矩阵的元 素，数据矩阵为包含0和1的二维矩阵，矩阵中1用來表示该位置包含在图像轮廓内。 4.2.1牛皮模板换算数据矩阵将牛皮网格化处理之后，通过矩阵可以表示网格化之后图像的信息，矩阵中有1元 素的位置则是牛皮模板的内部位置。所有1元素所在点组成牛皮模板的空间集合。 4.2.2皮件模板换算数据矩阵(1) 最小包络矩形将沙发各部件的边界正交处理z后，齐部件的几何

9、信息已改变为多边形，首先将凹 多边形转化成凸多边形，进而确定岀46个凸多边形。对于确定的46个凸多边形，因为最小包络矩形至少有一条边与该多边形的某一条 边重合，具有n个顶点的凸多边形，共有m 1条边,所以可以作出ml个外接矩形。依 次计算这nl个外接矩形的面积，之后比较大小，就可以确定所有46个部件的最小包 络矩形。计算包络矩形参数的步骤如下：step 1计算第i条边与x轴的夹角，可以根据连接第i条边两端的顶点坐标求得， 然后以顶点i为屮心对多边形进行旋转，使第i条边与x轴平行，则第i个最小包络矩 形的底边与旋转后的第i条边重合。step 2多边形旋转后更新所有的顶点坐标，更新方式按式进行，然

10、后在所有已更新 坐标值的顶点屮搜寻最大和最小的x值以及最大的y值。cos。 sin&x一 sin。 cos。step 3计算最小包络矩形的面积® = ()max - ymin)x(xmax -xmin),同时记录下矩形的长i严 max()爲一儿加，xmax - xmin),短边 wj = min(ymax - ymin,xmax 一xmin)。依次循环执行上述步骤直到ml个包络矩形全部求出，再逐个比较面积，最小的就 是该多边形的最小包络矩形。同时记录数据s严s, £,=<.,比二叱。利用matlab软件，按照step 1- step 3的顺序计算求得沙发各部件

11、包络矩形的参数 如表41所示。表4-1沙发各部件包络矩形参数编号原始面积换长换宽编号原始面积换长换宽10.0584275240.2035242120.0584275250.126211530.1033318260.126211540.0398119270.1134261150.0415244280.1134261160.03781192901134261170.0387156300.1134261180.0379205310.1134261190.0453186320.11342611100.03842443300225105340.37153229120.02991

12、26350.37153229130.0299126360.47934030140.0378119370.4793403()150.0332146380.54114630160.0406166390.54114630170.0731345400.11291915180.0584275410.0731345190.0297204420.0631247200.0297204430.0453186210.21162522440.0387156220.21162522450.0387156230.20352421460.019114说明：1.原始面积单位为平方米。2.换长与换宽的单位是20mmo通过相同

13、的方法，利用matlab软件求得餐椅各部件的包络矩形参数表如表42所示。表42餐椅各部件包络矩形参数编号原始面积换长换宽10.1485231720.02227230.008910240.1159211450.0788171260.0691171070.01517280.0891221090.03711091()0.0294145说明：1.原始面积单位为平方米。2.换长与换宽的单-位是20mnu(2) 包络矩形的换算矩阵包络矩形的换算矩阵为lixwi维的单位矩阵，表示皮件第i个部件的轮廓内部空间, 该矩阵决定了排料时各部件所要占用的空间。五. 问题分析5背景概述优化排料通常是指在一组给定尺寸的原

14、始板材上，尽可能多地排放需要的二维零件 产品，使得板材利用率最大，以减少废料。排料是优化组合的一类典型问题，在工业生产 小具有较高的实用和推广价值。提高板材利用率将会降低企业的生产成本，会给企业带 來经济效益。所以，排料问题的研究具有重要的经济价值。从计算复杂性理论来看，排料问题属于具有较高计算复杂性的一类问题np完全问 题，np是nondeterministic polynomial的缩写，即为非确定型多项式的意思。对丁，np 完全问题，至今还没有找到多项式时间算法，因而，求其有效的近似解法是必由之路。 对于这类问题，以n前已经成熟的计算理论和算法，或者根本无法求解，或者其求解的 计算量是爆

15、炸性的。所以，如何找到一种有效的排料算法具有重要的经济价值和理论价值。5.2问题一的分析木问题为在订单确定的情况下，要求我们针对n张牛皮，建立数学模型，确定皮件 的排料算法，使牛皮的总利用率最大，这是寻找平面最优布局的优化问题。在实际生产中，工厂均是规模化生产，因此本题实际要求我们确定制作单张皮件的 排料算法，以利于规模化生产。本题要求牛皮总利用率最大化的而提下，还要求使最后一张牛皮的利用率最大，厂 家要求最后一张牛皮剩余的部分尽量规整，利于再利用，则最后一张率用率最大包括剩 余牛皮的而积最大即余量最大和剩余部分形状尽可能规则两个部分。因此确定本题为双 目标优化问题，使总利用率最大的目标优先于

16、使最后一张牛皮的利用率最高的fi标。解决本题性质的双目标问题，可以通过两个阶段，建立不同的模型实现。(1) 第一阶段模型首先明确木阶段的口标是：确定制作单-张皮件的排料算法，使牛皮的总利用率最大 化。牛皮的利用率为皮件总而积与牛皮总而积和牛皮余量而积z差的比值，表述为：利用率=皮件总面积牛皮总面积-牛皮余量面积其次，根据题意的要求，以皮件各部件在牛皮原料上的位置作为决策变量。再次，根据皮件各部件必须在牛皮原料上，并冃在排料屮不能重叠，以及各部件均 要排料一次等限制，确定排料的约束条件。以此建立优化模型，因建立模型中包含集合等元素，普通的算法不能直接求解。考 虑将算法进行如下改进：将皮件齐部件按

17、照面积大小，从牛皮左上角开始，依次从左至 右，从上至下在牛皮上排布，使用模拟仿真的方法，对问题进行求解。(2) 第二阶段模型明确本阶段的目标是使最后一张牛皮的利用率最大，引进余量的面积，使用余量面 积的大小描述最后一张牛皮的利用率，余量面积越大，则对应的利用率越大。同样以皮件各部件在牛皮原料上的位置作为决策变量，根据皮件各部件必须在牛皮 原料上，各部件在排料中不能重叠，各部件不能与余量部分重叠以及各部件均要排料一 次等限制，建立优化模型。该阶段同样对解法进行改进，改进方法与第一阶段和同。通过两阶段模型，确定皮件的排料方式。根据牛皮模板的利用率的定义，计算牛皮 模板的利用率。5.3问题二的分析本

18、题是在釆购了 4（）张牛皮裁剪结束z后，利用裁剪的余量，再增加8张牛皮，要 求我们计算出增加的餐椅数量。因第一问模板会有余量存在，所以木问题是在模板数量 增加的情况下重新设计排料算法。制作餐椅同样要求模板的利用率最大，本问题是以餐椅模板部件的位置为决策变 量，以模板利用率最高为目标的组合优化问题。首先通过面积的分析，可以确定余量模 板不能制作所有的餐椅模板部件，则考虑将余量模板与原始模板组合排料。六、问题一模型的建立与求解6模型的建立根据问题分析，本问题为双目标规划问题，要通过两个阶段求解。首先根据各部件的面积和牛皮模板的面积，计算出制作一张沙发时所需最少模板数 量zs,则为前（zsj）张牛皮

19、原料排料建立第一阶段的优化模型，为最后一张牛皮的 排料建立第二阶段的优化模型。6.1.1第一阶段优化模型的建立（1）决策变量的选择根据问题分析，选择沙发模板各部件在前（zsj）张牛皮模板上的位置（心牙），以 及各部件的放置方向e为决策变量。（2）优化目标的确定根据问题分析，目标为牛皮模板的利用率z,本阶段中牛皮模板余量的面积为零， 则，利用率为各部件的面积之和与牛皮的总面积之商，表述为：46z二 （6）j=i（3）约束条件的表达（1）沙发模板各部件要放置在牛皮模板中，记d为第i个模板的占用空间集合，为 第丿个模板的集合，则此约束表述为：baj（62）其小心1,2,46;） = 1,2。当皮件模

20、板的左上顶点为（不,开）时，其对角顶点的坐标为x- +町厶+ （1 町）叱,yi rwj （1 町）厶），因此集合bj表不如卜:bix,yxi<x< xi + i;.l. + (1 - z;-, y. - (1 - t;- )£,- < y < y(2) 沙发模板屮任意两个部件不能冇重叠部分，表述为：bhbk =(6.3)其中h,k = ,2,，46;h工k。（3）对摆放方式的约束，用01变量个0表不横放1表示竖放其中i = 1,2,46 o模型的建立根据（1）、（2）和（3）,第一阶段的优化模型表述为:max462；=1st他 g =0)ri其 111 i

21、= 1,2,46; j = 1,2； h,k = 1,2,46; h# k。6.1.2第二阶段模型的建立1) 决策变量的选择根据问题分析，选则沙发模板各部件在第zs张模板上的位置（兀,开），以及各部件 的放置方向7；为决策变量。2）优化冃标的确定根据问题分析，目标为牛皮模板余量而积q最大，表述为:max gj（6.4）3）约束条件的表达（a）沙发模板各部件要放置在牛皮模板屮，记色为第i个模板的占用空间集合，为第丿个模板的集合，则此约束表述为:b u其中心1,2,46;/ = 1,2。(b)沙发模板中任意两个部件不能自重叠部分，表述为:bb严其中力,r = 1,2,46; h工k o(6.5)(

22、6.6)(c)牛皮模板余量部分在牛皮模板屮，表述为:dj匸(6.7)其中)= 1,2。(d)牛皮模板余量部分与沙发任一部件不能有重叠部分，表述为:(6.8)其中i = 1,2,- -,46 o(e)对摆放方式的约束，引进01变量衣示横放 衣示竖放其111 z = 1,2,-,46 o4) 模型的建立根据(1)、(2)和(3),第二阶段的优化模型表述为max gjbjgb严 s.t. dj u aydfb严ri其中 j = 1,2,46;丿=1,2； h,k = 1,2,46;/?工 k o6.2模型的求解6.2.1算法介绍i大i为原问题变量及约束数据为集合形式，使用普通的算法不能对问题进行求解

23、，所 以对问题解法进行改进。根据约束条件各个皮件互不重叠，冃不超过牛皮的范围等限制，将将皮件模板按照 面积从大到小的次序先后进行排序，按照面积的大小安排排料。排料过程中，将皮件部 件从左至右，从上至下依次搜索，并将各个皮件的横竖放置作为随机变量，多次重复排 放，利于较优解的寻找。算法流程见图61。开始牛皮矩阵alta.ii）和皮件矩阵l初始化结束:图61算法流程图622结果及说明通过matlab软件，计算出沙发各部件的排料方式如表6-1所示。 表61沙发排料方式编号第几牛 皮模板中横坐 标纵坐 标是否旋 转编 号第几牛 皮模板中横坐 标纵坐 标是否旋 转11138202433760021625

24、102514160133691612622214043768602721376053771212812217061531912916240073814313025679083158403136149192619003232217010162560333561811117413134246500122721403515660113325110362462001427991037316300151251103811630016187151392163011728615140361751181629204137647119118870422785012021887043285501211166004

25、437728122162180453739502331660146148190注：横纵坐标的单位仍为换算长20cmo由上表可知:1,2,6,10,11,15,16,18,19,21,22,25,28,29,35,3&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 个部件排在第三张牛皮中。每张牛皮模板上的排料结果如图62、6-3> 64所示。图6-2第一张牛皮排料情况图6-3第二张牛皮排料情

26、况图6-4第三张牛皮排料情况通过计算,第一二三张牛皮模板的利用率分别为87.64%, 86.83%, 75.52%。计算最后一张牛皮模板的剩余面积大小为0.1976 /n2 ,则牛皮的利用率”为(=)85.68% o7.2-0.1976七、问题二模型的建立与求解7.1餐椅数量最优化模型的建立根据问题分析，本问题是在第一问的基础上，增加牛皮模板的数量，在牛皮数量限 制的情况下计算能够多生产餐椅的数量。因制作单位餐椅的模板不再固定，存在多种组 合模板，因此为组合优化问题。7.1.1余量模板试排料第一问得到三种新的模板，即裁剪沙发皮件后的三种余量。将新增三种模板的矩阵 分别使用第一问中的程序进行尝试

27、性排版，发现这三种模板只能排下椅子皮件中最小的 两个皮件。而椅了皮件中面积最大的八个无法再原余料的基础上进行排放。已购置40张牛皮可以满足13张沙发的订单，在此情况下仍剩余一张整牛皮模板。 因此各模板数量为模板1和1共有9张，模板3,4,5各有13张。7.1.2模型的建立建立以餐椅的位置和放置方向为决策变量，以牛皮利用率最大为冃标的优化模型。46工s,maxz 2曰djcj>1匸s.t. < bh cl 以二jc屮 r = l,2,-,10; j = 1,2,3,4,5； hyk = 1,2,-,1o;a k。7.2模型的求解7.2.1混合排料余量的排料通过matlab软件计算，余

28、量3种模板共计39张模板共制作餐椅的9,10部件数量为 39张。(2)整牛皮的排料通过matlab软件计算,整牛皮制作27张1-8部件,因1-8的部件的数量小于9,10 部件的数量，因此共计制作27张餐椅。余量排料图见图71。图7-1余量模板排料情况7.2.2单张整牛皮单独排料在模板1和2上制作整数张餐椅。通过matlab软件求解，计算制得餐椅数量为27张。排料方案见图72。图7-2整牛皮模板排料方案根据分析，直接用9张也可以做出27张餐椅，比较土 72和71与63,结果表明, 按照第一问余量排料之后，在制作餐椅之后，剩余的余量部分明显优于原剩余余量。 因此选择混合排料方案更优。综合得到排料方

29、案见表7-1 o表71餐椅在原始模板上排料方案编号横坐标纵坐标是否旋转编号横坐标纵坐标是否旋转椅115330椅655300椅115520椅668701椅138201椅672141椅263960椅830690椅278681椅852430椅279401椅852531椅416691椅968870椅424121椅972310椅438431椅930791椅555180椅1038640椅556751椅1074401椅562531椅1074541八、模型的评价和改进本文首先将图像信息处理成矩阵格式，并通过网格化和换算矩阵的方法，使牛皮和 皮件均转化为与其实际尺寸相关的矩阵，使该问题转化为一个与矩阵运算相关的

30、数学问 题。以集合和矩阵运算为理论基础，首先凭经验给出一些排放规则（这样利于提高运算 效率），并通过计算机模拟仿真实验，比较各皮件随机放置的牛皮利用率，找到一个较 优方案，确定各皮件排放。本文模型可以推广到如服装、皮革和机械行业，对实际生产中不规则零件的排料问 题提供指导作用。依据木文给出的方法及原理，再根据实际需要，可以提高所选用的精 度，并冃，可以不必求出最小包络矩形，只需用一个矩阵表示能够放置该皮件的任意一 个矩形即可，通过判断矩阵值的匹配与否，进行编程的改进，这样更加切合实际。若需要尽可能提高牛皮利用率，还可以结合遗传算法，模拟退火算法，人工神经网 络算法等启发式算法，进行编程求解，这

31、样编程难度虽然有所增加，但是效率更快，利 于较优解的搜索。九、参考文献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(l,100);d=； f=|j； v(l )=0.5; %

32、m,n=find(b=l); %a 1 =min(m);a2=min(n); %bl=max(m);b2=max(n); %o=b 1 -a 1 ;p=b2-a2; o=sum(sum(b);xl=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(l 1,9); x6=ones(32,29);x32=ones( 11,9); x7=ones(25,22)

33、;x33=ones(l 1,9); x8=ones(25,22);x34=ones(24,4)； x9=ones(24,2 l);x35=ones(24,4)； x 10=ones(24,2 l);x36=ones(l 6,6); x 1 l=ones(31,13);x37=ones(15,6); x 12=ones(21,l 5);x38=ones(15,6); x 13=ones(21,15);x39=ones(15,6); xl4=ones(26,l l);x40=ones(14,6); xl5=ones(26,l l);x41=ones(20,4)； x 16=ones(26,l 1)

34、 ;x42=ones(20,4)； x 17=ones(26,l l);x43=ones(l 2,6); x 18=ones(26,11) ;x44=ones( 12,6); x 19=ones(26, l l);x45=ones(5,l 0); x20=ones( 19,15);x46=ones(4,l 1); 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=xl,x2,x3,x4,x5,x6,x7,x&x9,xl0,xl 1,x12,x13,x14

35、,x15,x16,x17,x18,x19,x20,x21,x22,x23,x24,x25,x26,x27,x28,x29,x30,x31 ,x32,x33 x34,x35,x36,x37,x3&x39,x40,x41 ,x42,x43,x44,x45,x46;for 1=2:10for e=l:46z=rand(l);讦 z>=0.6ae=rot90(ae);m,n=size(ae);elsem,n=size(ae);endfor i=l:103-mfor j=l: 117-nr=b(i:i+m-l ,j: j+n-1 )&a e;if sum(all(r)=0b(i:i

36、+m 1 j: j+n- l)=zeros(m,n);s=s;i,j;w=w,m*n;break;elsecontinueend讦 sum(-all(r)=0breakendendif sum(all(r)=0 break;endendif i>=103-m&j>=l 17-nt=t,e;elsev(l)=sum( w)/(o*p);endendif v(l)>v(l-l)y=v(l);u=b;endenddispc最大利用率为);disp(y);(2)第二张牛皮模板排料程序clear;clc;load b;q=；w=;s=；t=;o=sum(sum(b)%o=b 1

37、 -a 1 ;p=b2-a2;x 1 =ones(46,30)；x 18=ones( 1 &6);x2=ones(40,30);x 19=ones(18,6);x3=ones(40,30);x20=ones(20,5);x4=ones(32,29);x21=ones(l 1,9);x22=ones(l 1,9);x5=ones(24,21);x6=ones(24,2 l);x23=ones(l 6,6);x7=ones(31,13);x24=ones( 15,6);x25=ones(15,6);x8=ones(21,15);x26=ones(15,6);x9=ones(26,l 1);

38、x27=ones(20,4);x 10=ones(26,11) ;x28=ones( 12,6);xl l=ones(26,l l);x29=ones(12,6);xl2=ones(26,l 1);xl3=ones(19,15);xl4=ones(31,8);xl5=ones(34,5);xl6=ones(34,5);xl7=ones(24,7);a= x 1 ,x2,x3,x4,x5,x6,x7,x8,x9,x 10,xl l,xl2,x 13,x 14,x 15,x 16,x 17,x 18,x 19,x20,x21 ,x22,x23, x24,x25,x26,x27,x2&x29

39、;for e=l:29z=rand(l); ae=(z>=0.6);q=q;e;if z>=0.6ae=rot90(ae);m,n=size(ae);elsem,n=size(ae);endfor i=l:103-mfor j=l:l 17-n r=b(i:i+m-l ,j:j+n-1) & a e; if sum(-all(r)=0 b(i:i+m-l j:j+n l)=zeros(m,n); s=s;i,j;w=w,m *n;break;elsecontinueend讦 sum(-all(r)=0breakendendif sum(-all(r)=0 break;end

40、endifi>=103-m&j>=117-n t=t,e;elsev=sum(w)/o;endenddispc最大利用率为);disp(v);(3) 第三张牛皮模板排料程序clear;clc;load b;q=;w=；s=；t=;o=sum(sum(b);%o=b 1 -a 1 ;p=b2-a2;x 1 =ones(40,30) ;x 10=ones(20,5);xll=ones(ll,9)；x2=ones(24,21);x3=ones(24,2 l);x 12=ones( 16,6);x4=ones(3 l,13);xl 3=ones(15,6);xl4=ones(15,6);xl5=ones(15,6)；x5=ones(26jl);xl 6=ones( 12,6);x6=ones(26,11);x7=ones(19,15);x8=ones(31,8);x9=ones(34,5);a=x 1 ,x2,x3,x4,x5,x6,x7,x 8,x9,xlo,x 11 ,x 12,x 13,x 14,x 15,x 16; for e= 1:16z=rand(l);e=(z>=0.6);q=q;ej;if z>=0.6%ae=rot90(ae);m,n=size(ae);elsem,n=size(ae);endfor i=l:103-mfo