矩形件排样优化问题 数学建模论文.pdf

矩形件二维优化布局问题 摘要 本文针对矩形件二维优化布局问题，混合0-1规划等方法，建立了以材料最大利用 率为目标的单层优化模型，利用遗传算法，剩余矩阵算法对其进行求解，以此研究实际 生产生活中的矩形零件排样、切割问题 针对问题一的第一部分，题目要求在只能沿一个方向排样，且每行必为同种类型的 零件的条件下，求解使利用率最大的切割方案。通过分析我们将同种类型的零件按照不 同的摆放和排样方式组合成4 种不同类型的规则矩形块，降低排样的复杂程度。之后我 们定义了材料利用率并以此为标准确定以利用率最大为目标的目标函数，考虑组合矩形 块排列时面积、长度和数量等限制确定限制条件，建立了单目标规划模型，由于模型较 为简单我们采用枚举法并利用lingo 遍历求解，得到具体排列方案为编号为2 的零件横 排横放共4 行，每行29 个；编号为3 的零件横排横放共5 行，每行29 个；编号为4 的 零件横排横放共3 行，每行16 个。按照此方案最终材料的利用率为98.81%，并给出具 体排样图。最后对结果进行最优检验，确定其为最优排样方式。模型可靠性较高，更具 实用性。 针对问题一的第二部分，题目要求我们不考虑工艺限制，具体讨论限制更少的切割 方法。根据资料，现实生产加工环节中的切割方案可分为剪切切割和正交切割两种方式， 针对本问我们主要讨论正交切割方案下的材料利用率。首先我们根据材料利用率的定义 确定了以利用率最大为目标的目标函数，考虑零件在板材上排放时长度、宽度和面积等 限制确定限制条件，建立了单目标规划模型。由于本问零件组合方式过多，无法简单利 用枚举法求解，因此我们利用基于最低水平线的空闲区域可再利用有哪些信誉好的足球投注网站算法对模型进行 求解，利用Matlab得到去掉排样限制后材料利用率提高到99.03%，并对计算结果进行最 优检验，确定其为全局最优解。 针对问题二，题目要求我们求解从宽已知的卷材上切割出给定零件，所使用卷材长 度最小的切割方案 ，通过建立坐标系我们发现任意矩形零件的位置实际上只由其右上 角坐标和其摆放方式决定，以此将问题简化。首先我们仍以材料利用率为依据确定以利 用率最大为目标的目标函数，考虑零件在摆放时任意一个零件不出界、零件坐标关系、 邻接零件之间长度和宽度的限制条件和零件位置不出现重叠等限制确定限制条件建立 单目标规划模型。从数学计算复杂性理论看，本文属于NP问题，因此我们利用遗传算法 结合剩余矩阵算法，利用Matlab编程实现算法对模型进行求解，得到使用卷材的最小长 度为40分米，利用率为100%必为全局最优解，并给出其具体排样图。 本文的主要特色在于采用了智能、高效的遗传算法对矩形件二维优化问题进行了求 解，对解决该类问题起到了统筹、优化的目的，且相比于其他算法具有较优的空间复杂 度和精确度等优点，使矩形件排样问题更加科学化、智能化，为日后工厂合理设计矩形 件切割方案，提高生产效率，减少生产成本提供了参考依据。 关键词：单目标规划 0-1 规划 最低水平线法 遗传算法 剩余矩阵 一、 问题重述 问题1：现有有九种矩阵零件，按1~9编号。它们的尺寸（毫米）分别是（按编号排列）： 零件长度l=15,85,85,155,93,176,150,185,185 零件宽度w=55,70,75,115,185,69,37,175,120 零件个数M=200,200,200,100,100,200,400,100,300 现有一个长2500宽1000的板材，欲充分利用（最大利用率）该板材切割出零件，应采 用什么样的方案？ 有时由于工艺或其他实际情况限制，只能沿一个方向（纵向或横向）排样，而且每一行 只能排放一种类型的零件，排放这一行时，要么都是竖着排，要么都是横着排（如下图 所示）。如果有这种限制，应该怎样切？当工艺提高了，限制少了，切割的方法会更灵 活，请结合实际讨论几种限制更少的情况下的切割方法。 问题2： 欲从宽为15 （分米）的卷材上切割出二十五个零件(编号1~25)，尺寸（分米）分别是 （按编号排列）： 零件长度：12 4 6 10 2 6 4 4 7 4 6 4 6 4 2 8 8 8 6 2 8 3 2 3 2 零件宽度：6 7 7 2 5 4 2 6 9 5 4 6 3 5 4 4 6 3