最優切割問題研究

王奕為

摘 要：該文主要研究了在給定條件下如何對二維矩形木板的最優切割問題，重點研究分析了在完成要求的生產任務和木板利用率最高的前提下單一產品和多個產品的最優切割方案，在此基礎上進一步討論了不同要求下總利潤最大的木板切割方案，并通過建立相關數學模型進行求解，計算結果表明建立的數學模型有效可靠且尋優能力較好，能夠有效解決木板最優切割問題。

關鍵詞：最優切割? 原材料利用率? 產品利潤率? 枚舉法

中圖分類號：TS652? ? 文獻標識碼：A文章編號：1672-3791（2022）03（b）-0000-00

Study on the Optimal Cutting Problem

WANG Yiwei

（Yancheng Polytecnic College， Yancheng， Jiangsu Province， 224005 China）

Abstract： This paper mainly studies the optimal cutting problem of wood under given conditions， the optimal cutting schemes of single product and multi-product are studied and analyzed under the demand of required production tasks and the highest utilization rate of wood board. On this basis， the cutting scheme with the maximum total profit under different requirements is further discussed and solved by establishing relevant mathematical models. The numerical results show that the mathematical model is effective， reliable and has a good searching ability， the new model can effectively solve the problem of the optimal cutting of wood.

Key Words： Optimal Cutting; Raw material utilization; Product profit margin; Enumeration method

1 問題描述

“木板最優切割問題 ”是把相同形狀的一些原材料分割加工成若干個不向規格大小的零件的問題，此類問題在工程技術和工業生產中有著重要和廣泛的應用.工廠中經常會碰到一些材料切割的優化問題，為了節省材料，減少廢料對環境的污染，必須選擇最優的切割方案，實際上也是一類特殊的布局排樣優化問題[1-4]。這里的“木板最優切割問題”主要考慮某企業的實際條件限制下的單一材料切割問題。即在加工過程中，木板被切割成不同形狀和面積，分別加工成不同的產品。在木板的面積和數量有限的情況下，安排木板切割使得在完成生產任務的基礎上，使木板利用率最大化和企業利潤最大化，這是企業亟需解決的問題。簡化和優化切割操作，對提高企業的經濟效益和增大產品競爭力具有極為重要的意義。

1.1 問題背景

某企業新進一批木板，其相關數據如表1所示，在家具加工的過程中，需要使用切割工具生產產品，其生產的產品相關數據如表2所示，上述內容則為該企業設計木板的最優切割方案。

基本假設如下。

木板厚度和割縫寬度忽略不計。

每次切割都很精確，不會出現意外損耗。

切割產品的長和寬與原材料的長和寬平行。

不考慮切割方式增加所帶來的成本增加。

符號說明：

為矩形板材的長邊; 為矩形板材的寬邊; 為矩形板材的長寬比; 為矩形板材的面積;

Si為第 種產品用材的面積 ;Hi為第 種產品的單位利潤（i=1，2，3，4）。

1.2問題分析

論文主要研究的是木板的最優切割問題，此問題實質上是一個下料問題[5-7]，在進行切割時涉及到不同類型產品長和寬同時改變，是兩個變量在變，所以在建立模型時以剩余原材料的余量面積最小和使用的原材料的數量最少為其目標。在求解過程中，盡量讓矩形原料長邊處余料少。由于原料和產品的幾何形狀都是矩形，都是軸對稱圖形，若矩形產品用材的上邊延長線與矩形原材的上邊延長線有偏角時，對比前面切割的方式會產生較多的浪費，所以不予考慮此種情況。該文的解題思路也是沿著這樣的思想一步一步展開的，即通過簡單到復雜的情況逐步展開討論。

木板的最優切割

為了有效對木板進行切割和完成需求的生產任務，分別對單一產品和多產品混合的木板切割問題進行探討。

單一產品的木板最優切割

對單一產品的木板最優切割，考慮單一方向和復合方向的策略進行切割。以產品P1為例，若只考慮P1面積，可以計算出單一切割產品P1的理論利用率為：

S_1/S=（373×201×60）/（1500×3000）=99.96%

經粗略估計可得：采用單一方向（橫向或豎向）的產品切割方式，木板利用率僅為93.30%，會造成原材料的較大浪費，下面考慮采用復合方向規劃產品切割方式，具體方案如下。

（1）僅第一列采取以長為201 mm的一條邊豎排，則可計算出該行還可擺放P1的數目為豎直擺放1個P1，橫向擺放7個P1，還剩0.5×373=186.5mm2的未利用區域無法進行擺放。

（2）第一、第二列采取以長為201mm的一條邊豎排，則可計算出該行還可擺放P1的數目為豎直擺放2個P1，橫向擺放6個P1，還剩0.97×373=361.81mm2的未利用區域無法進行擺放。

同理可得：

K：前K列采取以長為201 mm的一條邊豎排，則可計算出該行還可擺放P1的數目為豎直擺放K （K=1，2，…，14）個P1，橫向擺放（3000-201×K）/373個P1（令（3000-201×K）/373的整數部分為N），則還剩[（3000-201×K）/373-N]×373mm2的未利用區域無法進行擺放。.

經過計算可得：K=13時，即第一至十三列采取以長為201mm的一條邊豎排，豎直擺放13個P1，橫向擺放1個P1為最優方案。同理可的P3產品的最優方案，即在一塊木板上切割P1 P3產品，木板利用率最高（即剩余木板面積最小）的切割方案的結果見表3。

2.2多產品混合的木板最優切割

首先考慮兩個不同產品在同一塊木板上的最優切割，完成給定的P1和P3產品的生產任務。為了得到所需產品P1和P3要求數量，且使用原材料木板數量最小的切割方案，采用木板利用率優先，產品數量要求其次的決策方案進行切割，具體決策過程如下。

第一步：根據木板利用率最高的方案，先對產品P3進行切割。

根據表3可得一塊板子最多排48個P3產品，即單獨切割P3所需原材料木板數為：

（P_3 的總需求量）/（每塊可切割P_3 最多的數量）=1623/48=33.8125

所以先在33塊木板上按單一產品的最優方案切割P3，此時33塊木板的利用率為99.17%。余39個產品P3再和P1進行組合切割。

考慮產品P3再P1進行組合切割，需要1塊原材料木板即可產品P3的切割完成，設在一塊木板上切割過39個P3產品后，余料所能切割P1的個數為n，則n的最大取值為：

（ 木板面積-39個P_3 產品面積）/（P_1 產品面積）=（1500×3000-39×406×229）/（373×201）≈11.6578

根據原材料木板的實際尺寸，經過實際計算，n的取值達不到11，則可得木板利用率為：

綜上討論可得：余 個產品P3和P1在一塊原材料木板上進行組合切割的利用率小于在一塊板材上單獨進行對產品P1的切割的利用率。又剩下產品P1較多，不適宜先與P3進行混合切割，所以第二步采用單獨對P1產品進行切割。

第二步：根據第一步的結果，對產品P1進行切割：

單獨切割P1所需原材料木板數為：

（P_1 的總需求量）/（每塊可切割P_1 最多的數量）=774/59=13.1186

所以先在13塊木板上按每塊木板上切割59個產品P1進行切割，此時13塊木板的利用率為98.30%。余7個產品P1未完成切割。

第三步：對余下沒有進行切割的產品P3和P1進行組合切割。

通過第一步和第二步的切割，余39個P3產品和7個P1產品，在1塊原材料木板上可以完成。此時原材料木板的利用率為：

綜上所求，給出P1和P3產品生產任務的木板總利用率最高的切割方案：總需求S1木板47塊，其中33塊用于切割產品P3，可切割1584個P3產品，木板利用率99.17%;13塊由于切割產品P1，可切割767個P1產品，木板利用率98.30%;1塊木板進行混合切割，切割為7個產品P1和39個產品P3，木板利用率92.24%;47塊木板完成切割任務的總利用率約為98.78%。

結合單一產品和兩個產品的最優切割策略，進一步考慮不同產品（P1，P2，P3，P4）在同一塊木板上的最優切割方案。

設第i 種產品的需求數量為N_i （i=1，2，3，4），則可得四種產品數量之間的比值關系：

即在優選組合方案時，可以按N_1：N_2：N_3：N_4≈1：3：2：2的比例進行考慮選取求解，對于方案確定后進行切割所產生的產品多余或剩余部分再進行單獨考慮。按上述方法的思路進行組合求解，可得如下最優組合方案，具體內容見表4和表5。

對方案1，根據要求的具體數量和比例關系，測算可得：為完成所有產品的生產任務，各類切割方法所需要進行切割的木板數為：方法1需要切割51～54塊左右：方法2需要切割13～14塊左右;方法3需要切割60～63塊左右;方法4需要切割8塊左右。

設完成任務后，方法1至少需要切割y_1塊木板，方法2至少需要切割y_2塊木板，方法3至少需要切割y_3塊木板，方法4至少需要切割y_4塊木板，則有：

按上述方案確定的木板數進行切割，可得：

即P1產品全部切割完成，剩余5個P2產品、13個P3產品、16個P4產品沒完成切割。

第二步：對第一步剩余產品完成切割。

根據第一步的結果，剩余5個P2產品、13個P3產品、16個P4產品可以在一塊原材料木板上即可切割完成，且木板有剩余。即全部完成4類產品的生產切割任務需138塊木板。同理根據方案2的切割方式，全部完成4類產品的生產任務需139塊木板。綜合可得最優切割方案為方案1。

如果不考慮產品P1，P2，P3，P4的需求數量，給定S1木板的數量（假設木板數量為100塊），求解總利潤最大的切割方案。根據給出的產品利潤，求每種產品的單位利潤，按單位利潤對產品進行排序，然后結合每塊木板切割產品的利用率給出每塊木板不同切割的利潤，最后給出總利潤最大的切割方案。

即四種產品的單位利潤率大小順序為：H_1>H_4>H_3>H_2.先考慮以產品的單位利潤高的產品進行切割方案的確定，尋找利潤率最高的切割方案。

設每塊木板可切割x_i （i=1，2，3，4）塊第 產品，每件產品的利潤為r_i （i=1，2，3，4），則每塊原材木板切割產生的最大利潤為

其中k_i （i=1，2，3，4）為每塊木板最多可切割的第 種產品的個數。

對一塊原材料木板進行切割，按木板利用率從大到小給出如下切割方案，計算在不同切割方案下單塊木板有效切割產品所產生的利潤，則可對不同方法的單位原材料木板有效切割所產生的利潤進行從大到小順序，然后再按照單位原材料木板進行有效切割所產生的利潤和這4種產品的單位利潤進行綜合排序，考慮以單位原材料木板進行有效切割所產生的利潤所對應的方案進行切割木板，綜合可得總利潤最高的切割方案。

3模型的評價

3.1模型優點

在建立過程中，充分考慮了在解決此問題當中的工業生產的實際意義;模型的求解不需要高深的數學知識，更適宜在工業生產中進行推廣。

3.2模型的缺點

模型的最后一問根據題意不考慮產品的數量，進一步可考慮在確定產品數量基礎上擴展模型。

參考文獻

[1]張鵬程.基于BIM體系的鋼筋施工深化與下料優化研究[D].福州：福建工程學院，2018.

[2]肖海華.矩形件下料問題的創新線性規劃布局方法研究與應用[D].廣西：廣西大學，2017.

[3]羅強.基于灰狼算法的矩形優化排樣及其在板式家具開料中的應用[D].武漢：華中科技大學，?2019.

[4]饒昊.板材切割問題的求解與應用[D].南昌：江西財經大學，2019.

[5]萬德福.基于遺傳蟻群算法對不定長一維線材切割優化[D].南昌：南昌大學，2020.

[6]郭百海，隋毅.基于排樣矩形的直角邊零件下料算法[J].計算機系統應用，2021，30（1）：162-167.

[7]季君，邢斐斐，黃敦華.等.解決二維下料問題的最優兩階段排樣方式[J].現代制造工程，2021（3）：81-86.