搜索
B题-李非，李廷志，陈微-二等奖1一．问题背景工厂在实际生产中需要对标准尺寸的原材料进行切割，以满足进一步加工的需要，称为下料问题（CuttingStockProblem）。在工程应用中，下料问题可能以不同的的形式表述，但本质上可简化为相同的数学模型。典型的二维下料问题可表述如下：将若干相同规格的矩形原材料切割成m种规格的矩形零件，下料时零件的边必须分别和原材料的边平行，所有零件的厚度均与原材料一致。特别当所有零件的宽度均与原材料相等，则问题称为一维下料问题。相关数据表明，原材料成本占总生产成本的百分比可以高达45%～60%，而下料方案的优劣直接影响原材料的利用率，进而影响原材料成本。因此需要建立优化的下料方案，使得在生产能力容许的条件下，以最少数量的原材料，尽可能按时完成需求任务,同时下料方式数也尽量地小。二．问题描述现需要建立优化的下料方案，使得在生产能力容许的条件下，以最少数量的原材料，尽可能按时完成需求任务，同时下料方式数也尽量得少。在该目标下要求考虑下面两个问题：1.首先建立一维单一原材料实用下料问题的数学模型，并用此模型求解下列问题，制定出在生产能力容许的条件下满足需求的下料方案,同时求出等额完成任务所需的原材料数，所采用的下料方式数和废料总长度。该企业每天最大下料能力是100块，单一原材料的长度为3000mm，需要完成一项有53种不同长度零件的下料任务。此外，在每个切割点处由于锯缝所产生的损耗为5mm。要求在4天内完成的零件标号(i)为:5,7,9,12,15,18,20,25,28,36,48；要求不迟于6天完成的零件标号(i)为:4,11,24,29,32,38,40,46,50。2.建立二维单一原材料实用下料问题的数学模型，并用此模型求解下列问题。制定出在企业生产能力容许的条件下满足需求的下料方案，同时求出等额完成任务所需的原材料块数和所需下料方式数。单一原材料的长度为3000mm，宽度为100mm，需要完成一项有43种不同长度和宽度零件的下料任务。切割所引起的锯缝损耗忽略不计。该企业每天最大下料能力是20块，要求在4天内完成的零件标号(i)为:3,7,9,12,15,18,20,25,28,36。三．基本假设1.假设工厂每天都以其最大下料能力工作。四．符号说明C：指企业每天最大的下料块数。L：原材料的长度。W：原材料的宽度。iw：第i种零件的宽度，且,1,,iwWim=。B题-李非，李廷志，陈微-二等奖2il：第i种零件的长度，且,1,,iiwlLim=。σ：原材料切割点处由于锯缝所产生的损耗。m：所需切割的零件的种类。in：第i种零件所需的切割的数量，1,,im=。p：总的下料方式数。jia：第j种下料方式中第i种零件的切割数量，1,,,1,,imjp==。jx：第j种下料方式使用的次数，1,,jp=。q：所需原材料的数量，1pjjqx==∑。五．问题分析一个好的下料方案首先应该使原材料的利用率最大，从而减少损失，降低成本，提高经济效益。其次要求所采用的不同的下料方式尽可能少，即希望用最少的下料方式来完成任务。因为在生产中转换下料方式需要费用和时间，既提高成本，又降低效率。此外，每种零件有各自的交货时间，每天下料的数量受到企业生产能力的限制。因此实用下料问题的目标是在生产能力容许的条件下，以最少数量的原材料，尽可能按时完成需求任务，同时下料方式数也尽量得少。本题可以转化为多目标优化问题，利用线性规划和整数规划相关方法求解。下料方式下料方式描述如何将单块原材料切割为若干零件，例如下图表示二维情况下原材料的一种下料方式。图1二维情况下原材料的一种下料方式。就本问题而言，模型仅关心不同下料方式带来的零件生产种类和数量的变化，而忽略其具体布局，也就是说，所切割的零件种类及数目完全相同，仅布局不同的下料方式认为是同B题-李非，李廷志，陈微-二等奖3一种下料方式。下料方式以向量1Tma(a,,a)=表示，其中ia为该种下料方式中第i种零件的切割数量。通常生产需要采取多种不同的下料方式来完成生产任务，完成任务所需的下料方式的集合（简称下料方式集）记为：{}11111pjpmmaaAa,j,,paa⎛⎞⎜⎟===⎜⎟⎜⎟⎝⎠…A的维数为mp×，其中p为下料方式数，m为所需切割的零件的种类。可行的下料方式集A满足原材料长度和宽度的约束。a)在一维单一原材料情况下，可行的下料方式集A应满足：（5mmσ=为切割损耗）111mjiiial(m)L,j,,pσ=−−≤=∑ib)在二维单一原材料情况下，可行的下料方式集A中的每一种下料方式必须是可实现的，即存在满足要求的零件切割布局。下料方案下料方案描述一批原材料如何切割为任务所需的零件，例如共使用多少块原材料，以及各原材料分别采用何种下料方式。由于频繁转换下料方式会带来额外的时间和材料的损耗，工厂在确定一批原材料的下料方案后，会尽量将采用相同下料方式的原材料连续切割，减少转换次数，降低生产成本。在基于单一规格原材料的下料方案优化问题中，不考虑时间因素，同批原材料之间的生产次序可以忽略，认为在给定下料方式集的基础上，下料方案仅由每种下料方式使用的次数决定，记为：1pTx(x,,x)=，jx：第j种下料方式使用的次数，且1,,jp=。可行的下料方案应满足零件个数的约束，设下料方式集为mpA×，则有：mpAxn×≥其中1mn(n,,n)=…，且jx为整数，满足01jx,j,,p≥=。该下料方案使用的原材料数量为：B题-李非，李廷志，陈微-二等奖41pjjqx==∑注意到可行的下料方案中零件个数的约束为不等式约束，与题设等额完成任务似有不符，但事实上，如果以使用的总原材料数量作为规划目标，并将多生产的零件视为废料，两者等价。时间约束假设工厂以最大的生产能力生产，并且每天切割的原材料数量为常数C，此时原问题可以转化为无时间约束的多阶段下料方案优化问题。例如当100C=时，要求四天内完成的零件必须使用前400块原材料生产，六天内完成的零件必须使用前600块原材料生产，等等。进一步，通过把最终下料方案分解为三个阶段的下料方案，可以将对下料方案的时间约束转化为零件个数的约束，简述如下：设前4天的下料方案为x'，在4天内完成的任务为n'；第5、6天的下料方案为x''，在6天内完成的任务为n''；剩余时间的下料方案为x'''，最终完成的任务为n，则有：111400600piippiiiiAx'n'A(x'x'')n''A(x'x''x''')nx'x'x''===≥⎧⎪+≥⎪⎪++≥⎪⎨≤⎪⎪⎪+≤⎪⎩∑∑∑等价转化为：000110040011110600An'x'AAn''x''AAAnx''',,,,,,⎛⎞⎛⎞⎜⎟⎜⎟⎛⎞⎜⎟⎜⎟⎜⎟⎜⎟⎜⎟≥⎜⎟⎜⎟⎜⎟⎜⎟−−−⎝⎠⎜⎟⎜⎟⎜⎟⎜⎟−−−−−⎝⎠⎝⎠（1）最终使用的原材料数量为：B题-李非，李廷志，陈微-二等奖51pjjjjq(x')(x'')(x''')=⎡⎤=++⎣⎦∑下料问题的分解由上分析可知，下料问题可以分解为两个子问题：下料方式集的确定和基于此下料方式集的下料方案的选择。其中下料方式集可以借助搜索算法产生或根据经验选取适当的下料方式集；下料方案的选择寻优可以表达为线性规划或整数规划，使用单纯形法、分支定界法等技巧求解。六．模型的建立与求解一维下料模型的建立及求解（1）无时间约束时模型的建立与求解下料方式集针对特定一组零件，列举满足长度约束的所有下料方式，分别计算其废料长度ε（mm），统计产生相同废料长度ε的下料方式数()Nε，结果如下：0500100015002000250030003500024681012x106下料方式数变化趋势一定废料长度上限下的下料方式数050010001500200025003000350000.511.522.533.544.5x104一定废料长度下的下料方式数废料长度(a)(b)图2：(a)为()kNεε∫随ε的变化趋势，(b)为()Nε随ε的变化趋势废料长度小于一定上限的下料方式数随上限的增加而迅速增大，从下表的数据中也可以B题-李非，李廷志，陈微-二等奖6看出这点。表1()Nε随ε增大而迅速增大ε(mm）05101001000()Nε40882239985435988339550810160465直观地分析可知，可供选取的下料方式p越多，越容易得到用料较省的下料方案，反之，过少的下料方式有可能导致下料方案中对原材料的利用率迅速下降，甚至无可行的下料方案。另一方面，下料方式数p对应下料方案的线性规划模型的变量数，p越大，求解越困难，况且实际生产中每次转换下料方式所增加的成本在一定程度上抵消在原材料上节约的成本。因此，下料方式的选取需要权衡各方面因素，绝非越多越好。当所要切割的零件有53种时，所有可行的下料方式共有10307032种。问题的关键在于如何从中适当选取下料方式，构造下一步的规划求解需要的下料方式集。进一步的计算表明，当下料方式数达到一定数量时，继续增加下料方式对于下料方案的优化没有显著影响，换句话说，当p较大时，下料方案x与p的变化近似无关，这一结论将在下料方案的规划求解中得到验证。综上，分别采取满足0ε=，1ε≤，2ε≤，3ε≤，4ε≤，5ε≤的下料方式集0A、1A、2A、3A、4A、5A，进行下一步的规划求解。线性规划首先不考虑时间约束，建立线性规划模型：1min..0,1,,pjjjqxstAxnxjp==≥≥=∑（2）注意到模型中并未要求jx为整数，求解结果中jx也未必是整数，因此直接线性规划所得到结果并不满足题目要求，但可以在此基础上构造满足整数要求的可行解。设1(,,)pxxx=为满足约束Axn≥的解，构造1(,,)pxxx⎡⎤⎡⎤=⎡⎤⎢⎥⎢⎥⎢⎥为各分量的向上取整值，由A、x中各分量的非负性，可以证明Axn≥⎡⎤⎢⎥。因此，若x为线性规划范畴下的可行解，x⎡⎤⎢⎥即为可行的下料方案，同理，若x为线性规划范畴下的最优解，x⎡⎤⎢⎥即为较优的下料方案，对比同一下料方式集下最优的下料方案，其原材料使用数量之差不大于x中非零分量的个数，例如在下料方式集0A下，线性规划结B题-李非，李廷志，陈微-二等奖7果为801.8q=，在此基础上构造x⎡⎤⎢⎥，计算其原材料使用量850q=，x中分量大于0.01的个数为66，若认为只有对应分量大于一定值的下料方式才被有效使用，则可认为有效使用的下料方式'p为66种。由此可估计在下料方式集0A下，其最优整数规划解的q介于802～850之间，且已找到850q=的可行解。表2不同废料长度下的下料方案下料方案012345T201'302'124'035'087'16p4088280377121407161086200080239985'p666466676864q801.81796.98796.98796.98796.98796.98注：T为相应结果的计算机求解时间。整数规划整数规划本质上属于NP问题，在下料方式集05~AA的规模下，无法直接求解，但事实上并非其中所有的下料方式被使用。线性规划结果表明，在给定下料方式集A下，实际有效使用的下料方式数远小于可选的下料方式数()6640882，可以认为仅使用较少的下料方式也可较好地完成零件的加工任务。为了对不同下料方式进行评价并选取简单合理的参考依据，这里引入有效度的概念：【有效度】：在零件生产任务n一定的条件下，下料方式集A中各下料方式ja的有效度()jaκ定义为线性规划模型的最优解x中的第j个分量，即()jjaxκ=。（参见公式（2））通过去除有效度较小的下料方式，问题规模得到缩减，大大增加整数规划的求解的可能性。经验及计算表明：对于本问题，可求解的整数规划的下料方式数不超过100，如果需要短时间内求解，可选的下料方式数应控制在80以内。（鉴于NP问题的特点，这些数字不会随计算平台的差异而显著变化）基于以上讨论，可以得到一种下料问题的快速求解方法：给定,nA，首先通过无整数约束的线性规划计算各下料方式的有效度，选取有效度较大的若干下料方式作为整数规划的下料方式集，记为'A，问题可