铁塔制造中角钢优化下料系统设计思想与算法探讨

■程 默 ■江西省送变电建设公司，江西 南昌 330200

由于原材料的价格的不断升高和日趋激烈的市场竞争，使得铁塔制造企业必须要面对降低生产成本、提高生产效率等问题。工业领域中下料问题的应用十分广泛，在理论上铁塔行业中的角钢下料属于NP完全问题中规模较大的，所以对其进行求解的过程比较复杂。现在仍然有许多企业采用手工计算的方式，这样不但材料的利用率不高而且还浪费了时间，虽然有的运用了计算机辅助下料方法，但是功能和方法比较单一，没有办法与采购、库存等各个部门实现数据的协同、共享工作，导致下料流程不合格。所以，探讨铁塔制造中角钢优化下料系统设计思想与算法具有重要的工程应用价值和理论意义。

1 优化下料算法

工业当中，关于优化下料的问题，在国外称为CSP，包括材料的排样问题、切割问题和装箱问题。根据是否为空间尺寸下料问题可划分为广义下料问题和狭义下料问题。在工业领域当中，下料问题存在的比较广泛。对于下料问题的不断深入的研究，可以得出目前主要的求解手段有两大类:

1．1 最优解法

数学模型中一维下料问题是一个对整数进行规划的问题，一般的下料优化方法是通过将整数变量松弛后，看做是线性规划，运用单纯形方法进行求解，然后将得到的结果圆整，但是这样不能确保一定得到最优解，并且进行圆整后会导致零件生产过量或者生产不足，这就需要对其进行再处理;也可以运用针对整数规划求解的割平面和分支定界法进行求解;与此之外还可以采用枚举法，通过比较可行解空间内所有点的目标函数从而找出下料问题的最优解;但是这些方法计算效率比较低，经常因为解空间太大而对实际问题的处理束手无策，所以这些方法只能对小规模问题进行优化。

1．2 启发式算法

优化下料问题作为一个NPC难的问题，有复杂的计算程度，求解时间根据问题规模呈现指数级的增长，所以通常没有多项式算法。由于存在复杂的实际情况，所以不能通过最优算法来求得每个问题实例中的最优解，因此启发式算法的求解比较常用。针对最优算法，可以用启发式算法来这样进行定义:如果算法是基于经验或直观构造，那么在能够接受的花费下为待解决优化问题的每一个实例给出一个可行解，是无法事先预约这个可行解与最优解存在的偏离程度的。通过启发式算法寻找出最优解的近似解，可以在可接受的花费的前提下得到一个满意的问题解，使得生产实际中能够应用优化下料技术，所以启发式算法在现阶段的研究较多，根据规则的不同，启发式算法的构成也不同。

2 设计优化步骤

2．1 零件分组

对于下料的实际生产当中，我们需要安排许多种类的零件，通过长度对零件进行分组，对每组的四个零件优化，这种方法所得到的最优解只是每组内的一部分的最优解而不是得到整体的。我们可以运用这样的分组原则:将截面规格相同的零件按照尺寸长多进行从大到小的排列，取出两个最小长度零件和最大长度零件，将取出的这四个零件合成一组，使得零件可以长短搭配。根据这种分组原则，不仅可以使安排所有这四种零件的概率得到提高，使原材料的消耗得到降低，还使下料的排列方式数量得到减少，并提高了优化计算程序总体运行速度，使系统的稳定性得到了加强。

2．2 求全部下料方式

分组后可通过下面步骤求出下料方式:(1)零件的种类数不大于4时，可以直接进行数学模型的计算，如果零件不少于1种时，根据前面的分组原则对零件进行分组。(2)对截面规格相同的原材料的尺寸长度种类数进行判断，如果种类数是1时，可以直接求得所有下料方式，如果种类数比1大时，要先将对应的1种原材料尺寸的所有下料方式求出，这时所求的4种零件只剩下3种零件了，依次进行判断，可以得到全部的下料方式，也就是4种零件所对应1种原材料的尺寸长度的所有下料方式。(3)将每组零件对应的原材料的所有下料方式相互混合在一起，就可以得到了每组零件对应于所有原材料的各种下料方式，线性规划方程组当中的系数矩阵正是由这些下料方式组成。

2．3 关于整数线性规划

求出下料方式以后就可以建立整数线性规划的相关模型了，对于设计角钢的优化下料，决策变量要求只取出整数值，求出的解中不能够出现小数或分数，使所用原材料总根数最小等于目标函数和以达到零件需要量为约束条件所进行的数学规划问题就是角钢优化下料问题。可表示为:MAXZ=CX;Aχ≤b;χ≥0。

其中，C代表下料方式的最大可利用长度。

对与不等式约束条件极值问题，最普通的算法和一般求解的方法是单纯形法，总体思路:先要引进人工的变量，把数学整体模型转变成标准的线性规划方面的问题。通过已经得到的等式相互约束条件将目标函数当中的某些自变量约去，使得非基变量变成零，求出一组基向量所对应的基本可行解，通过这种基本可行解进行考察，看使目标函数达到最小值的是不是这一点。不是话，再去考察其他的基本可行解使得目标函数达到最小值。

对于原始单纯形法，每次进行迭代都要将整个单纯形表改写，对于单纯形表上的所有数据，都要参与到运算当中，某些运算其实是不必要的，如果约束方程的变量个数n和个数m比较大时，对于计算机的计算量和储存量要求都很大，会导致计算量和储存量方面的浪费，对单纯形法进行改进，将单纯形法当中需要的计算依次按格式排列，防止出现不必要的计算。

3 结束语

对于角钢的优化下料系统，整个系统的核心是优化计算模块，所以想要实现计算功就要有高性能的算法。我们要加大对下料系统的算法研究，以确保满足当前阈值的下料方式，兼顾加工难度、利用率以及整体计算时间。本篇文章将铁塔厂角钢优化下料工作做为应用的背景，不断提高原材料利用率和下料车间工作效率，从生产管理和下料技术两个的角度出发，探究了角钢的优化下料系统，优化了下料工作的整体性，加大了市场竞争力和企业快速反应能力。

［1］李琼，金升平．一维优化下料问题的模型与算法的综合比较［J］．武汉交通科技大学学报，1998．

［2］华中平，张立．基于线性规划的角钢优化下料算法研究．湖北工业大学学报，2005．

［3］王连杰．基于线性规划的一维优化下料系统研究与与开发．大连理工大学硕士论文，2005．