板材玻璃下料问题-设计--论文

板材玻璃下料问题 摘要 根据玻璃板材的最优化下料要求 不同的下料策略形成不同的线性规划模型 排 样下料问题在很多工业领域中都有广泛的应用 解决好排样问题 可以提高材料的利 用率 在充分理解题意的基础上 以使用原材料张数最少为目标 采用逐级优化的方 法 进行下料方案的筛选 在问题一中 首先选用单一下料两个方向排料优选的下料策略 成品料的长在原 材料的长和宽两个方向上分别排列 求出最优解 其次采用单一下料中成品料的长和 宽在原材料的长 宽两个方向套裁排料优选 算出所需原材料的块数和利用率 最后 按照零件需求量 进行几种零件配套优选 用新易优化板材切割软件求出最优的板材 切割方法 列以原材料消耗总张数最少为目标函数的数学模型 用 LINGO 软件编程 求出最佳下料方案 针对最优的下料特点建立了模型二并有模拟退火算法求出近似最 优解 按照原材料的利用率 筛选出最佳的下料方案为按照零件需求量 进行几种零件 的配套优选下料方案 所求需要原材料的块数为 548 利用率为 95 03 问题二的求解以第一题相似 当有两种规格的原材料时 在第一题的基础上 用 玻璃板材切割软件排出两种原材料的最佳切割方法 建立数学模型 用 LINGO 软件编 程 算出最佳的下料方案 求得需要规格为 2100cm 1650cm 的原材料 532 块 需要规 格为 2000cm 1500cm 的原材料 16 块 共计 548 块 利用率为 95 40 此模型可以推广到更多板材排样下料领域的应用 通过逐级优化和组合原理 确 定各种切割方式 然后再进行线性规格问题的求解 关键词 优化排样 板材下料 最优化 线性规划 模拟退火遗传算法 1 一 问题重述 在大型建筑工程中 需要大量使用玻璃材料 如门窗等 在作材料预算时 需要 求出原材料的张数 已知板材玻璃原材料和下料后的成品料均为矩形 由于玻璃材料特点 切割玻璃 时 刀具只能走直线 且中间不能拐弯或停顿 即每切一刀均将玻璃板一分为二 切 割次序和方法的不同 各种规格搭配 即下料策略 不同 材料的消耗将不同 工程 实际需要解决如下问题 在给定一组材料规格尺寸后 1 在原材料只有一种规格的情况下 例如长为 2100cm 宽 1650cm 给出最优 下料策略 时所需要材料张数最少 2 在原材料为两种规格的情况下 例如 2100cm 1650cm 和 2000cm 1500cm 给出最优下料策略 使所需要材料张数最少 且利用率 实际使用总面积与原材料总 面积之比 尽量高 3 下表是一些成品料及所需块数 长 宽 块数 分别以一种原材料 2100cm 1650cm 及两种原材料规格 2100cm 1650cm 2000cm 1500cm 为例 分别给出 1 和 2 的算法及数字结果 并给出两种情况下的利用率 表 1 成品料规格及所需块数 序号长 宽块数序号长 宽块数 1865 857982857 71598 3804 7461964857 67528 5857 665286804 663224 7804 6613088804 63984 9804 6315610804 563224 11804 53619612804 535392 13804 55139214865 44698 15762 44619616715 44698 17680 44622418675 44628 19667 4462820655 44684 21647 4465622667 426308 23580 44622424552 446196 25551 44639226527 426392 二 模型假设 1 假设不考虑在切割板材玻璃的过程中的损耗 2 假设不考虑人为的损耗 3 假设不考虑切割工艺的不同 4 假设不考虑玻璃厚度的影响 2 5 假设不考虑刀片的厚度 6 假设切割玻璃的刀片可旋转 7 假设不考虑两种原材料的优先级及成本 只考虑原材料的利用率 三 符号说明 符号表示意义 1 L规格为 2100cm 1650cm 的原材料的长 1 W规格为 2100cm 1650cm 的原材料的宽 2 L规格为 2000cm 1500cm 的原材料的长 2 W规格为 2000cm 1500cm 的原材料的宽 i l成品零件的长 i 1 2 26 i w成品零件的宽 i 1 2 26 i n所需成品料的块数 i 1 2 26 K共有成品材料种类 n有一种规格原材料时 所需原材料的块数 11 S规格为 2100cm 1650cm 的原材料的面积 12 S规格为 2000cm 1500cm 的原材料的面积 i L x 1 第 i 个成品料的在方向上能被排下的个数 i x 1 L i L y 1 第 i 个成品料的在方向上能被排下的个数 i y 1 L i W x 1 第 i 个成品料的在方向上能被排下的个数 i x 1 W i W y 1 第 i 个成品料的在方向上能被排下的个数 i y 1 W ji b 第 j 种切割方式下在 L 方向套裁切割被排下的个数 i x 3 符号表示意义 jk d 第 j 种切割方式下在 L 方向套裁切割被排下的个数 i y j 第 j 种切割方式下长度方向的余料 j S 第 j 种切割方式下余料面积 j N 第 j 种切割方式使用的次数 xn第 n 种切割方法 1 N 有两种规格原材料是 所需规格为 2100cm 1650cm 原材料的块数 2 N 有两种规格原材料是 所需规格为 2000cm 1500cm 原材料的块数 四 问题分析 板材玻璃下料问题属于线性规划中的二维下料 板材下料 玻璃最优化切割中 原材料有两个方向 长和宽 在只有一种原材料的时候 令原材料的长为 L 宽为 W 零件的长为 宽为 从操作方便的角度考虑 一张板材上不宜 i x i y262 1 i 下过多的零件 但一般来说 参加套裁的零件种类越多 材料的利用率越高 在实际 玻璃切割中要兼顾这两方面的情况 既要考虑操作的方便 又要考虑材料的利用率 一般我们讨论零件种数最多为 3 种或 4 种的情况 而且由于玻璃材料特点 切割玻璃 时 刀具只能走直线 且中间不能拐弯或停顿 即每切一刀均将玻璃板一分为二 是 一种典型的 Guillotine 切割 国内外对 Guillotine 下料问题的研究非常活跃 已取 得了不少的研究结论 对剪切下料一般的处理方法有 使用背包算法以保证能实现一 刀切的剪切工艺 在一张板材上只排一种规格的零件的单一下料法或只排少数几种的 综合套裁法 考虑到本题的实际情况 我们使用第二种方法 当然 在保证利用率不 减的情况下 所下的零件数越少越好 既然原材料有长和宽两个方向 零件也有长和宽两个方向 则每个零件的长可在 原材料的长和宽方向上排列 宽也可在原材料的长和宽的方向上排列 这就够成了二 维下料方式的多样性 当所需下料的零件种类较多时 下料方式也就相应的比较多 这又为二维下料增加了困难 为了克服这个困难 并考虑到采取组成最优化方案的切 割方式的材料利用率都不应太低 因此采取逐级优化的方法 进行优化切割方案的筛 选 对于问题一有一种原材料的时候 有以下三种切割方案 1 单一下料两个方向排料优选 2 单一下料在长 宽两个方向套裁排料优选 3 按照零件需求量 进行几种成品料配套优选 选出最佳下料方案 对于问题二有两种原材料的时候 在只考虑原材料利用率的情况下 选用与第一 4 题中只有一种原材料时的第三种切割方案 即按照零件需求量 进行几种零件配套优 选 选出最佳下料方案 最后 根据所求的 1 题和 2 题中原材料的数量 算出每种切割方案的利用 率 选出最佳切割方案 五 模型的建立与求解 5 1 问题一 模型的建立既求解 5 1 1 模型I 逐级优化模型的建立与求解 5 1 1 1 单一下料两个方向排料优选 对于一张原材料上仅裁一种零件 即单一下料 的切割方式 每一种零件可以排 出两种单一切割方式 第一种 成品料的长在原材料长的方向上排列的下料方式 第 二种 成品料的长在原材料宽的方向上排列的下料方式 1 单一下料两个方向排料优选数学模型如下 i 1 2 26 l 11ii lLINTL i 1 2 26 w 11ii wLINTL i 1 2 26 l 11ii lWINTW i 1 2 26 w 11ii wWINTW 1111 WLS 100 11 26 1 1 nS nS i ii 如第一种零件在方向上能排 2 在方向上仅能排1次 1 l 1 L l 1111 lLINTL 1 y 1 W 因此能切下第一种零件的总数是2 1 2 个 如图5 1 图5 1 另一方面 在方向上排1次 在方向上能排2次 所以整块玻璃能容纳下 1 l 1 W 1 w 1 L 以一种零件的总数是1 2 2 个 如图5 2 5 图5 2 两个方向切割的零件数相等 可任选一种切割方式 若切割第二个零件 情况就 有所不同了 在方向能排2次 在方向上也能排2次 因此能切下第二种零件 2 l 1 L 2 w 1 W 的总数是2 2 4 个 如图5 3 图5 3 另一方面 在方向能排1次 在方向上也能排2次 因此能切下第二种零 2 l 1 W 2 w 1 L 件的总数是1 2 2 个 如图5 4 图5 4 综上可以看出 图5 3的切割方式比图5 4的切割方式的利用率要高 所以单一下 料也存在比较优选的问题 称作单一下料的初级优化 同理 用Excle对26种材料做单一下料的初级优化后 得到如下的数据 长宽面积 成品料所 需块数 每块原料 切割个数 所需原材 料块数 186585774130598249 285771561275598425 3804746599784196449 48576755784752847 58576675716192847 6804663533052224638 6 7804661531444308652 880463951375684614 980463150732456610 10804563452652224638 11804536430944196633 12804535430140392666 13804551443004392666 1486544638579098617 15762446339852196825 1671544631889098813 17680446303280224925 186754463010502894 196674462974822894 2065544629213084910 216474462885625697 22667426284142308935 23580446258680224925 24552446246192196922 25551446245746392944 26527426224502392944 总计 729 表5 5 通过上述计算求得利用率为 70 72 100 11 26 1 1 nS nS i ii 2 单一下料两个方向排料优选结果如下 通过计算解得 在原材料只有一种规格2100cm 1650cm的情况下 用单一下料两 个方向排料优选的方法需要原材料729块 原材料的利用率为72 70 5 1 1 2 单一下料在长 宽两个方向套裁排料优选 成品料在原材料和方向上套裁下料 和可以套裁 但这时应注意 在切 1 L 1 W i l i w 割玻璃时 每切一刀将玻璃板一分为二 数学模型与单一下料两个方向排料选优一样 用Excle对26种材料做单一下料的在长 宽两个方向套裁排料优化后 得到如下的数据 长宽面积 成品料所 需块数 切割个数 块 原材料 所需原材 料块数 186585774130598249 285771561275598425 3804746599784196449 7 48576755784752856 58576675716192856 6804663533052224638 7804661531444308652 880463951375684614 980463150732456610 10804563452652224638 11804536430944196728 12804535430140392756 13804551443004392666 1486544638579098617 15762446339852196922 1671544631889098911 176804463032802241023 1867544630105028103 1966744629748228103 2065544629213084109 2164744628856256106 226674262841423081031 235804462586802241121 245524462461921961118 255514462457463921136 265274262245023921233 总计 670 表5 6 通过上述计算求得利用率为 87 78 100 11 26 1 1 nS nS i ii 单一下料在长 宽两个方向套裁排料优选结果如下 通过计算解得 在原材料只有一种规格2100cm 1650cm的情况下 用单一下料在 长 宽两个方向套裁排料优选的方法需要原材料670块 原材料的利用率为78 87 5 1 1 3 按照零件需求量 进行几种成品料配套优选 按照零件需求量 进行玻璃套裁下料方式的数学模型表示为 1 1 2 1 i m mk mkjmkijij wdlbL 8 2 0 j 且 ij l mkj w i 1 2 m k m 1 m 2 2m 3 k m如果则 如果则 4 i 0 ji b0 jim d0 ji b0 jim b 5 mkjkijiji lWdwWba 1 1 6 i m i ijij wlaWLS 1 11 7 j n j j SNS 1 min 8 ij n j ji nNa 1 且为整数 9 0 j N 上述9个方程组成了玻璃下料问题的数学模型 我们的目的是要求出满足上述9个 方程的各种切割方式的张数 j N 通过 新易优化板材切割 软件 排出玻璃板材的最优切割方法 共有72种切割 方案 每一种切割方案如附录中表1 0所示 建立线性规划方程组 n j jj xN 1 min 整数 2 10 2 1 1 njx mibxa ts j n j iiji 求得的利用率为 03 95 100 11 26 1 1 nS nS i ii 按照零件需求量 进行几种成品料配套优选结果如下 通过用LINGO软件 对上述27个线性方程进行编程求解 求得在原材料只有一种规 格2100cm 1650cm的情况下 用按照零件需求量 进行几种成品料配套优选的方法需 要原材料548块 原材料的利用率为95 03 9 所以 通过逐级优化 筛选优化切割方案比较得出 按照零件需求量 进行几种 成品料配套优选的下料策略原材料的利用率最高 为95 03 故应采取这种下料策略 所需要原材料张数最少 为548张 5 1 2 模型II 模拟退火算法模型的建立与求解 5 1 2 1 模型的准备 模拟退火算法来源于固体退火原理 将固体加温至充分高 再让其徐徐冷却 加温时 固体内部粒子随温升变为无序状 内能增大 而徐徐冷却时粒子渐趋有序 在每个温度都达到平衡态 最后在常温时达到基态 内能减为最小 根据 Metropolis准则 粒子在温度时趋于平衡的概率为 其中为温度时T e KTE ET 的内能 为其改变量 为Boltzmann常数 用固体退火模拟组合优化问题 E k 将内能模拟为目标函数值 温度演化成控制参数 即得到解组合优化问题EfTt 的模拟退火算法 由初始解 i和控制参数初值开始 对当前解重复 产生新解 计t 算目标函数差 接受或舍弃 的迭代 并逐步衰减值 算法终止时的当前解即为t 所得近似最优解 这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程 退火 过程由冷却进度表 Cooling Schedule 控制 包括控制参数的初值及其衰减因子t 每个值时的迭代次数和停止条件 t tLS 模拟退火的基本思想 1 初始化 初始温度 充分大 初始解状态 S 是算法迭代的起点 每个值TT 的迭代次数L 2 对k 1 做第 3 至第6步 L 3 产生新解S 4 计算增量 t C S C S 其中C S 为评价函数 5 若 t 0 然后转第 2步 TT 终止条件通常取为连续若干个新解都没有被接受时终止算法 模拟退火算法新解的产生和接受可分为如下四个步骤 第一步是由一个产生函数从当前解产生一个位于解空间的新解 为便于后续的 计算和接受 减少算法耗时 通常选择由当前新解经过简单地变换即可产生新解的 方法 如对构成新解的全部或部分元素进行置换 互换等 注意到产生新解的变换 方法决定了当前新解的邻域结构 因而对冷却进度表的选取有一定的影响 第二步是计算与新解所对应的目标函数差 因为目标函数差仅由变换部分产生 所以目标函数差的计算最好按增量计算 事实表明 对大多数应用而言 这是计算 目标函数差的最快方法 第三步是判断新解是否被接受 判断的依据是一个接受准则 最常用的接受准 则是Metropo1is准则 若 t 98 x16 2 x27 x48 x51 x56 2 x57 x59 98 2 x3 2 x7 x12 2 x13 2 x25 2 x27 2 x19 2 x25 2 x27 2 x28 2 x32 2 x34 2 x36 2 x39 2 x43 2 x46 x49 2 x50 2 x51 x55 2 x58 x59 x60 x68 196 2 x3 3 x50 4 x55 3 x67 28 x2 2 x13 2 x25 x32 28 x10 2 x16 2 x20 2 x29 2 x38 2 x39 2 x45 x47 x49 2 x62 4 x65 x72 224 x2 2 x4 2 x6 x10 2 x14 2 x21 2 x30 4 x34 2 x37 x39 2 x40 2 x42 x46 x47 x4 18 9 2 x52 2 X56 2 x57 2 x61 2 x67 308 4 x9 4 x11 2 x22 2 x24 x39 x59 84 2 x10 2 x31 2 x35 2 x65 56 x7 x11 2 x16 2 x22 x23 2 x29 2 x31 2 x62 x72 224 2 x2 2 x4 2 x7 2 x11 3 x12 2 x18 4 x19 2 x20 2 x21 3 x23 2 x24 2 x30 x36 2 x37 2 x53 196 2 x6 2 x7 x9 3 x10 x14 x19 2 x26 x44 x45 3 x46 x47 3 x48 4 x54 x59 4 x63 2 x64 392 6 x1 6 x5 6 x8 2 x9 2 x18 2 x23 4 x26 6 x33 2 x35 6 x41 2 x44 4 x45 4 x47 3 x49 2 x70 392 x1 2 x4 2 x6 2 x15 2 x16 3 x17 x24 x33 x43 x52 98 x1 3 x3 2 x4 2 x6 3 x13 2 x17 2 x20 2 x25 x29 2 x35 3 x38 3 x40 x41 3 x42 2 x51 x66 2 x72 196 x12 x15 x17 x25 x27 x28 3 x32 x42 3 x43 2 x52 5 x68 x71 98 3 x21 3 x22 6 x28 3 x31 2 x32 3 x37 6 x62 10 x69 224 x14 x41 x50 3 x57 x62 7 x66 28 3 x14 2 x27 28 3 x52 x61 4 x64 3 x68 84 4 x12 2 x15 x21 x24 x33 x67 x71 x72 56 4 x18 x29 x42 3 x44 3 x48 4 x53 x55 x59 3 x60 2 x70 308 x22 x26 x31 x36 x37 4 x54 3 x56 x58 x62 x63 224 3 x2 2 x5 2 x15 x22 x31 x46 x49 x52 4 x70 196 2 x8 x18 2 x23 3 x24 3 x30 4 x36 2 x44 2 x48 4 x53 4 x58 4 x60 3 x63 2 x70 9 x71 392 3 x2 x5 x8 3 x14 x18 x21 x23 2 x26 3 x30 2 x36 x37 x53 2 x54 2 x63 x64 3 x66 392 3 模型II求解Matlab程序 clear clc s1 0 s2 0 s3 0 s4 0 temp2 0 kk 0 cc load cc txt l cc 1 w cc 2 n cc 3 R 0 for j 1 26 m 2100 l j fix 2100 l j e 1650 w j fix 1650 w j 19 while n j 0 n j n j fix 2100 l j fix 1650 w j R R 1 kk 0 temp1 0 temp2 0 for i j 26 if e w i temp1 i kk 1 end end if m w i temp2 i kk 1 end end end s1 0 s2 0 if kk 0 if temp1 0 n temp1 n temp1 max fix e l temp1 fix 2100 w temp1 fix e w temp1 fix 2100 l temp1 end if temp2 0 n temp2 n temp2 max fix m l temp2 fix 1650 e w temp2 fix m w temp2 fix 1650 e l temp2 end end 20 end end R 4 Matlab程序调用cc txt数据 865 857 98 857 715 98 804 746 196 857 675 28 857 665 28 804 663 224 804 661 308 804 639 84 804 631 56 804 563 224 804 536 196 804 535 392 804 551 392 865 446 98 762 446 196 715 446 98 680 446 224 675 446 28 667 446 28 655 446 84 647 446 56 667 426 308 580 446 224 552 446 196 551 446 26 527 426 392 5 有两种原材料时 进行玻璃套裁下料的 77 种最优切割方案如表 2 0 12345678910111213 12212 23 3222 422 51111 66 76 81111 91111 10412 玻 璃 一 111111 21 1222 13121 142 1511121 16122 1722 18112 1922 202 21112 2224 2324 2422 2522 26222 2722 2822 29122 30122 3122 322 336 3422 35211 3624 37121 382 3922 4024 41112 42 432 4422 452212 4622 47222 48112 49111 502221 51111 522221 53111 542 22 552 564 57112 586 5933 60112 61112 6215 6322 6412 65111 66211 67112 682 6932 70112 71 72211 73 742 75 761 玻 璃 二 77112 14151617181920212223242526 1 2233 311 43 51111 621 721 81111 91111 10 1111111 1211111 1311111 14323 151 16211 173 玻 璃 一 1811111 23 1932 20211111 2111111 2211 2321 24311 25311 2621 27131 2821 292 302 3122 321133 3311 34311 3511111 36 3712 38232 39311 40 4111111 42236 4343 4421 45 4621 472 4811111 4911111 50 5111111 52 5311121 549 55441 5642 571111 58 59 603 614 24 62 633 64151 6511211 6622 6721 68341 691 703 7138 721 73236 7433 75226 76112111 玻 璃 二 77 表 2 0 6 有两种原材料时 求解玻璃套裁下料的 LINGO 程序 min x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 x14 x15 x16 x17 x18 x19 x 20 x21 x22 x23 x24 x25 x26 x27 x28 x29 x30 x31 x32 x33 x34 x35 x36 x37 x3 8 x39 x40 x41 x42 x43 x44 x45 x46 x47 x48 x49 x50 x51 x52 x53 x54 x56 x57 x58 x59 x60 x61 x62 x63 x64 x65 x66 x67 x68 x69 x70 x71 x72 x73 x74 x75 x76 x77 x5 x8 x9 x13 x29 x37 x49 x51 x60 x61 x65 x67 x70 2 x72 98 x5 x8 x9 2 x44 2 x46 x49 x51 x60 2 x63 x77 98 2 x4 2 x14 2 x17 2 x20 2 x28 x30 2 x32 2 x36 2 x37 2 x38 2 x40 x49 x51 2 x54 x70 x72 196 2 x4 x37 x67 28 2 x17 2 x28 x64 3 x69 2 x74 28 2 x1 x5 x8 x11 x15 2 x24 2 x27 2 x31 x41 2 x44 2 x45 x48 2 x50 x57 6 x58 3 x59 x62 2 x63 2 x67 2 x69 224 x9 x11 2 x12 2 x13 x15 2 x30 2 x35 4 x36 4 x40 x41 2 x46 x48 2 x52 x57 3 x57 2 x60 5 x62 2 x66 x77 308 4 x10 x15 x16 x18 x21 2 x25 2 x39 2 x47 x53 x66 x72 84 2 x1 2 x15 x18 2 x19 x21 2 x29 2 x34 x53 56 x1 2 x3 x10 2 x16 2 x19 2 x22 2