多级下料问题的建模（有出处）695--中英文翻译
多级下料问题的建模
摘要
在多级下料问题（CSP）的切割过程是分布在几个连续的阶段。每一个阶段
除了最后一个生产中间产品。中间产品清单可给予或任意。我们的目标是尽量减
少材料总量减少了产成品库存足以满足采取客户的需求。如果中间的大小，给出
了列生成技术可以应用到多级切割问题。如果中间的大小也得不到那么另一个方
面是增加了问题的复杂性。我们建议对于这种情况，动态生成两行（中间大小）
和列的特别程序模式）。我们把这种为行和列的生成方法。该方法使用一个辅助
问题嵌入修订后的单纯形算法框架。这是一个非线性背包问题，可以有效解决。
与此相反对列代方法开发的技术不能保证最优解。然而，结果计算实验是非常有
前途，并证明该方法是一种宝贵的工具除了为多级 CSP 的建模和求解。¢2002
年 Elsevier 科学 B.诉保留所有权利。
关键词：线性规划;多级料问题;大规模优化，行和列代
1 简介
一维下料问题（CSP）的推广具有重要的现实时，切削过程是分布在几个连
续的阶段。这不仅包括多级 CSP 的切割模式和他们的活动，而且中间产品和生产
它们的数量每一个阶段
除了最后的切割工艺之一，并在每一个阶段的切割过程消耗除第一一。这些中间
产品削减生产规模较小的中间或成品尺寸。中间产品产量和在切割过程的输入。
这种问题发生在
几乎每一个行业，一个典型的 CSP 的发生：纸张，薄膜，皮革，钢铁等虽然本
文的结果同样适用于任何行业，多级切割需要为宗旨的地方，学科领域说明，
我们将使用的术语在造纸行业所接受。特别是，我们会将向作为其宽度几何定义
的产品推出。轧辊直径，展开纸的总长度，纸卡尺不适合目前的调查有关。
图。¢1说明了三个阶段的切削过程。在这个例子中三种类型的股票中一滚，
S2 和 S3是用于生产九成品卷（的 F1 -¢F9 键）类型。有趣的是，股票辊能提供
任何阶段的进程。在这里，中一去的第一阶段，S2 的进入到第二和 S3 去了三分
之一。相反，成品辊可以生产在任何阶段。三种类型的中间辊为 I1，I2和I3 被
切断前两个阶段。显然，我们可能会看到股票种类，中间产品的扩散，即使削减
实际问题阶段。
是一个重载多级字，特别是在运筹学和 CSP 领域。吉尔摩和戈莫里[7]指的是
二维 CSP 的切割沿第一条解决了，然后通过切割带自己的跨越，作为一个多阶
段的问题。在我们的情况下，所有削减都是沿（纵向）和问题是一维的 CSP。¢D
yckhoff[3]提出的多级为所谓的一切模型切割多级。一切模型是一个极端的例子
不是一个常见的，众所周知的情况下一阶段的问题，无限的削减。有趣的是注意
到，这些一切和多切模式只是同一个问题的两个不同的配方，而在现实世界的
情况下，一期CSP 是往往是多级 CSP 的放宽。一阶段放宽提供了一个合理的下界
原来的多级 CSP 的。
几位研究人员袭击了多级的 CSP。哈斯勒[9]提出了一个以两阶段问题络筒
机在第一阶段，在第二条生产复卷。他探索的方法与模式唱片代要么事先或在单
纯使用迭代列生成技术。他代表在成品卷筒和检查方面络筒机模式模式是否可以
被分解成一中间辊组合合法。如果这样的组合是允许的，该模式被接纳对问题的
矩阵。虽然这种方法是可行的，它有一些缺点。它潜在的，包括不同中间辊数量
庞大，并确定是否可以分割的格局是一复杂的装箱问题。此外，这种方法并不容
易切削加工规模更以上两个阶段。
费雷拉和其他[4]也探讨两阶段的问题，他们称之为两阶段问题。笔者改编
哈斯勒的顺序启发式程序[8]，最初为一典型的开发总警司，在两个阶段的切削
过程。在每一个连续的过程步骤，他们正试图寻找一套''好''中间辊保证了第一
阶段和第二好的模式的良好格局。如果在第一阶段的模式被接受，在成品卷筒上
残留的问题是更新，减少了下令由模式及其活动定义的金额数量。显然，这类似
于启发式为解决一两个阶段的 CSP 手工操作。与此启发式的主要困难是产生一组
良好的中间辊。
卡瓦略和罗德里格斯[1]按照线性规划的方法。他们的问题，但是，是受一
个技术限制，完成了一个卷筒，宽度应包括每一个中间辊。的限制允许预定义一
个可能的中间辊名单。笔者重新初始 LP 问题成唱片中提出的问题方面，成品辊
中间辊的条款。阿列生成与常规的辅助问题背包技术被应用。
一个的中间辊智能一代的想法[10]出现时，两个阶段的系统 -削薄和切
割-进行了研究。在本论文中，我们''''的思想结晶，并提出一行和列求解多级
一维的 CSP 发电技术。该技术是一种列生成的精液技术的推广建议的 Gilmore 和
戈莫里[5,6]为一个典型的 CSP 解决，或在我们的符号，一个单级的 CSP。对于
一个多级的问题，更复杂辅助问题可能会导致列进入基础上的候选人，连同组
合行相应的新的中间辊。我们扩大在 LP矩阵行和列。一个有限单纯形算法的迭代
次数，导致要么最优或接近最优的解决方案。在接下来的章节中，我们将制订两
个阶段的 CSP 两种基本模式，目前行 andcolumn 代方法，然后分析计算实验。结
果有些从作者的论文借来的[12]。
2 模型的中间辊定列表
有三种辊尺寸名单：
•列出股票的大小。
•列出的中间尺寸。
•列出成品尺寸。
请看图。¢2（一），这表明辊之间的关系，这三种类型。股票体积可用金
额是众所周知的。股票的大小可能会被消耗在切削过程的每一个阶段，可切成中
间或成品卷筒。中间辊的输入和输出。该中间辊技术的限制非常严格：每卷的大
小所消耗的总人数不能超过生产量。理想情况下应该有一个总的平衡，否则，有
些过度无人认领的''''中间辊数量应该去库存在仓库里，如果有存储空间可用。
但是，这是另一种材料的浪费之间的折衷与相关的成本和仓储问题成本，这超
出了目前的调查范围。因此，我们认为我们正在考虑开放与不等式约束的问题，
我们认为浪费无人认领的中间辊。对于成品辊拥有一支管理有序的数量应得到满
足。
在这里，我们考虑一项股票辊宽度为两阶段的 CSP 将在第一阶段切成几个
（图2（b））中间辊。产成品辊在第二阶段削减中间卷。我们假设一个中间辊宽
度出来的第一阶段，将第二个满足最低最高限制。每一个中间辊宽度也应包括一
个最小边将在第二阶段修整。
让W和Y是成品，中间辊宽度载体，分别为。的切削模式第一阶段和第二阶
段为代表的A11 和A22 号矩阵分别。为了弥补一个完整的唱片我们定义另一个矩
阵矩阵 A12往，显示两者之间的关系。每一列连接的 J矩阵的A12矢量，其中只
有一个非零元素鈥樷€1鈥欌€出现在我的位置相对应的中间辊我认为应削减
根据裁剪定义列矩阵 A22 座因子。
我们可以制订一个多级 CSP 的线性规划模型：
在这里，向量 x1和x2 是图案活动的第一和第二个阶段，分别为 B 是向量
要求对成品辊目标函数（1）尽量减少所用的股票，是由长期 1Tx1定义成双
数。约束（2）保证
中间辊在第二阶段 A12x2 消费应不超过其在生产 A11x1
第一阶段，的 B 卷•客户需求应该得到满足。
请注意，整体矩阵具有特殊的结构。有两个对角块 A11 和A22 号代表两个阶
段切割图案，连接 A12座，以及0块在左下方角落。右手边是由由 0上的中间辊
和载体的需求湾模型（1） - （3）一个两阶段的 CSP 唱片介绍，明确涉及中间
辊。该矩阵可能已满如果问题比较小。在这种情况下，对各个阶段的所有模式可
呈现在矩阵。否则，是一个列选择适当的技术在网上列生成。但在两种情况下，
我们是否提前产生的所有列，或使用列生成，在矩阵的行数保持不变，因为可
能的中间大小的列表给出。
2.1 双重问题
在这里，向量 U1和U2 是双变量向量对应的中间辊和成品辊，分别。对偶问
题（4） - （6）辅助导致两个问题，应该在解决类型的列选择步骤，修订后的
单纯形算法。
2.2。列生成
在第一类的辅助问题，是关系到第一阶段削减模式生成切削过程。中间辊
列表保持不变。显然，这种类型是与第一组问题的双重约束（5），辅助问题在
本质上是相同的背包问题，因为我们在一个典型或一个阶段的 CSP。辅助问题可
以表示为背包以下问题：在这里，U1是一个目标函数的系数是主问题的双变量
的值向量;Y是中间辊宽度载体;¢W0 的是股票辊宽度和向量 a是一个变量的向
量。如果目标函数值超过1.0，一个新列第一阶段产生。这种情况紧跟从第一组
的限制（5）可作为 UT 斯达康提交一答1161T。该为解向量进入到矩阵答11 列对
第二类是辅助问题与成品辊切割产生的模式利用现有的中间辊。这种类型是与约
束（5）第二组。对于每个中间辊系列YJ 我们应该解决以下背包问题：在这里，
U2 是目标函数的系数是主对偶变量值的向量问题;¢w是一个成品尺寸的载体;
额敏是一项强制性的最低边缘，eminP0;鹰击是中间宽辊 J和向量 a是一个变量
的向量。让 u1j是一个双变量的值对应于 j的中间尺寸如果目标函数价值超过
u1j，一个新列第二阶段产生。这种状况紧跟从约束第二组（5）可作为 UT 斯达
康提交2¢A22 号 6¢UT 斯达康一答12。由于矩阵答12 结构，右边归结为对偶变
量对应的中间载体卷。
该解决方案作为载体进入A22 号为矩阵列。如果我们没有中间辊中的不确定
性，上述两种类型的背包-背包 i 和背包第二至足以解决问题最佳状态。
3。模型未知的中间辊
如果中间辊是未知的，我们面临更加复杂的局面。我们可以自由地选择任何合适
的从一个给定范围内的中间大小 Ÿ[Ymin成员;¢yMax的]。由于每个中间辊和轧
辊成品关联用矩阵的唱片，在唱片的不确定性矩阵在两个方向延伸行：列和行。
摘要：
展开>>
收起<<
多级下料问题的建模摘要在多级下料问题（CSP）的切割过程是分布在几个连续的阶段。每一个阶段除了最后一个生产中间产品。中间产品清单可给予或任意。我们的目标是尽量减少材料总量减少了产成品库存足以满足采取客户的需求。如果中间的大小，给出了列生成技术可以应用到多级切割问题。如果中间的大小也得不到那么另一个方面是增加了问题的复杂性。我们建议对于这种情况，动态生成两行（中间大小）和列的特别程序模式）。我们把这种为行和列的生成方法。该方法使用一个辅助问题嵌入修订后的单纯形算法框架。这是一个非线性背包问题，可以有效解决。与此相反对列代方法开发的技术不能保证最优解。然而，结果计算实验是非常有前途，并证明该方法是...
相关推荐
-
2024年党建工作要点工作计划5篇供参考
2023-12-16 999+ -
2025年专题生活会对照带头严守政治纪律和政治规矩，维护党的团结统一等“四个带头方面”个人对照检查发言材料4110字文稿
2024-12-21 999+ -
2025年医保局局长、科技局领导干部专题“四个带头”方面对照检查材料2篇例文（附：反面典型案例剖析情况）
2025-02-09 452 -
2025年国有企业党委书记、市总工会党组书记民主生活会“四个带头”方面对照个人检查发言材料2篇文(附：典型案例、上年度整改+个人情况)
2025-02-09 503 -
2025年市委组织部部长、教育局党委书记生活会“四个带头”个人对照检查发言材料2篇文(典型案例+个人事项)
2025-02-09 621 -
2025年市财政局党组书记、局长、市检察院党组领导班子对照“四个带头”方面生活会个人对照检视发言材料2篇文（含以案为鉴反思、以案促改促治方面）
2025-02-09 503 -
市检察院党组、市财政局领导班子2025年生活会对照“四个带头”方面检视发言材料2份文【含以违纪行为为典型案例剖析】
2025-02-09 460 -
2025年市财政局领导对照“四个带头”生活会检视发言材料2篇例文【含以违纪行为为典型案例剖析】
2025-02-09 580 -
单位领导班子2025年聚焦“四个带头”生活会对照检查材料2篇文(含：典型案例剖析反思、落实意识形态责任制)
2025-02-09 750 -
2025年镇党委副书记、市科学技术局领导班子生活会对照“四个带头”检视材料2篇文【含违纪行为典型案例分析】
2025-02-09 254
作者：闻远设计
分类：课程设计课件资料
价格：20光币
属性：8 页
大小：65.5KB
格式：DOC
时间：2023-08-11
