張若愚，劉祥，曾水生，王梓榆，劉明

摘 要：在彎管成型技術(shù)中，不同形狀的彎管或許對(duì)應(yīng)著不同尺寸的直管，這就需要對(duì)管材的下料進(jìn)行規(guī)劃。基于此，設(shè)計(jì)一種基于線(xiàn)性規(guī)劃的管材下料算法，針對(duì)管材使用最少和管材余量最少兩種情況，分別求解出最優(yōu)下料方案，并通過(guò)UI設(shè)計(jì)實(shí)現(xiàn)人機(jī)交互，便于操作使用。

關(guān)鍵詞：動(dòng)態(tài)規(guī)劃；線(xiàn)性規(guī)劃；GLPK UI設(shè)計(jì)；管材下料

中圖分類(lèi)號(hào)：TG385? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文章編號(hào)：2096-6903（2023）10-0113-03

0 引言

彎管成型技術(shù)是在一根長(zhǎng)度固定的直管上，通過(guò)推進(jìn)機(jī)構(gòu)和彎曲模施壓使得直管彎曲成特定形狀的技術(shù)。不同形狀的彎管對(duì)直管的長(zhǎng)度、壁厚、材料等有不同的要求，而對(duì)于管材的切割，一般是根據(jù)下料表在多根長(zhǎng)度相同的長(zhǎng)管上切割出所需長(zhǎng)度和數(shù)量的短管。不同的切割方案會(huì)導(dǎo)致不同的剩余量和原料使用數(shù)目，從而影響原料管材的利用率。合理地規(guī)劃切割方案，使管材的利用率盡可能達(dá)到最大是當(dāng)前研究的一個(gè)重點(diǎn)[1]。

本文基于線(xiàn)性規(guī)劃算法，針對(duì)兩種不同下料問(wèn)題，在確保一定余量和損耗的情況下，給出了合理的切割方案，有效地提高了原料管材利用率，降低了成本。

1 數(shù)學(xué)模型建立

本文的管材切割問(wèn)題可以簡(jiǎn)化為如下假設(shè)：設(shè)有足夠數(shù)量、總長(zhǎng)度為L(zhǎng)的原料管材，現(xiàn)需要加工成k種長(zhǎng)度的短管，長(zhǎng)度分別為p1、p2、p3…pk，對(duì)應(yīng)需求量分別為n1、n2、n3…nk，問(wèn)如何加工可以使得管材使用最少或余量最少？

問(wèn)題可以分為兩個(gè)部分進(jìn)行解決，先是得出所有的下料組合方案M，然后根據(jù)目標(biāo)需求，對(duì)方案矩陣M進(jìn)行最優(yōu)解空間的求解。管材下料規(guī)劃流程如圖1所示。

1.1 動(dòng)態(tài)規(guī)劃求解所有下料方案

假設(shè)管材的前端最小余量長(zhǎng)度為，后端最小余量長(zhǎng)度為m2，每次切割損耗為N，那么動(dòng)態(tài)規(guī)劃系統(tǒng)的目標(biāo)函數(shù)如式（1）所示。

maxl=∑（L-m1-m2-（t+1）N）? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （1）

其中，l為切割后管材的實(shí)際長(zhǎng)度，t為單根管材切割的次數(shù)。

此外，動(dòng)態(tài)規(guī)劃系統(tǒng)的控制變量可以用最大使用長(zhǎng)度Lmax如式（2）所示。

Lmax≤L-m1-m2-N? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （2）

動(dòng)態(tài)規(guī)劃問(wèn)題需要有合理的約束條件，這里的約束條件可以用最大管材使用長(zhǎng)度Lmax和第i種方案中第s種長(zhǎng)度短管的切割數(shù)量nis如式（3）所示。

（3）

當(dāng)前問(wèn)題中管材切割方案集合為f1，狀態(tài)量方程如式（4）所示。

（4）

根據(jù)狀態(tài)量方程，可以求出當(dāng)前條件下所有的切割方案組合，并存儲(chǔ)在矩陣Mk×m當(dāng)中。其中m為方案數(shù)量[2]。當(dāng)前結(jié)果如表1所示。

1.2 線(xiàn)性規(guī)劃求解最優(yōu)方案

一維的管材切割問(wèn)題是一種線(xiàn)性規(guī)劃問(wèn)題，考慮到管材數(shù)目要為整數(shù)，所以此問(wèn)題是一種整數(shù)規(guī)劃。本文分別考慮使用原料管材最少和管材余量最少兩種情況下的線(xiàn)性規(guī)劃求解[3-6]。

假設(shè)Xm為對(duì)應(yīng)方案Bm的切割原料管材的根數(shù)，則由表1的動(dòng)態(tài)規(guī)劃求解結(jié)果，給出使用原料管材最少的目標(biāo)函數(shù)如式（5）所示。

（5）

其中z1表示所需原料管材的總根數(shù)。

在求解過(guò)程中，切割出的每種長(zhǎng)度的管材數(shù)要大于或等于對(duì)應(yīng)需求數(shù)，所以給出其約束條件如式（6）所示。

（6）

此外，原料管材根數(shù)和切割出的管材根數(shù)均要為整數(shù)，如式（7）所示。

（7）

而對(duì)于管材余量最少的情況，結(jié)合表1可以得到此情況下的目標(biāo)函數(shù)如式（8）所示。

（8）

其中z2表示總余量。此情況下的約束條件與上述公式（6）（7）相同。

求解上述條件下的線(xiàn)性規(guī)劃問(wèn)題即可得出兩種情況下的最優(yōu)切割方案。

2 程序設(shè)計(jì)

本文使用Qt 5.15+Visual Studio 2019軟件，結(jié)合C++編程語(yǔ)言實(shí)現(xiàn)UI設(shè)計(jì)。其中線(xiàn)性規(guī)劃模塊使用數(shù)學(xué)工具庫(kù)GLPK（GNU Linear Programming Kit）求解。GLPK是專(zhuān)門(mén)用來(lái)求解線(xiàn)性規(guī)劃問(wèn)題（LP）、混合整數(shù)規(guī)劃問(wèn)題（MIP）和其他相關(guān)問(wèn)題的開(kāi)源工具庫(kù)。本文算法包括動(dòng)態(tài)規(guī)劃求解下料方案組合、線(xiàn)性規(guī)劃求解最優(yōu)方案組合（包括使用原料管材最少和管材余量最少）兩個(gè)部分。

動(dòng)態(tài)規(guī)劃部分利用第三方工具包libxl實(shí)現(xiàn)對(duì)Excel文件中數(shù)據(jù)的讀取。包括切割出下料管的長(zhǎng)度weights和相應(yīng)數(shù)量nums，再輸入原料管材最大使用長(zhǎng)度max_weights。通過(guò)迭代處理，最終返回管路組合weight_num作為線(xiàn)性規(guī)劃部分的輸入量代入計(jì)算。

線(xiàn)性規(guī)劃部分主要利用GLPK進(jìn)行求解。先是對(duì)動(dòng)態(tài)規(guī)劃部分得到的方案組合進(jìn)行處理，轉(zhuǎn)換為標(biāo)準(zhǔn)的矩陣形式，如表1所示。再創(chuàng)建GLPK的求解模型，根據(jù)公式（5～8）對(duì)模型中的各項(xiàng)參數(shù)，如目標(biāo)函數(shù)的變量系數(shù)及求解形式（最大化或最小化）、變量個(gè)數(shù)及類(lèi)型、約束條件個(gè)數(shù)及范圍等進(jìn)行設(shè)置，最后調(diào)用GLPK Solver進(jìn)行求解。此外，可以通過(guò)glp相關(guān)函數(shù)調(diào)取變量值和目標(biāo)函數(shù)的結(jié)果。GLPK線(xiàn)性規(guī)劃部分代碼如圖2所示。

為了方便使用算法，本文設(shè)計(jì)了相應(yīng)的UI界面。主要功能包括讀取用戶(hù)選擇的計(jì)算機(jī)路徑下Excel文件中的數(shù)據(jù)，包括切割出下料管的長(zhǎng)度和對(duì)應(yīng)數(shù)量，然后鍵入其他相關(guān)數(shù)據(jù)如原料管長(zhǎng)度等，再利用QPlainButton控件實(shí)現(xiàn)對(duì)兩種求解情況的選擇，最后將計(jì)算結(jié)果顯示在QTextEdit中。使用管材最少時(shí)和總剩余量最少時(shí)的UI顯示結(jié)果分別如圖3、圖4所示。此外，用戶(hù)還可以將計(jì)算結(jié)果保存到自定義路徑的文件夾中，方便重復(fù)使用。

3 實(shí)驗(yàn)測(cè)試與對(duì)比

在設(shè)計(jì)完成后，將之與市面上同類(lèi)型的下料軟件SmartCUT PRO和參考文獻(xiàn)[1]中的設(shè)計(jì)進(jìn)行對(duì)比。同樣，在Intel i5-8300 CPU 2.30 GHz 8.00 GB Windows x64系統(tǒng)計(jì)算機(jī)上運(yùn)行，其相關(guān)測(cè)試數(shù)據(jù)和顯示結(jié)果如表2～表5所示。

從三者的測(cè)試結(jié)果對(duì)比可以發(fā)現(xiàn)，先本文所設(shè)計(jì)的下料系統(tǒng)的平均利用率明顯高于其他兩款軟件。表4用SmartCUT PRO最終計(jì)算出所用的原料管材數(shù)為35根，本文計(jì)算出所用原料管材數(shù)為30根，有的設(shè)計(jì)未給出每種方式下原料管材使用個(gè)數(shù)。對(duì)比來(lái)看，本文所設(shè)計(jì)的系統(tǒng)計(jì)算出的切管方案的原料管材使用更少。

4 結(jié)束語(yǔ)

管材下料問(wèn)題經(jīng)過(guò)長(zhǎng)期研究逐漸趨于成熟，限制計(jì)算結(jié)果優(yōu)劣的因素主要在于數(shù)學(xué)模型和科學(xué)計(jì)算工具的準(zhǔn)確性。目前市面上的科學(xué)計(jì)算工具五花八門(mén)，很多都提供學(xué)術(shù)版開(kāi)源使用，但每種求解器提供的計(jì)算方法有所不同，選擇合適的科學(xué)計(jì)算工具可以更加高效、準(zhǔn)確的計(jì)算出想要的結(jié)果。本文使用基于C++編程語(yǔ)言的GLPK線(xiàn)性規(guī)劃求解器，能夠快速、準(zhǔn)確的計(jì)算出相應(yīng)結(jié)果，并與其他同類(lèi)型軟件進(jìn)行比較。研究結(jié)果表明：用該種方法和求解器進(jìn)行管材下料規(guī)劃可以取得更優(yōu)結(jié)果。

參考文獻(xiàn)

[1] 姬玉生，丁龍斌，鄭曉芳，等.基于線(xiàn)性動(dòng)態(tài)規(guī)劃的管材切割最優(yōu)使用率優(yōu)化研究[J].科技創(chuàng)新導(dǎo)報(bào)，2021，18（11）：66-69.

[2] 李建星，谷安，徐廣增，等.一維下料問(wèn)題的優(yōu)化算法及其編程[J].機(jī)電一體化，2011，17（5）：100-104.

[3] 鄧龍.鋼管熱軋下料切割算法研究及應(yīng)用[J].寶鋼技術(shù)，2022（6）：52-57.

[4] 田雙，呂林，蔡亞慶，等.基于Lingo的求解一維下料問(wèn)題簡(jiǎn)易算法設(shè)計(jì)與實(shí)現(xiàn)[J].產(chǎn)業(yè)與科技論壇，2021，20（7）：45-47.

[5] 劉潤(rùn)濤，陳媛婧.型材下料問(wèn)題算法研究[J].計(jì)算機(jī)工程與應(yīng)用，2009，45（25）：215-217.

[6] 李培勇.多規(guī)格—維型材優(yōu)化下料[J].機(jī)械科學(xué)與技術(shù)，2003 （S2）：80-83+86.