薄膜切割模型数学建模

《薄膜切割模型数学建模》由会员分享，可在线阅读，更多相关《薄膜切割模型数学建模（14页珍藏版）》请在金锄头文库上搜索。

1、薄膜切割模型摘要本文研究的是薄膜切割方案的设计问题。要设计一个满意的切割方案，就 要使得既满足客户对产品量的要求，又使下料后的剩余边料总长最小，从而使 材料利用率最大，达到减少材料损失，降低成本，提高经济效益的目的。为了 解决此问题，我们分别就问题一、二建立了两个优化模型，并采用启发式多级 序列线性优化算法对其进行求解。 对于问题一：由问题分析可知，此题可以归结为无重复规格的一维下料问 题。针对此问题，我们建立了优化模型一（整数规划模型） ，并采用启发式多级 序列线性优化算法在 Lingo 中对其进行求解，得到切割 264 根大卷，使用 16 种 切割方式即可完成任务，材料利用率为 99.21

2、% ，详细的切割方案见表 5.1。 对于问题二：在问题一的基础上，考虑部分订单有时间限制的情况，我们 建立了改进的优化模型二（改进的整数规划模型） ，同样采用启发式算法进行求 解，在求解过程中，我们优先考虑有时间限制的3、7、9号订单，选择其中最优 的一种切割方式进行切割, 并尽可能多地重复使用此种切割方式; 然后对剩余的 薄膜重新优化选取新的当前最优的切割方式, 不断地重复上面的操作, 直到所有 剩余的薄膜数目均减小至零为止. 由此，我们得到切割159根大卷，花6天半就 能完成3、7、9号订单的任务，总共切割264 根大卷，花11天，使用14种切割方 式即可完成所有的任务，材料的利用率为99

3、.16%，详细的切割方案见表6.1 最后，我们对模型进行了评价、改进和推广。并在改进中建立了基于遗传 算法的优化模型和求解算法。关键字：启发式算法 一维下料问题 遗传算法 整数规划1. 问题重述1.1 问题背景直接从薄膜厂制膜车间生产出来的的薄膜，在薄膜行业称为半成品，简称 大卷或母卷，宽度一般为 8100mm，厚度有若干种规格（如 19 微米、21 微米等） ，长度则根据厚度不同而有所不同。薄膜厂销售部门首先接到客户订单或直接 提货单，客户订单或提货单中有所需要的薄膜类型（如 BOPP 膜、消光膜、 CPP 膜、珠光膜等） ，薄膜厚度(如 19 微米，21 微米等)、薄膜宽度（如 330mm

4、，620mm 等， ） 、件数；其次销售部门根据当前市场行情同客户商谈价格， 谈好价格后，客户会发过来一个清单；然后销售部会根据情况把相同薄膜类型、 相同厚度的需求合在一起，进行组合优化，形成一个切割任务单；最后在切割 车间通过机器将大卷切割成客户需要的规格（切割好后送达客户的薄膜称为小 卷，假设一般小卷的最小宽度为 330mm） 。某薄膜厂接到的订货（来自不同客 户的订货的汇总）数据见附录一。1.2 问题提出问题一：请你为该厂设计一个满意的切割方案送交切割车间，该切割方案 须指出切割大卷的总卷数、切割的方式数，材料的利用率等数据。 问题二：若该厂的薄膜切割机每天最多只能处理 24 大卷的切割

5、任务，3,7,9 号订单属于加急订单，必须在一周内完成切割，然后发货，问该怎样调整切割 方案，在这种方案下完成整个切割任务单需要多少天。2. 模型的假设与符号说明2.1 模型假设假设 1：每个切割点处由于锯缝所产生的损耗可忽略。 假设 2：每种薄膜有各自的交货时间,若某薄膜无交货时间,则记该薄膜交货时间 为无穷大。 假设 3：切割时零件的长和宽与原材料的长或宽平行。 假设 4：薄膜切割机不会发生故障，每天均能完成 24 大卷的任务。2.2 符号说明M使用的大卷总数（待求）ML大卷的宽度jL订单号需要的小卷规格（宽度）j(1,2,10)j Ljn订单号对相应规格小卷的需求量j(1,2,10)j

6、Lijx第 种最优的切割方式中第种规格薄膜的重复块数。ijI总共有的最优切割方式数id第 种切割方式耗用的大卷数iiS第 种切割方式下耗用的大卷数的有效使用宽度ip利用率N每天最多能处理的大卷数24N 1t限制的一周时间17t 3. 问题分析此题研究的是薄膜切割方案的设计问题。要设计一个满意的切割方案，就 要使得既满足客户要求，又使下料后的剩余边料总长最小，从而使材料利用率 最大，达到减少材料损失，降低成本，提高经济效益的目的。为了解决此问题， 我们将此问题归结为无重复规格的一维下料问题来求解。 针对问题一：在薄膜类型相同、厚度相同的情况下，由题意可推出薄膜的 长度也相同，那么就说明问题给出的

7、薄膜原材料的规格是统一的，所以可将此 问题归结为无重复规格的一维下料问题。为此，先采用嵌套穷举算法并利用计 算机自动确定所有可能的截切方案，然后对截切方案进行筛选，在筛选过程中 若单从数学模型的真实性这一角度来看，当然希望所考虑的截切方案越多越好， 但这必然使相应的模型趋于大型化、复杂化，从而增加求解的困难。反之，若 选用的截切方案太少，则相应的模型会变得太粗糙，甚至会把最佳的方案也漏 掉。因此，为了使建立的数学模型既简便又能较真实地反映实际问题的本质规 律，通常要对所生成的截切方案进行科学的简化。因此我们考虑：(1)去掉余料较大的部分方案，这是因为若某种截切方案所剩余料较大，则反映在相应的数

8、 学模型的解中，按这些方案下料的原材料根数必定很少甚至为零。(2)将余料较 小的那些方案取出单独考虑。在实际加工过程中让其充分生产，以满足需要。 这是因为在模型的解中，这些方案所对应的原材料根数必定很多。(3)考虑到生 产施工的实际情况，所筛选的截切方案的种类不宜过多，这样可以减轻劳动强 度和劳动复杂性，有效节省时间。 针对问题二：考虑到薄膜切割机有每日最大工作量的限制以及存在某些薄 膜完成的时间限制的情况，我们可以在模型一的基础上把那些有时间需求的薄 膜提前生产，并根据所耗费的大卷总数除以该厂每天最大工作量来判断完成时 间。在具体的求解过程中，我们可以采用启发式多级序列线性优化算法来逐级 求

9、解，首先我们应先考虑有时间限制的3、7、9号订单， 在当前可行的下料方 式中选择其中最优的（即尽可能的含有3、7、9）一种进行下料, 并尽可能多地 重复使用此种下料方式; 然后对剩余的坯料重新优化选取新的当前最优的下料 方式, 不断地重复上面的操作, 直到所有剩余的坯料数目均减小至零为止. 原问 题的最优解就是各个序列优化问题所求得的最优下料方式的总合.4. 数据分析为了问题求解的方便，将各种薄膜规格按照从大到小排序，即在求解中保 证先切割规格大的薄膜，然后在余料中切割规格小的，如此一来可以相对提高 原材料的利用率。为此，将原始数据作如下处理 表 4.1 按规格降序排列的订货单规格序号 订单号

10、规格（宽度，单位：mm）件数11022509429180018238147013947136026356125015765100053749203188382015692620456101330206设每根大卷的长度为,从中用去根(待定)加工成已知各种宽度规格LII 的成品根, ,有,则表jLjn1,2,10j L12345678910LLLLLLLLLL4.1 可以等价转换成表 4.2表 4.2 薄膜规格参数表 宽度 规格1L2L3L4L5L6L7L8L9L10L数量 1n2n3n4n5n6n7n8n9n10n5. 问题一的解答针对问题一，在假设 1、假设 3 的基础上，我们建立了模型一。5

11、.1 模型的建立（整数规划模型）5.1.1 确定目标函数将此薄膜切割优化问题转化为多级序列线性优化问题求解. 每级求解时, 在 当前可行的切割方式中选择其中最优的一种进行切割, 并尽可能多地重复使用 此种切割方式; 然后对剩余的薄膜重新优化选取新的当前最优的切割方式, 不断 地重复上面的操作, 直到所有剩余的薄膜数目均减小至零为止. 原问题的最优解 就是各个序列优化问题所求得的最优下料方式的总合. 由此中思路我们可以确 定目标函数为101maxiijj jSx L其中，表示第种规格的薄膜的宽度；表示第 种最优的切割方式中第种jLjijxij规格薄膜的重复块数。5.1.2 确定约束条件结合实际情

12、况，在第 件大卷上截取宽度规格为的块数是非负整数；ijLijx在某种最优的切割方式中第种规格薄膜的重复块数应该不大于该种规格所需j 要的数量。而且每一根大卷上切割的薄膜总长度必须小于该大卷的长度；此外， 在保证用料最少的情况下必须满足每一种规格所要求的数量。将这些约束抽象 成数学表达式，可以写成如下形式：1101. .(1,2, ;1,2,10)ijjIijj iijji jijxnxnstiI j x Ld LxN LL其中，表示总共有的最优切割方式数；表示一个大卷的宽度；表示ILid第 种下料方式耗用的大卷数；表示第种规格薄膜需要完成的件数ijnj5.1.3 综上所述，问题一的模型为101

13、maxiijj jSx L1101. .(1,2, ;1,2,10)ijjIijj iijji jijxnxnstiI j x Ld LxN LL5.2 启发式多级序列线性优化算法Step 1 依给定条件调用当前最优下料计算子程序, 求解得到优化值 组成的ijjx L作为第一级下料方式.101ijj jx LStep 2 计算此种下料方式的重复次数, 即此种下料方式所需原材料L 的根数id11221010min/,/,/iiiidnxnxnxLStep 3 计算去掉 根后, 余下的每种待切割的毛坯的根数 idjjiijnnd xStep 4 将作为新一级优化计算的给定值,如果所有的 都已减小至

14、零, 则优化jnjn计算结束; 否则转Step 1, 重新调用当前最优下料方式计算子程序, 求得新一级的 下料方式和重复次数.Step 5 各级最优下料方式及其重复次数的集合即为多级序列线性优化的最终结果.算法流程如图 5.1 所示给定,jjL L ni=1求出当前最优下料方式nj 是否全为 0停止d=minn1/xi1,n2/xi2, ,n10/xi10nj=nj-dxiji=i+1是否5.3 模型的求解对模型一，利用启发式算法在 Lingo 中求解得到满意的切割方案如下表： 表 5.1 最佳方案表 订单号切 割 方 式需 大 卷 数12345678910余 料利用率138212000000

15、000 29140220000000 3220071000000 41200504000000 5300051200000 63700110410000 74100120040000 8300050100010 94500000000220 103400040003001099.21%111000100230050 121000000130180 1310000000032090 1410000002120310 15190000003020420 1680000000040900其中，Lp=L 用的总大卷数-总的余料利用率用的总大卷数用的总大卷数 1Ii iMm5.4 结果分析由表 5.1

16、数据可得，用的总大卷数为 264，切割的方式有 16 种，利用率为 99.21%。每种切割方式用到的大卷数和完成的对应订单数不尽相同，详细数据 见表 5.1。在用启发式算法求解时，我们结合背包原理和实际经验，先处理规格 大的薄膜，后处理规格小的，但从表 5.1 的数据可以很明显地看出启发式算法 的贪婪性，为了材料利用最大化，余料最小化的目的，在优先选择切割方式时 还是先处理规格小的，所以此种算法存在它本身的弊端，为了尽量地克服此缺 陷，可以使用其他智能优化算法求解（如遗传算法等） 。6. 问题二的解答针对问题二，在假设 1、2、3、4 的基础上，我们建立了模型二.6.1 模型的建立（改进的整数规划模型）6.1.1 确定目标函数（同模型一的目标函数）101maxiijj jSx L6.1.2 确定约束条件在模型一约束条件的基础上，由于时间的限制， 需要对订单号为 3,7,9 的 薄膜优