1997B：长方体材料截断切割的优化设计(1)【公众号：数模加油站】.pdf

第卷年第期月数学的 实 践与 认 识从,长方体材料截断切割的优化设计姚健钢侯作良罗武安指导教师马斌北京大学,北京编者按本文又引 蛾断切割间题从间题从多方面进行的讨论,包括时的准则,并时的多种解法、笋时各种优化准则的讨论与随机模拟摘 要在工业生产中,常需要采取将物体一分为二的截断切割方式从一块长方体材料中切出一个小长方体,其加工费用取决于水平切割和垂直切割的截面面积,以及调整刀具时的额外费用本文讨论了怎样安扫砌割的次序可使加工费用最少首先我们通过恰当地变换使水平切割和垂直切割具有对称性奋简化了问题 然后通过分析各次切割之间的相互关系,运用局部调整的方法给出并巧妙地证明了无额外费用情形下的最优准则,且讨论了最优解的唯一性对于,般情形,得到了两种算法一、把间题用图论语言描述,将其转化为求有向图中的最短路径,并结合这里的特点对巧二法进行了改进,二、通过缩减需要考虑的切割方式的数目,又引周整刀具的次数分类枚举求解我们将无额外费用时的最优准则与局部最优准则相结合,得出了一般情形下的优化准则,并通过随移模拟进行检验,证实其在概率的意义下具有良好的效果,同时对局部最优准则也作出了合理的评价最后,我们将所得的结论和算法应用于一组实例一、问题的表述略二、符号约定与的处理翠沐廿片我们将长方体材料中构成其底面的两个方向的边分别称为长和宽,而垂直于底面的边称为高如图所示,长方体的长、宽、高均被分成了三段,中间的一段是要切出的小长方体相应边的尺寸,分别用式,表示,而其余各段则为两长方体对应侧面之间的距离,分别用。,。,。,。,。表示下面我们考虑,设待切长方体材料的水平切割与垂直切割的单位面积的费用之比为,现构造一个新的长方体如下保持待切长方体的长、宽不变,将高变为原来的保持水平切割单位面积的费用不变,而垂直切割单位面积的费用扩大倍对于两长方体相应的切割方式,在水平方向上的截面面积和切割费用是相同的,在垂直方向上,新长方体的截面面积和切割费用分别是原来的和,倍,而,。,二,因此对两个长方体计算出的加工费用总是相等的这样我们对原长方体的考虑可通过新长方体来实现,而对新长方体两方向切割的单位面积的费用比是也就是说,可以通过调整长方体的尺寸而将,变为,以增加水平切割与垂直切割的对称性在下文中,除特别说明之外,均认为二三、无额外费用情形下的最优准则所进行的六次切割是与小长方体的各侧面相对应的,即每个切割截面中分别包含小长方体的一个侧面而小长方体的侧面又能用它与原长方体的相应侧面之间的距离来标识,是为方便起见,可将各次切割的位置用字母。,。,。,。,。来代表并且易见当某次切割的位置为二、二取。,。,二,时,获取更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：544457657获取更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：544457657期姚健钢等长方体材料截断切割的优化设计此次切去的长方体中垂直于截面的那条边的长度亦为这样每种切割顺序便对应于。,。、,。,。的一个排列,该抖咧既可看作字母序列,又可看作数值序列,两者的联系将在下文中体现此时。,又由 互知不妨设,故水平切割和垂直切割之间具有完全的对称性下面我们考虑调整相邻两次切割的顺序是否能够降低费用这两次切割进行之前材料的大小是确定的,显然无论两次切割的顺序怎样安排,切后得到的长方体都是相同的,于是仅需比较在两种不同的顺序下,这两次切割的截面面积之和即可如果这相邻两次切割的截面是平行的,那么无论谁先谁后,两次切割的结果都是把被切的长方体分成三片,保留中间含有小长方体的一片,在两个切割位置上的裁面面积是不变的,因此顺序调整与否不影响费用如果这相邻两次切割的截面不平行,由于 目前所具有的对称性,我们不妨设它们的位置为。和。,而在这两次切割之前的长方体中有关线段的长度如图所示以了图图两种顺序下切割所得到的截面中总有一条边的长是,于是比较截面面积就转化为对各截面中另一条边长度的比较如图,在顺序。,。、下,两截面中非的边的长度之和是在顺序。“下,相应的和是,两者之差为二夕,一,刀二好一久于是当。沙时,切割顺序。的费用相对较少而当、,时,交换它们的切割顺序后费用较少综上所述,我们得到结论在切割顺序的数值序列中,如果有相邻两个数,其中前面的数小于等于后面的数,那么交换这两次切割的顺序,加工费用将有所减少或保持不变对于任意一种切割方式所对应的切割顺序数值序列,我们对其进行如下形式的调整只要有相邻的两个数中前面的数小于等于后面的数,便交换它们的顺序由前述结论,交换后所得序列对应切割方式的加工费用将不多于交换前的费用一我们将这种交换过程分阶段地进行下去首先将数列中最大的数与原本排在它前面的数一一交换而使其成为第一项,然后再将次大的数逐次向前调整到第二项,依次类推,最终使得此序列成为单调递减的蜀咧注意到在调整过程中,加工的费用总是减少或不变的,因此该单调递减序列所对应切割方式的加工费用小于等于任何其它切割方式的费用,从而它就是最优解换言之,我们得到在。情形下的优化准则称之为有序切割准则计算出小长方体各钡业 面与原长方体相应侧面之间的距离,“,。,。,。,并将它们按数值从大到小抖网得到一字母序列,据此顺序来逐次选择截面位置的切割方式就是最优的以下我们对最优解的唯一性作些讨论当、,。,。,。,。,。中至少有两个数相等时,将它们排成单调递减数列有多种方式,即相等的那些数之间的先后关系是不确定的不过由前面的讨论知,交换相邻的相等两数后而引起的切割方式的改变对费用没有影响胡大些递减数列所对应的各种切割方式的加工费用都是相等的,它们均为问题的最优解获取更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：544457657获取更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：544457657数学的实践与认识卷当,之,。,。,。这些数互不相同时,只能刹诚唯一的一个单调递减的数列如果还有某种切割方式也是最优的,那么与其对应的数值序列在变为单调递减数列的调整过程中,各次交换时应总保持费用不变,于是由式得这种交换只能为同方向的切割位置之问的交换逆过来看就是说,当单调递减数列中有相邻两项对应同一个方向时,还有其它最优解,例如交换此两项的顺序后所得到的切割方式从而我们知道当,“,。,。,。,。这六个数互不相同,且按数值从大到小扫诚的序列中,相邻两项的字母不同时,最优切割方式是唯一的四、对可能为最优解的切割方式的讨论现在考虑在一种切割方式中,截面平行的两次切割的顺序,不妨讨论截面是与长方体的长方向垂直的切割,用互 中的记号,就是位置为。,和。的切割设,。分别是第,。次切割,且“,“当,、,、时,交换。,更的次序,得到另一种切割方式新、旧切割方式相比,各次切割的方向是相同的,因此调整刀具的额外费用不变易见两方式前,次切割的截面面积也是对应相等的,从而这些步骤的费用也相同如图对第。次切割后新旧切割方式所得到的两个长方体,将其中一个关于截面作反射后得到的长方体与另一个相比,两者就小长方体的相对位置而言是相同的,在宽和高方向上的长度也是相等的,只是新方式得到的长方体在长方向上缩短“,一。这两个长方体此后各次切割的位置也是对应相同的,因此新切割方式的截面面积总不超过旧切割方式的相应面积,故按新切割方式的加工费用小于等于按旧切割方式的加工费用这样我们可以得到如下的论断粼,产臼产一一日气方式式工工工新新方冬冬反反射后后,图有些切割方式对应的数值序列中,同方向上的两个数总是排在前面的较大 或两数相等,取出所有这样的切割方式,其中必定含有最优解下面考虑这些切割方式的总数切割的位置共有六个,而六个元素的全排列数为二,因此不同的切割方式本来共有种二但对于一组已知数据而言,。,与。,。,与。,与。的大小关系是确定的,故它们在切割顺序数值序列中的相对位置是固定的,从而需考虑的切割方式可以缩减为反借抢丁 二种五、一般情形下的算法把一系列切割以后待加工物体所处的状态和这些切瓤中最后一次垂直切割的方向合在一起作为一个顶点如果待加工物体从顶点所代表的状态出发,经过一次切割以后可以变成另一顶点,所代表的状态,就作一条从顶点二到顶点,的有向边,同时把此次切割的加工费用作为这条有向边的长度这样就得到一个有向图,把它称为状态图从而问题转化为在状态图中求一条从表示待加工物体原始状态的顶点 称为起点 到最终状态的顶点称为终点的最短路径以下是幼、提出的寻求最短路径的标号算法【算法,。标号算法设有向图二,刀,们,其中是图所有顶点的集合,召引。,哟。,妊,黝,是图中全部有向边的集合,州二,是有向边 恤,的长度现要搜索一条从起点到终点。的最短路径我们用枷以表示顶点二是否作了标记,用二表示从仅经过已作标记顶点到达汪的最短路径的长度,表示已作标记的最后一个顶点获取更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：544457657获取更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：544457657期姚健钢等长方体材料截断切割的优化设计赋初值叼 川以,肠。浏川、二任认夕刘对于所有满足,习。,。的顶点,夕才,重新定义时如下二,、,、,护当弘二日口寸,认为侧,劝如果所有满足。劝二知卜。的顶点都成立,则不存在从到,的通路,算法终止否则取,二。,其中,满足二,忿任二,夕二、然后令,劣、,“尸如果刀 川亡 二,。,则找到一条从到亡的最短路径,算法终止否则重复进行步骤,直到最后形成一条从到。的最短路径结合此具体问题的特殊性还能对算法作出改进首先根据 互 中的结论,沿同一方向的两次切割的顺序不妨认为是确定的,于是可从状态图中删去一些边其次,如果把为达到与某顶点相应的状态而需要进行的切割次数作为该顶点的层数,那么状态图便具有层次结构于是可以从第零层出发,以层次代替标号,采用按广度搜素的方法,寻找最短路径从而得到下面的算法算法层次搜索算法设有向图代,侧,其中是图。所有顶点的集合,引,、,。引,是图中全部有向边的集合,洲,刃是有向边的二,长度,州,为顶点的层次现要搜索一条从起点到终点的最短路径,显然有识,州,我们用。二表示从仅经过层次比州二小的顶点到达二的最短路径的长度,用表示搜索的层次,。、。,。,代表从起点到顶点,的最短路径中比,的层次低一级的顶点赋初值,、任、,对于所有满足州,卜。,。的顶点,重新定义武,如下又一任乍,夕任刀夕几了夕、上一一才击如果,发生了变化,则令。“。,。,为使达到最小值的顶点二如果。,。小于,重复进行步骤直到。利用、。,。,中记录的信息,就得到一条从,到的最短路径,同时,就是这条路径的长度对于确定的。值,用算法可以很容易地求出一种最优切割方式算法本质上是穷举算法一种改进,比简单地逐一枚举速度要快但具体到这里,问题的规模很小,在兮中我们已经把需考虑的切割方式减少到叨种,因此采用下述的分类枚举法也是可行的,并且它能够给出当。在一定范围内变化时的全部最优解垂直切割的方向有两个,因此至少要调整刀具一次垂直切割共进行四次,故调整刀具的次数至多是一于是额外费用有,二。,。三种可能由对称性易见,在那加种候选的切割方式中,额外费用为。,。,。的各有种,我们把切割费用和额外费用分开考虑,便得到如下的算法算法分类枚举法根据给定的数据。,“,。,。、,。,对种候选的切割方式逐一计算出六次切割的费用之和获取更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：544457657获取更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：544457657数学的实践与认识卷对这些切割方式,按照它们额外费用的值。,。,。分成三类,在各类的种切割方式中,分别将切割费用最少的方式全部选出这三个最小费用分别记为、,。,凉。对。州青况讨论,比较出工。,、。,。中的最小值,与此相对应的切割方式即为最优的按照中最后的分析,通过适当调整来求出全部最优解我们编制了十程序。印和来分别实现算法和算法略六、各种优化准则的讨论当调整刀具的额外费用。井。时,对于适当数据,互中提到的种候选切割方式都有可能成为最优解现已有如下的两种优化准则局部最优准则每次选择一个包括调整刀具费用在内的加工费用最少的待切割面进行切割有序切割准则按照 互中给出的有序切割准则确定切割的次序从 谷 中的分析可以知道,最优的切割次序是从整体来考虑切割和调整刀一具的费用而得到的对于有序切割准则,它忽略了调整刀具的费用,只考虑切割的费用,可以肯定当调整刀具的费用与切割的费用的 比值,不大时,它是非常有效的如果,较大,则由此给出的切割方式就有可能不够理想对于局部最优准则,它只注意了当前的情况,缺乏全局的考虑,因此有一定的局限性但另一方面它同时考虑了切割的费用和调整刀具的费用,所以具有一定的稳定性,不会出现非常差的情形注意到在加工过程中,如果有一个垂直方向的两次切割都已经完成,那么在以后的切割中,不论怎么安排切割次序,调整刀具的费用都不会发生变化,所以这时可以忽略调整刀具的费用,按照有序切割的准则安排后面的切割次序于是我们考虑先按照局部最优准则,再按照有序切割准则安排切割次序,从而得到一种新的准则由于有序切割准则的操作十分方便,并且在某些情况下能够得到非常好的结果,因此不妨再把新准则的结果与有序准则的结果相比较,选择种较好的切割次序综合优化准则先按照局部最优的准则安扫砌割次序,直到有一个垂直方向的两次切割都已经完成,再按照有序切割准则安排剩下的切割次序,并计算出相应的费用按照有序切割准则安排切割次序,并计算相应的费用侧从前两种方案中选择加工费用较少的切割次序进行切割为了给出量上的比较,我们进行了随机模拟一具体算法为产生九个,区间上和一个,月区间上均匀分布的随机数,依次表示待加工长方体的长、宽、高分别被切割成三段的长度和调整刀具的额外费用,其中。是反映调整刀具的额外费用与切割费用比值的参数,并约定单位面积的切割费用是一个单位然后对这三种优化准则各自确定的切割方式,分别计算出它们的费用比实际最优切割方式的费用多花销的百分比,称为浪费率浪费率越接近、说明此准则的优良程度越好,依次令,为和。,各进行。次随机实验,再利用软件工具箱中的数据处理函数,得到各种准则在不同情况下浪费率的均值见表和分布图象略表局局部最优准则则亡二吞吞有有序切割准则则咦咦综综合优化准则则从这些数据和图略象中可以看出当,时,局部最优准则浪费率的均值最大,并月汾布也最分散,效果不好有序切割准则的浪费率均值低于,并且它的分布主要集中在。到。之间,效果还可以综合优化准则的浪费率均值非常低,并且它的分布集中在。以内,效果很好当,二。时,局部最优准则的浪费率均值低于,效果比,二、时有所提高有序切割准则的浪费率的期擎急剧增加,分布也很分散,效果才睦综合优化准则的浪费率分布与,时相比没有显著变化由此可见,随机模拟实验的结果与我们最初的分析是一致的七、实例分析我们考虑这样一组实例。,二,。,二,二,。二。,。,。,。,。二,和。的取值如表所其中各线段长的单位为厘米,。的单位是元,垂直切割的费用为每平方厘米元在下文中,长度的单位均为厘米,面积的单位为平方厘米,费用的单位为元获取更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：544457657获取更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：544457657期姚健钢等长方体材料截断切割的优化设计如图,与,“、。,。,。,。相对应的切割位置分别产生小长方体的左侧面、右侧面、前侧面、后侧面、下底面和上底面,下面我们用这些方位来描述切割的顺序情形,尸二情形二,表情形。,、,亡二情形、对于前三种情形,根据互中对进行的讨论和互 中给出的优化准则,其最优解可直接写出,结果如下情形此时有。,。,。,。,故最优切割方式如表略所示总的截面面积是,即加工费用总计是元情形因为故。,。应调整为。,二,二。二,。、,且每平方厘米的切割费用为二元现在有。,二。,。“最优切割方式如表略 所示总的截面面积是,加工费用为二元情形此时,、,所以。,应调整为,邻,二邻,、,且每平方厘米的切割费用为二元显然有。,。,。,故最优切割方式如表略所示截面面积总计是,加工费用为二。又二元根据 互 中对于最优解唯一性的分析可知,前两种情形下的最优切割方式都有两种,另一种切割方式分别是由交换第三刀和第四刀、,交换第二刀和第三刀的切割位置而得到的而情形。下的最优解是唯一的情形同情形,应先将、,分别调整为之、,刃。,且每平方厘米的切割费用为元运用如中的算法可得出需调整刀具至次时的最小切割费用分别是,元,“二元,、,二幻元由于,因此总有十。山。,于是对。分情况讨论时只需比较,十。和。即可与。相应的切割方式在表略中给出,与,相应的切割方式见下表,并且是唯一的表切切割序号号第一刀刀第二刀刀第三刀刀第四刀刀第五刀刀第六刀刀切切割位置置前前下下后后左左上上右右截截面边长长火。只只截截面面积积总总截面面积积总加工费用用又二二兀兀兀解关于。的方程,十,七。得。习于是我们得到结果当。时,最优切割方式有“前下左后上右”和户饥生下后上右”两种,最小费用是。元当。时,最优切割方式有“前下左后上右”、“前左下后上右”和“前下后左上右,三种,最小费用均为元当。三时,最优切割方式为“前下后左上右”,最小费用是犯。十。元八、模型的评价优点对于尸的情形给出了确切、简明的最优准则而在。郑时,所述的优化准则在概率意义下亦接近于最优通过构造状态图给切割问题以图论描述,随后利用寻求最短路径的算法求解的过程,不仅适用于长方体形状材料的切割,而且可以处理其它各种形状的切割问题,具有一般性当计算的规模增大时,它与单纯的穷举算法相比,能够显著地提高效率分类枚举的算法对求解此间题也具有实用性,在尺寸给定的情况下,一次搜索便能够得出。取各种值时的最优切割方式,采用随机模拟对各优化准则进行的评价是较为全面和合理的缺点对于。的情形,尚没有得到确定的最优准则参考文 献陈森发,网络模型及其优化,东南大学出版社,北京,。年获取更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：544457657获取更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：544457657