基于线性规划的管材下料最优化研究▲

张若愚，刘祥，曾水生，王梓榆，刘明

摘 要：在弯管成型技术中，不同形状的弯管或许对应着不同尺寸的直管，这就需要对管材的下料进行规划。基于此，设计一种基于线性规划的管材下料算法，针对管材使用最少和管材余量最少两种情况，分别求解出最优下料方案，并通过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.