递推矩阵的列生成算法下的一维下料方案研究

马俊燕，韩志会，骆德铖，肖海华

（广西大学机械工程学院，广西 南宁 530004）

1 引言

下料问题被应用在很多领域中，一维下料亦是如此，如金属、造纸、纺织品和木材等，增大材料利用率，降低成本，一直是企业追求的目标，即快速的获得下料方案[1-2]。对此国内外许多学者都对一维下料问题进行了深入研究，发表了大量优秀期刊著作，新算法、改进算法和混合算法不断被提出。文献[3]通过在采用一维下料CAD系统生成线材的下料方案，明显提高材料利用率考虑基础上，考虑优化目标与工艺约束作为参考；文献[4]采用修正传统的顺序启发式算法的改进的混合启发式算法，提高了切割率；文献[5]提出改进的蚁群算法降低了不定长原管一维下料废料率，文献[6]介绍了顺序修正法和动态规划算法提高了钢钉下料的材料利用率；文献[7]以满足零件需求为导向的对一维下料问题借用混合启发式算法进行求解，在综合考虑材料利用率情况下，能快速求解，但是求解质量不高；由于这些算法无法适用高精度布局优化问题，在求解问题时往往会陷入局部寻优。同时针对一维下料问题，也有很多通过建立常规线性规划模型，在进行求解。文献[8]提出一种线型规划与启发式算法结合的方法；文献[9]不同于启发式算法研究，提出分支定界法解决下料问题。文献[10-11]是针对二维下料问题进行列生成算法，并验证符合实际案例；文献[12]通过大量实验对枚举法、列生成算法和混合算法进行了对比。若常规线性规划问题中的决策变量要求为整数，则该问题就变为整数线性规划问题，其求解算法主要有穷举法、割平面法和分支界定法，但是以上方法具有适用于规模较小的一维切割问题、求解结果不精确、容易陷入局部寻优等缺点。为求解一维下料问题数学模型的过程中，提出了采用一种基于递推矩阵的列生成法并结合分支定界算法来求解一维下料整数线性规划问题，此方法对比其他算法能够快速得到较少的下料方案数量。

2 递推矩阵的列生成算法

在2.1节中，首先借用常规列生成算法思路建立列生成优化模型；2.2节中，为求解未知列向量Pj，这里引入递推矩阵Sj和常数向量Dj，并对它们进行递推求解；具体算法实现流程步骤见2.3节。

2.1 列生成优化模型的建立

针对一定环境下对于一维下料问题进行描述，实际优化目标主要有两个：一是原材料使用量最少；二是余料总和最少。这里是原材料的使用量最少，建立数学模型如下：

（1）以最小化原材料消耗量为优化目标：

xj≥0且为整数，j=1，2，…，n

式中：xj—决策变量；表示第j（j=1，2，…，n）种有效切割方式重复的次数；n—切割方式数

（2）满足需求约束：

式中：m—零件种类数；d i—每种零件数量，并且m=n。

（3）满足有效切割方式约束，指切割原材料的余料长度小于最短零件长度lmin的切割方式：

为降低水体中各类水质要素的浓度水平，改善大伙房水库的水环境质量，对排放进入水库的污染源进行控制并削减其排放总量。本次设计了3组数值试验，如表1。

式中：li—每种零件长度；H—原材料的长度，并且数量不限；ɑij—第j种切割方式切割出来第i种零件的数量。

（4）常规列生成算法的研究步骤可知，需要把整数规划模型转化成基于列生成的优化模型，上面中约束条件中的需求约束公式（2）的矩阵表达式，如式（4）所示。

式中：A—系数矩阵；Pj—m×1阶的列向量，也是该线性规划数学模型的未知向量。

（5）用变量Pj来表示的X：

式中：Dj—1×m阶的不等式右边的常数向量；kj—满足一定条件的非负常数项；Sj—递推矩阵，也是m×n阶的矩阵。

（6）利用上述X的表达式，将下料模型中的未知变量X消去，得到关于未知列向量Pj的基于矩阵变化列生成的线性规划模型，如下：

式中：j=1，2，…，n；C—1×n阶已知常数向量，为目标函数中价值数系，取值为C=(c1，c2，…，cn)=(1，1，…，1)；Pj≥0；Dj—1×m阶的不等式右边的常数向量，其数值由相关递推关系式获得；L—各种零件的长度集合，是一个1×m阶的已知行向量，其数值为L=(l1，l2，…，ln)

2.2 递推矩阵的生成

以数学模型（6）为例，阐述递推矩阵的生成，观察数学模型（7）可知，只有Sj和Dj为未知向量，要求解决策变量为Pj的模型（6），则必须先求出Sj和Dj。由于j=1，2，…，n，所以每次Pj的求取都必须先求解模型（6）中的未知向量Sj和Dj。通过观察发现Sj和Sj-1是存在递推关系式。在转化模型求解添加列Pj的过程中可以归纳得到递推矩阵Sj的递推关系式。

式中：S1—单位矩阵。

（2）未知向量Dj和递推矩阵Sj也存在关系，通过递推矩阵Sj可得Dj，令Dj(i，：)=kj，带入模型（6）中参与求解模型。

式中：D1—由问题可知的已知向量。

2.3 递推矩阵的列生成法求解问题步骤

针对模型（6）的求解，采用单纯形法和分支定界法相结合的方法进行求解，得出整数添加列Pj。为更清晰地阐述这里的算法在一维下料问题中的应用，采用这里的算法求解常规线性规划问题过程，如图1所示。

图1 这里的算法求解常规线性规划问题过程Fig.1 The Algorithm Here Solvesthe Conventional Linear Programming Problem

将最后一次生成的添加列Pj带入相关公式X=D-kSP和Z=C(D-SPk)中，可以求得的原问题模型的决策变量X和目标函数最优值Z。

3 案例分析

实例运行的计算机的配置如下：Inte（l R）Pentium（R）CPU G630＠2.70GHz，RAM为6.00GB，64位操作系统。软件版本为MATLABR2016a（9.0.0.341360）64-bi（t win64）。

在本节中，为了验证算法对一维下料方式的有效性，从降低下料方案数量方面针对一组数值数据采用多种算法优化求解并将结果与这里采用算法所得的结果进行分析比较，验证算法的优势。在工业切割下料中，满足给定订单所需的下料方案的数量对于切割下料设备可实现的产能可能是至关重要的，因为在不同下料方案之间进行切换下料通常需要耗费一定的时间。因此，在规划切割下料时，不一定只要求最小成本的下料方案，而且还需要要求具有较少（或甚至最少）的下料方案数量。对于生产设备不足，产能有限的工厂，每种下料方案的切换都需要重新设置下料设备，此过程必须中断切割下料过程，那么就会产生耗时的情况。所以为避免非生产性的设置时间，最小化下料方案数量对生产设备不足的工厂尤为重要。

现有另外一组有关一维下料方面的订单，原材料长度为1000，供应充足。现需要下料10种零件，10种零件的长度和需求，如表1所示。

表1 订单数据Tab.1 Order Data

为评估这里的算法对一维下料方式的有效，这里与Cláudio Alves et a（l 2009）、Foerster和Wäscher（2000）、Araujo（2014）、Yanasse（2006）等人为减少切割下料方案数量而提出的算法进行测试比较。这里他们采用的算法分别命名为Claudio、KOMBI、MOGA和Yanasse。对表1中订单的数据进行测试，分别采用Claudio、KOMBI、MOGA、Yanasse和采用算法进行优化求解，得出下料方案数量，如表2所示。

表2 多种算法求得的下料方案数量Tab.2 Number of Blanking Schemes Obtained by Various Algorithms

每种算法相对于Claudio产生的百分比变化，如表3所示。

表3 每种算法相对于Claudio产生的变化/%Tab.3 Variations of Each Algorithm Relative to Claudio/%

表中：负号“-”—在排样方案数量方面每种算法相对于Claudio减少的变化，反之，若出现加号“+”，则表示增加的变化。

由表3分析可知，在降低下料方案数量方面，KOMBI、MOGA、Yanasse和这里的算法相对于Claudio分别降低了6.18%、4.25%、4.45%和9.09%。对比数据可知这里采用的算法相比较MOGA和Yanasse两种算法得到了更大的百分比变化数值，大幅度地降低了下料方案的数量，相比较KOMBI算法在降低下料方案数量方面，这里采用的算法也表现良好，结果证明了此算法对于一维下料实例应用的有效性。

4 结语

针对一维下料问题，建立数学优化模型，采用一种基于递推矩阵的列生成新的迭代方法，更新了传统方法中求解逆矩阵的迭代过程。并通过对比其他算法，这里的算法从降低下料方案数量，针对案例分析得到了理想的结果，验证了采用算法在一维下料领域的有效性和优势。