矩形木板最优切割方案的设计与实现

邹涵 李涛 朱婷婷

摘要：本文所设计的最优切割方案使用了回溯法和递归算法对最优切割问题进行划分，使木板最优切割问题转化为不同切割方式下木板的最大利用率问题，同时根据切割要求对切割方案进行优化，选择最优方案。

关键词：木板;最大利用率;优化排样;回溯法;递归

中图分类号：TP31 文献标志码：A

文章编号：1009-3044（2019）29-0267-02

1概述

把較大的矩形木板切割成若干个不同规格大小的小矩形产品，在工业生产和家居设计中有着广泛的应用。在木板切割生产过程中因为要完成各种需求的生产任务而极易造成资源浪费，对木板最优切割方案进行设计，可以在生产前得到利用率最高的方案，结合生产任务进行调整，在保证生产任务完成的前提下，节约生产成本，减少资源浪费，提高经济收益。

方案设计可以利用优化排样的方法，传统的优化排样都是人工凭借经验直接进行的，浪费时间并且效果不理想，如今随着科技的发展，已经可以利用智能优化排样也就是计算机辅助优化排样来达到目的。

2问题分析

要想得到木板最优切割方案，需要利用计算机辅助处理，设计出优化排样算法，搜索出使木板利用率最高的方案作为最优方案，本文利用整数规划和回溯法尝试不同方案进行标记，进而得出使木板利用率最高的切割方案。因为产品分割尺寸与木板尺寸多半相差较大，所以需要依据木板尺寸及产品切割尺寸，对切割方案进行筛选。木板分割过程中一款木板所需要分割成的产品的种类也会有所限制，所以需要考虑产品的多样性，同时依照需求进行分割设计，也就是需要考虑优化排样的约束条件。

所谓回溯法，就是按选优条件向前搜索，以达到目标，它采用试错的思想，在前进与回撤的过程中进行标记，直到所有方案尝试完为止，由于木板数量只能为整数，所以规划中的变量限制为整数。它将问题的解空间转化成了图或树的结构表示，然后使用深度优先搜索策略进行遍历，遍历的过程中记录和寻找所有可行解得到最优解。我们用迭代来实现回溯法，提高效率。

在算法设计过程中假设木板厚度和割缝宽度忽略不计，假设分割木板时均按照横向分割（沿着木板长的方向）或纵向分割（沿着木板宽的方向），忽略其他角度的分割方式。即可得出四种切割方式：一是木板横向切割，产品纵向放置;二是木板纵向切割，产品横向放置;三是木板横向切割，产品横向放置;四是木板纵向切割，产品横向放置。模拟图如下图1表示：

这四种方式任意组合便可引申出其他组合切割方式，但是，对于不同产品如何组合切割的问题，还需要采用一些约束条件来寻找出最优方案。

3算法设计

按规定在木板上，分割出多种不同产品，设计优化木板分割方法，记木板原材料长c，宽为K，产品种类为i，产品长为厶，产品宽为W（默认横向为长，纵向为宽），数量为N，则目标函数为：

4总结

本文主要研究的是木板在切割成不同矩形产品时如何使资源得到充分利用，减少资源浪费，文章利用回溯法来辅助优化排样，可以将算法和模型推广到工厂生产或加工等实际问题中，它们常需要将大矩形板材（如钢板、玻璃、印刷电路板、包装纸等）切割成各种形状的小板材，利用计算机辅助处理可以提高工作效率和资源利用率，但本文木板切割时没有考虑到割缝宽度及木板厚度差异，算法模型较为理想化，实际情况中存在误差，所以还需要进一步研究处理。