2022年薄膜切割模型数学 .pdf

薄膜切割模型摘要本文研究的是薄膜切割方案的设计问题。要设计一个满意的切割方案，就要使得既满足客户对产品量的要求，又使下料后的剩余边料总长最小，从而使材料利用率最大，达到减少材料损失，降低成本，提高经济效益的目的。为了解决此问题，我们分别就问题一、二建立了两个优化模型，并采用启发式多级序列线性优化算法对其进行求解。对于问题一：由问题分析可知，此题可以归结为无重复规格的一维下料问题。针对此问题，我们建立了优化模型一（整数规划模型），并采用启发式多级序列线性优化算法在Lingo 中对其进行求解，得到切割264 根大卷，使用 16 种切割方式即可完成任务，材料利用率为99.21%，详细的切割方案见表5.1。对于问题二：在问题一的基础上，考虑部分订单有时间限制的情况，我们建立了改进的优化模型二（改进的整数规划模型），同样采用启发式算法进行求解，在求解过程中，我们优先考虑有时间限制的3、7、9号订单，选择其中最优的一种切割方式进行切割,并尽可能多地重复使用此种切割方式;然后对剩余的薄膜重新优化选取新的当前最优的切割方式,不断地重复上面的操作,直到所有剩余的薄膜数目均减小至零为止.由此，我们得到切割 159根大卷，花 6天半就能完成3、7、9号订单的任务，总共切割 264 根大卷，花 11天，使用 14种切割方式即可完成所有的任务，材料的利用率为99.16%，详细的切割方案见表 6.1 最后，我们对模型进行了评价、改进和推广。并在改进中建立了基于遗传算法的优化模型和求解算法。关键字：启发式算法一维下料问题遗传算法整数规划名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 14 页 -1.问题重述1.1 问题背景直接从薄膜厂制膜车间生产出来的的薄膜，在薄膜行业称为半成品，简称大卷或母卷，宽度一般为8100mm，厚度有若干种规格（如19 微米、21 微米等），长度则根据厚度不同而有所不同。薄膜厂销售部门首先接到客户订单或直接提货单，客户订单或提货单中有所需要的薄膜类型（如BOPP 膜、消光膜、CPP膜、珠光膜等），薄膜厚度(如 19 微米，21 微米等)、薄膜宽度（如330mm，620mm等，）、件数；其次销售部门根据当前市场行情同客户商谈价格，谈好价格后，客户会发过来一个清单；然后销售部会根据情况把相同薄膜类型、相同厚度的需求合在一起，进行组合优化，形成一个切割任务单；最后在切割车间通过机器将大卷切割成客户需要的规格（切割好后送达客户的薄膜称为小卷，假设一般小卷的最小宽度为 330mm）。某薄膜厂接到的订货（来自不同客户的订货的汇总）数据见附录一。1.2 问题提出问题一：请你为该厂设计一个满意的切割方案送交切割车间，该切割方案须指出切割大卷的总卷数、切割的方式数，材料的利用率等数据。问题二：若该厂的薄膜切割机每天最多只能处理24 大卷的切割任务，3,7,9号订单属于加急订单，必须在一周内完成切割，然后发货，问该怎样调整切割方案，在这种方案下完成整个切割任务单需要多少天。2.模型的假设与符号说明2.1 模型假设假设 1：每个切割点处由于锯缝所产生的损耗可忽略。假设 2：每种薄膜有各自的交货时间,若某薄膜无交货时间,则记该薄膜交货时间为无穷大。假设 3：切割时零件的长和宽与原材料的长或宽平行。假设 4：薄膜切割机不会发生故障，每天均能完成24 大卷的任务。名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 14 页 -2.2 符号说明M使用的大卷总数（M待求）L大卷的宽度jL订单号j(1,2,10)j需要的小卷规格（宽度）jn订单号j(1,2,10)j对相应规格小卷的需求量ijx第i种最优的切割方式中第j种规格薄膜的重复块数。I总共有的最优切割方式数id第i种切割方式耗用的大卷数iS第i种切割方式下耗用的大卷数的有效使用宽度p利用率N每天最多能处理的大卷数24N1t限制的一周时间17t3.问题分析此题研究的是薄膜切割方案的设计问题。要设计一个满意的切割方案，就要使得既满足客户要求，又使下料后的剩余边料总长最小，从而使材料利用率最大，达到减少材料损失，降低成本，提高经济效益的目的。为了解决此问题，我们将此问题归结为无重复规格的一维下料问题来求解。针对问题一：在薄膜类型相同、厚度相同的情况下，由题意可推出薄膜的长度也相同，那么就说明问题给出的薄膜原材料的规格是统一的，所以可将此问题归结为无重复规格的一维下料问题。为此，先采用嵌套穷举算法并利用计算机自动确定所有可能的截切方案，然后对截切方案进行筛选，在筛选过程中若单从数学模型的真实性这一角度来看，当然希望所考虑的截切方案越多越好，但这必然使相应的模型趋于大型化、复杂化，从而增加求解的困难。反之，若选用的截切方案太少，则相应的模型会变得太粗糙，甚至会把最佳的方案也漏掉。因此，为了使建立的数学模型既简便又能较真实地反映实际问题的本质规律，通常要对所生成的截切方案进行科学的简化。因此我们考虑：(1)去掉余料较大的部分方案，名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 14 页 -这是因为若某种截切方案所剩余料较大，则反映在相应的数学模型的解中，按这些方案下料的原材料根数必定很少甚至为零。(2)将余料较小的那些方案取出单独考虑。在实际加工过程中让其充分生产，以满足需要。这是因为在模型的解中，这些方案所对应的原材料根数必定很多。(3)考虑到生产施工的实际情况，所筛选的截切方案的种类不宜过多，这样可以减轻劳动强度和劳动复杂性，有效节省时间。针对问题二：考虑到薄膜切割机有每日最大工作量的限制以及存在某些薄膜完成的时间限制的情况，我们可以在模型一的基础上把那些有时间需求的薄膜提前生产，并根据所耗费的大卷总数除以该厂每天最大工作量来判断完成时间。在具体的求解过程中，我们可以采用启发式多级序列线性优化算法来逐级求解，首先我们应先考虑有时间限制的3、7、9号订单，在当前可行的下料方式中选择其中最优的（即尽可能的含有3、7、9）一种进行下料,并尽可能多地重复使用此种下料方式;然后对剩余的坯料重新优化选取新的当前最优的下料方式,不断地重复上面的操作,直到所有剩余的坯料数目均减小至零为止.原问题的最优解就是各个序列优化问题所求得的最优下料方式的总合.4.数据分析为了问题求解的方便，将各种薄膜规格按照从大到小排序，即在求解中保证先切割规格大的薄膜，然后在余料中切割规格小的，如此一来可以相对提高原材料的利用率。为此，将原始数据作如下处理表 4.1 按规格降序排列的订货单规格序号订单号规格（宽度，单位：mm）件数1 10 2250 94 2 9 1800 182 3 8 1470 139 4 7 1360 263 5 6 1250 157 6 5 1000 53 7 4 920 318 8 3 820 156 9 2 620 456 10 1 330 206 设每根大卷的长度为L,从中用去I根(I待定)加工成已知各种宽度规格jL的成品jn 根,1,2,10j,有12345678910LLLLLLLLLL,则表4.1 可以等价转换成表4.2 名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 14 页 -表 4.2 薄膜规格参数表宽 度规格1L2L3L4L5L6L7L8L9L10L数量1n2n3n4n5n6n7n8n9n10n5.问题一的解答针对问题一，在假设1、假设 3 的基础上，我们建立了模型一。5.1 模型的建立（整数规划模型）5.1.1确定目标函数将此薄膜切割优化问题转化为多级序列线性优化问题求解.每级求解时,在当前可行的切割方式中选择其中最优的一种进行切割,并尽可能多地重复使用此种切割方式;然后对剩余的薄膜重新优化选取新的当前最优的切割方式,不断地重复上面的操作,直到所有剩余的薄膜数目均减小至零为止.原问题的最优解就是各个序列优化问题所求得的最优下料方式的总合.由此中思路我们可以确定目标函数为101maxiijjjSx L其中，jL 表示第j种规格的薄膜的宽度；ijx 表示第i种最优的切割方式中第j种规格薄膜的重复块数。5.1.2确定约束条件结合实际情况，在第i件大卷上截取宽度规格为jL 的块数ijx 是非负整数；在某种最优的切割方式中第j种规格薄膜的重复块数应该不大于该种规格所需要的数量。而且每一根大卷上切割的薄膜总长度必须小于该大卷的长度；此外，在保证用料最少的情况下必须满足每一种规格所要求的数量。将这些约束抽象成数学表达式，可以写成如下形式：1101.(1,2,;1,2,10)ijjIijjiijjijijxnxnstiIjx Ld LxN名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 14 页 -其中，I表示总共有的最优切割方式数；L表示一个大卷的宽度；id 表示第i种下料方式耗用的大卷数；jn表示第j种规格薄膜需要完成的件数5.1.3综上所述，问题一的模型为101maxiijjjSx L1101.(1,2,;1,2,10)ijjIijjiijjijijxnxnstiI jx Ld LxN5.2 启发式多级序列线性优化算法Step 1依给定条件调用当前最优下料计算子程序,求解得到优化值ijjx L 组成的101ijjjx L 作为第一级下料方式.Step 2计算此种下料方式的重复次数,即此种下料方式所需原材料L 的根数id11221010min/,/,/iiiidnxnxnxStep 3计算去掉id 根后,余下的每种待切割的毛坯的根数jjii jnnd xStep 4将jn 作为新一级优化计算的给定值,如果所有的jn 都已减小至零,则优化计算结束;否则转Step 1,重新调用当前最优下料方式计算子程序,求得新一级的下料方式和重复次数.Step 5各级最优下料方式及其重复次数的集合即为多级序列线性优化的最终结果.算法流程如图 5.1 所示名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 14 页 -5.3 模型的求解对模型一，利用启发式算法在Lingo 中求解得到满意的切割方案如下表：表 5.1 最佳方案表切割方式需大卷数订单号余料利用率1 2 3 4 5 6 7 8 9 10 1 38 2 12 0 0 0 0 0 0 0 0 0 99.21%2 9 14 0 2 2 0 0 0 0 0 0 0 3 2 2 0 0 7 1 0 0 0 0 0 0 4 12 0 0 5 0 4 0 0 0 0 0 0 5 3 0 0 0 5 1 2 0 0 0 0 0 6 37 0 0 1 1 0 4 1 0 0 0 0 7 41 0 0 1 2 0 0 4 0 0 0 0 8 3 0 0 0 5 0 1 0 0 0 1 0 9 45 0 0 0 0 0 0 0 0 2 2 0 10 34 0 0 0 4 0 0 0 3 0 0 10 11 1 0 0 0 1 0 0 2 3 0 0 50 12 1 0 0 0 0 0 0 1 3 0 1 80 13 10 0 0 0 0 0 0 0 3 2 0 90 给定,jjL Lni=1 求出当前最优下料方式nj 是否全为 0 停止d=minn1/xi1,n2/xi2,n10/xi10 nj=nj-dxiji=i+1 是否名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 14 页 -14 1 0 0 0 0 0 0 2 1 2 0 310 15 19 0 0 0 0 0 0 3 0 2 0 420 16 8 0 0 0 0 0 0 0 0 4 0 900 其中，Lp=L用的总大卷数-总的余料利用率用的总大卷数用的总大卷数1IiiMm5.4 结果分析由表 5.1 数据可得，用的总大卷数为264，切割的方式有 16 种，利用率为99.21%。每种切割方式用到的大卷数和完成的对应订单数不尽相同，详细数据见表 5.1。在用启发式算法求解时，我们结合背包原理和实际经验，先处理规格大的薄膜，后处理规格小的，但从表5.1 的数据可以很明显地看出启发式算法的贪婪性，为了材料利用最大化，余料最小化的目的，在优先选择切割方式时还是先处理规格小的，所以此种算法存在它本身的弊端，为了尽量地克服此缺陷，可以使用其他智能优化算法求解（如遗传算法等）。6.问题二的解答针对问题二，在假设1、2、3、4 的基础上，我们建立了模型二.6.1 模型的建立（改进的整数规划模型）6.1.1确定目标函数（同模型一的目标函数）101maxiijjjSx L6.1.2确定约束条件在模型一约束条件的基础上，由于时间的限制，需要对订单号为 3,7,9的薄膜优先考虑，并且要在规定的时间内完成所要求的数量；对于其他没有时间限制类型的薄膜不考虑时间的约束，只需要保证利用率高，用料少的情况。由此，需要添加一些约束条件。先考虑满足订单号为3,7,9 的薄膜的切割方式，设含有此三种规格薄膜的切割方式共有 I种，则有效薄膜总宽度不大于规定时间内用的总大卷数，即名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 14 页 -33779911()Iiiiix Lx Lx LNt LII其中，24N表示每天最多能处理的大卷数；17t为限制的时间一周6.1.3综上所述，问题二的模型为101maxiijjjSx L110133779911.(1,2,;1,2,10)()ijjIijjiijjijIiiiiijxnxnx Ld LstiI jx Lx Lx LNt LIIxN6.2 模型的求解对模型二，利用启发式算法在Lingo 中求解得到满意的切割方案如下表：表 6.1 问题二的方案表切割方式需大卷数订单号余料利用率1 2 3 4 5 6 7 8 9 10 1 52 0 4 3 0 0 0 1 0 1 0 0 99.16%2 49 0 5 0 1 0 0 3 0 0 0 0 3 3 0 1 0 3 2 0 2 0 0 0 0 4 43 1 0 0 0 1 0 1 0 3 0 10 5 1 0 0 0 0 2 0 1 2 1 0 0 6 1 2 0 0 0 2 0 4 0 0 0 0 7 10 3 0 0 0 0 1 1 0 0 2 0 8 52 0 0 0 5 0 1 0 0 0 1 0 9 11 2 0 0 0 0 0 0 2 0 2 0 10 13 8 0 0 0 0 2 0 2 0 0 0 名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 14 页 -11 5 1 0 0 0 0 5 0 1 0 0 50 12 11 0 0 0 0 0 4 0 2 0 0 160 13 12 0 0 0 0 0 0 0 5 0 0 750 14 1 0 0 0 0 0 0 0 2 0 0 5160 其中，Lp=L用的总大卷数-总的余料利用率用的总大卷数用的总大卷数1IiiMm6.3 结果分析由表 6.1 中的数据知，订单号为3、7、9 的薄膜生产完需要159根大卷，使用了 7 种切割方式，而一周内最多能生产24*7=168 根，所以可以按时完成任务；但由于提前完成的时间不是很多，如果切割机每天没有按最大生产能力生产或期间出现了故障，那么就不可能按时完成任务，所以此种方案在实际使用中还需要进行改进。完成全部任务所用的总大卷数为264，并且最后一根剩余5160mm，可以建议工厂留作他用，不需要完全舍弃。总利用率为99.16%。7.模型的评价、改进及推广7.1 模型评价优点：1.在模型求解中，采用了启发式算法，它大大地节省了时间和空间(计算和存储),且利用率达到了 99.21%，节材的效果很显著.2.在模型二中，考虑了部分薄膜的完成有时间限制的情况，由此得到的满意方案相比于模型一，更加符合实际，有更高的适应性。缺点：由于我们采用的启发式算法本身也是一种贪婪算法，具有主观倾向，而且一般不能求得全局最优解，只能获得近似的满意解，以致得到的模型结果还存在一定误差。7.2 模型改进1.在求解时可以多运行几次，然后综合分析，取一个相对最优的结果作为我们的满意方案。2可以采用智能算法诸如基因遗传算法来对本文求解，然后可以对两种算法的名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 14 页 -结果进行比较分析，从而得出更加令人满意的方案。接下来，我们就模型的缺点提出基于遗传算法的模型与算法，有兴趣的读者可以尝试去求解。确定目标函数设每根大卷的宽度为L,从中用去I根(I待定)加工成已知各种宽度规格jL的成品jn 根,1,2,10j,不妨设12345678910LLLLLLLLLL，即在下料时按照大规格的优先考虑。设ijx 表示在第i根大卷上截取宽度规格为jL的根数(1,2,1,2,10)iIj。则在整个完成的进程中，造成的总浪费满足下式10101011111()IIijjijjjjijijjLx LILx LILn L从上式可以看出，如果用的总大卷数I确定，那么总的浪费量就为一个常数。所以只需要考虑目标函数是否有利于确定I，是否能使前(1)I根大卷的剩余部分尽可能小，而使最后一根的剩余材料取最大值。为此，目标函数可以写成101minIjjjx L确定约束条件结合实际情况，在第i根大卷上截取长度规格为jL 的根数ijx 是非负整数；而且每一根大卷上切割的薄膜总长度必须小于该大卷的长度；此外，在保证用料最少的情况下必须满足每一种规格所要求的数量。将这些约束抽象成数学表达式，可以写成如下形式：1011.(1,2,;1,2,10)ijjjIijjiijx LLxnstiI jxN综上所述，基于遗传算法的模型为101minIjjjx L名师资料总结-精品资料欢迎下载-名师精心整理-第 11 页，共 14 页 -1011.(1,2,;1,2,10)ijjjIijjiijx LLxnstiI jxN遗传算法Step 1.初始化，置迭代的最大次数，解不能再改善的最大迭代次数，选择杂交的概率 pc，选择变异的概率Pm，种群规模 M，随机生成 M 个可行解。Step 2.以概率 pe确定通过种群 M 通过杂交算子产生2 个新解。Step 3.以概率 Pm确定通过种群 M 通过变异算子产生1 个新解。Step 4.是否己产生 M 个新解，若是执行下一步，否则转Step 2。Step 5.对 2 枷个解评价函数值 f，按 f 的值从大到小进行排序，选定前M 个解作为种群。Step 6.是否迭代次数已达最大迭代次数或解不能再改善的迭代次数己达最大迭代次数，若是执行下一步，否则转Step 2。Step 7.输出最优解，算法结束。7.3 模型推广我们建的模型不仅适用于薄膜的切割问题，也可用于对类似的一维下料问题进行求解；同时，还可以推广到二维实用下料的优化问题中去。参考文献1 陈光亭，裘哲勇，数学建模M，北京：高等教育出版社，2010.2 宋来忠，王志明,数学建模与实验 M,北京：科学出版社,2005.3 王庚，王敏生，现代数学建模方法M，北京：科学出版社，2008.4 薛定宇，陈阳泉，高等应用数学问题的MATLAB 求解M，北京：清华大学出版社，2008.5 王小东，李刚，欧宗瑛，一维下料优化的一种新算法，大连理工大学学报，第 44 卷第 3 期，2004.5 名师资料总结-精品资料欢迎下载-名师精心整理-第 12 页，共 14 页 -附录附录一：订货单汇总薄膜类型相同、厚度相同订单号规格（宽度，单位：mm）件数1 330 206 2 620 456 3 820 156 4 920 318 5 1000 53 6 1250 157 7 1360 263 8 1470 139 9 1800 182 10 2250 94 附录二：实现程序（启发式多级序列线性优化算法）第一问：第一阶段的实现程序如下，其他阶段的类似，而且要用到上一阶段的部分结果。min=8100-(330*x1+620*x2+820*x3+920*x4+1000*x5+1250*x6+1360*x7+1470*x8+1800*x9+2250*x10);bnd(0,x1,206);bnd(0,x2,456);bnd(0,x3,156);bnd(0,x4,318);bnd(0,x5,53);bnd(0,x6,157);bnd(0,x7,263);bnd(0,x8,139);bnd(0,x9,182);bnd(0,x10,94);330*x1+620*x2+820*x3+920*x4+1000*x5+1250*x6+1360*x7+1470*x8+1800*x9+2250*x10=8100;gin(x1);gin(x2);gin(x3);gin(x4);gin(x5);gin(x6);gin(x7);gin(x8);gin(x9);gin(x10);第二问：第一阶段的实现程序如下，其他阶段的类似，而且要用到上一阶段的部分结果。名师资料总结-精品资料欢迎下载-名师精心整理-第 13 页，共 14 页 -min=8100-(820*x3+1360*x7+1800*x9+620*x2+920*x4+1000*x5+1250*x6+1470*x8+330*x1+2250*x10);bnd(0,x1,206);bnd(0,x2,456);bnd(0,x3,156);bnd(0,x4,318);bnd(0,x5,53);bnd(0,x6,157);bnd(0,x7,263);bnd(0,x8,139);bnd(0,x9,182);bnd(0,x10,94);820*x3+1360*x7+1800*x9+330*x1+620*x2+920*x4+1000*x5+1250*x6+1470*x8+2250*x10=8100;gin(x1);gin(x2);gin(x3);gin(x4);gin(x5);gin(x6);gin(x7);gin(x8);gin(x9);gin(x10);名师资料总结-精品资料欢迎下载-名师精心整理-第 14 页，共 14 页 -