首页 > 论文范文 > 工程工业论文 > 轻工业论文 > 木材加工工业论文 > 整数规划背景下对木板排样优化问题的探讨

整数规划背景下对木板排样优化问题的探讨

2020-07-01 464 上传者：管理员

摘要：目前,大多数工业生产过程中主要使用人工神经网络算法以及模拟退火等现代化算法来分割木材。而在实际排样过程中,使用单一的算法往往得不到最优方案。故本文根据不同排样问题的复杂程度,建立整数线性规划模型、木板排样优化模型,运用遗传算法,并利用Matlab、C++进行编程求解,得出不同生产条件下板材的最优分割方案和最大利用率,易与实际生产联系紧密。

关键词：
Matlab
整数线性规划
木材加工
木板排样优化模型
板材分割
遗传算法
加入收藏

1、概述

在实际工程技术与工业生产中，将较大的矩形板材分割为若干个不同类型矩形零件的问题，对机器设备的制造成本以及生产周期有着非常深远的影响。如何使板材的利用率最大化，是一个好的切割方案首先要解决的问题。板材优化问题就是规划原材料与每个零件的最优布局问题，使板材余料尽可能的减少，从而减少资源浪费，降低成本，提高经济效益。

2、问题分析

在解决板材分割问题时，首先要建立木板排样优化模型，寻求木板切割的最优方案，再利用整数线性规划模型做出进一步的划分，得到目标函数方程及约束条件组，运用Matlab进行编程求解，即可求解出简单的木板分割问题。为了简化计算的复杂，我们假设木板的长、宽、生产任务等均为整数。

对于更复杂的问题，如目标产品种类过多，在这种情况下，通过整数线性规划很难求出最优解，故本文引进了遗传算法来计算木板的最大利用率，并采用整数编码的方式来解决木板排样问题。另外，在解决切割多种目标产品问题时，本文引进了一个新的概念—重要度。根据每块木板上产品最多可切割的数量，得出各产品的重要度，每次进行板材切割时，按照板材的重要度依次切割，重要度靠前的板材尽可能多的切割，从而简化问题的复杂程度。

3、算法设计

在算法设计过程中，不考虑木板厚度的影响，仅以长宽作为考量标准，并忽略切割时，因技术带来的余料损失的误差。假设木板分割方式均是按照横向切割(沿木板长的方向)和纵向分割(沿木板宽的方向)，不考虑其他切割方式。如在木板A切割产品x，由数学排列组合知识可得四种切割方式，分别如下图所示。其中(1)(2)对A进行横向切割，x分别纵向和横向放置;(3)(4)对A的进行纵向切割，x分别纵向和横向放置。

四种分割方式图

确定了木板切割的四种方式后，将系统的阐述如何得到木板排样的最优方案。首先，建立木板排样优化模型。假设有相同长度和宽度的一批矩形样品P1，其面积集合为为{Ki};另外有与原木板相同长度和宽度的一批木板Si，其面积集合为{Qj}。木板的排样其实就是将这批样品P1适当地放在木板Si上。所谓的木板排样模型就是寻找最合理的放置方式从而获得木板的最大利用率。使目标函数获得最大值:

公式1

其次，建立整数线性规划模型。整数线性规划模型是指通过线性约束条件组下，求出线性目标函数最值的一种模型。对于大部分木板切割问题，需要依据实际问题得到目标函数方程和约束条件。再依据整数线性规划的方程，运用Matlab或Lingo进行编程求解，求解出木板分割的最大利润率。

当木板切割的目标产品种类繁多，并对各类产品的生产量都有明确的要求时，需要引入适应度函数。适应度函数主要用于产品分割方案的评价，同时也是优化过程中的一个重要依据。在此模型中，适应度函数可以定义为所用木板总量h的利用率与前n-1个木板的利用率之和，具体函数如下:

公式2

其中，为h个木板S1面积之和，选用木板面积之和，为h-1个木板排放的产品Pi面积之和，为前h-1个木板的面积之和。

对于更复杂的问题，需要引入本文的核心算法—遗传算法，并采用整数编码的方式来解决木板排样问题。遗传算法的核心因子是染色体，待排产品的数目n与染色体的长度相同，产品P的排列序号记为染色体的基因编码。因此，染色体的序号可以组成0～n-1的一个全排列。然后，按照编码顺序依次将产品Pi排入木板S中，这种方式也被称为基因编码。针对木板排样优化问题，首先将系统进行初始化，木板S1和产品Pi尺寸数据读入，然后对随机生成的种群赋值，再评估染色体。通过不断的循环，如果不满足循环评估条件，则重新选择染色体并进行染色体的交叉和变异，得到最优保持并回到评估染色体流程继续循环。如果满足，即可得到最优的染色体交叉情况，从而得出最优切割方案。

4、结语

本文通过建立木板排样优化模型和整数线性规划模型，引入遗传算法，并运用Matlab,C++编程，从而求出木板的最大利用率和最优分割方案，在优化排样时具有重大意义。

参考文献：

[1]刘咏.基于梯形和平行四边形的圆片下料算法设计与实现[D].2016.05.19.

[2]余鹏.生成矩形毛坯最优四块排样方式的精准算法[D].2008.04.01.

[3]司守奎,孙兆亮.数学建模算法与应用.北京:国防工业出版社,2019.1.

[4]朱银龙,吴海云,刘琦.基于线性规划的材料切割设计研究[J].技术与市场,2018(11):95.

[5]谭汉松,彭迎春.板材最优切割算法的设计与实现[J].计算机科学与应用,2003(18):95.

[6]袁哲,王永振,赵汉驰.矩形石板优化排样及切割路径规划研究[J].制造业自动化.

吴雨婷,张玉.基于整数规划下木板排样优化问题的研究[J].科技风,2020(17):111.