基于直角坐標(biāo)系的木板最優(yōu)切割方案研究

李澤坤 何騰 侯夢雪

本文主要研究針對不同產(chǎn)品的需求，給出最優(yōu)木板切割方案，使其在滿足不同需求的情況下木板利用率最高或家具廠獲利最大。主要使用C++與MATLAB編程，對所建模型進(jìn)行求解，最終給出木板切割方案圖以及最優(yōu)切割方案。本文以板材左下角為原點，建立二維直角坐標(biāo)系，在該坐標(biāo)系中，每一個矩形產(chǎn)品可通過左上角和右下角坐標(biāo)確定其切割位置，在此基礎(chǔ)上建立數(shù)學(xué)模型。通過兩種尋優(yōu)切割規(guī)則，使目標(biāo)利用率盡可能大，求解該模型得出三種利用率最高的切割方案。

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

1.引言

隨著徐州市經(jīng)濟(jì)的快速發(fā)展，居民生活水平不斷提高，住房需求也日益增長，家居也在人們生活中扮演重要角色。徐州某家居廠新購進(jìn)一批長3000mm，寬1500mm的，可做為四種產(chǎn)品原材料的木材。在四種產(chǎn)品各項指標(biāo)已確定的條件下，能否合理利用木材，給出最優(yōu)切割方案直接影響了木材利用率與家具廠利潤收益。

2.模型建立與求解

設(shè)所用板材尺寸為，由題意知，所需毛坯共m種（k=2），第i種毛坯個數(shù)為n，長度為l，寬度為w。針對一塊板材，所能切割的毛坯總量為：（1）

基本目標(biāo)為：所切割毛坯數(shù)盡可能多，以提高板材利用率。

基本約束條件為：根據(jù)實際情況，所切割各毛坯間不會有相互重疊的區(qū)域，且切的毛坯不會有除板材之外的部分。

切割規(guī)則：每個毛坯可被橫向切割或縱向切割。

切割方式：從板材左下角開始，切至板材右上角以結(jié)束板材切割。板材左下角坐標(biāo)為（0，0）。由于毛坯在板材上的位置可由毛坯左上角坐標(biāo)與右下角坐標(biāo)完全確定。設(shè)（x，y）， （x，y）為第i

塊矩形毛坯左上角與右下角坐標(biāo)（其中（），對于本問求解

一塊板材中P1，P3的最佳切割數(shù)量，使得板材利用率最高，相應(yīng)的最優(yōu)切割方案即確定每塊矩形毛坯在板材左上角（x，y），右下角（x，y）坐標(biāo)。

毛坯可采取橫切，豎切兩種切割方式，繼而毛坯兩坐標(biāo)間存在下述關(guān)系：

（2）（3）

其中公式（2）為橫排，公式（3）為豎排。

因此，本文對于每塊毛坯的切割，共有三個自變量，分別為x，y和決定毛坯橫切或豎切的量s，s=0表示橫切、s=1表示豎

切。故（x，y），（x，y）有以下關(guān)系：（4）

設(shè)R，R為任意兩個矩形毛坯，他們的左上角與右下角坐標(biāo)分別為：（x，y），（x，y）; （x，y），（x，y）。為滿足切割時毛坯不可能重疊的條件，則它們必然至少滿足公式（5）所示的四種情況之一并且將公式（4）與（5）聯(lián)立得到（6）。

（5）（6）

同樣，對于任意一個矩形毛坯Ra，其切割不能超出板材之外，則毛坯Ra的坐標(biāo)應(yīng)滿足

（7）

即可得出切割后的最高利用率目標(biāo)函數(shù)：

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

綜上所述，得到優(yōu)化后的切割模型為：（9）

（10）

其中u（x）為跳躍函數(shù)：（11）

從以上建立的數(shù)學(xué)模型來看，該優(yōu)化問題混合且不可微，其中x， y是連續(xù)的，而s，z是離散的，且u（x）不可微。對此類優(yōu)化問題，目前在理論上還沒有有效的求最優(yōu)解的算法，但針對本文的實際問題，滿足上述條件情況下可進(jìn)行近似計算。

在切割過程中為保證盡量可能多的毛坯被切割，故在切割前應(yīng)優(yōu)先判斷是否存在一個毛坯的長l>W`。若存在，則需在可切割毛

坯中選取一種可使剩余廢料最少的切割方式。計算公式如下：（12），且滿足：，而對于所有情況，則按照下面方案選擇毛坯及切割方式;先

針對給定的i求出以下四中方式中的非負(fù)最小值：

（13），其中

進(jìn)而重復(fù)以上兩步驟可得最優(yōu)的三種切割方案如下圖：

方案一 ????????????方案二 ???????????方案三

3.結(jié)論

方案編號

P1的數(shù)量

P3的數(shù)量

參考文獻(xiàn)

[1]劉倩.“一刀切”約束下的矩形件優(yōu)化排樣算法比較與整合研究[D].天津： 河北工業(yè)大學(xué)，2012.

[2]劉淑偉，郭順生，郭鈞，等.基于改進(jìn)遺傳算法的矩形件下料優(yōu)化方法研究[J].機(jī)械制造，2015，53（12）：76-79.

[3]吳忻生，吳超成，劉海明.基于改進(jìn)遺傳算法的矩形件排樣優(yōu)化算法[J].制造業(yè)自動化，2013，35（19）：55-58，155.