数学建模论文—薄膜切割问题.doc

科院10组： 蔡光达 王良泽南 熊佩玉薄膜切割问题摘要本文讨论的是薄膜的合理切割问题，属于优化问题中的组合问题。该问题的关键在于如何合理地安排薄膜切割的模式，使得材料利用率达到最大且原材料使用最少。因此我们建立了线性优化模型，用LINGO和MATLAB软件求解，得出在订单所需薄膜件数的限定下，最合理的切割方式。对于问题一，我们先求出10种规格的小卷的切割模式，由于符合条件切割模式有1000多种，所以随机选取了一件大卷的利用率大于99%的16种模式（具体模式见表2）作为切割方式的基本模式。然后，我们以切割大卷的总件数最小为目标函数，建立模型，运用MATLAB软件求解，共运用了9种切割模式（具体模式见表3），切割大卷的总卷数为265件，材料利用率为99.80%。对于问题二，该问题在问题一的基础上加入了时间限制，我们把时间限制转化为对大卷数目的约束，即在切割的168件大卷中第3、7、9号订单的小卷件数必须全部切割完成。最后建立线性优化模型，求解得出前7天内运用第1、5、6、9共4种模式切割，然后改变切割模式，用第3、4、8、9、10、15共6种模式切割（具体模式见表4），切割大卷的总卷数为265件，完成整个切割任务单用时12天,材料利用率为99.63%。关键词：线性优化模型 利用率 切割模式1. 问题重述1.1问题背景直接从薄膜厂制膜车间生产出来的的薄膜，在薄膜行业称为半成品，简称大卷或母卷，宽度一般为8100mm，厚度有若干种规格（如19微米、21微米等），长度则根据厚度不同而有所不同。薄膜厂销售部门首先接到客户订单或直接提货单，客户订单或提货单中有所需要的薄膜类型（如BOPP膜、消光膜、CPP膜、珠光膜等），薄膜厚度(如19微米，21微米等)、薄膜宽度（如330mm，620mm等，）、件数；其次销售部门根据当前市场行情同客户商谈价格，谈好价格后，客户会发过来一个清单；然后销售部会根据情况把相同薄膜类型、相同厚度的需求合在一起，进行组合优化，形成一个切割任务单；最后在切割车间通过机器将大卷切割成客户需要的规格（切割好后送达客户的薄膜称为小卷，假设一般小卷的最小宽度为330mm）。某薄膜厂接到如下订货（来自不同客户的订货的汇总）1.2需要解决的问题问题1请你为该厂设计一个满意的切割方案送交切割车间，该切割方案须指出切割大卷的总卷数、切割的方式数，材料的利用率等数据。问题2若该厂的薄膜切割机每天最多只能处理24大卷的切割任务，3,7,9号订单属于加急订单，必须在一周内完成切割，然后发货，问该怎样调整切割方案，在这种方案下完成整个切割任务单需要多少天。2. 模型假设假设1：切割过程中不会出现机器故障等其他非正常故障。假设2：假设大卷类型、厚度与客户订单的类型、厚度一致假设3：每种切割模式下的余料浪费不能超过100mm假设4：忽略薄膜切割过程中大卷的损耗假设5：每次切割都准确无误假设6：没有额外追加订单假设7：大卷总数足够多3. 符号说明符号符号说明切割模式的总数第种切割模式第小卷的种类小卷的总规格类型按照第种切割方式所切割的大卷件数第种小卷的宽度第种切割方式得到宽度为的小卷件数第种小卷的需求量大卷的宽度切割大卷的总件数每天最多处理的大卷件数一周内处理的大卷总数第个大卷种切割的第种小卷的件数T完成切割任务天数材料的利用率一张大卷能切出的小卷数量切得剩余材料的量最多能完全切割的大卷总数剩余没有切的小卷数4. 问题分析切割问题是下料问题的一个分支，而一维下料问题是组合优化中的一个经典问题，如果要得到理论上的严格全局最有下料方案。就要求所有可行下料方式都进入线性规划模型的系数矩阵，从计算的复杂性理论上看，这属于NPC（NP完全）难问题。因此，我们放弃常规的整数规划解法，而在以优化选取下料方式的前提下，寻找建立下料方案的模型。本文要求一个好的下料方案在生产能力允许的条件下要满足两个要求：首先，应该使原材料的利用率最大，即用最少数量的原材料；其次要求所采取的不同下料方式尽可能少。本文主要分析的是怎样切割薄膜使得所用原材料总数最少且材料利用率最大。订单中要求的小卷规格都不能与大卷规格成整数倍，即大卷无论只切割哪一种规格，都不可能完全切完，一定会有剩余，这是对问题的极端分析，可以更清晰的了解问题和认识问题，从中理清思路，找出最好的解答策略。针对问题一：对于薄膜切割问题首先要确定采用哪些切割模式。所谓切割模式，是指按照订单要求在原料大卷上安排切割的一种组合。例如，我们可以将8100mm的大卷切割成13件宽度为620mm的小卷，余料为40mm；或者将8100mm的大卷切割成宽度为820mm的小卷1件和宽度为1470mm、1250mm、920mm的各2件，余料为0。显然，可行的切割模式很多。于是问题转化为在满足客户需要的条件下，按照哪几种合理的模式进行切割，每种模式切割多少件大卷最为节省。而由于需求的小卷规格为10种，所以枚举法大的工作量较大，消耗时间，且不具有普遍性。我们设法把切割方式作为约束条件，放在规划中一起解决。针对问题二：该问题在问题一的基础上增加了限制条件，即薄膜切割机每天最多只能处理24大卷的切割任务；3,7,9号订单必须在一周内完成切割。对于这两个限定其实我们可以和在一起讨论，切割时间与切割大卷件数有一定的关系，我们将3,7,9号订单分离出来考虑，并把对时间的限制转化为对大卷件数的限制，即要求在切割的前168件小卷内3、7、9号订单中的三种规格的小卷必须完成切割。在这样的基础上，再考虑搭配最佳切割方式，建立的数学模型同问题一完全一样，只是增加了一个限制约束。最终运用软件求出这种方案下得最佳材料的利用率和切割大卷的总卷数。5. 数据分析4.1对数据的极端分析首先对数据进行一系列简单的分析，主要是进行一些极端的分析，对问题总体有了一个大致的了解。当一张大卷只被切割成一种规格的小卷时，能切出的小卷数量x以及剩余材料的量y(其中超过330的都用红色字体表示出来)、在所需件数范围内最多能完全切割的大卷总数a以及剩余没有切的小卷数b。表1：对数据的极端分析（规格单位：mm）订单号规格件数133020624180814262045613403513820156972017349203188740396510005381006561250157660026171360263513005238147013957502749180018249004521022509431350311规格最大的是10号，规格最小的是1号；件数最多的是2号，件数最少的是5号；x最大的是1号，x最小的是10号；y最大的是10号，y最小的是2号；a最大的是7号，a最小的是5号。4.2对选出的利用率高的切割方式数据分析一个大卷的不同切割方式有1000多种，为简化计算，我们对切割方式进行了限制并随机挑选出16种大卷利用率大于99%的方案作为本题求解的进本模式。具体切割模式如下：表2：切割大卷的基本模式（小卷规格单位：mm）规格模式330620820920100012501360147018002250余料利用率100120202000100%2190000000103099.63%3011000100003099.63%420071000000100%500100040014099.51%600100000408099.01%759100000005099.%38803250000000100%901000103102099.75%1001000301011099.88%1100050100010100%1230200040003099.63%1310001010301099.88%1410001000032099.75%1520012000022099.75%1621100001023099.63%6. 问题一的解答6.1模型一的建立6.1.1确定目标函数该模型的建立是为了解决薄膜的切割问题，为了使切割方案合理，我们以大卷的最少使用件数为目标函数函数建立模型。目标函数：6.1.2确定约束条件从题目中分析可知，主要的约束条件有两个，I切割出的小卷总宽度小于等于，且余料小于，即：II 最终切割得到的小卷件数必须达到订货件数，即：6.1.3综上所述，得出目标最优化模型：6.2模型一的求解首先从第一张大卷开始，将10种规格合理分配和安排，从而获取1种最佳切割方式作为第1种切割方式，然后一直使用这种方法，直到某一种或几种规格的小卷因为已经完成或快完成目标而使得方案无法进行时，再根据实际情况，对剩下要完成的薄膜重新组合分配，再寻找出第2种切割方法，然后继续以上的方法，得出第2种切割方案，以后方案依此类推，直到获得第种方案为止。算法思想：切割刚开始执行时，处理答卷总数z=0,每经过for语句每循环一次，z的值加1，最终输出的z值就是切割大卷总数。再根据z值，求得材料利用率，切割方式可以根据最终程序输出的每一种规格的薄膜在每一次切割答卷时产生的件数得出。模拟的流程如下所示:开始将z赋值为0进入第一种切割方式每切一次大卷z加1开始该切割方式的实施后经过s次循环后是否开始下一切割方式以同样的方法进行是否完全结束切割否是结束方式是否能实施最终求得结果：表3：使用的薄膜切割方式方式330mm620mm820mm920mm1000mm1250mm1360mm1470mm1800mm2250mm余料大卷数3011000100003031803250000000209010001031020381001000301011015110005010001044123020004000305413100010103010481410001000032051621100001023010求和717510265547150265切割大卷总件数： 材料利用率： 6.3模型一的结果分析我们选出了比较合适的方式在方案中加以利用，但是由于我们为了提高材料利用率，切割数量超出了订单中要求的件数，大卷总数265可能比完全按照订单切割的方案要多，但我们之所以多，不是多了切割出来的废料，而是多了按照一定规格切割出的薄膜，因此不作为废料进行计算，算得的结果很高99.80%接近100%。7. 问题二的解答7.1模型二的建立7.1.1确定目标函数问题二要求出完成整个切割任务单需要的天数，因为该厂的薄膜切割机每天最多只能处理24大卷的切割任务，所以我们仍以使用大卷的最少件数为目标函数。目标函数： 所需天数： 7.1.2确定约束条件模型二的约束条件是在模型一的基础上将对订单号为3,7,9的小卷规格分离出来，对其加以限定约束，使其在一周之内完成。我们将其时间限制转化为对切割大卷件数的限制。分析可知，在切到第168个大卷之前必须完成对上述三个订单的切割。即：7.1.3综上所述，得出多目标最优化模型7.2模型二的求解模型二的求解，需要在模型一的基础上，对于i=3,7,9这种特殊情况分开进行考虑，由于受一周时间的限制，我们决定重新设定一个类似于z的新的变量w，它的取值范围是1,7d,这样处理，会出现两个关于大卷数量的值：z，w。我们将选取其中较大的值进行下一步计算，计算完成切割任务天数T是将z和w中较大值与24的比值取整后加1得出结果。结果如下表所示表4：问题二的薄膜切割模式模式330mm620mm820mm920mm1000mm1250mm1360mm1470mm1800mm2250mm余料/mm大卷数/件1001202020004630110001000030404200710000003021900000001030780325000010039010001031020151001000301011051520012000022012600100000408041500100040014066求和2316615374674230265由于1,3,9号是加急订单，为了在规定时间内完成，我们应该以以下四种切割方式为优先方式，模式330mm620mm820mm920mm1000mm1250mm1360mm1470mm1800mm2250mm余料/mm大卷数/件10012020200046901000103102015600100000408041500100040014066表5：优先切割模式7.3模型二的结果分析由上表可知，七天内实际完成1,3,9号订单件数分别为156，264，194件，此结果满足题意要求，大卷总数是265，材料利用率为：接近1，说明此方案是可行的。完成整个切割任务单的天数为天。8. 模型的评价、改进和推广8.1模型评价模型优点：（1）从切割一开始就进行最优化方案，寻找最优解，方法快捷简便且容易理解，容易被人接受。（2）对于实际生活中的各种类似情况都可以通用，实用性强。（3）模型二在针对类似问题时，只需修改w的范围和i的取值即可投入使用。模型缺点：该模型对切割模式较少的下料问题比较适用，但对于一些问题更复杂的情况就不易算出或求解不出。另外该题工作量也稍微有一点大，且多生产了一些规格的薄膜。8.2模型改进8.2.1改进为了提高材料利用率造成的损失按订单要求切割件数与实际切割件数的比较订单12345678910要求2064561563185315726313918294实际 2354641583205315826413918294比较发现订单号为1,2,3,4,6,7的实际切割件数超出了订单切割件数，这是我们为了保证材料利用率较高而造成的结果，下面分析它的利与弊，若以后订单中仍会用到，则可以获取利润，若以后订单中很少用到，则会有损失。对这种情况，我们考虑对于那些订货率很高的规格的薄膜，允许超出了订单中的件数，对订货率较低的规格的薄膜，我们不允许超出订单中的件数。最终可以获取更高的利润。对于问题2出现了加急订单，若能够使用我们改进后的方案，还有多余的薄膜可以利用，能够更快的完成加急订单的任务，提高可信度。8.2.2改进只对单一个体的考虑而忽视了整体在求最优解时，太过直接，应该将眼光放长远对整体考虑，考虑到各种最优方案在整体模型中的不同阶段的合理分配，再进行一次优化，建立出一个对于整体最有利的模型，并加以推广运用到各行各业中的类似项目。在求最优解时，太过直接，应该将眼光放长远对整体考虑，考虑到各种最优方案在模型中的不同阶段的合理分配，再进行一次优化，建立出一个对于整体最有利的模型，并加以推广运用到各行各业中的类似项目。8.3模型推广我们建立的模型具有普遍意义，模型的建立不仅易于多数人的理解，而且可以应用到实际生活中的很多问题。如制造业中各种板材、线材、型材、管材零件的切割下料，服装行业的剪裁问题等等。参考文献1刘勇彪.等界面长条类材料下料方案的最优化设计J.机械设计与制造，1994,5. 2闵仲求.合理下料的实用数学模型及其计算机软件的研究J.系统工程理论与实践，1982,4.3刘道海，方毅，黄樟灿.一种求解组合优化问题的演化算法J.武汉大学学报（理学版），2002,48.4王小东，李刚，欧宗瑛。一维下料的一种新算法J.大连理工大学学报，2004,44.附录附录一：附件：订货单汇总薄膜类型相同、厚度相同。订单号规格（宽度，单位：mm）件数133020626204563820156492031851000536125015771360263814701399180018210225094附录二：问题一的求解问题一的LINGO程序（方案选择）：model:sets: fangs/1.20/:x;xingh/1.10/:jian,kuan;links(fangs,xingh):mjian;endsetsmin=sum(fangs:x);for(xingh(j):sum(fangs(i):mjian(i,j)*x(i)jian(j);for(fangs(i):length-min(xingh(j):kuan(j)+1sum(xingh(j):mjian(i,j)*kuan(j);for(fangs(i):sum(xingh(j):mjian(i,j)*kuan(j)sum(xingh(j):jian(j)*kuan(j)/8100);for(fangs:gin(x);for(links:gin(mjian);data:jian=206,456,156,318,53,157,263,139,182,94;kuan=330,620,820,920,1000,1250,1360,1470,1800,2250;enddatadata: !ole(C:Documents and SettingsAdministrator桌面jieguo.xls,moshi)=mjian;!ole(C:Documents and SettingsAdministrator桌面jieguo.xls,juanshu)=x;enddataend问题一的MATLAB程序（结果求解）：clc,clearz=1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ;z=z;a=-00120202001900000010001100010000200710000000100040010010000040591000000003250000000100010310