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

李澤坤 何騰 侯夢雪

本文主要研究針對不同產品的需求，給出最優木板切割方案，使其在滿足不同需求的情況下木板利用率最高或家具廠獲利最大。主要使用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.