多级下料问题的建模、二十面相对挤压镁锂合金的强化作用.docx

《多级下料问题的建模、二十面相对挤压镁锂合金的强化作用.docx》由会员分享，可在线阅读，更多相关《多级下料问题的建模、二十面相对挤压镁锂合金的强化作用.docx（17页珍藏版）》请在第一文库网上搜索。

1、多级下料问题的建模摘要在多级下料问题（CSP）的切割过程是分布在几个连续的阶段。每一个阶段除了最后一个生产中间产品。中间产品清单可给予或任意。我们的目标是尽量减少材料总量减少了产成品库存足以满足采取客户的需求。如果中间的大小，给出了列生成技术可以应用到多级切割问题。如果中间的大小也得不到那么另一个方面是增加了问题的复杂性。我们建议对于这种情况，动态生成两行（中间大小）和列的特别程序模式）。我们把这种为行和列的生成方法。该方法使用一个辅助问题嵌入修订后的单纯形算法框架。这是一个非线性背包问题，可以有效解决。与此相反对列代方法开发的技术不能保证最优解。然而，结果计算实验是非常有前途，并证明该方法是

2、一种宝贵的工具除了为多级CSP的建模和求解。2002年Elsevier科学B.诉保留所有权利。关键词：线性规划;多级料问题;大规模优化，行和列代1简介一维下料问题（CSP）的推广具有重要的现实时，切削过程是分布在几个连续的阶段。这不仅包括多级CSP的切割模式和他们的活动，而且中间产品和生产它们的数量每一个阶段除了最后的切割工艺之一，并在每一个阶段的切割过程消耗除第一一。这些中间产品削减生产规模较小的中间或成品尺寸。中间产品产量和在切割过程的输入。这种问题发生在几乎每一个行业，一个典型的CSP的发生：纸张，薄膜，皮革，钢铁等虽然本文的结果同样适用于任何行业，多级切割需要为宗旨的地方，学科领域说明

3、，我们将使用的术语在造纸行业所接受。特别是，我们会将向作为其宽度几何定义的产品推出。轧辐直径，展开纸的总长度，纸卡尺不适合目前的调查有关。图。1说明了三个阶段的切削过程。在这个例子中三种类型的股票中一滚,S2和S3是用于生产九成品卷（的Fl - F9键）类型。有趣的是，股票辑能提供任何阶段的进程。在这里，中一去的第一阶段，S2的进入到第二和S3去了三分之一。相反，成品相可以生产在任何阶段。三种类型的中间限为, 12和13被切断前两个阶段。显然，我们可能会看到股票种类，中间产品的扩散，即使削减实际问题阶段。是一个重载多级字，特别是在运筹学和CSP领域。吉尔摩和戈莫里7指的是二维CSP的切割沿第一

4、条解决了，然后通过切割带自己的跨越，作为一个多阶段的问题。在我们的情况下，所有削减都是沿（纵向）和问题是一维的CSPo Dyckhoff3提出的多级为所谓的一切模型切割多级。一切模型是一个极端的例子不是一个常见的，众所周知的情况下一阶段的问题，无限的削减。有趣的是注意到，这些一切和多切模式只是同一个问题的两个不同的配方，而在现实世界的情况下，一期CSP是往往是多级CSP的放宽。一阶段放宽提供了一个合理的下界原来的多级CSP的。几位研究人员袭击了多级的CSP。哈斯勒9提出了一个以两阶段问题络筒机在第一阶段，在第二条生产复卷。他探索的方法与模式唱片代要么事先或在单纯使用迭代列生成技术。他代表在成品

5、卷筒和检查方面络筒机模式模式是否可以被分解成一中间辐组合合法。如果这样的组合是允许的，该模式被接纳对问题的矩阵。虽然这种方法是可行的，它有一些缺点。它潜在的，包括不同中间辑数量庞大，并确定是否可以分割的格局是一复杂的装箱问题。止匕外，这种方法并不容易切削加工规模更以上两个阶段。费雷拉和其他4也探讨两阶段的问题，他们称之为两阶段问题。笔者改编哈斯勒的顺序启发式程序8,最初为一典型的开发总警司，在两个阶段的切削过程。在每一个连续的过程步骤，他们正试图寻找一套好中间辐保证了第一阶段和第二好的模式的良好格局。如果在第一阶段的模式被接受，在成品卷筒上残留的问题是更新，减少了下令由模式及其活动定义的金额数

6、量。显然，这类似于启发式为解决一两个阶段的CSP手工操作。与此启发式的主要困难是产生一组良好的中间辐。卡瓦略和罗德里格斯1按照线性规划的方法。他们的问题，但是，是受一个技术限制，完成了一个卷筒，宽度应包括每一个中间辐。的限制允许预定义一个可能的中间辐名单。笔者重新初始LP问题成唱片中提出的问题方面，成品辐中间辐的条款。阿列生成与常规的辅助问题背包技术被应用。一个的中间辐智能一代的想法10出现时，两个阶段的系统-削薄和切割-进行了研究。在本论文中，我们的思想结晶，并提出一行和列求解多级一维的CSP发电技术。该技术是一种列生成的精液技术的推广建议的Gilmore和戈莫里5, 6为一个典型的CSP解

7、决，或在我们的符号，一个单级的CSP。对于一个多级的问题，更复杂辅助问题可能会导致列进入基础上的候选人，连同组合行相应的新的中间辐。我们扩大在LP矩阵行和列。一个有限单纯形算法的迭代次数,导致要么最优或接近最优的解决方案。在接下来的章节中，我们将制订两个阶段的CSP两种基本模式，目前行andcolun代方法，然后分析计算实验。结果有些从作者的论文借来的12。2模型的中间辐定列表有三种根尺寸名单：列出股票的大小。列出的中间尺寸。列出成品尺寸。请看图。2 （-）,这表明辐之间的关系，这三种类型。股票体积可用金额是众所周知的。股票的大小可能会被消耗在切削过程的每一个阶段，可切成中间或成品卷筒。中间短

8、的输入和输出。该中间辐技术的限制非常严格：每卷的大小所消耗的总人数不能超过生产量。理想情况下应该有一个总的平衡，否则，有些过度无人认领的中间辐数量应该去库存在仓库里，如果有存储空间可用。但是，这是另一种材料的浪费之间的折衷与相关的成本和仓储问题成本，这超出了目前的调查范围。因此，我们认为我们正在考虑开放与不等式约束的问题，我们认为浪费无人认领的中间辐。对于成品辐拥有一支管理有序的数量应得到满足。在这里，我们考虑一项股票辐宽度为两阶段的CSP将在第一阶段切成几个（图2 （b）中间辑。产成品辐在第二阶段削减中间卷。我们假设一个中间辐宽度出来的第一阶段，将第二个满足最低最高限制。每一个中间辑宽度也应

9、包括一个最小边将在第二阶段修整。让W和Y是成品，中间辐宽度载体，分别为。的切削模式第一阶段和第二阶段为代表的All和A22号矩阵分别。为了弥补一个完整的唱片我们定义另一个矩阵矩阵A12往，显示两者之间的关系。每一列连接的J矩阵的A12矢量，其中只有一个非零元素金次黛1趺械出现在我的位置相对应的中间辐我认为应削减根据裁剪定义列矩阵A22座因子。我们可以制订一个多级CSP的线性规划模型：在这里，向量xl和x2是图案活动的第一和第二个阶段，分别为B是向量要求对成品辐目标函数（1）尽量减少所用的股票，是由长期ITxl定义成双数。约束（2）保证中间辐在第二阶段A12x2消费应不超过其在生产Allxl第一

10、阶段，的B卷客户需求应该得到满足。请注意，整体矩阵具有特殊的结构。有两个对角块All和A22号代表两个阶段切割图案，连接A12座，以及0块在左下方角落。右手边是由由0上的中间辐和载体的需求湾模型（1）- （3） 一个两阶段的CSP唱片介绍，明确涉及中间辐。该矩阵可能已满如果问题比较小。在这种情况下，对各个阶段的所有模式可呈现在矩阵。否则，是一个列选择适当的技术在网上列生成。但在两种情况下，我们是否提前产生的所有列，或使用列生成，在矩阵的行数保持不变，因为可能的中间大小的列表给出。2.1 双重问题在这里，向量U1和U2是双变量向量对应的中间辐和成品辐，分别。对偶问题（4） - （6）辅助导致两个

11、问题，应该在解决类型的列选择步骤，修订后的单纯形算法。2.2o列生成在第一类的辅助问题，是关系到第一阶段削减模式生成切削过程。中间辑列表保持不变。显然，这种类型是与第一组问题的双重约束（5）,辅助问题在本质上是相同的背包问题，因为我们在一个典型或一个阶段的CSP。辅助问题可以表示为背包以下问题：在这里，U1是一个目标函数的系数是主问题的双变量的值向量;Y是中间辐宽度载体；W0的是股票辐宽度和向量a是一个变量的向量。如果目标函数值超过1.0, 一个新列第一阶段产生。这种情况紧跟从第一组的限制（5）可作为UT斯达康提交一答1161To该为解向量进入到矩阵答11列对第二类是辅助问题与成品辐切割产生的

12、模式利用现有的中间辐。这种类型是与约束（5）第二组。对于每个中间辑系列YJ我们应该解决以下背包问题：在这里，U2是目标函数的系数是主对偶变量值的向量问题；w是一个成品尺寸的载体；额敏是一项强制性的最低边缘，eminPO;鹰击是中间宽辐J和向量a是一个变量的向量。让ulj是一个双变量的值对应于j的中间尺寸如果目标函数价值超过ulj,一个新列第二阶段产生。这种状况紧跟从约束第二组（5）可作为UT斯达康提交2 A22号6 UT斯达康一答12o由于矩阵答12结构，右边归结为对偶变量对应的中间载体卷。该解决方案作为载体进入A22号为矩阵列。如果我们没有中间辐中的不确定性，上述两种类型的背包-背包i和背包

13、第二至足以解决问题最佳状态。3o模型未知的中间辐如果中间辐是未知的，我们面临更加复杂的局面。我们可以自由地选择任何合适的从一个给定范围内的中间大小YYmin成员；yMax的。由于每个中间辑和轧辐成品关联用矩阵的唱片，在唱片的不确定性矩阵在两个方向延伸行：歹U和行。出于这个原因，一列生成技术不能单独解决这个问题。另一方面，中间辑潜在的巨大数目可能产生的一切可能性预先排除。我们可以估计在现实生活中不同的中间辑潜力。让颐，范围为中间辐宽度。参数锢是依赖于机器的，但通常颐800毫米。设d是至少幅宽的精度。通常情况下为0.5毫米。因此，不同N =4辐这个公式给我们一个估计61600。当然，对于特殊情况的

14、多级CSP的估计可能是少得多。虽然如此，全尺寸的LP矩阵往往是非常大的。另一种说法，对先进的中间辑代的是一个业务问题。该在一次中间辑的多样性减缓物质流，复杂滚跟踪任务，并提供切割作业少的灵活性。一家造纸厂总是倾向于用最少的操作一些不同中间辐尺寸。不用说，这将是非常可取的有一个聪明的办法产生中间辐这可以做切割模式-只在需要时。下一步，我们将目前的行和列的一代技术的两个阶段的问题(1)- (3)o3.1o行与列代随着背包一，二和背包，我们可能面临的问题与第三类辅助同时产生新的中间辐和切割模式。在这里，我们应该记住矩阵的唱片行目前的中间和成品卷。 (如果我们对股票的限制，我们辐将包括额外的行卷，以及

15、股票。)的LP模式矩阵的列切进入中间辐和中间辐到成品的股票名单。在这里，我们正在努力适应修正单纯到一个任务，是不是它的典型。据了解，上每一步的修正单纯一列正进入更换的基础和另一列是离开的基础。如果列在事先不知道，我们使用一列生成技术，扩大了 LP矩阵列方向。修订后的单纯没有使我们有能力产生未知行。现在的问题是如何能产生未知的中间辑使用修订后的单纯的步骤？让我们限制搜索生成中间辐不超过上一个新的中间辐修订后的每一个单纯的一步。因此，我们应该生成矩阵的新的唱片行，并在非退化的情况下，矩阵的秩的唱片将有效地增加1。矩阵的基础上，应还可以扩大一行和一列，因为只有一列叶片旋转过程中的基础第一步，我们得出结论，两列实际上应该是在一个单一步骤生成。其中一应添加到矩阵基础上无条件地与其他人都不应取代现有的一个旋转的一步。让向量y为中间辐尺寸已经在模型到目前为止，变量z是一个新的中间轧辐尺寸和V是一个相应的对偶变量。我们面临如下非线性整数规划问题：这里有两个变量新列：列在第一阶段和第二阶段柱A22