《最优下料问题》由会员分享，可在线阅读，更多相关《最优下料问题（33页珍藏版）》请在金锄头文库上搜索。
1、主讲：黄先玖黄先玖1a实实用下料用下料问题问题研究生建模研究生建模2004年年B题题2al“下料下料问题问题(cutting stock problem)”是把是把相同形状的一些原材料分割加工成若干相同形状的一些原材料分割加工成若干个不同个不同规规格大小的零件的格大小的零件的问题问题，此，此类问类问题题在工程技在工程技术术和工和工业业生生产产中有着重要和中有着重要和广泛的广泛的应应用用. 这这里的里的“实实用下料用下料问题问题”则则是是在某企在某企业业的的实际实际条件限制下的条件限制下的单单一材料一材料的下料的下料问题问题。 3al现现考考虑单虑单一原材料下料一原材料下料问题问题. 设这设这种
2、原材料呈种原材料呈长长方形，方形，长长度度为为L,宽宽度度为为W，现现在需要将一批在需要将一批这这种种长长方形原料分割成方形原料分割成m种种规规格的零件格的零件, 所有零所有零件的厚度均与原材料一致，但件的厚度均与原材料一致，但长长度和度和宽宽度分度分别别为为(l1,w1) ，(lm,wm )，其中，其中wiliL，wiW. (i=1,2,m)。m种零件的需求量分种零件的需求量分别为别为n1,n2,nm。下料下料时时，零件的，零件的边边必必须须分分别别和原材和原材料的料的边边平行。平行。这类问题这类问题在工程上通常在工程上通常简简称称为为二二维维下料下料问题问题。特。特别别当所有零件的当所有零
3、件的宽宽度均与原材度均与原材料相等，即，料相等，即，则问题则问题称称为为一一维维下料下料问题问题。特。特别别当所有零件的当所有零件的宽宽度均与原材料相等，即度均与原材料相等，即wi=W. (i=1,2,m) ，则问题则问题称称为为一一维维下料下料问题问题。 4al一个好的下料方案首先一个好的下料方案首先应该应该使原材料的使原材料的利用率最大，从而减少利用率最大，从而减少损损失，降低成本，失，降低成本，提高提高经济经济效益。其次要求所采用的不同效益。其次要求所采用的不同的下料方式尽可能少，即希望用最少的的下料方式尽可能少，即希望用最少的下料方式来完成任下料方式来完成任务务。因。因为为在生在生产产
4、中中转转换换下料方式需要下料方式需要费费用和用和时间时间，既提高成，既提高成本，又降低效率。此外，每种零件有各本，又降低效率。此外，每种零件有各自的交自的交货时间货时间，每天下料的数量受到企，每天下料的数量受到企业业生生产产能力的限制。因此能力的限制。因此实实用下料用下料问题问题的目的目标标是在生是在生产产能力容能力容许许的条件下，以的条件下，以最少数量的原材料，尽可能按最少数量的原材料，尽可能按时时完成需完成需求任求任务务, 同同时时下料方式数也尽量地小下料方式数也尽量地小.请请你你们为们为某企某企业业考考虑虑下面两个下面两个问题问题。5a问题 ：l1.建立一维单一原材料实用下料问题的数学模
5、型, 并用此模型求解下列问题，制定出在生产能力容许的条件下满足需求的下料方案, 同时求出等额完成任务所需的原材料数，所采用的下料方式数和废料总长度. 单一原材料的长度为 3000mm, 需要完成一项有53种不同长度零件的下料任务. 具体数据见表一，其中 li为需求零件的长度，ni为需求零件的数量. 此外，在每个切割点处由于锯缝所产生的损耗为5mm. 据估计，该企业每天最大下料能力是100块 ，要求在4天内完成的零件标号(i)为: 5,7,9,12,15,18,20,25, 28,36,48; 6al要求不迟于6天完成的零件标号(i)为:4,11,24,29,32,38,40,46,50. (提
6、示：可分层建模。(1).先考虑用材料既少,下料方式又少的模型, 或先仅考虑所用材料最少的模型及增加一种下料方式大致相当于使原材料总损耗增加0.08%情况下的最佳方案。 (2).在解决具体问题时,先制定4天的下料方案,再制定6天的下料方案,最后制定53种零件的下料方案. 这一提示对第2题也部分适用.)7a8al2.建立二建立二维单维单一原材料一原材料实实用下料用下料问题问题的数学模的数学模型型, 并用此模型求解下列并用此模型求解下列问题问题.制定出在企制定出在企业业生生产产能力容能力容许许的条件下的条件下满满足需求的下料方案足需求的下料方案, 同同时时求出等求出等额额完成任完成任务务所需的原材料
7、所需的原材料块块数和所需数和所需下料方式数下料方式数.这这个个问题问题的的单单一原材料的一原材料的长长度度为为 3000mm,宽宽度度为为100mm, 需要完成一需要完成一项项有有43种种不同不同长长度和度和宽宽度零件的下料任度零件的下料任务务. 具体数据具体数据见见表二，其中表二，其中 li,wi,ni分分别为别为需求零件的需求零件的长长度、度、宽宽度和数量度和数量. 切割切割时时的的锯缝锯缝可以是直的也可以是可以是直的也可以是弯的，切割所引起的弯的，切割所引起的锯缝损锯缝损耗忽略不耗忽略不计计.据估据估计计，该该企企业业每天最大下料能力是每天最大下料能力是20块块 要求在要求在4天内天内完
8、成的零件完成的零件标标号号(i)为为: 3,7,9,12,15, 18, 20, 25, 28, 36. 9a10a1、下料下料问题问题(cutting stock problem)”是把相同形状的一些原材料分割加工成若干个不同规格大小的零件的问题；2、二二维维下料下料问题问题-下料时，零件的边必须分别和原材料的边平行 ;3、一一维维下料下料问题问题-所有零件的宽度均与原材料相等 。词汇词汇:11a 本本题题是是有有交交货货时时间间限限制制的的大大规规模模单单一一原原材料下料材料下料问题问题。 l1、目、目标标是既要所用材料最少，也要下料是既要所用材料最少，也要下料方式少。方式少。l2、有交、
9、有交货时间货时间限制限制 分析分析:12a假设l（1）每天下料的数量受到企）每天下料的数量受到企业业生生产产能力的能力的限制，在未完成需求任限制，在未完成需求任务务前，每天下料的前，每天下料的数量等于最大下料能力。数量等于最大下料能力。l（2）每个切割点）每个切割点处处由于由于锯缝锯缝所所产产生的生的损损耗耗不可忽略。不可忽略。l（3）增加一种下料方式大致相当于使原材）增加一种下料方式大致相当于使原材料料总损总损耗增加耗增加0.08%。l（4）每种零件有各自的交）每种零件有各自的交货时间货时间，若某零，若某零件无交件无交货时间货时间，则记该则记该零件交零件交货时间为货时间为无无穷穷大。大。 一
10、一维维下料下料问题问题13a变变量定量定义义（符号） 零件种类总数 第i种下料方式下料的根数 下料方式的种类数 第i种下料方式每根的余料 14a模型的建立15a16a然后代入，推得该线光源的范围为0.03, 0.03m。17a模型的求解对于该问题，因为可能的下料方式将随需要的零件种类数量成指数级增长，所以它是一个NPHard问题。这样对于大多数问题，一般方法无法得到最优结果或无法及时得到最优结果。因此对于大规模的一维下料问题，我们给出了结合动态规划和贪婪算法的新算法，称之为DP贪婪算法。基本思想是：基本思想是：对对模型模型计计算算时时，不用先得到一定数，不用先得到一定数量的下料方案，而是在量的
11、下料方案，而是在选选取下料方案取下料方案时时就以数学就以数学模型中的目模型中的目标标和和约约束条件束条件为为基基础础来来进进行行寻寻找。找。 18a为了保证尽量节省材料，应该尽量将比较大的零件先进行处理，并同时辅以长度小的零件，以保证单个原料的利用率尽量大。因此对每一个零件按照其长度大小依次给定处理顺序的权值。为了保证时间的要求，有要求的零件应该尽量优先处理，对每一个零件按时间紧迫度t依次给定一个处理顺序的权值。两者的结合将作为每一个零件动态规划初始权值。在决定了处理顺序后，首先利用贪婪思想，选取当前尚没有得到的零件集合中权值最大的一个进行处理。 19a调用动态规划方法，得到一种下料方式，此方
12、法里含有当前的零件，在得到此下料方式后，先尽可能按照此方式进行处理，以尽量减少下料方式数，然后再应用贪婪思想。依次类推，直到得到所有的零件。这样我们将得到一种下料方案。如果此方案满足约束要求则停止处理，否则对权值进行调整，如果结果不能满足时间紧迫度的限制，则将优先权值步长直接调节到理论上限，随后通过二分查找的方法进行选择，如果材料利用率过低，则参照以上方法进行调节。而后重复上述过程，直到得到合理结果。 20a1. 局部最优/计算当前单根利用率最大值，并得到一组可行下料方案FOR I = 1 TO 工件总种类数FOR J = 原材料总长度 DOWNTO 0 IF 在J的位置已经有解 FOR K
13、= 第I件工件中未切割的数量 DOWNTO 1 当前长度 = J + 第I件工件的长度*K IF 当前长度位置尚未得到解 THEN 保存当前解 ELSE 对两个解进行比较选取较优解FOR I = 材料长度 DOWNTO 1IF 当前长度有解存在 THEN 返回解算法描述算法描述： 21a2.全局贪婪对所有需要的零件进行处理FOR I = 1 TO 工件种类总数WHILE 如果当前种类还有剩余(按照权值大小依次处理) DO利用上述局部最优处理选取一种至少含有当前种类一根的最优解累加计算结果 更新数据表格3.反复调整调整权值IF 得到全局的解法不合理IF 不能按时完成零件 按规则加大优先权值ELS
14、E 浪费过于大 按规则加大长度权值调用上述全局贪婪算法描述算法描述： 22al二二维维情情况况下下，假假设设在在矩矩形形原原料料切切割割时时采采用用正正交交切切割割，切切割割时时的的锯锯缝缝可可以以是是直直的的也也可可以以是是弯弯的的；不不允允许许零零件件旋旋转转；而而且且切切割割所所引引起起的的锯缝损锯缝损耗忽略不耗忽略不计计。二二维维下料下料问题问题23a24a25a 目前，解有交目前，解有交货时间货时间限制的二限制的二维维下料下料问题问题的常用的常用方法是启方法是启发发式算法，但是式算法，但是这这种方法在大种方法在大规规模的下模的下料料问题问题中并不能将中并不能将问题问题的的规规模降到一
15、个合理的范模降到一个合理的范围围。对对于大于大规规模的二模的二维维下料下料问题问题，本文，本文给给出新的出新的求解方法。先利用降求解方法。先利用降维维思想将二思想将二维维下料下料问题问题化化为为两个一两个一维维下料下料问题问题，对对每一个一每一个一维维下料下料问题问题，再，再使用本文一使用本文一维维下料下料问题问题的的DP贪贪婪算法婪算法进进行行计计算，算，再将两者的再将两者的结结果果结结合起来，得到最合起来，得到最终终的的结结果。果。 模型求解模型求解26a 本文采用的降维思想为：第一步，先考虑长度（或宽度）这一维(以下采用先考虑宽度为例进行说明)，将宽度相同的零件归为一类，对每一类,假设各
16、自存在与该类等宽与原母板等长的母板。这样，每一类零件宽度与各自的母板宽度相等，这就转化为一维下料问题。故可借助一维下料模型的算法解出原母板在长度维上的切割方式。这种方式找到的是长度维上的局部近似最优。第二步，考虑宽度（或长度）这一维。由上一步，我们可以得到每一宽度各自所需的母板根数，可将每一类宽度视为一维切割中一个零件的长度，将每一类所需的根数作为零件的下料任务，原母板的宽度作为现在一维切割原料的长，这样又得到一个一维下料问题，同样借助一维下料 模型的解法来获得局部近似最优解。经过上述两步后，二维下料问题就转化为了两个一维下料问题，在借助一维下料问题的求解算法得到两个局部最优解后，可以通过两者
17、的结合得到最终解。算法的基本思想是： 27a首先比较长的种类和宽的种类，从中选取种类比较少的一个作为第一次降维考虑的基础(在不影响一般性的前提下，以下假设宽度种类较少来进行描述)。按照宽度对所有零件进行分类，然后假设已经有各种宽度的模板足够多，而模板的长和原材料的长相等。这样在接下来的切割过程中将不考虑跨度问题，这样将完全变为一维下料问题。为了得到更优的解应该优先处理宽度最宽的一类，所以依据宽度给定每一类零件一个权值。同时要考虑到交货时间的要求，交货时间比较短的零件应该优先处理，所以依据交货时间给定每一类零件一个权值，两者的结合作为处理顺序的权值。 28a在接下来的处理中，应该选取当前未处理集
18、合中权值最大一类宽度的零件借助一维下料算法进行处理，以得到需要此类宽度模板的数量。为了提高原材料利用率，当一类宽度零件处理完毕后，如果有一些余料，将采用动态规划方法，在利用率高的要求下将其它宽度的零件尽量用这些余料来获得，直到剩下的余料不能再被使用为止。重复这个过程，可以得到每一类宽度的模板需要多少数目，同时得到一种下料方案。 29a接下来，将每一种宽度作为一维下料问题中零件的规格，而每一类宽度需要的数目就是一维下料问题中零件的数量要求，而此次一维下料问题的原材料长度是二维下料问题中原材料的宽度，对于这个一维下料问题借助上文的算法对其进行处理，得到一种下料方案。将第一次得到的一维下料方案和第二
19、次得到的一维下料方案按顺序进行组合，即得到这个问题的下料方案。而第二次一维下料问题所需要的原材料个数就是在二维下料问题中所需要原材料块数。 30a比较所有零件每一维的类别数对所有零件以其中类别数最少的一维为主进行排序WHILE 能取出一个等长（宽）分组(按照权值顺序)取出其中一个等长（宽）分组在该分组内调用一维算法计算一组可行解综合所有解，在另一维上得到一组满足第一问的原始数据调用一维算法得到一维下料方案将两次得到的下料方案进行组合，得到二维下料方案IF 下料方案不能满足时间限制 THEN调整权值重新计算，重新调用算法进行计算 算法描述算法描述：31a于是我们可以得到结结果与果与讨论讨论 我们
20、用TC编写了本文算法的程序，并将给定的实例代入程序进行了计算。对一维模型，经计算使用800根原料可以得到所有所需的零件，只超出最优量3根，废料总长度为7232mm,共使用58种下料方式，原材料的利用率r99.6%。对二维模型，经计算使用451块原料可以得到所有所需的零件，比最优用量超出3块，废料总面积为7232，共使用了66种下料方式，材料利用率r99.2%。图1给出其中一种下料方式 332538393939332538393939图图 1 二二维时给维时给定定实实例的一种下料方式例的一种下料方式32a从原材料的利用率，可以看出原材料得到从原材料的利用率，可以看出原材料得到较为较为充充分的利用，分的利用，这这也也说说明模型和求解算法是十分有效明模型和求解算法是十分有效和理想的。又因和理想的。又因为为算法算法设计时设计时考考虑虑了普遍的情况，了普遍的情况，所以算法在解决大多数所以算法在解决大多数实际实际下料下料问题问题，特，特别别是大是大规规模下料模下料问题时问题时是切是切实实有效的。有效的。 33a
