工厂实际生产的下料问题-李非

1、B题.李非,李廷志,陈微二等奖一.问题背景工厂在实际生产中需要对标准尺寸的原材料进行切割，以满足进一步加工的需要，称为 卜料问题（Cutting Stock Problem）。在I：程应用中，卜料问题可能以不同的的形式表述，但本质上可简化为相同的数学模型。 典型的二维卜科问题可表述如F：将若干相同规格的矩形原材料切割成JW种规格的矩形手 件，卜料时零件的边必须分别和原材料的边平行,所有零件的厚度均与原材料一致。特别当 所有零件的宽度均与原材料相等，则问题称为一维卜料问题。相关数据表明，原材料成本占总生产成本的百分比可以高达45%60%,而卜料方案的 优劣宜接影响原材料的利川率，进而影响原材料成

2、本。因此需要建立优化的卜料方案，使得 在生产能力容许的条件卜.，以最少数吊:的原材料，尽可能按时完成需求任务，同时卜料方式 数也尽最地小。二.问题描述现需要建立优化的卜.料方案，使得在生产能力容许的条件卜，以最少数局的原材料，尽 可能按时完成需求任务，同时卜料方式数也尽量得少。在该目标卜.要求考虑卜面两个问题： 1.苜先建立-维单一原材料实用卜料问题的数学模型，并用此模型求解卜列问题，制定出 在生产能力容许的条件卜满足需求的卜料方案，同时求出等额完成任务所需的原材料 数，所采用的卜料方式数和废料总长度。该企业每天最大卜料能力是100块，单一原材 料的长度为3000mm,需要完成一项有53种不同

3、长度零件的卜.料任务。此外，在每个切割点处由锯缝所产生的损耗为5mm。要求在4天内完成的零件标号（,）为:5,7,9,12,15,18.20,25,28,36,48 ：要求不迟6天完成的零件标号（） 为：4,11,24,29,32,38,40.46,50。2.建立二维单一原材料实用下料问题的数学模型,并用此模型求解卜.列问题。制定出在企 业生产能力容许的条件卜.满足需求的卜料方案，同时求出等额完成任务所需的原材料块 数和所需卜料方式数。单一原材料的长度为3000mm,宽度为100mm,需要完成一项 仃43种不同长度和宽度零件的卜.料任务。切割所引起的锯缝损耗忽略不计。该企业每 天最大卜料能力是

4、20块,要求在4大内完成的零件标号（。为:3,7,9,12,15,18,20,25.28,36。三.基本假设1.假设工厂每天都以其最大卜料能力工作。四.符号说明C：指企业每天最大的卜料块数。L：原材料的长度。卬：原材料的宽度。吗：第i种零件的宽度,且叫W,i = L，LL：第种零件的长度，且吗4乙，=L，叫0：原材料切割点处由锯缝所产生的损耗。相：所需切割的零件的种类。，：第种零件所需的切割的数最，, =1，/P：总的下料方式数。ai ：第/种卜.料方式中第i种零件的切割数吊:，i = L，?，尸1，P。/：第/种卜料方式使用的次数，/ = 1，。q ：所需原材料的数尿：，q = J五.问题分

5、析一个好的卜料方案首先应该使原材料的利用率最大，从而减少损失，降低成本，提高经 济效益。其次要求所采用的不同的卜.料方式尽可能少，即冷型用最少的卜料方式来完成任务。 因为在生产中转换卜料方式需要费用和时间，既提高成本,又降低效率.此外，每种零件仃 各自的交货时间，每天卜料的数吊:受到企业生产能力的限制。因此实用卜料问题的H标是在 生产能力容许的条件卜.，以最少数吊:的原材料，尽可能按时完成需求任务，同时卜料方式数 也尽量得少。本题可以转化为多目标优化问题，利用线性规划和整数规划相关方法求解。下料方式卜料方式描述如何将单块原材料切割为若干零件，例如卜图表示二维情况卜原材料的一 种卜料方式。图1二

6、维情况下原材料的一种下料方式.就本问题而言，模型仅关心不同卜料方式带来的专件生产种类和数局的变化，而忽略其 具体布局,也就是说,所切割的零件种类及数目完全相同,仅布局不同的下料方式认为是同 #B题.李非，李廷志,陈舜二等奖一种卜.料方式。卜料方式以向最。= （一,”尸我示，其中q.为该种卜料方式中第i种 零件的切割数吊:。通常生产需要采取多种不同的卜料方式来完成生产任务，完成任务所需的卜料方式的集 合（简称卜料方式集）记为：A的维数为7X，其中p为卜料方式数，川为所需切割的零件的种类。可行的下料方式集A满足原材料长度和宽度的约束。a）在一维单一原材料情况下，可行的卜料方式集A应满足：（b =

7、57？为切割损 耗）m-（j = 1,，p r=lb）在二维单原材料情况卜.，可行的卜.料方式集A中的每一种卜.料方式必须是可实现的，即存在满足要求的零件切割布局。下料方案卜料方案描述一批原材料如何切割为任务所需的零件，例如共使用多少块原材料，以及 各原材料分别采用何种卜料方式。由濒繁转换卜料方式会带来额外的时间和材料的损耗, 厂在确定一批原材料的卜料方案后，会尽显将采用相同卜料方式的原材料连续切割，减少 转换次数，降低生产成本。在基单一规格原材料的卜料方案优化问题中，不考虑时间因素, 同批原材料之间的生产次序可以忽略，认为在给定卜料方式集的基础上，卜制方案仅由每种 下料方式使用的次数决定，记

8、为：X = （W,/尸，W：第j种卜料方式使用的次数，且j = l,P。可行的卜料方案应满足零件个数的约束，设卜.料方式集为4心，则行：4叼心其中=且/为整数，满足x，2 0, j = 1,，p。该卜料方案使用的原材料数最为：q = 六1注意到可行的卜料方案中零件个数的约束为不等式约束，与题设等额完成任务似有不 符，但事实上，如果以使用的总原材料数吊作为规划目标，并将多生产的零件视为废料，两 者等价。时间约束假设工厂以最大的生产能力生产，并旦每天切割的原材料数最为常数c,此时原问题可以转化为无时间约束的多阶段卜料方案优化问题。例如当C = 100时，要求四天内完成的零件必须使用前400块原材料

9、生产，六天内完成的号件必须使用前600块原材料生产，等 等。进一步，通过把最终卜料方案分解为三个阶段的卜料方案，可以将对卜料方案的时间约 束转化为零件个数的约束，简述如下：设前4天的卜.料方案为X,在4天内完成的任务为；第5、6天的卜.料方案为X”，在6天内完成的任务为“；剩余时间的卜料方案为工，最终完成的任务为，则有：A(xxn)nn, n-400600,最终使用的原材料数仄为:B题.李非，李廷志,陈微二等奖9下料问题的分解由上分析可知，卜料问题可以分解为两个子问题：卜料方式集的确定和基卜此卜料方式 集的卜料方案的选择。其中卜料方式集可以借助搜索算法产生或根据经验选取适当的卜料方 式集；卜料

10、方案的选择寻优可以表达为线性规划或整数规划，使用单纯形法、分支定界法等 技巧求解。六.模型的建立与求解一维下料模型的建立及求解(1)无时间约束时模型的建立与求解下料方式集针对特定组零件，列举满足长度约束的所仃卜.料方式，分别计算其废料长度 (mm),统计产生相同废料长度的卜料方式数N3),结果如卜.:x 10500 1000 1500 2000 2500 3000 3500(a)於 y/thL 金U.M.U铛 MX0.53.53252005001000 1500 2000 2500 3000 3500度外长度卜科方式故变化&势x104图2 ： (a)为/可()随的变化趋势(b)为N()随的变化

11、趋势废料K度小厂一定上限的卜料方式数随上限的增加而迅速增大，从卜.表的数据中也可以看出这点。表1 N(切随增大而迅速增大S (nun)05101001000N()40882239985435988339550810160465亘观地分析可知，可供选取的卜.料方式p越多，越容易得到用料较省的卜料方案，反 之,过少的卜料方式有可能导致卜料方案中对原材料的利用率迅速卜降，甚至无可行的卜料 方案。另一方面，卜料方式数p对应下料方案的线性规划模型的变尻数，越大，求解越 困难，况且实际生产中每次转换卜料方式所增加的成本在一定程度上抵消在原材料上节约的 成本。因此，卜料方式的选取需要权衡各方面因素，绝非越多

12、越好。当所要切割的零件有53种时，所仃可行的卜料方式共有10307032种。问题的关键在广 如何从中适当选取卜料方式，构造卜一步的规划求解需要的卜料方式集。进一步的计算表明， 当卜料方式数达到一定数品:时，继续增加卜料方式对广卜料方案的优化没有显著影响，换句 话说，当p较大时，卜料方案X与p的变化近似无关，这一结论将在卜.料方案的规划求解 中得到验证。综上，分别采取满足=0,2, 43, n(2)WNO, j = l,p注意到模型中并未要求w为整数，求解结果中w也未必是整数，因此自接线性规划所 得到结果并不满足题目要求，但可以在此基础上构造满足整数要求的可行解。设x = (W,H)为满足约束A

13、vN的解，构造打=(卜，,因)为各分属的向上取整值，由A、x中各分最的非负性，可以证明因此，若x为线性规划范畴卜.的可行解，x即为可行的卜料方案,同理，若x为线性 规划范畤卜的最优解，即为较优的卜料方案，对比同一下料方式集卜最优的卜料方案，其原材料使用数成之差不大中非零分仄的个数，例如在卜料方式集4L线性规划结 果为q = 80L8,在此基础上构造计算其原材料使用= 850,文中分吊大0.01 的个数为66,若认为只仃对应分吊:大r一定值的卜料方式才被有效使用，则可认为有效使 用的卜.料方式P为66种。由此可估计在卜.料方式集4卜.，其最优整数规划解的4介广802850之间，且已找到q = 8

14、50的可行解。表2不同废料长度下的下料方案卜科方案012345T20”130”212”4X)3508”73P4088280377121407161086200080239985P666466676864q801.81796.98796.98796.98796.98796.98注:T为相应结果的计算机求解时间。缴规划整数规划本质上属NP问题，在卜料方式集儿A的规模卜，无法汽接求解，但事实上并非其中所有的下料方式被使用。线性规划结果表明,在给定下料方式集A卜，实际力效使用的卜科方式数远小广可选的卜料方式数(66440882),可以认为仅使用较少的F料方式也可较好地完成零件的加工任务。为了对不同卜料

15、方式进行评价并选取简单合理的参考依据，这里引入有效度的概念:【有效度】：在零件生产任务一定的条件下，卜料方式集A中各卜料方式出的仃效度k()定义为线性规划模型的最优解x中的第，个分属，WK(aJ) = xJ.(参见公式(2)通过去除有效度较小的卜料方式，问题规模得到缩减，大大增加整数规划的求解的可能 性。经验及计算表明：对广本问题，可求解的整数规划的卜.料方式数不超过100,如果需要 短时间内求解，可选的卜.料方式数应控制在80以内。(鉴NP问题的特点，这些数字不会 随计算平台的差异而显著变化)基于以上讨论，可以得到一种卜料问题的快速求解方法：给定,4,首先通过无整数约束的线性规划计算各卜料方

16、式的有效度，选取有效度较大的若干卜料方式作为整数规划的 下料方式集，记为A,问题可以重新表述为：nun q =六1sJ. Axn(3)W为整数，且WNO, j = L，P卜料方式数p可以根据需要调节，较小的使得求解更快，而较大的可能产生更优 的结果。表3中p、/分别为调整过程中尝试使用的卜料方式数和原材料使用数足，灰色栏表示下料方式数已达卜.限，继续减少将导致问蜃无法计算。Ap表示整数规划结果中对应 卜料方式使用次数为0的个数，这些卜料方式不计入最后的卜料方式数p。表3不同下料方案集下，其有效使用下料方式数及原材料使用量变化趋势卜料方案pqApP(I上述数据表明，按照较优的卜料方案，在不考虑时

17、间约束的情况卜，零件的加工任务可 以在8天内完成，使用799块原材料，采用47种卜料方式，废料总长度为5667mm。(2)有时间约束时模型的建立与求解有时间约束的卜料问题，参见公式(1),其线性规划形式如卜.:SJ.= Z(xy+(x)+(/)1j=l，AAAT ,一10AA0o oA 0 0,xx”人nn-400600,n o为整数，且j=i,，p其中：r为第1、2、3、4天的下料方案，X”为第5、6天的下料方案，X”为随后几 天的卜.料方案，且(n ,/ = 5,7,9,12,15,18,20,25, 28,36.48 n *. = ,0，其它仇，i = 4.11,24,29,32,38.

18、40.46,50 n=0 ,其它对有时间约束的卜料问题，上述求解方法仍然适用。首先对无整数约束问题采用线性 规划求解，根据有效度选择适当的卜料方案，设市新选择后，三个时段刻的卜料方式集分别为整数规划模型可写为:nuns.t.AA，A，-1,-1,0AAn0-1,0、 0Am 0 0 nn-400,-600,n(fy为整数，且c/yzo, j=i,，p计算表明A；41Am的维数远远小4的维数，使得整数规划在较短时间内即可求解。计算结果表明，按照较优的下料方案，在题设时间约束卜.，零件的加工任务可以在8 天内完成，使用799块原材料，采用49种卜.料方式,废料总长度为5987mm,具体下料方 案见

19、附录(1)。二维模型建立及求解(1)无时间约束时模型的建立与求解B题.李非，李廷志,陈微二等奖下料方式集与一维情况不同，针对特定一组零件，即使列举其所仃的可行下料方式也是相当复杂的 问题。犷实上，实际生产中并不需要过户复杂精细的卜料方式，简单实用才是根本。所以基 r本题背景，二维情况卜的卜料方式可以适当简化，既增加方案的实用性，乂降低求解的复 杂性。分析数据可知零件的宽度共分4个规格：50mm、35mm、30mm、20mm,根据零件的 宽度分类，统计各宽度下的零件种类数分别有6、2、20、分种,共43种零件。因此，可以 根据零件的宽度分类限制原材料的切割方法，降低卜料方式的数量。实际生产中，对

20、二维原材料的切割方法，通常遵循以卜原则：首先宽度方向上尽质排 满零件，然后在长度方向上尽显:相邻排布相同宽度的零件。因此，对本题中的零件尺寸，设计实用的二维原材料切割方法为：（1） 将零件沿宽度方向切割为 3000mm X 50mm、3000mm X 35mm、3000mm X30mm、3000min X 20iuin 的标准（T:（2） 在标准件的基础上，同一宽度的标准件上只用来切割为宽度与之相同的零件。根据上述方法首先将3000111111X100111111的原材料沿宽度方向切割为上述4种规格的标 准件，共有 6 种方法:50mmX2、30mll1X3、20mmX5、50mm + 30m

21、m+20mll1、30mniX2 + 20mm X 2、35mm X 2 4- 3Omni,设用了不同切割方法的原材料数量:分别 为%，%，/，/、/，%，总共产生标准件的数最分别为M，NN3，N有:原材料总数9 =k=l0、210;2001000000U 03012.00512例如从上式中可知：N=2q i+q、,这表示，对J; 3000mm X50inm的标准件，采用第 1种方法，每切割一块原材料，产生2个，采用第4种方法，每切割一块原材料产生1个， 因此该规格的标准件的总数为2% +% ,其他情况依此类推。给定名即可计算总共产生的标准件数吊:nn1,N3，n4,此时问题转 化为基广标准件

22、的卜料问题。而根据上述切割原则，3OOOminX5Onun的标准件上只用来切 割宽度为50mm的零件，这时二维卜料问题可简化为一维单一原材料的卜料问题。表4不同规格标准件的分料方式数序号1234标准件50mm35nmi30mm20mm叫622015Pk8281578641353274 X6 y?!”= 7 I W 力- /V V4ZJP1E6乃工人P3E川内工一1 、形式也可改写为:mmxj为整数,Jlx/NO, j = l,，Pk，A = 1,2,3,4 q为整数，且q NO, i = l,6q = q,i-i0 0 0 0 0 0、- 1,一1-1,，一-I,-,-1- 1.一-1,T-1

23、,911,一1-1,-LI0200000030000050002210000O相应的切割方式集记为4, a，a，4，其中4表示为? x 0的矩阵。13xj为整数，且xjNO. j = l, 、Pk，& = 1,2,3,4为整数，且qNO, i = ir.6其中,约束条件个数为47个，规划变吊为828+15+78641十35327+6=114817个，类 似地使用快速求解法,从中选择有效度大法0的下料方式共166种,再进行整数规划,结 果如下:表5无时间约束时二维下料的整数规划结果线性规划原材料使用 527.13下料方式数46596结果/%q、%/4.99043.1310.40351.78116

24、.83整数规划原材料使用538下料方式数 47结果4%/%0043213571172133410021050结果表明，使用538块原材料即可，若以最大生产能力计算，仅须27天即可完成生产 任务。(2)有时间约束时模型的建立与求解与一维情况类似，有时间约束的规划模型见公式(5),其中X、表示前4天的卜.料方案，X、q”表示随后几天的卜料方案，表5无时间约束时二维下料的整数规划结果线性规划原材料使用643. 33卜料方式数*Kqs结果0. 1647. 4700. 3120. 0612. 00qqqZ3. 82070. 7812. 53321. 37154. 83整数规划原材料使用 638卜料方式数

25、结果qs048011912qq”5q)10071132815566mmq = q + q/I1!4心,A-lXX /I 1 2 I 3 4 I 5 6 n w rfH q q q q q q / I/、1 一 / .7 7 .J ./ I 1 2 I 3 4 Xw”.nJ plAR ADePJARpuXKW1 13 9 4 5 16u0, 1 = 1, -,6结果表明，使用565块原材料即可，抬以最大生产能力计算，仅须29天即可完成生产 任务,共使用50种下料方式首先使用6种标准件切割方式下到2414块不同规格的标准件, 再对这些标准件使用50种卜料方式切割即可，具体的卜料方案见附象(2)。七

26、.模型评价求解结果表明，使用较少的分料方式，在充分规划的情况卜，也可以较好地a.约原材料。 对一维单一原材料，计算结果表明，仅使用49种卜料方式，799块原材料就可完成生产 任务，废料长度仅为5987mm,原材料有效使用率高达99.75%。对广二维单一原材料，计 算结果表明，仅组合使用6种标准件切割方式及50种标准件卜料方式，利用565块原材料 就可完成生产任务。本模型在对问题深入分析地基础上，有效地使用背包问题及线性规划、M线性规划等算 法，对实用卜料问题提出简明的方案优化算法，结果接近最优解。模型在算法的稳定性等 方面缺乏理论分析，有效度的定义需要更加严密的证明。B题.李非，李廷志,陈微二

27、等奖参考文献黄崇斌 二维板材优化下料快速搜索仃法计算机辅助程20002卢”清 袁永生卜料向趣数学模型研究运筹与管界19963林晓颖 王远 多II标卜料问题的研究哈尔滨师苑大学自然科学学报20034傅远便线性规划和整数规划成都科技大学出版社19905是就达等数学建模国防科技大学HI版社20036 .M al_eno de Carvalho LP models for bin packing and cutting ctock problems European Journal of OperationalResearch 20027 David L Applegate The Cutting-S

28、tock Approach to Bin Packing: Theory and Experiment; 2003附录附录(1) 一维单一原材料下料方案:下料方式序 号生产零 件总数生产零件个数及编号废料长度 (mm)使用次 附4天使用的卜料方式及其 详细内容13111042125124111112622495233111082253644111108232424854111118232434865111110202324851537511210522394850831111194183194011201141847105112104535454911401121473435123210393

29、11361140815204914411110216183437154211141825381642110318303417521110271837445018511111031821344549195111110231825323552206111120451829344849216121204618324748225111110418323435462351111104202834354924811114093435454849第56天使用的下料方式及 其详细内容25311104548288264111104557798106276123035510310428411110256858710329411110857828710430311105596485314111107597287103324111105617085102335111206638287102VV344111103647088983561111110278285878810210336731303187971033772122036879398