最優(yōu)切割問題研究

王奕為

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

關(guān)鍵詞：最優(yōu)切割? 原材料利用率? 產(chǎn)品利潤率? 枚舉法

中圖分類號(hào)：TS652? ? 文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：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 問題描述

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

1.1 問題背景

某企業(yè)新進(jìn)一批木板，其相關(guān)數(shù)據(jù)如表1所示，在家具加工的過程中，需要使用切割工具生產(chǎn)產(chǎn)品，其生產(chǎn)的產(chǎn)品相關(guān)數(shù)據(jù)如表2所示，上述內(nèi)容則為該企業(yè)設(shè)計(jì)木板的最優(yōu)切割方案。

基本假設(shè)如下。

木板厚度和割縫寬度忽略不計(jì)。

每次切割都很精確，不會(huì)出現(xiàn)意外損耗。

切割產(chǎn)品的長和寬與原材料的長和寬平行。

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

符號(hào)說明：

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

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

1.2問題分析

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

木板的最優(yōu)切割

為了有效對木板進(jìn)行切割和完成需求的生產(chǎn)任務(wù)，分別對單一產(chǎn)品和多產(chǎn)品混合的木板切割問題進(jìn)行探討。

單一產(chǎn)品的木板最優(yōu)切割

對單一產(chǎn)品的木板最優(yōu)切割，考慮單一方向和復(fù)合方向的策略進(jìn)行切割。以產(chǎn)品P1為例，若只考慮P1面積，可以計(jì)算出單一切割產(chǎn)品P1的理論利用率為：

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

經(jīng)粗略估計(jì)可得：采用單一方向（橫向或豎向）的產(chǎn)品切割方式，木板利用率僅為93.30%，會(huì)造成原材料的較大浪費(fèi)，下面考慮采用復(fù)合方向規(guī)劃產(chǎn)品切割方式，具體方案如下。

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

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

同理可得：

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

經(jīng)過計(jì)算可得：K=13時(shí)，即第一至十三列采取以長為201mm的一條邊豎排，豎直擺放13個(gè)P1，橫向擺放1個(gè)P1為最優(yōu)方案。同理可的P3產(chǎn)品的最優(yōu)方案，即在一塊木板上切割P1 P3產(chǎn)品，木板利用率最高（即剩余木板面積最?。┑那懈罘桨傅慕Y(jié)果見表3。

2.2多產(chǎn)品混合的木板最優(yōu)切割

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

第一步：根據(jù)木板利用率最高的方案，先對產(chǎn)品P3進(jìn)行切割。

根據(jù)表3可得一塊板子最多排48個(gè)P3產(chǎn)品，即單獨(dú)切割P3所需原材料木板數(shù)為：

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

所以先在33塊木板上按單一產(chǎn)品的最優(yōu)方案切割P3，此時(shí)33塊木板的利用率為99.17%。余39個(gè)產(chǎn)品P3再和P1進(jìn)行組合切割。

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

（ 木板面積-39個(gè)P_3 產(chǎn)品面積）/（P_1 產(chǎn)品面積）=（1500×3000-39×406×229）/（373×201）≈11.6578

根據(jù)原材料木板的實(shí)際尺寸，經(jīng)過實(shí)際計(jì)算，n的取值達(dá)不到11，則可得木板利用率為：

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

第二步：根據(jù)第一步的結(jié)果，對產(chǎn)品P1進(jìn)行切割：

單獨(dú)切割P1所需原材料木板數(shù)為：

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

所以先在13塊木板上按每塊木板上切割59個(gè)產(chǎn)品P1進(jìn)行切割，此時(shí)13塊木板的利用率為98.30%。余7個(gè)產(chǎn)品P1未完成切割。

第三步：對余下沒有進(jìn)行切割的產(chǎn)品P3和P1進(jìn)行組合切割。

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

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

結(jié)合單一產(chǎn)品和兩個(gè)產(chǎn)品的最優(yōu)切割策略，進(jìn)一步考慮不同產(chǎn)品（P1，P2，P3，P4）在同一塊木板上的最優(yōu)切割方案。

設(shè)第i 種產(chǎn)品的需求數(shù)量為N_i （i=1，2，3，4），則可得四種產(chǎn)品數(shù)量之間的比值關(guān)系：

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

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

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

按上述方案確定的木板數(shù)進(jìn)行切割，可得：

即P1產(chǎn)品全部切割完成，剩余5個(gè)P2產(chǎn)品、13個(gè)P3產(chǎn)品、16個(gè)P4產(chǎn)品沒完成切割。

第二步：對第一步剩余產(chǎn)品完成切割。

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

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

即四種產(chǎn)品的單位利潤率大小順序?yàn)椋篐_1>H_4>H_3>H_2.先考慮以產(chǎn)品的單位利潤高的產(chǎn)品進(jìn)行切割方案的確定，尋找利潤率最高的切割方案。

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

其中k_i （i=1，2，3，4）為每塊木板最多可切割的第 種產(chǎn)品的個(gè)數(shù)。

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

3模型的評價(jià)

3.1模型優(yōu)點(diǎn)

在建立過程中，充分考慮了在解決此問題當(dāng)中的工業(yè)生產(chǎn)的實(shí)際意義;模型的求解不需要高深的數(shù)學(xué)知識(shí)，更適宜在工業(yè)生產(chǎn)中進(jìn)行推廣。

3.2模型的缺點(diǎn)

模型的最后一問根據(jù)題意不考慮產(chǎn)品的數(shù)量，進(jìn)一步可考慮在確定產(chǎn)品數(shù)量基礎(chǔ)上擴(kuò)展模型。

參考文獻(xiàn)

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

[2]肖海華.矩形件下料問題的創(chuàng)新線性規(guī)劃布局方法研究與應(yīng)用[D].廣西：廣西大學(xué)，2017.

[3]羅強(qiáng).基于灰狼算法的矩形優(yōu)化排樣及其在板式家具開料中的應(yīng)用[D].武漢：華中科技大學(xué)，?2019.

[4]饒昊.板材切割問題的求解與應(yīng)用[D].南昌：江西財(cái)經(jīng)大學(xué)，2019.

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

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

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