基于背包算法的木板切割方案設計

周康喬，嚴沛鑫，龐國慶

(南通大學，江蘇 南通 226000)

1 問題背景

有一批長為3 000 mm、寬為1 500 mm的木板，需使用切割工具生產(chǎn)出P1、P2、P3和P4四種不同的產(chǎn)品(產(chǎn)品參數(shù)如表1)，在不考慮木板厚度和割縫寬度的前提下，給出：(1)僅切割P1、P2產(chǎn)品時單塊木板利用率最高的切割方案；(2)給定100張木板，給出總利潤最大的切割方案。

表1 各產(chǎn)品參數(shù)Tab.1 Product parameters

2 模型的建立與求解

2.1 問題(1)模型的建立與求解

2.1.1 動態(tài)規(guī)劃模型的建立

基于背包算法[1]建立動態(tài)規(guī)劃模型。將木塊的面積進行離散化后得到3 000×1 500塊正方形區(qū)域，每個區(qū)域為1 mm×1 mm的小方塊。為了準確地定位每塊正方形區(qū)域的位置，現(xiàn)以木板S1的左下角頂點為原點建立直角坐標系，用每塊正方形的右上角坐標表示該正方形，最終可將整個木塊看作是3 000×1 000個離散化的點。

當P1產(chǎn)品往X軸方向放置時：

a)如果P1產(chǎn)品豎放，當x>w1時，點(x,y)的最大可切割面積為f(x,y),則f(x,y)與點(x-w1,y)的最大可切割面積f(x-w1,y)有關。

點(x,y)的最大可切割面積f(x,y)可表示為：

b)如果P1產(chǎn)品橫放，當x>l1時，點(x,y)的最大可切割面積為f(x,y),則f(x,y)與點(x-l1,y)的最大可切割面積f(x-l1,y)有關。

點(x,y)的最大可切割面積f(x,y)可表示為：

當P1產(chǎn)品往y軸方向放置時：

c)如果P1產(chǎn)品橫放，當y>w2時，點(x,y)的最大可切割面積為f(x,y),則f(x,y)與點(x,y-w1)的最大可切割面積f(x,y-w1)有關。

點(x,y)的最大可切割面積f(x,y)可表示為：

d)如果P1產(chǎn)品豎放，當y>l1時，點(x,y)的最大可切割面積為f(x,y),則f(x,y)與點(x,y-l1)的最大可切割面積f(x,y-l1)有關。

點(x,y)的最大可切割面積f(x,y)可表示為：

假設P1產(chǎn)品的長為l1、寬為w1，P3產(chǎn)品的長為l3、寬為w3，點(x,y)的最大可切割面積需要考慮8種情況。

2.1.2 動態(tài)規(guī)劃模型的求解

從高到低的三種切割方案如表2所示：

表2 三種方案結(jié)果表Tab.2 Results of three schemes

每個方案對應的切割方案如下：

圖1 方案一切割圖Fig.1 Cutting diagram of scheme one

圖2 方案二切割圖Fig.2 Cutting diagram of scheme two

圖3 方案三切割圖Fig.3 Cutting diagram of scheme three

2.2 問題(2)模型的建立與求解

僅考慮利潤最大化而不考慮這四種產(chǎn)品的生產(chǎn)任務時，設計100塊木板的切割方案，因為每塊木板的利潤是相互獨立的，所以僅需要設計1塊木板的最大利潤切割方案，對其他99塊木板進行同樣方案的切割，即可得到這100塊木板總體的利潤達到最大。

2.2.1 動態(tài)規(guī)劃模型的建立

1塊木板上不考慮切割得到的產(chǎn)品數(shù)量，僅考慮切割得到的所有產(chǎn)品的總利潤最大化，這一問題與對單塊木板S1切割產(chǎn)品使得到的產(chǎn)品數(shù)量最大化問題求解方向相反，但求解理論的本質(zhì)相同[2]。因此，可在問題(1)的基礎上，將動態(tài)規(guī)劃的目標函數(shù)改為木板切割后得到的利潤最大，記4種產(chǎn)品的單件利潤分別為kj(j=1,2,3,4)點(x,y)處的利潤值為g(x,y)。

其中，kj(j=1,2,3,4)表示第j種產(chǎn)品的利潤，lj(j=1,2,3,4)表示第j種產(chǎn)品的長度，wj(j=1,2,3,4)表示第j種產(chǎn)品的寬度。

2.2.2 動態(tài)規(guī)劃模型的求解

在問題(1)離散化的基礎上，將整塊木板轉(zhuǎn)化為3 000×1 500個離散化的點，同樣定義元胞數(shù)組d，其中g(shù){x,y}的值表示橫坐標為x，縱坐標為y時，其左下角的區(qū)域面積可以切割的最大利潤?，F(xiàn)對3 000×1 500個離散點進行從左到右、從下到上依次遍歷。對每個點左下部分的區(qū)域面積可分割的Pj(j=1,2,3,4)產(chǎn)品的利潤進行最大值求解。此處同樣采用動態(tài)規(guī)劃的方式進行求解，具體的求解步驟如下：

Step1：當橫坐標或縱坐標為0時，將元胞中該點的初始值設置為0，表示當木板長度或?qū)挾葹?時，最多可以切割0個Pj(j=1,2,3,4)產(chǎn)品。

Step2：按照從左到右、從下到上的次序依次遞推每一個g{x,y}值所表示的最優(yōu)切割利潤。

Step3：判斷當前坐標是否可放置產(chǎn)品。記當前坐標為(x,y)，m=min(x,y),若m

Step4：由動態(tài)規(guī)劃的思想可知，如果當前點的所有子狀態(tài)的最優(yōu)解已經(jīng)求得，則可用所有子狀態(tài)的最優(yōu)解推導出當前狀態(tài)的最優(yōu)解。此處采用的遞推公式如下：

其中，kj(j=1,2,3,4)表示第j種產(chǎn)品的利潤，lj(j=1,2,3,4)表示第j種產(chǎn)品的長度，wj(j=1,2,3,4)表示第j種產(chǎn)品的寬度。

Step5：求得整塊木板的最優(yōu)解為g{3 000,1 500}。

對于上述動態(tài)規(guī)劃模型，運用軟件進行求解，得到單塊S1木板所切割得到所有產(chǎn)品的總利潤最大方案如表3：

因而得到在不考慮產(chǎn)品需求量的前提下，100塊S1木板總利潤最大的切割方案如表4：

表3 單個木板利潤最大化切割方案Tab.3 Single board profit maximization cutting plan

表4 100塊木板利潤最大化切割方案Tab.4 Profit maximization cutting plan of 100 wood boards

3 結(jié)語

本研究根據(jù)切割要求，啟發(fā)式地運用動態(tài)規(guī)劃模型和背包算法，充分考慮木板利用率的影響因素，考慮全面。同時，該模型與算法能結(jié)合實際情況應用于其他領域物品的切割問題，實用性強，具有很好的推廣性。