基于背包算法的木板切割方案設(shè)計(jì)

周康喬，嚴(yán)沛鑫，龐國慶

(南通大學(xué)，江蘇 南通 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)品時(shí)單塊木板利用率最高的切割方案；(2)給定100張木板，給出總利潤最大的切割方案。

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

2 模型的建立與求解

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

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

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

當(dāng)P1產(chǎn)品往X軸方向放置時(shí)：

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

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

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

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

當(dāng)P1產(chǎn)品往y軸方向放置時(shí)：

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

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

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

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

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

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

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

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

每個(gè)方案對應(yīng)的切割方案如下：

圖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)任務(wù)時(shí)，設(shè)計(jì)100塊木板的切割方案，因?yàn)槊繅K木板的利潤是相互獨(dú)立的，所以僅需要設(shè)計(jì)1塊木板的最大利潤切割方案，對其他99塊木板進(jìn)行同樣方案的切割，即可得到這100塊木板總體的利潤達(dá)到最大。

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

1塊木板上不考慮切割得到的產(chǎn)品數(shù)量，僅考慮切割得到的所有產(chǎn)品的總利潤最大化，這一問題與對單塊木板S1切割產(chǎn)品使得到的產(chǎn)品數(shù)量最大化問題求解方向相反，但求解理論的本質(zhì)相同[2]。因此，可在問題(1)的基礎(chǔ)上，將動態(tài)規(guī)劃的目標(biāo)函數(shù)改為木板切割后得到的利潤最大，記4種產(chǎn)品的單件利潤分別為kj(j=1,2,3,4)點(diǎn)(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)離散化的基礎(chǔ)上，將整塊木板轉(zhuǎn)化為3 000×1 500個(gè)離散化的點(diǎn)，同樣定義元胞數(shù)組d，其中g(shù){x,y}的值表示橫坐標(biāo)為x，縱坐標(biāo)為y時(shí)，其左下角的區(qū)域面積可以切割的最大利潤。現(xiàn)對3 000×1 500個(gè)離散點(diǎn)進(jìn)行從左到右、從下到上依次遍歷。對每個(gè)點(diǎn)左下部分的區(qū)域面積可分割的Pj(j=1,2,3,4)產(chǎn)品的利潤進(jìn)行最大值求解。此處同樣采用動態(tài)規(guī)劃的方式進(jìn)行求解，具體的求解步驟如下：

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

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

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

Step4：由動態(tài)規(guī)劃的思想可知，如果當(dāng)前點(diǎn)的所有子狀態(tài)的最優(yōu)解已經(jīng)求得，則可用所有子狀態(tài)的最優(yōu)解推導(dǎo)出當(dāng)前狀態(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ī)劃模型，運(yùn)用軟件進(jìn)行求解，得到單塊S1木板所切割得到所有產(chǎn)品的總利潤最大方案如表3：

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

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

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

3 結(jié)語

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