实用一维下料问题模型与求解算法

《实用一维下料问题模型与求解算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第八届中国青年运筹信息管理学者大会论文集桂林，2005年8月18—22日，第556—561页实用一维下料问题模型与求解算法袁月明1龙建成1许鹏21北京交通大学交通运输学院，北京，100044；2北京交通大学电子信息工程学院，北京，100044摘要本文针对单一原材料下料问题原材料需求量大、零件类别多、生产时间有限制等特点．考虑到依据人工经验根难给出全面的而且最优的下料方式集合．分别建立了一维下料问题最佳下料方式获取模型和下料方式选取模型；并且提出了可行的下料方式生成算法，采用LINGO软件实现了相应的模型和算法。计算结果表明本文对一维下料问题的求解模型具有普适性、易操作性、结果可靠等优点。

2、关键词一维下料问题，下料方式．方式选取模型，LINGO1引言下料问题在工业或建筑业许多原材料生产中经常涉及到，根据原材料和生产零件产品的不同可以分为一维下料问题和二维下料问题。如何建立合理的模型和良好的求解算法是目前普遍关注并研究的问题⋯”““1。下料问题可以看作为最优化问题的一子问题，可以应用线性规划、整数规划问题的解法进行求解⋯I，但当原材料的数量和所需产品的个数都很大时，问题的规模会迅速增加变得非常复杂，利用现有的算法求解不具有可操作性而且很难或者几乎不可能得到最优方案。针对上述问题一些学者提出采用遗传算法⋯⋯”“⋯⋯⋯、模拟退火算法⋯I和神经网络等最优化搜索算法对其进行建模并利用

3、计算机模拟进行求解”1，但是不可避免会出现收敛速度慢、陷入局部极小值等问题。因此，本文针对一维下料问题的实际特点，提出一种简便易行的求解算法，并且得到了很好的应用结果。2变量及符号说明单一原材料的一维下料问题可以表述为：利用长度为L的某种原材料，切割成”种不同长度的产品：魂，玟，⋯，魄．原材料与所需产品的厚度相等，若所需产品的个数分别为置，k，⋯，≈。，问如何下料才能充分利用原材料使下料后的剩余边料总长最小，从而使材料利用率最大，达到减少材料损失、降低成本、提高经济效益的目的。在实际生产实践中可能还要求在厂商生产能力容许的条件下，以最少数量的原材料，尽可能按时完成需求任务，同时保证下料方

4、式数也尽量地少。本文中使用的变量及符号说明如下：实用一维下料问题模型与求解算法f：零件标号，最大标号为s；L：第i号零件长度：L；原料总长；Ⅵ：第i号零件宽度；w：原料宽度15i：第i号零件需求数量；盯：一维下料每个切割点由于锯缝所产生￡：每天最大的下料能力；的损耗：，。：宽度为w的零件标号集合；Ⅸ：一种下料方式产生标号为i的零件的个数；丁；要求完成期限；3模型本问题的求解目标是在生产能力容许的条件下，以最少数量的原材料尽可能按时完成所需产品的需求任务，同时保证下料方式数尽可能少，所以建立合理、适当的下料方式集合是基础性的一步。如果所需产品的数目太多，那么下料方式的组合数目也会变得十分庞

5、大，很难一一列举出所有有效的下料方式，最优下料方式更是几乎不可能，因此我们构建了求解边料最省的下料方式模型称为最佳下料方式获取模型和求解边料次省的下料方式模型称为下料方式选取模型，从中选取有利的下料方式集合达到求解目的。3．1一维最佳下料方式获取模型一维下料方式获取模型的实现关键就在于可行的下料方式的获得。废料少的下料方式总是更容易被采用：因此，有必要建立一个获取最佳(废料最省)下料方式的模型。模型以废料最省为目标，以下料方式满足材料原长，零件数量不超过要求生产数量为约束。建立模型(1)如下：IIlinz=L->：啦‘(1)fst．∑啦‘+(∑％一1)tT_

6、)Ⅸ≥0且为整数Vf其中：，l；表示标号为f的零件要求的生产数量，这里《不一定是珞。目标函数(1)表示废料最省；约束条件(2)该下料方式生产的零件，其长度之和以及锯缝损耗的总和不超过原料长度；约束(3)保证不会由于超额生产零件而增加余料。3．2一维下料方式选取模型在建立模型前，需要得到可行的下料方式集合Ui然后，在U中选取有利的方式进行原材料分割。模型以原材料最省以及下料方式最小为目标；按照时间限制要求完成任务为约束。建立模型(2)如下：袁月明龙建成许鹏rainzi=∑xjrainZ2=∑吩St．∑a,jxj>--ni∑8，T工』≤T-E(1一％)xj=O工，≥O且为整数W(4)(5)(

7、6)(7)(8)其中：xi表示第J种下料方式的下料数量。瞄；表示第J种下料方式生产标号为f的零件个数。y，、辞为0-1变量，第，种下料h-式被采用则yf=1，否则y，=0。第J种下料方式包含需前了’天完成的零件则矿=l，否则矿=0。目标函数(4)表示使用最少的原材料：目标函数(5)表示使用最少的下料方式：约束(6)表示满足各类零件的生产要求：约束(7)表示有生产日期要求的零件在规定日期内完成；约束(8)描述变量沙；。由于模型(2)为