基于線性規劃的管材下料最優化研究▲

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

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

關鍵詞：動態規劃；線性規劃；GLPK UI設計；管材下料

中圖分類號：TG385? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻標識碼：A? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文章編號：2096-6903（2023）10-0113-03

0 引言

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

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

1 數學模型建立

本文的管材切割問題可以簡化為如下假設：設有足夠數量、總長度為L的原料管材，現需要加工成k種長度的短管，長度分別為p1、p2、p3…pk，對應需求量分別為n1、n2、n3…nk，問如何加工可以使得管材使用最少或余量最少？

問題可以分為兩個部分進行解決，先是得出所有的下料組合方案M，然后根據目標需求，對方案矩陣M進行最優解空間的求解。管材下料規劃流程如圖1所示。

1.1 動態規劃求解所有下料方案

假設管材的前端最小余量長度為，后端最小余量長度為m2，每次切割損耗為N，那么動態規劃系統的目標函數如式（1）所示。

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

其中，l為切割后管材的實際長度，t為單根管材切割的次數。

此外，動態規劃系統的控制變量可以用最大使用長度Lmax如式（2）所示。

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

動態規劃問題需要有合理的約束條件，這里的約束條件可以用最大管材使用長度Lmax和第i種方案中第s種長度短管的切割數量nis如式（3）所示。

（3）

當前問題中管材切割方案集合為f1，狀態量方程如式（4）所示。

（4）

根據狀態量方程，可以求出當前條件下所有的切割方案組合，并存儲在矩陣Mk×m當中。其中m為方案數量[2]。當前結果如表1所示。

1.2 線性規劃求解最優方案

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

假設Xm為對應方案Bm的切割原料管材的根數，則由表1的動態規劃求解結果，給出使用原料管材最少的目標函數如式（5）所示。

（5）

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

在求解過程中，切割出的每種長度的管材數要大于或等于對應需求數，所以給出其約束條件如式（6）所示。

（6）

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

（7）

而對于管材余量最少的情況，結合表1可以得到此情況下的目標函數如式（8）所示。

（8）

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

求解上述條件下的線性規劃問題即可得出兩種情況下的最優切割方案。

2 程序設計

本文使用Qt 5.15+Visual Studio 2019軟件，結合C++編程語言實現UI設計。其中線性規劃模塊使用數學工具庫GLPK（GNU Linear Programming Kit）求解。GLPK是專門用來求解線性規劃問題（LP）、混合整數規劃問題（MIP）和其他相關問題的開源工具庫。本文算法包括動態規劃求解下料方案組合、線性規劃求解最優方案組合（包括使用原料管材最少和管材余量最少）兩個部分。

動態規劃部分利用第三方工具包libxl實現對Excel文件中數據的讀取。包括切割出下料管的長度weights和相應數量nums，再輸入原料管材最大使用長度max_weights。通過迭代處理，最終返回管路組合weight_num作為線性規劃部分的輸入量代入計算。

線性規劃部分主要利用GLPK進行求解。先是對動態規劃部分得到的方案組合進行處理，轉換為標準的矩陣形式，如表1所示。再創建GLPK的求解模型，根據公式（5～8）對模型中的各項參數，如目標函數的變量系數及求解形式（最大化或最小化）、變量個數及類型、約束條件個數及范圍等進行設置，最后調用GLPK Solver進行求解。此外，可以通過glp相關函數調取變量值和目標函數的結果。GLPK線性規劃部分代碼如圖2所示。

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

3 實驗測試與對比

在設計完成后，將之與市面上同類型的下料軟件SmartCUT PRO和參考文獻[1]中的設計進行對比。同樣，在Intel i5-8300 CPU 2.30 GHz 8.00 GB Windows x64系統計算機上運行，其相關測試數據和顯示結果如表2～表5所示。

從三者的測試結果對比可以發現，先本文所設計的下料系統的平均利用率明顯高于其他兩款軟件。表4用SmartCUT PRO最終計算出所用的原料管材數為35根，本文計算出所用原料管材數為30根，有的設計未給出每種方式下原料管材使用個數。對比來看，本文所設計的系統計算出的切管方案的原料管材使用更少。

4 結束語

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

參考文獻

[1] 姬玉生，丁龍斌，鄭曉芳，等.基于線性動態規劃的管材切割最優使用率優化研究[J].科技創新導報，2021，18（11）：66-69.

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

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

[4] 田雙，呂林，蔡亞慶，等.基于Lingo的求解一維下料問題簡易算法設計與實現[J].產業與科技論壇，2021，20（7）：45-47.

[5] 劉潤濤，陳媛婧.型材下料問題算法研究[J].計算機工程與應用，2009，45（25）：215-217.

[6] 李培勇.多規格—維型材優化下料[J].機械科學與技術，2003 （S2）：80-83+86.