实用下料问题

好用下料问题 一．问题的重述 “下料问题cutting stock problem”是把相同形态的一些原材料分割加工成若干个不同规格大小的零件的问题，此类问题在工程技术和工业生产中有着重要和广泛的应用. 这里的“好用下料问题”则是在某企业的实际条件限制下的单一材料的下料问题。 现考虑单一原材料下料问题. 设这种原材料呈长方形，长度为,宽度为，现在须要将一批这种长方形原料分割成种规格的零件, 全部零件的厚度均与原材料一样，但长度和宽度分别为，其中wi＜. 种零件的需求量分别为.下料时，零件的边必需分别和原材料的边平行。这类问题在工程上通常简称为二维下料问题。特殊当全部零件的宽度均与原材料相等，即，则问题称为一维下料问题。 一个好的下料方案首先应当使原材料的利用率最大，从而削减损失，降低成本，提高经济效益。其次要求所采纳的不同的下料方式尽可能少，即希望用最少的下料方式来完成任务。因为在生产中转换下料方式须要费用和时间，既提高成本，又降低效率。此外，每种零件有各自的交货时间，每天下料的数量受到企业生产实力的限制。因此好用下料问题的目标是在生产实力容许的条件下，以最少数量的原材料，尽可能按时完成需求任务, 同时下料方式数也尽量地小。现在我们要为某企业考虑下面两个问题。 1．建立一维单一原材料好用下料问题的数学模型, 并用此模型求解下列问题，制定出在生产实力容许的条件下满意需求的下料方案, 同时求出等额完成任务所需的原材料数，所采纳的下料方式数和废料总长度. 单一原材料的长度为 3000mm, 须要完成一项有53种不同长度零件的下料任务. 详细数据见表一略，其中 为需求零件的长度，为需求零件的数量. 此外，在每个切割点处由于锯缝所产生的损耗为5mm. 据估计，该企业每天最大下料实力是100块 ，要求在4天内完成的零件标号为 5,7,9,12,15,18,20,25, 28,36,48；要求不迟于6天完成的零件标号为4,11,24,29,32,38,40,46,50。 2．立二维单一原材料好用下料问题的数学模型, 并用此模型求解下列问题.制定出在企业生产实力容许的条件下满意需求的下料方案, 同时求出等额完成任务所需的原材料块数和所需下料方式数.这个问题的单一原材料的长度为 3000mm,宽度为100mm, 须要完成一项有43种不同长度和宽度零件的下料任务. 详细数据见表二略，其中 分别为需求零件的长度、宽度和数量. 切割时的锯缝可以是直的也可以是弯的，切割所引起的锯缝损耗忽视不计.据估计，该企业每天最大下料实力是20块 要求在4天内完成的零件标号为 3,7,9,12,15, 18, 20, 25, 28, 36. 二．问题的分析 在生产实践中，常常会遇到如钢材、木材等条型材的下料问题，即如何依据原材料的长度、零件的尺寸以与需求量确定出访原材料消耗最少的最优下料方案。本题要求在生产实力容许的条件下，以最少数量的原材料，尽可能按时完成需求任务, 同时下料方式数也尽量地小。 对于一维下料问题，首先我们必需找出全部可行的下料方式；然后才能确定下料方式作为决策变量和形式约束条件的结构系数，这样才能建立优化决策模型，通过计算机编程计算得到我们所须要的最优下料方案。考虑到这里是单一原材料下料问题，这大大削减了下料方式；但由于零件的种类有53种之多，因此下料方式仍旧许多，计算量很大，所以在建立优化模型的基础上，我们须要找到比较合适的算法来解决这类实际问题。近年来，国内外关于这方面的探讨比较活跃，并涌现出了不少近似算法，如Gilmore与Gomory用线性规划建立的一刀切问题的数学模型；Dyckhoff提出的线性规划方法以与Sarker提出的动态规划方法等。由于下料问题属于布局问题，不同于一般的数值性优化,近年又出现应用遗传算法来求解下料优化问题。我们力图建立一种好用的模型多目标整数规划模型[1] [2][7]，并提出一种新的优化思想方法启发式多层次逐层优化方法，解决此问题；同时与其他的求解方法进行比较。 对于二维下料问题，我们采纳分类层次分析法；由于原材料的长度为3000mm，宽度为100mm，而43种零件的长度最小的为155mm，这样就不会出现零件的长边在原材料的宽边上切割的状况，也就是说零件的长边都是顺着原材料的长边切割的。考虑到零件的宽有20，30，35，50（mm）这4种规格，为了尽量节约材料，我们应当使原材料在宽边上尽量利用完全，这样只有几种宽边完全利用的组合方式（5种），分别为50-50，50-30-20， 30-30-20-20，35-35-30，20-20-20-20-20。我们把零件按宽边的规格分为4类（20，30，35，50），对每一类都可按问题一的处理一维下料问题的方式找最优的方案，然后再把他们按上述的几种方式进行组合，以求得最优解。 三．问题的假设 1．对于第一问的假设 1） 在每个切割点处由于锯缝所产生的损耗为5mm； 2） 企业每天的最大下料实力为100块； 3） 考虑下料方式的数量对总损耗的影响，下料方式越少则原材料总损耗越小； 4） 对于剩余长度为mm的材料，可以通过微小调整锯缝的位置锯得长度为mm的零件； 2．对于其次问的假设 1） 切割所引起的锯缝损耗忽视不计； 2） 切割时锯缝可以是直的也可以是弯的，但要求转弯为直角； 3） 企业每天最大的下料实力是20块； 4） 原材料和零件都是长方形。 四．符号说明 原材料的长度（3000mm） 原材料的宽度（100mm） 所用的原材料总数量 所采纳的下料方式总数量 第i号零件的长度（单位mm，） 第i号零件的宽度 第i号零件的需求量 第j种下料方式中切割第i号零件的数量 按第j种下料方式切割的原材料的数量 按第j种下料方式切割的废料长度（mm） 第一问中要求在4天内完成的零件号的集合 第一问中要求在不迟于6天完成的零件号的集合 其次问中要求在4天内完成的零件号的集合 五．模型的建立与求解 1．对问题一的解决 此问要求在4天内完成的零件标号为 5,7,9,12,15,18,20,25, 28,36,48；不迟于6天完成的零件标号为4,11,24,29,32,38,40,46,50。而该企业每天最大下料实力是100块，我们要制定出在生产实力容许的条件下满意需求的下料方案，同时要求等额完成任务，我们的目标是要尽可能节约材料，尽可能用少的下料方式。 为此我们建立多目标整数规划模型（首先我们约定） , （1） 注1.我们有若采纳了第j种下料方式，则为大于0的整数，因此；若没有采纳第j种下料方式，则为0，如上定义可得，这样即表示了所用的下料方式数量； 2．约束中第一条是考虑了锯缝时，原材料长度L