国内外非常活跃的研究课题材料利用率的最大化一直是人们追求的目标（最终版）

第一篇：国内外非常活跃的研究课题材料利用率的最大化一直是人们追求的目标（最终版）

国内外非常活跃的研究课题材料利用率的最大化一直是人们追求的目标。这类矩形件的排料属典型的组合优化问题 具有很高的计算复杂性。所谓有限制二维板材优化下料 就是利用一定规格的板材 为指定尺寸 指定数量和指定纹理的零件下料 在满足配套的和切割便利前提下 使板材的利用率最高。在各行各业的下料中，涉及大量的二维优化下料问题，最优二维下料所涉及的知识面非常广泛，具体的方法种类繁多，应用也极为普遍。传统的下料工作都是人工依靠经验进行的，时间长并且效果不理想。由于生产实际的需要，人们迫切需要利用现代科技来解决这一问题。本文在分析国内外下料问题研究现状基础上，引入 A 玩具企业关于布绒玩具布料二维裁剪的实例，要求使用布料皮数最少来实现公司的既定目标，实现其利润的最大值。本文以 lingo 软件作为计算平台和工具库，计算具有实用价值的二维不规则零件优化下料系统。该系统具有良好的数据接口和友好的交互环境，用户可以方便地输入和调整参数该系统具有快速的响应特性，可以在比较短的时间内得到下料结果。关键词：优化，二维，下料 I 龙麒文：最优二维下料 ABSTRACT Optimized packing has been a very active research topic at home and abroad tomaximize material utilization has been one goal.Such materials are of rectangulartypical combinatorial optimization problems with high computational complexity.The so-called two-dimensional sheet optimization of restricted feeding is the use ofcertain specifications sheet the specified size specify the quantity and texture of theparts under the specified materials and cutting in the supporting facilities to meet theprerequisite to make sheet usage.Under the compound in all walks of life involvinga large number of two-dimensional optimization of cutting stock problem the optimaltwo-dimensional cutting stock a wide range of knowledge involved the specificmethod of a wide range of applications are very common.Under the traditionalmanual work is expected to rely on experience and a long time and are not ideal.Since the actual production needs people urgently need to use modern technology tosolve this problem.This paper analyzes the domestic and international issues of material under thepresent situation based on the introduction of A toy business on the two-dimensionalcutting fabric toys instance requires the least number of fabric skin to achieve thecompanys stated objectives to achieve their maximum profit.This paper lingo software computing platforms and tools as libraries computinghas the practical value of the two-dimensional irregular parts optimized blanks.Thesystem has a good data interface and friendly interaction environment users caneasily input and adjust the parameters the system has fast response characteristicscan be obtained within a relatively short period of time under the expected results.KEY WORDS：Optimization two-dimensional cutting II 2010 届数学与应用数学专业毕业论文 第1章 前 言1.1 下料问题概况1.1.1 下料问题的提出及意义 随着全球资源的日益匮乏，人们对资源利用问题的研究愈来愈重视。最大限度地提高原材料利用率是生产中提高效益的一个重要手段。平面下料，一般是指把表示零件二维轮廓的多个相同或不同的几何图形，在原材料平面区域上找到一个合理布局，使得几何图形之间不出现重叠并且材料利用率几何图形的面积/原材料平面区域的面积最高。在理论上，下料问题涉及到计算几何、运筹学、计算机图形学、逻辑推理等多学科、多领域的知识，属于复杂的组合最优化问题，从数学计算复杂性理论的角度来看，优化下料问题是属于具有最高计算复杂性问题。但是，在很多企业，仍然是在没有下料图的情况下进行人工下料，下料技术人员仅仅凭借自己的经验自由地在材料上下料，一般排出来的并不是最优的方案，并且材料浪费很多有些企业，即使有下料图，但是一方面下料图是人工绘制，费时费力，效率低下，另一方面也不能做到最优化下料，材料利用率仍然不高。而且对规模较大的下料问题，不但手工下料不可能做到真正的优化，即使采用计算机辅助下料也必须开发高效的算法才一能实现利用率相对较高的优化料和切割。因此，企业必须寻求快速高效的下料方式，以提高在市场中的竞争能力。计算机和计算机辅助技术的应用和发展，大大提高了工作效率和质量，使得许多人工难以完成的工作成为可能。上世纪四十年代以来，人们便尝试着提出各种理论，设计不同的计算方法来解决计算机辅助优化下料问题。优化下料问题实际上是一个十分困难的问题，从数学计算复杂性理论看，它属于 NP 完全问题，也就是说在一般情况下，即使是使用很快的计算机，在人们可以接受的时间内也不太可能求出这类问题的最优解。另一方面，由于实际生产的需要，人们又迫切需要利用现代科技对这一问题给出一个能满足生产需要的求解方法。这些方法应该是能以较高的计算速度求出一个近似的解。所谓近似的解是指虽然不是最优解，但接近最优解，并且要比人工下料的效果好，能达到或超过人们所期

望的材料利用率。下料系统的意义，可以归纳为:通过节约材料、减少下料工作量和化简切割工艺，1 龙麒文：最优二维下料最终达到降低产品成本的目的。1.节约材料，提高经济效益 人工下料受人的工作态度、能力等主观因素所限制，很难给出材料利用率最高或者接近最高的下料方案。应用计算机辅助优化下料，可以充分发挥计算机强大的计算能力，经过大量下料方案的比较，选出材料利用率最高或者接近最高的下料方案，以达到节约材料的目的。2.减少下料工作量，加快下料速度 人工下料时，为了得到一个较好的下料方案，往往需要长时间的反复工作。而计算机辅助下料，则可以在非常短的时间内完成下料，并且得到高质量的下料方案。3.化简切割工艺，减少切割工作量 下料时经常遇到这样的情况，存在许多材料利用率接近的下料方案，称其中材料利用率最高的下料方案为最优下料方案。应用计算机辅助下料，可以在大量的达到最优或接近最优的下料方案中，选择切割工艺尽可能简单的下料方案，减少切割工作量。在生产实践中，下料问题广泛出现并等待解决。下料的优劣，直接与材料成本及经济效益有关，而传统的手工下料效率低、劳动强度大，不仅耗费了企业技术人员大量的劳动，而且下料时间长、材料利用率低，降低了企业的生产效率和企业的市场反应能力，增加了生产成本。在激烈的市场竞争中，企业必须降低生产成本、提高生产效率、增强对市场的反映和应变能力，否则，将面临淘汰的威胁。企业必须寻求快速高效的下料方式，以提高在市场中的竞争能力。所以，特别是在零件种类繁多，零件数目巨大，零件形状复杂的情况下，由人工实现下料问题的难度很大，而利用计算机辅助下料可以通过计算机实现优化下料工作，节约材料、减少下料工作量，提高下料效率，最终达到降低产品成本的目的，提高了企业的竞争力。对下料问题的研究已经有很久的历史，特别是在最近的三十年，这类问题已经在操作研究和计算机科学两方面都取得了广泛的关注，原因是它有巨大的理论背景和广泛的应用领域。1.1.2 下料问题的分类及应用 我们通常说的下料问题，指的就是平面下料问题，按照零件的维数可以划分为：一维下料问题、二维下料问题和三维布局问题，其中二维下料问题是研究最广也是最深入的因为研究的侧重点和表现形式不同，广义的说，下料问题又有很多名称，如：下料问题、装箱问题、背包问题、货盘装载、布局问题、最优平衡、内存分配等。随着二维下料问题应用范围的越来越广泛，对其的研究也逐渐加深，从开始的对矩形件的下料问题研究，到对不规则零件的下料.由于二维不规则零件下料问题有着有更广泛 2 2010 届数学与应用数学专业毕业论文的应用领域，所以，也成为了目前下料问题研究的重点和难点。下料问题广泛应用于铂金加工，服装，印刷业中各种图书的排版，航空航天工业，造船业，纺织业，玻璃加工业及交通运输，电子工业中集成电路的排布及仓库零件的存储等。表 l 所示为材料下料问题较多的行业，这些行业构成了下料的主要应用领域： 表 1 构成了下料的主要应用领域 应用分类 举例 金件加工 工业用各种金件、厨房用具和各种家用电器用金件、打字机 电子元件用金件、电动机用硅钢片、造船业金件 服装行业 各种布料、皮革下料，如衬衫、西服、鞋袜、降落伞等。布 料皮革定级中的优化下料等 纸业与玻璃页 办公用纸、财务用纸的裁制等，玻璃的裁制 木材制品 各种家具 印刷业排版 各种书刊、报纸排版、印刷电路板 集装箱装货 将货物组合优化后装入有限空间的集装箱中 型材棒材下料 棒材、角钢、工字钢等各种型材下料，建筑业中钢筋、铝合 金下料 微电子工业 集成电路的排布 军事国防 图形目标的搜索等优化问题 航空航天 航天器仓布局1.2 二维下料问题1.2.1 二维下料问题的分类 二维排料问题大致分为两类：第一类是矩形件下料问题，这类问题可以说是下料问题研究的热点，在工业生产中常见的要求有两类:一是材料数量无限，而要求的矩形件数量是固定的，要求耗用材料量最少二是材料数量有限要求排列出尽可能多的矩形，使废料最少。第二类是不规则件的下料问题。这类问题是下料问题研究的难点，由于零件和材料均为任意形状，切各自的大小均不同，使得每一次排料均得重新下料，因此，增加 3 龙麒文：最优二维下料了问题的难度，所以下料问题的解法只是寻找一个较好的解决问题的方法，寻找近优解而不是最优解。1.2.2 二维下料问题现状综述 优化下料技术的研究理论涉及到线性规划、动态规划、启发式算法以及人工智能等多种学术研究前沿理论，国内外许多学者对二维下料（下料）问题进行了大量的研究，取得了一定的成果。对于学术的深层发展和繁荣，具有一定的推动意义： Lindecrantz1 1964 首 次 提 出 基 于动 态 规 划解 决矩 形 材等 切 割 问题 的算 法。Gilmore amp Gomory 2 3 1965，Beasley 4 1985都是采用的用动态规划解决无约束二维截断切割问题。Viswanathan amp Bagchi5 1993提出了一个从底向上的最佳优先搜索算法，解决约束二维直角截断切割问题。黄继进 6 1994结合动态规划和人工智能启发式搜索的思想，通过修正 Haims 使用动

态规划法实现二维矩形优化排料的算法，提出了带预选搜索步深的二维一刀切矩形优化排料算法，简称 GRSCO 排料算法。Tarnowski71994提出了解决二维 Guillotine 切割问题的多项式（二次）时间算法，将初始问题分解为三个子问题，其中两个由多项式时间内的动态规划求解，还有一个子问题求解的时间为常量。1.2.3 二维下料问题的发展趋势 目前排样问题的主要研究热点集中在二维排样方面，主要包括矩形排样和二维不规则排样问题。矩形排样方面，主要以研究动态规划方法、矩形定位策略和排样方案智能搜索为主。二维不规则排样方面，由于形状的复杂性，还必须考虑几何形状上的表示方法，以及几何区域之间的重叠、靠接、包含等计算同时旋转角度上的随意性使得可行的排样方案数量上为无穷大。因此当前研究趋势主要集中在以下几个方面: l不规则形状的表示和几何计算:不规则形状表示在早期的文献中多采用矩形拟合方法，目前这种方法由于不够精确已很少出现，而主要以点阵图形表示法和多边形表示法为主。其中点阵表示法图形计算较为简单，但是精度较低，时间复杂度较高。多边形表示法目前已成为研究热点，用于快速计算多边形重叠判断和靠接位置的临界多边形 NFP 则是多边形法排样的关键问题。2零件定位策略:从原来的“最左最下”原则，目前己发展到“最低水平线”、最高材料利用率、以及综合评价等原则。3方案编码和解码:从最初的序号编码，目前发展到主要包括序号和角度编码，序号、角度和向限区间编码，坐标点和角度编码，是否允许镜像等因素也逐渐加入到 4 2010 届数学与应用数学专业毕业论文了编码当中。方案的解码负责将编码还原为具体的排样方案，必须和零件定位策略相结合，并在保证零件不重叠等约束条件下得到一个排样方案。4智能搜索算法从最初的启发式算法目前发展到大量采用智能算法例如模拟退火算法、禁忌搜索算法、遗传算法、人工神经网络以及蚁群算法等。1.3 论文背景及主要研究方向1.3.1 论文背景 XX 玩具实业有限公司是集设计、开发、生产、销售为一体的中大型企业，真正具有自主品牌的毛绒玩具企业。XX 公司位于占地面积 10000平方米，环境优雅，交通极为便利。公司现有衣车300 台，裁床机 4 台，打棉机 2 台，冲棉机 3 台，龙门过针机 2 台，电脑绣花机 3 台，及其它配套的设备。产品设计人员均为大专以上设计及相关专业毕业，具有极高的灵感及创意。曾在行业产品设计比赛中多次获得殊荣。开发师们功底同样深厚，都有至少 4 年以上的工作经历，技术娴熟，深谙消费者的理念。公司拥有自己的玩具品牌，有 30 多个系列 1000 多个品种，涵盖毛绒玩具、节日礼品、汽车用品、文具用品、手机玩具、床上用品、儿童玩具、声控玩具、影控玩具、录音玩具、音乐玩具、电动玩具、智能玩具等，产品不仅新颖美观，而且大方实用。公司立足大陆，面向世界。除在国内建立经销加盟的网络外，还和众多知名的公司建立良好的合作关系。在国外公司产品出口欧美、俄罗斯、日本、台湾等国家和地区，公司的品牌产品已经走向五湖四海。公司严格执行 GB6675-2007、GB9832、GB5296.5 和欧洲 EN--71 的标准生产，参照“COC”社会责任运作，于 2009 年通过 ISO9001:2008 国际质量体系认证。公司秉承着以为消费者提供高质、环保、安全、时尚的毛绒玩具的宗旨，引导国内玩具市场的流行趋势，致力于打造中国玩具毛绒玩具第一品牌1.3.2 论文主要研究内容 毛绒玩具是绝大多数小孩子所喜爱的玩具，消费量很大，中国制造的毛绒玩具也很普遍。然而，大部分企业技术含量低，劳动强度大，资源浪费严重，经济效益低。显而易见，只有开发出一种最优化的利用原材料进行合理的下料，就能改变这种资源浪费。经过多次试验比较，我们终于成功开发了这项技术，并成立此玩具公司，进行 5 龙麒文：最优二维下料科学高效利用原材料，合理下料。生产毛绒玩具的过程中，主要生产环节就集中于玩具的裁剪和缝纫问题上面，其中，关于裁剪方面的布料下料最大化利用则是企业利润提升的关键，所以，在这，我们通过所学的专业知识，对二维下料的最大化利用作相关的探讨和研究。现 XX 公司收得一份 10 万毛绒玩具的订单，因公司的生产线和生产原材料即布匹尺寸是固定的，制作毛绒玩具所必需的裁剪样式也是由 5 种裁剪图样所构成：图样【1】3 件、图样【2】3 件、图样【3】2 件、图样【4】1 件、图样【5】1 件。我们要实现公司的的利润最大化利用，就必须通过最优化处理，找到最合适的下料方法，使布匹的利用率达到最大化，以此，我们利用最优二维下料来解决此事。1.4 解决问题的方法与思路 对于二维下料问题，下料方式要满足零件长，宽方向上的套裁，所以远比一维下料复杂且数量大得多.因此，我们希望通过降维启发式方法即通过形成“板条”而把二维下料问题降为一维下料的方法来解决.在此称一维下料的原材料为“条材”，而二维下料的原材料为“板材”.板材与条材的区别在于:条材加工时只考虑长度而板材要同时考虑长、宽.如果把零件成组看待，板条就是这样一种零件组:其在一个方向上的长度等于或近似于原材料的长或宽方向的长度然后在另

一个方向即原材料的宽或长方向进行裁剪.这样，二维下料问题因“板条”的引人便降为一维下料问题。因此，要实现目标，就要分两步进行：第一步：寻求一张原始布皮所能裁剪出的图样的所有方案。第二步：综合所有方案，运用数学知识，构造目标函数，得出最少布匹完成方案。6 2010 届数学与应用数学专业毕业论文 第 2 章 数学模型的建立2.1 数学模型的选择 零件的宽度决定板条的种类，当种类确定后，则要在不超过宽或长度的前提下在原材料上进行板条的布局有若干种.而布局方式一旦确定，就只剩下每个板条内部零件组的组合问题，这时就可利用一维中求解下料问题的启发式多级序列线性优化的方法来解决.其建模的具体过程类似于一维的分层建模思想，即先满足原材料最少要求，再从中选出其中满足时间要求的二维下料最优方案.