《工厂实际生产的下料问题-李非》由会员分享，可在线阅读，更多相关《工厂实际生产的下料问题-李非（19页珍藏版）》请在金锄头文库上搜索。
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题.李非，李廷志,陈微二等奖#下料问题的分解由上分析可知，卜料问题可以分解为两个子问题：卜料方式集的确定和基卜此卜料方式 集的卜料方案的选择。其中卜料方式集可以借助搜索算法产生或根据经验选取适当的卜料方 式集；卜料
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料方式也可较好地完成零件的加工任务。为了对不同卜料方式进行评价并选取简单合理的参考依据，这里引入有效度的概念:【有效度】：在零件生产任务一定的条件下，卜料方式集A中各卜料方式出的仃效度k()定义为线性规划模型的最优解x中的第，个分属，WK(aJ) = xJ.(参见公式(2)通过去除有效度较小的卜料方式
