基于直角坐标系的木板最优切割方案研究

李泽坤 何腾 侯梦雪

本文主要研究针对不同产品的需求，给出最优木板切割方案，使其在满足不同需求的情况下木板利用率最高或家具厂获利最大。主要使用C++与MATLAB编程，对所建模型进行求解，最终给出木板切割方案图以及最优切割方案。本文以板材左下角为原点，建立二维直角坐标系，在该坐标系中，每一个矩形产品可通过左上角和右下角坐标确定其切割位置，在此基础上建立数学模型。通过两种寻优切割规则，使目标利用率尽可能大，求解该模型得出三种利用率最高的切割方案。

木材利用率;切割方案;切割模型

1.引言

随着徐州市经济的快速发展，居民生活水平不断提高，住房需求也日益增长，家居也在人们生活中扮演重要角色。徐州某家居厂新购进一批长3000mm，宽1500mm的，可做为四种产品原材料的木材。在四种产品各项指标已确定的条件下，能否合理利用木材，给出最优切割方案直接影响了木材利用率与家具厂利润收益。

2.模型建立与求解

设所用板材尺寸为，由题意知，所需毛坯共m种（k=2），第i种毛坯个数为n，长度为l，宽度为w。针对一块板材，所能切割的毛坯总量为：（1）

基本目标为：所切割毛坯数尽可能多，以提高板材利用率。

基本约束条件为：根据实际情况，所切割各毛坯间不会有相互重叠的区域，且切的毛坯不会有除板材之外的部分。

切割规则：每个毛坯可被横向切割或纵向切割。

切割方式：从板材左下角开始，切至板材右上角以结束板材切割。板材左下角坐标为（0，0）。由于毛坯在板材上的位置可由毛坯左上角坐标与右下角坐标完全确定。设（x，y）， （x，y）为第i

块矩形毛坯左上角与右下角坐标（其中（），对于本问求解

一块板材中P1，P3的最佳切割数量，使得板材利用率最高，相应的最优切割方案即确定每块矩形毛坯在板材左上角（x，y），右下角（x，y）坐標。

毛坯可采取横切，竖切两种切割方式，继而毛坯两坐标间存在下述关系：

（2）（3）

其中公式（2）为横排，公式（3）为竖排。

因此，本文对于每块毛坯的切割，共有三个自变量，分别为x，y和决定毛坯横切或竖切的量s，s=0表示横切、s=1表示竖

切。故（x，y），（x，y）有以下关系：（4）

设R，R为任意两个矩形毛坯，他们的左上角与右下角坐标分别为：（x，y），（x，y）; （x，y），（x，y）。为满足切割时毛坯不可能重叠的条件，则它们必然至少满足公式（5）所示的四种情况之一并且将公式（4）与（5）联立得到（6）。

（5）（6）

同样，对于任意一个矩形毛坯Ra，其切割不能超出板材之外，则毛坯Ra的坐标应满足

（7）

即可得出切割后的最高利用率目标函数：

（8），其中zi=0或1。

综上所述，得到优化后的切割模型为：（9）

（10）

其中u（x）为跳跃函数：（11）

从以上建立的数学模型来看，该优化问题混合且不可微，其中x， y是连续的，而s，z是离散的，且u（x）不可微。对此类优化问题，目前在理论上还没有有效的求最优解的算法，但针对本文的实际问题，满足上述条件情况下可进行近似计算。

在切割过程中为保证尽量可能多的毛坯被切割，故在切割前应优先判断是否存在一个毛坯的长l>W`。若存在，则需在可切割毛

坯中选取一种可使剩余废料最少的切割方式。计算公式如下：（12），且满足：，而对于所有情况，则按照下面方案选择毛坯及切割方式;先

针对给定的i求出以下四中方式中的非负最小值：

（13），其中

进而重复以上两步骤可得最优的三种切割方案如下图：

方案一             方案二            方案三

3.結论

方案编号

P1的数量

P3的数量

参考文献

[1]刘倩.“一刀切”约束下的矩形件优化排样算法比较与整合研究[D].天津： 河北工业大学，2012.

[2]刘淑伟，郭顺生，郭钧，等.基于改进遗传算法的矩形件下料优化方法研究[J].机械制造，2015，53（12）：76-79.

[3]吴忻生，吴超成，刘海明.基于改进遗传算法的矩形件排样优化算法[J].制造业自动化，2013，35（19）：55-58，155.