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

周康喬，嚴沛鑫，龐國慶

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

1 問題背景

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

表1 各產品參數Tab.1 Product parameters

2 模型的建立與求解

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

2.1.1 動態規劃模型的建立

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

當P1產品往X軸方向放置時：

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

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

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

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

當P1產品往y軸方向放置時：

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

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

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

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

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

2.1.2 動態規劃模型的求解

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

表2 三種方案結果表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)模型的建立與求解

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

2.2.1 動態規劃模型的建立

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

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

2.2.2 動態規劃模型的求解

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

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

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

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

Step4：由動態規劃的思想可知，如果當前點的所有子狀態的最優解已經求得，則可用所有子狀態的最優解推導出當前狀態的最優解。此處采用的遞推公式如下：

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

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

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

因而得到在不考慮產品需求量的前提下，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 結語

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