最优切割模型

1、薄膜最优切割模型摘要本文解决的是根据客户订单如何对薄膜半成品进行合理切割的问题。对薄膜 的切割是否合理主要由材料利用率，工序复杂度和成本损失这三个方面来评价， 为实现薄膜的最优切割，建立了以下两个薄膜最优切割模型。模型一：对问题一，以每次切割薄膜余量最少为目标建立最优切割方式数学 模型，通过matlab编程求解该模型得到8282种可供选择最优切割方式。结合最 优切割方案的三个目标：材料利用率最大、切割方式最少、切割大卷总数最少， 和客户订单及相关约束条件建立多目标整数规划模型。对该多目标通过有宽度的 分层序列法求解得到不同优先级的两种切割方案：优先切割大卷总数得到方案 一，其材料利用率99.9

2、98%，切割大卷总数262,切割方式13；优先切割方式得 到方案二，其材料利用率95.52%，切割大卷总数274，切割方式6。模型二：对问题二，和问题一处理方法相同。结合薄膜切割机每天的工作量 和客户的加急订单，对加急订单完成时间进行约束，同样以材料利用率、切割方 式和切割大卷总数.为目标，建立问题二的多目标整数规划模型，通过有宽度分 层序列法得到两个供选择方案：优先切割大卷总数得到方案一，其材料利用率 98.87%，切割大卷总数262，切割方式27，订单完成的天数11；优先切割方式 得到方案二，其材料利用率98.87%，切割大卷总数265,切割方式8，订单完成 的天数12。关键字：多目标的整

3、数规划模型有宽度的层次分析法最优切割方式问题重述问题背景：直接从薄膜厂制膜车间生产出来的的薄膜，在薄膜行业称为半成品，简称大 卷或母卷，宽度一般为8100mm，厚度有若干种规格（如19微米、21微米等）， 长度则根据厚度不同而有所不同。薄膜厂销售部门首先接到客户订单或直接提货 单，客户订单或提货单中有所需要的薄膜类型（如BOPP膜、消光膜、CPP膜、 珠光膜等），薄膜厚度（如19微米，21微米等）、薄膜宽度（如330mm，620mm 等，）、件数；其次销售部门根据当前市场行情同客户商谈价格，谈好价格后，客 户会发过来一个清单；然后销售部会根据情况把相同薄膜类型、相同厚度的需求 合在一起，进行组

4、合优化，形成一个切割任务单；最后在切割车间通过机器将大 卷切割成客户需要的规格（切割好后送达客户的薄膜称为小卷，假设一般小卷的 最小宽度为330mm）。某薄膜厂接到如下订货（来自不同客户的订货的汇总）附件：订货单汇总一一薄膜类型相同、厚度相同。订单号规格（宽度，单位：mm）件数133020626204563820156492031851000536125015771360263814701399180018210225094待求解问题：问题一、请你为该厂设计一个满意的切割方案送交切割车间，该切割方案须 指出切割大卷的总卷数、切割的方式数，材料的利用率等数据。问题二、若该厂的薄膜切割机每天最多只

5、能处理24大卷的切割任务，3,7,9 号订单属于加急订单，必须在一周内完成切割，然后发货，问该怎样调整切割方 案，在这种方案下完成整个切割任务单需要多少天。符号说明与模型假设模型假设：假设一：薄膜厚度、长度相同。假设二：薄膜切割过程中不会出现工序故障。假设三：薄膜厂的半成品数量充足，可以满足客户需要。假设四：企业决策人对材料利用率所能容许的宽容限度为95%-100%。符号说明符号说明n薄膜厂大卷的利用率d大卷薄膜的宽度ni第j种切割方式切割得到的第1种薄膜类型的数量d.1第i种薄膜类型的宽度n.1客户需要的第i种薄膜类型的总数量n通过计算机搜索到的所有最优切割方式数k j第j种切割方式的重复次

6、数m求解目标函数所得的切割方式数m .min切割大卷总数下界s每次切割大卷后的剩余量问题分析该问题是根据客户订单确定对薄膜半成品进行合理切割的方案。薄膜有不同 的类型和规格，客户订单中薄膜的类型和厚度均相同，这样选择与之相符合的同 种类型的薄膜半成品进行切割，以满足顾客需要。问题一的分析：由于薄膜半成品的宽度要远大于小卷宽度，所以在进行切割 时有多种切割方案，且各种切割方案的材料剩余量会有所不同。由实际情况知， 切割方式不同时，要对机器进行调整换刀。所以切割方案越多，工序就愈复杂， 调整所需的费用和时间就相应增加。因此，减少切割方案数、提高材料的利用率 和减少所要使用的总大卷数是合理切割的关键

7、。分别以这三个平衡准则为目标建 立多目标的整数线性规划模型，切割方式数和切割大卷总数相互制约不能同时达 到最优，故采用有宽度的层次分析法求解该多目标规划模型，即当材料利用率达 到一定时，分别优先两个目标时得到两种不同的切割方案，客户可根据需要选择 适合的方案执行。问题二的分析：由于每天所能切割的大卷数有限，且某些订单必须在一周内 完成，因此对加急订单可以考虑优先完成。先用Matlab搜索较为合理的切割方 案（材料剩余尽量小），同问题一一样建立类似的多目标规划模型，再添加使加 急订单优先完成的约束条件。然后分别求解出使各个目标最优的满意解。同样采 用有宽度的层次分析反得到两种最优切割方案。最后结

8、合实际，通过分析比较各 个目标在企业心中所占的比重，推荐出一种满意的切割方案。模型准备4.1数据处理对客户订单中的不同类型的薄膜按订单号一次记为一类型、二类型十 类型薄膜。每一个大卷切割十种类型的薄膜，对应的最大数目分别为：24、13、 9 、 8、 8、 6 、 5 、 5 、 4 、 3。4.2切割大卷总数下界对薄膜的理想切割方式是材料利用率达到100%，当材料利用率达到100% 时求得的切割大卷总数时理想的最少切割大卷总数。可以作为切割方案切割大卷 总数的下界。求解下界方法如下：切割大卷总数下界=客户需求总量；大卷薄膜宽度即:犯min d求得当利用率为100%时，理想的最少切割总数为26

9、2卷。可以最为最优切 割方案得评价标准，最优切割方案得到的切割总数与262相差很少时，说明方案 比较合理的。4.3对任意大卷的最优切割方式最理想的切割方式是大卷正好被完全切割没有剩余，以任意一卷半成品切割 后剩余的薄膜材料最少为目标，确定最优切割方式如下：min s = d -En di=1约束条件：对该薄膜类型的切割总数不超过客户订单中的需求量即：n n结合目标函数和约束条件得到对任意大卷的最优切割方式数学模型：min s = d - E n d= 1s.t. n ? j I 0 k = 0 i j切割方式数 m = sgn(k.)(n = 8281)j=1目标三：减少切割大卷总数降低工序复

10、杂度，切割大卷总数=尤kj j=15.2约束条件客户需求约束：生产小卷薄膜满足顾客需要* * k n= nj =1 i =1大卷薄膜的宽度约束：对任意一个大卷切割得到的所有小卷薄膜的总宽度不会超过大卷宽度0.i n d di=13）整数约束：切割大卷总数和每次切割小卷均为整数n e Nk e N5.3问题一的多目标规划模型结合目标函数和约束条件得到问题意的多目标规划模型r工妙疽max 门=j=i i=100%尤VVminm =乙 sgn（k ）j=min工 kj j = 1 如 kn = nj=i i=i j j is.t 0 n d 0j I 0 k = 0i j切割方式数 m = sgn(

11、k )(n = 8281)j=1目标三：减少切割大卷总数降低工序复杂度，切割大卷总数=kjj=16.2约束条件客户需求约束：生产小卷薄膜满足顾客需要 k n= nj =1 i =1三、四、七号定单是加急订单需在一个星期内完成，为满足客户需要，考虑 优先切割三、四、七号订单，当着三种订单切割结束后在切割其它订单，引入函 数sgn X =* 0则切割者三种订单的总的大卷数不会超过一个星期内可以切|0 X = 0割的大卷数总会共和，即：k sgn(n ) 24*7j=1大卷薄膜的宽度约束：对任意一个大卷切割得到的所有小卷薄膜的总宽度不会超过大卷宽度0.i n d di=13）整数约束：切割大卷总数和

12、每次切割小卷均为整数n e Nk e N6.3问题二的多目标规划模型结合目标函数和约束条件得到数学模型r工妙疽max 门=j=i i=100%尤VVminm =乙 sgn（k ）j=min工 kj j = 1yk n = nj=1 i=1 7 7y k sgn(n ) 24*7j=10 n d di=1n e Nk： e N6.4模型的求解问题二和问题一求解基本一致，此时考虑大卷切割机每天的工作量和客户的 加急订单，为满足客户需要含有加急订单的切割方式在前一个星期内执行即可。 模型的求解运用有宽度的分层序列法，对目标一优先和目标二优先时分别求解， 通过lingo编程（见附录三）得到两个方案如下

13、：(1)方案一：目标一优先表6.1：目标一优先结果表序号切割方式重复 次数单个大卷 余量利用率大卷总数11*心18099.97%26221*+2*+4畛47031* +1* +1* +3* +1*(21041*+4*+2咆48051* +4啕+2*岔+1*11062咆+5*16072*+1*+2*+1*31082*+3*+2*+1*1092*+1*+3*+2*80102咆+2* +1* +1* +2*120113咆+1* +1* +1* +1* 0+1* 110124咆+2咆+1*+1*110134咆+2啕+1*+2*210145咆+4*3701513*140161*+3*+2*+1*1201

14、71*+2*+3*+1*+1*120181*+3*+4*330191* +4崎+4临+2*610201*+11*+1*130212*&+2* +2* 420222吟+4咆+1*+2咆340233吟+2咆+1*+2哑220243吟+2咆+1*+2呃11025$*+3* +1* +1* +1* 120266临+1* *4啥 *1*220278临+4*岔220表格说明：在切割方式一栏中，-表示规格，1,2表示一个大卷切割的 件数。黑体有灰色底纹的切割方式含有加急订单，在第一个星期内完成。目标一优先时得到切割方式27种，材料利用率99.97%,切割的大卷总数262 卷，完成任务需要11天。其材料利用率

15、和大卷总数非常理想，但切割方式数过 多，需要进一步优化。（2）方案二：目标二优先表6.2:目标二优先结果表序号切割方式重复次数单个大卷 余量利用率大卷总数11* +4*168098.87%26521* +2啥+4*26031* +4*q+2*48041* +1* +1* +3*+1* 531055*+6*340613*184072*&+2* +2*48085*&+3噫+1* +1* +1* 2220表格说明：（1）在切割方式一栏中，-表示规格，1,2表示一个大卷切割的 件数。（2）黑体有灰色底纹的切割方式含有加急订单，在第一个星期内完成。目标二优先时得到的切割方案其材料利用率为98.87%，大

16、卷总数265卷， 切割方式8种，完成任务需要11天。6.5方案决策指南方案一和方案二比较，在一般情况下以目标二优先得到的切割方案是较优 的。但企业决策人可以根据实际选择适合自己的方案执行。模型的评价7.1模型的评价优点：1）结合实际情况，根据企业所关注的方面建立三个目标，很具有现实意义。2）将不同目标的优先级进行排序后，依次求解出不同目标下切割方案，可以满 足企业在不同情况下的需求3）从人性化的角度，根据不同企业的容忍限度制定出令企业满意的切割方案。不足：1）通过计算机搜索最优方案时，由于变量较多，程序运行较长时间。2）由计算机搜索出的最优方案有限，最后求解整数线性函数，得到的并不一定 是最优

17、解，只是满意解。模型的改进与推广8.1模型改进为减少搜索范围，减少运算量，提高算法收敛到最优解的速度，可以制定一 些合理的准则确定切割方案。准则:1）在各种规格的组合中，以每卷余料最少的切割方式优先；2）将有时间限制的订单优先考虑；3）第j种切割方式中，若重复k次正好可以将某一订单完成，则下次寻找 方案时，不考虑此订单的规格；4）将未完成的订单重复第二步；5）当所有的订单都完成时，停止搜索。问题一的多目标规划模型：XrH k n dj ij imax 门=j=i i=i100%!叩顶、minm =乙 sgn（k ）j=1mink d、j=1求解结果序号方式重复次 数每卷余量总利用率大卷总 数1

18、2临+12*38099.6%26524*&+2* +2* 9032*&+7* +1* 2045噫+4*12055*3+1* +2* 3061*+1*+4*+1*37071*+2*+4*41085唯+1*+1*3092愠+2*450104唯+3*3410111*+2*+3*250121*+3*180133*+2* 990142*q+1* +2* 1310153响+2*18420164愠9900171*16740总方案数为17种，材料利用率达99.6%，总的大卷数为265,但程序运行 时间大大缩短了。8.2模型推广本模型对于求解一维下料问题有较好的参考价值参考文献1.董臻圃编，数学建模方法与实践，

19、国防工业出版社10附录附录一：下料方案的确定：clear;clc;guige =330620820920100012501360147018002250;jianshu=206 4561563185315726313918294;shangxian=8100./guige;shangxian=fix(shangxian);k=0;for i1=0:24for i2=0:13for i3=0:9for i4=0:8for i5=0:8for i6=0:6for i7=0:5for i8=0:5for i9=0:4for i10=0:3t=i1,i2,i3,i4,i5,i6,i7,i8,i9,i1

20、0;t1=8100-sum(guige.*t);if t1=0k=k+1;fangan(k,:)=t;yuliang(k)=t1;endendendendendendendendendendendsave yuliang;save fangan;附录二：第一问目标1：(最少大卷数)model:sets :fangshi/1.8281/:genshu,xuanqu;bmgg/1.10/:guige,xuqiu;xishu(fangshi,bmgg):c; !c(i,j)表示按照第i种方式切割时能获得的第j种薄膜的 数量；endsetsdata:guige=330 620 820 920 1000

21、 1250 1360 1470 1800 2250;xuqiu=206 456 156 318 53 157 263 139 182 94;c=file(fangan.txt);enddatamin=sum(fangshi(i):genshu(i);for(bmgg(j):sum(fangshi(i):c(i,j)*genshu(i)=xuqiu(j);for(fangshi(i):gin(genshu(i);End第一问目标2：(最少切割方案)model:sets:fangshi/1.8281/:genshu,xuanqu;bmgg/1.10/:guige,xuqiu;xishu(fangs

22、hi,bmgg):c; !c(i,j)表示按照第i种方式切割时能获得的第j种薄膜的 数量;endsetsdata:guige=330 620 820 920 1000 1250 1360 1470 1800 2250;xuqiu=206 456 156 318 53 157 263 139 182 94;c=file(fangan.txt);enddatafor(fangshi(i):bin(xuanqu(i);!当xuanqu(i)=0时，表示不选取对应的薄膜，而对应的genshu(i)也等于0;! 当xuanqu(i)=1 时，对应的genshu(i)不可能大于 10000*xuanqu(

23、i);!xuanqu(i)这个变量是为了把问题线性化的;for(fangshi(i):genshu(i)=xuqiu(j);for(fangshi(i):gin(genshu(i);sum(fangshi(i):sum(bmgg(j):c(i,j)*guige(j)*genshu(i)/sum(fan gshi(m):genshu(m)*8100)=0.99;sum(fangshi(i):genshu(i)=274;!sum(fangshi(i):xuanqu(i)=xuqiu(j);sum(fangshi(i):genshu(i)*if(c(i,3)+c(i,7)+c(i,9)#gt#0,1

24、,0)= 168;for(fangshi(i):gin(genshu(i);end第二问目标1的优化：(尽量使切割方案减少)model:sets:fangshi/1.27/:genshu,xuanqu;bmgg/1.10/:guige,xuqiu;xishu(fangshi,bmgg):c; !c(i,j)表示按照第i种方式切割时能获得的第j种薄膜的 数量;endsetsdata:guige=330 620 820 920 1000 1250 1360 1470 1800 2250;xuqiu=206 456 156 318 53 157 263 139 182 94;c=0 01000004

25、00012004000001400002001011031000140002100020000500002001000210200321000020130020002210012000310111010040020100104200120000500040000013000000001000320001120031000113000004001440200000111010000002000000202240000102032000000213200001002503101001061040000108000004000;enddatafor(fangshi(i):bin(xuanqu(i);!当xuanqu(i)= 0时，不选取对应的薄膜，而对应的genshu(i)也等于0;! 当xuanqu(i)=1 时，对应的genshu(i)不可能大于 10000*xuanqu(i);!xuanqu(i)这个变量是为了把问题线性化的；for(fangshi(i):genshu(i)=xuqiu(j);for(fangshi(i):gin(genshu(i);sum(fangshi(i):sum(bmgg(j):c(i,j)*guige(j)*genshu(i)/sum