摘 要

本文研究的目的在于改进在玻璃加工企业中二维平面切割的优化问题。通过对排样优化问题的算法的求解方法进行分析与改进，在玻璃分割中优化排样分割算法，实现材料利用率的最大化，从而降低产品的生产成本，在实际生产中具有非常广泛的应用。因此，研究二维最优化玻璃分割算法具有巨大的经济效益，解决这个最优化难题成为当今世界的一个前沿课题和热点问题。

本文的研究内容如下：

1.本文首先讲述了本文的主要研究内容，阐述了国内外在二维最优化玻璃排样分割算法方面的研究现状，简要概括了设计的任务和研究手段，对比了不同的算法之间的优劣并采用了动态规划算法作为本文的基本研究手段。

2.本文接着对二维玻璃切割系统的初步框架进行设计，并对算法实现方案进行了选择。在计算机上，使用C语言开发编程实现了本文研究的算法，并进行了实验仿真。实验结果表明改进的动态规划算法能够有效地求解二维玻璃排样切割问题，实现了排样分割的最优化设计。

3.最后，本文就对于二维最优化玻璃分割算法设计研究的所做的工作进行了归纳与总结，且就本文研究问题的特点和所得设计结果进行分析，得出实践性的结论。

关键词：排样分割问题，C语言，动态规划算法

ABSTRACT

The purpose of this study is to improve the optimization of two-dimensional planar cutting in glass processing enterprises. Layout optimization problem based on the algorithm of the method of analysis and improvement, optimization layout segmentation algorithm in the glass partition, maximize the utilization ratio of materials, so as to reduce the production cost of the products, has a very broad application in practical production. Therefore, it is of great economic benefit to study the two dimensional optimal glass segmentation algorithm.

The research content of this paper is as follows:

1. This article first tells the story of the main research content of this article, both at home and abroad is expounded in the two-dimensional layout optimization glass segmentation algorithm, the current status of briefly summarized the design task and the research method, compared the advantages and disadvantages between different algorithm and USES the dynamic programming algorithm as the basic research methods in this paper.

2. Then, the preliminary framework of the two-dimensional glass cutting system is designed and the algorithm implementation scheme is selected. On the computer, the algorithm studied in this paper is realized by using C programming language, and the experiment simulation is carried out. The experimental results show that the improved dynamic programming algorithm can effectively solve the problem of two dimensional glass layout cutting and realize the optimal design of layout division.

3. At last, in this paper, the glass segmentation algorithm for two dimensional optimization design research has carried on the induction and summary of the work done by, and the problems in this paper, we study the characteristics and the design results were analyzed, and practical conclusion.

Key words: layout segmentation problem, C language, dynamic programming algorithm

目录

1绪论 1

1.1背景及研究意义 1

1.2研究现状及趋势 2

1.2.1国外研究现状 2

1.2.2国内研究现状 2

1.2.3研究趋势 3

1.3本文研究内容 4

2单一排样分割分析 5

2.1单一排样分割概念 5

2.2单一排样分割存在的问题 6

3 排样分割算法设计 7

3.1 动态规划算法 7

3.2 动态规划基本思想 8

3.3背包问题的求解方法 8

3.3.1背包问题描述 8

3.3.2背包问题的数学模型 9

3.3.3背包问题的求解 9

3.4优化排样算法模型 9

3.5动态规划算法的实现 11

3.6动态规划算法的改进 12

4分割算法实现与验证 13

4.1 Visual C 6.0开发环境介绍 13

4.2功能模块 14

4.3单一排样分割软件实现 15

4.3.1界面菜单功能介绍 15

4.3.2实验测试流程 17

4.4 实验结果分析 21

4.4.1无约束排样结果分析 21

4.4.2无约束分段排样结果分析 22

4.4.2板材分割利用率影响因素分析 22

5总结与展望 23

参考文献 24

附录 25

致谢 26

1绪论

1.1背景及研究意义

切割问题是在现实生活中经常能够遇到的一类问题。随着人民生活水平的提高，人们对各种装饰材料的需求大大增加，尤其是建筑行业的快速发展使玻璃行业越来越受到人们的重视；但是，国内大多数企业切割排版主要还是依靠人工来实现，这样必然会造成工作效率低以及材料浪费严重等后果，企业的发展必然会受到限制。在在这样的情形下,由此产生了许多新兴的高科技产物，其中最重要的产物之一就是计算机辅助排样(CAN)。目前，计算机辅助排样技术已经日益成熟并且被广泛地应用于各种材料的排样分割生产之中，它通过提供最优化的排样分割方案，可以充分节约原材料，从而达到减少生产成本、提高企业利润的目的。

在本文中，研究二维最优化玻璃分割算法的意义在于实现玻璃排样分割的最优化，通过设计生成一个最优化算法，计算得出相对最好的排样分割方案，以提高材料的利用率、减少排样布局的时间和优化切割的路径，这样就能降低产品生产成本，提高经济效益。第一，可以提高材料利用率；在很多企业生产中，玻璃排样分割都是靠人工操作这种传统的方法实现的，人工排样主要是靠个人的经验和技能熟练程度进行判断的，要最大限度地提高排样布局效率和材料利用率是很困难的。所以，人工排样的方法受到个人的工作状态和工作能力的影响与限制，难以给出材料利用率最优的排样分割方案。而通过设计玻璃最优化排样分割算法，能够利用计算的超级强大快速的计算能力，计算出质量最优的排样分割方案，从而可以节约原材料，提高经济效益。第二，可以减少排样工作量；当使用人工进行排样计算吋，为了得到一个较好的排样方案，往往需要较长时间的反复考虑计算。而通过设计最优化排样分割算法，就可以在很短的时间内完成排样的任务，并且可以简单地得到最优的排样方案。第三,可以化简切割工艺；在实际排样过程中会遇到很多的复杂问题，比如会遇到这样的情况，同时存在许多材料利用率较为接近的排样优化方案，那么把材料利用率最高、切割工艺最简的方案称作为最优排样方案^[1]。研究设计最优化排样分割算法，就能从这几种最优的排样分割方案中，选择出切割工艺相对更简单的排样方案，从而减少切割工作量。因此，本文对二维最优化玻璃分割算法的研究是具有重要意义的。

1.2研究现状及趋势

1.2.1国外研究现状

国外对于排样分割问题的研究开始比国内的较早，最早关于切割（GSP）问题的研究开始于1939年，在这个时候Kantorovich就提出了关于一维下料的问题；然后在20世纪60年代初期，Gilmore和Gomory等人相继发表了四篇著名的文章， 他们提出了用列生成法求解一维CSP问题，并对二维CSP问题进行了开创性的探讨，提出了一维下料优化方案和二维排样优化问题^[2]；70年代至今，众多学者针对排样问题的一个或几个方面提出算法和解决方案，由于毛坯在单张板材上的排样问题也是NP完全问题，再加上实际中条件的限制也会使问题更加复杂，因此排样问题具有多样性特点，直到现在仍没有很好的标准方法来解决这个问题。但是，由于近代以来计算机技术的迅速发展和使用，诸如线性规划、运筹学理论的发展，使得CSP问题的研究有可能付诸于生产实践，导致这个优化难题重新引起众多学者的研究兴趣和广泛关注，随着研究领域的日益拓宽，已经取得了大量实践性研究结论和成果^[3]。从此，这个领域不同应用研究的文章数量迅速增长，涉及面不断拓宽，方法和技术不断完善，各种求解方法迅速出现并蓬勃发展，不断在各个领域学科的杂志期刊上发表出来。1988年,在EURO IX/TIMS XXVIII国际会议上，为了对CSP问题进行更深入的研究，专门成立了一个下料问题兴趣小组SICUP( Special Interest Group on Cutting and Packing Problem)。

在这过去的几十年里，尽管已经做了很多关于排样分割问题的研究，但由于NP完全问题的复杂性和多样性，在理论上依然没有彻底的解决方法，所以排样优化问题依旧是人们未来研究的热点问题之一。

1.2.2国内研究现状

国内对于排样分割问题的研究始于20世纪80年代，起步相对于国外较晚，研究学者主要集中于各个高等院校和研究所。对冲裁件排样的研究从20世纪80年代开始，以华中科技大学、上海交通大学的研究工作最具有代表性，主要有人机交互法、边界加密方法和不相交判别法等，借助人机交互方式进行图形的旋转和平移以达到优化排样的目的，围绕着冲裁件自动排样，将零件处理为多边形的方法或采用碰撞算法直接对零件进行排样，对一维下料问题进行相关的求解等。