整数线性规划模型在切割问题中的应用

俞雅静　钱峰

摘要：本文利用整数线性规划理论，讨论了单样矩形构件切割优化模型的建立与求解问题，并利用仿真实验证明了最优切割结果的合理性和有效性。

关键词：整数线性规划模型;分枝定界法;仿真实验

1.引言

切割问题在各领域中都有着广泛的应用，如汽车、船舶等金属材料的分割，服装、玩具、鞋子制造过程中布匹或皮革的下料等[1]。优化切割问题的排样方案，可以减少切割过程中存在的资源浪费现象，是企业降低生产成本，增大生产效率，承担环境责任要解决的关键问题[2]。切割问题的核心是规划产品在原件上的排列布局，从原件中分离出产品进行加工和制造使用。很多学者对矩形件排样进行研究，提出多种切实可行的排放算法和优化算法[3]。

2.整数线性规划原理和方法

整数线性规划（ILP问题）是要求变量取整数值的线性规划问题。它以线性规划的最优解为出发点，运用多种基本算法求解。ILP问题的一般形式如下：

变量取整实质上是一种非线性约束，这使得求解困难程度加大，其中分支定界法是求解ILP问题的有效方法，其基本思想是枚举ILP问题的可行解。

3.矩形构件切割问题的整数线性规划模型

单样矩形产品构件切割问题通常是将一块矩形产品构件，互不重叠的排布在一个大的矩形原料上，在满足一定的工艺要求的前提下，充分利用原料的各个边，直到原料的利用率达到最高。切割时要在产品不超过原件边界，产品不互相重合的情况下，尽量多的满足产品摆放数量最多，且原料的边角余料最少且不可以再利用，就要设计出适合不同约束条件下的矩形排列优化方案。

为建立产品构件切割问题的数学模型，首先定义变量：L、W是原料的长宽;l、w是产品的长宽;X1是横向上产品横向排列的个数;X2是横向上产品纵向排列的个数;Y1是纵向上产品横向排列的个数;Y2是纵向上产品纵向排列的个数;在切割产品的时候，通常从原件的边界开始切割，使边的利用率达到最高。最外层排列完之后，再向内部剩余的面积以相同的方式进行切割，如此循环往复，直到剩余原件的面积无法进一步的切割，从而达到原件利用率最大。

其中约束（2）表示在原件横向上排列X11个矩件，纵向上排列X12个矩件，要保证横向上排列的长度小于原件的长;要求存在都是横排或纵排的矩件的长度要小于原件的宽，从而使切割产品的面积占原件面积得到最大值。

利用LINGO软件实现分枝定界法的求解（见图1），求出的切割最优解为，即原件横向上产品横

向排列有1个;纵向上产品横向排列有7个;横向上产品纵向排列有13个;纵向上产品纵向排列有4个。共计需要59个，其中产品构件的最大利用率约为98.3%

4.切割问题模型仿真

为了有效验证上述模型解的最优性，利用玻璃切割优化软件将切割问题模型得到了实现。分别在一块原件中模拟切割54-59块产品，并设计算出横竖切割的产品个数和原件的优化率，见软件切割的仿真模拟图：

通过玻璃切割優化软件的仿真模拟，可以得出最优的产品构件切割方案：切59个产品，原件的利用率最大：98.30%

5.结论

本文围绕着整数线性规划模型在切割问题中的应用进行研究，从理论和方法上面进行探讨，并利用玻璃优化切割软件将切割模型得到进一步的验证。因此得出该模型可操作性性强，具有很强的适应性和可变性，可在市场上推广使用。

参考文献

[1]Dagli.C.H，and tatoglu， M.Y.An approach to two dimcnsional cutting stock problems[J].Intcrantional Journal of Production Rcscarch， 1987，25： 175-190.

[2]刁在筠，刘桂真，戎晓霞，王光辉.运筹学[M].4版.北京：高等教育出版社，2016.07.

[3]陈仕军.矩形件下料优化算法研究[D].华中科技大学硕士论文，2009.

作者简介：俞雅静（1998-），女，本科生，主要研究方向：应用统计;

钱峰（1975-），男，副教授，主要研究方向：高等数学，概率论与数理统计，运筹学整数线性规划。