实用下料问题

课程设计论文学院:理学院专业:课程名称数学建模课程设计题目实用下料问题队号学生姓名学号0学生姓名学号学生姓名学号学生姓名学号指导教师2012年6月实用下料问题摘要本文是为针对如何下料问题进行研究的，通过对于两个问题的分析，进而建立两个模型：针对第一个问题建立模型一，设计MATLAB程序即贪婪算法。针对第二个问题建立模型二，首先将二维下料问题转化为一维下料问题，进而引入规划模型，同时设计MATLAB程序，并对程序运行结果进行相应的分析。问题一：为了解决一维下料问题，根据一维下料问题的特点以及要求，建立起由约束条件组合而成的规划模型。利用取得每个决策中的最优值，较快的获得问题的最优解：前6天下料方案整和为一个方案比制定4天，6天方案更优，且前6天需用原材料根数为268，利用率为99.21%，3天完成；剩余下料方案为需用原材料根数为538，利用率为98.92%，6天完成。（详见表6-1和附录表6-4、表6-5）。问题二：基于零件长、宽两个方向上的限制的情况后，根据问题2中待加工的零件的宽只集中在50mm，30mm，35mm，20mm四种规格上，将二维问题转化为一维问题，分别用一维下料问题的方法寻求四种宽度条材在一维情况下的最优方案。在这一过程中，可根据一维下料问题求解的方法，建立模型二，解多目标整数规划，再进行最优组合，可以得到两个阶段所使用的条材。（详见表6-2）。关键词：MATLAB，最优化，下料目录摘要Ⅰ主要符号表III1　引言—问题重述与分析11.1　问题重述11.2　问题分析22　模型假设32.1　模型一的假设32.2　模型二的假设33　模型的建立33.1模型一的建立33.2模型二的建立74模型求解85结果分析85.1模型一的结果分析85.2模型二的结果分析96模型的优点与推广10附录A需求材料的数据11附录B6天下料的方案13附录C剩余下料方案15附录DMATLAB程序21参考文献27主要符号表模型一：符号说明等额完成任务所需的原材料数原材料个数零件标号在第个原材料上切割的第个零件标号的零件数量规格种数需求零件长度单一原材料长度需求零件数量需下料的全部零件总长度下料方式数废料的总长度模型二：符号说明第i号零件的宽度第i号零件的需求量需求零件长度全部可行的下料方式数表示第i号零件在第j种方式下切得数表示第j种下料方式耗材的块数表示第i号零件在第j种下料方式下切得的第k块零件的中心的横坐标表示第i号零件在第j种下料方式下切得的第k块零件的中心的纵坐标1　引言—问题重述与分析1．1问题的重述“下料问题(cuttingstockproblem)”是把相同形状的一些原材料分割加工成若干个不同规格大小的零件的问题，此类问题在工程技术和工业生产中有着重要和广泛的应用.这里的“实用下料问题”则是在某企业的实际条件限制下的单一材料的下料问题。现考虑单一原材料下料问题.设这种原材料呈长方形，长度为,宽度为，现在需要将一批这种长方形原料分割成种规格的零件,所有零件的厚度均与原材料一致，但长度和宽度分别为，其中wi＜.种零件的需求量分别为.下料时，零件的边必须分别和原材料的边平行。这类问题在工程上通常简称为二维下料问题。特别当所有零件的宽度均与原材料相等，即，则问题称为一维下料问题。一个好的下料方案首先应该使原材料的利用率最大，从而减少损失，降低成本，提高经济效益。其次要求所采用的不同的下料方式尽可能少，即希望用最少的下料方式来完成任务。因为在生产中转换下料方式需要费用和时间，既提高成本，又降低效率。此外，每种零件有各自的交货时间，每天下料的数量受到企业生产能力的限制。因此实用下料问题的目标是在生产能力容许的条件下，以最少数量的原材料，尽可能按时完成需求任务,同时下料方式数也尽量地小.请你们为某企业考虑下面两个问题。1.建立一维单一原材料实用下料问题的数学模型,并用此模型求解下列问题，制定出在生产能力容许的条件下满足需求的下料方案,同时求出等额完成任务所需的原材料数，所采用的下料方式数和废料总长度.单一原材料的长度为3000mm,需要完成一项有53种不同长度零件的下料任务.具体数据见表一，其中为需求零件的长度，为需求零件的数量.此外，在每个切割点处由于锯缝所产生的损耗为5mm.据估计，该企业每天最大下料能力是100块，要求在4天内完成的零件标号()为:5,7,9,12,15,18,20,25,28,36,48;要求不迟于6天完成的零件标号()为:4,11,24,29,32,38,40,46,50.(提示：可分层建模。(1).先考虑用材料既少,下料方式又少的模型,或先仅考虑所用材料最少的模型及增加一种下料方式大致相当于使原材料总损耗增加0.08%情况下的最佳方案。(2).在解决具体问题时,先制定4天的下料方案,再制定6天的下料方案,最后制定53种零件的下料方案。（这一提示对第2题也部分适用。)2.建立二维单一原材料实用下料问题的数学模型,并用此模型求解下列问题.制定出在企业生产能力容许的条件下满足需求的下料方案,同时求出等额完成任务所需的原材料块数和所需下料方式数.这个问题的单一原材料的长度为3000mm,宽度为100mm,需要完成一项有43种不同长度和宽度零件的下料任务.具体数据见表二，其中分别为需求零件的长度、宽度和数量.切割时的锯缝可以是直的也可以是弯的，切割所引起的锯缝损耗忽略不计.据估计，该企业每天最大下料能力是20块要求在4天内完成的零件标号()为:3,7,9,12,15,18,20,25,28,36。1．2问题的分析这是一个典型的多目标决策优化问题.首先,一个好的下料方案应该使原材料的利用率最大,从而减少损失,降低成本,提高经济效益.其次,要求所采用的不同下料方式尽可能少,即希望用最少的下料方式来完成任务.因为在生产中转换下料方式需要费用和时间,既提高成本,又降低效率.此外,由题意知每种零件有各自的交货时间,每天下料的数量又受到企业生产能力的限制.因此实用下料问题的目标是在生产能力容许的条件下,以最少数量的原材料,尽可能按时完成需求任务,同时下料方式数也尽量地少.为顺利解决该下料问题,根据该问题的特点,我们先从最基本的单目标决策问题入手,以材料损耗最少为目标,通过不同的数学原理建立多个单目标决策的最优化模型,得出最初的结果,并加以比较分析.然后逐步增加其约束条件——最小的下料方式数,并根据该约束条件进一步完善我们的最优化模型,得到损耗最少,下料方式数又小的结果.接下来检验在所得下料方式的排列中,是否存在可以满足时间条件限制的排列方式.若存在,则该结果即为最优解;若不存在,则这个结果就不符合题意,必须重新构建多目标决策的最优化模型,在新模型中以客户时间需求为第一目标,材料损耗最少,下料方式最少为第二目标.因此,在下料时就应该优先生产那些有时间限制要求的零件,并且求出在需求的时间段内下料方式和损耗的最优结果,紧接着再求出剩余板材下料方式和损耗的最优结果,从而最终得出既满足时间条件限制又满足损耗少、下料方式数小的最优结果。2　模型假设2．1问题一的假设1.每切得一个规格的零件需要的原材料,且切割损耗不计入余料。2.企业每天的最大下料能力为100块。3.切割时零件的长和宽要与原材料的长或宽平行。4.所需零件厚度和宽度均与原材料相等。5.考虑下料方式的数量对总损耗的影响，下料方式越少则原材料总损耗越小。2．2问题二的假设1.企业每天的最大下料量为20块。2.切割时的锯缝可以是直的也可以是弯的。3．所需的零件厚度均与原材料相等。4.切割所引起的锯缝的损耗忽略不计。3　模型的建立3．1模型一的建立1）．约束条件如题，设原材料呈长方形，长度为L，现在需要将一批这种长方形原料分割成m种规格的零件,所有零件的厚度和宽度均与原材料一致，第i种规格的零件的长度为，需求量为个。共耗用个原材料，且在第k个原材料上切割的第i个零件标号的零件数量为，则有：（1）原材料规格与锯缝损耗约束条件为：,（2）需求量约束条件为：以及对的非负整数要求。（3）下料方式约束条件为：（4）下料能力约束条件为：每天的最大下料能力有：2)．目标函数的建立目标函数的建立是为求的的最小值，因此建立如下：=其中，={0,1,2,---}为非负整数的集合。3）求得所需原材料的最小值设，表示需下料的全部零件总长度。进而定义：，为整数=,其他则所需原材料的最小值为，若由目标函数求得的结果，则计算结果有误，则需要修正程序的算法，或是重新建立模型。由上式求得的最小值可避免犯一些明显的错误，并且可对程序进行验证。4）结果表示：（1）等额完成任务所需的原材料数：（2）下料方式数：（3）废料总长度：（4）下料方案：从上述模型可得出，下料方案为满足模型约束条件的最优解。3.1.1算法实现——随机决策下的贪婪算法步骤1：对于给定需要完成的产品，长度和需求量分别为L和n，构造一个n行1列矩阵NL，形如：其中表示第1种材料的第i个排列，中的表示第一种材料的总需求量。步骤2：产生100个随机数组，每个随机数组包含20个数，随机数组的取值范围为,其中表示第i个数组里面的第j个随机数的值。将每一组数组的值对应到步骤1构造的矩阵中的第个数中,结果是产生100组策略，每组策略有20个值。步骤:3：将产生的步骤2产生的100组策略装进100个队列中，对每个队列进行分流操作,从第1组的第一个值开始累加到第一组的第20个数，累加过程中如果累加值超出3000的，该值不被采用，否则该值被分流进盒子，如果循环操作至第100组随机值，最后结果将产生出100组随机策略组合，每组的累加值均满足小于3000，即：步骤4：对步骤3产生的100种满足条件的随机组合采取择优选择，即选择，此为一次贪心决策结果，将构成的各长度值从矩阵中去掉，即将其值变为0.步骤5:判断矩阵中的非零值个数，当时，即表示中的每个值都已经被选出，否则继续步骤2～步骤5。由以上步骤1～步骤5结束后易知最终结果为各类型需求量均能被满足，此为最终的解。在实际操作中可能步骤2中的100个随机数组中有些数组的20个随机值出现雷同数值，亦即，此时如果所对应的为，那么该随机决策将是一种伪决策，此行为将导致矩阵中的某一值被累加了多次，为此，可以将步骤5中的判断函数:改为即中剩下未被选择时即跳出，然后对剩下的进行重组合，即将中等于0的数剔除，非零数值重新组合成新的,再继续运行步骤1～步骤5即可尽量避免当时所对应的为的情况。至此，利用Matlab编程可求出满足题目要求的方案，从方案中可以检测出时所对应的为的情况仅为四种，对四种方案人为处理后即可得到最终结果。易求出该算法的时间复杂度仅为，其中表示总需求量，表示随机决策的个数（本文中取100），表示每个随机决策中的队列长度（本文中取20）。此算法较之遗传算法等的优点是减少时间复杂度，可以在较短时间内求出满意解，而空间复杂度基本相同，缺点是下料方案是随机性的，结果中有些下料方案可能只被执行数次。3．1模型二的建立3.2.1问题二模型的初步分析与建立问题二中的二维下料问题，由于零件长、宽两个方向上的限制，相比于一维下料问题复杂得多。这一问题还要求集合D中的零件必须在第一阶段(前四天)完成，而企业每天的下料能力是20块。基于这一条件，本文模型的目标是尽可能节省原材料，并采用尽量少的下料方式。其中：全部可行下料方式数：表示第号零件在第种方式下切得的个数；：表示第种下料方式耗材块数；D={零件|=3,7，9,12,15,18,20,25,28,36}，即前4天须完成的零件集合：第号零件的长、宽、加工个数：第号零件在第中下料方式下切得第块零件中心的横坐标、纵坐标。3.2.2模型的进一步分析根据问题二的特点，待加工的零件的宽只集中在50mm，30mm，35mm，20mm四种规格上，可将二维问题转化为一维问题，对四种宽度且长3000mm的条材，分别用一维下料问题的方法寻求四种宽度条材在一维情况下的最优方案。根据一维下料问题求解的方法，解多目标整数规划，可以得到两个阶段所使用的条材。然后，将上述四种宽度的条材进行搭配，按仅有的无损失的方式列出。并进