截断切割的最忧方案 287 具只两求与 三、变量及符号说明 符号说明 点,至固中真目的国 ao,bo,co:长方体的长、宽、高;ak,b,c:第k次切割后得到的长方体的长、宽、高;f为 第k次切割所需费用 根求, 对长方体的“截断切割”共计有三种方式:部三 水平切割:平行于底面切割;团定的 垂直纵向切割:平行于侧面切割 3) (2 式垂直横向切割:平行于正面切割、出 3.对长方体的六个平面分别进行标号,如图所示: 其中左侧面为1面,右侧面为2面,正面为3面,背面为 4面,底面为5面,顶面为6面 待加工长方体和成品长方体两者左侧面、右侧面、顶面、 底面、正面背面间的距离分别为w,n,t,v,,v, 以某一方式切割出一个长方体需要调整刀具的次数为 n,则有1n≤3.A ),牌算的 不,的到圆 「四、问题分析和模型建立下已0以,小高只理面的完的同 通过分析我们可以知道,对长方体进行第k次切割的费用函数和切割后长方体的长 宽、高,有三种情况:,非个向回词已平冰果5宝 i)第k次切割为水平切割:直垂喜物,平 =mk1b两 a三ak-1 a=a-1 直 bF b-1 或{b=b (1) i)第k次切割为垂直横向切割 if=a 不 2,或{b (2) )第k次切割为垂直纵向切割: 1比劳以不里友 fr= br 与左距 b=b或4-1-n2 道所以,且标数可表示为m立+,其中
288 全国大学生数学建模竞赛优秀论文汇编 第k次切割调正了刀具 d1=0,b= 否则 青己 我们的目标就是找到一种切割顺序,使总切割费用最小 ,,, 五、模型求解 关于上述模型的求解,我们能够建立以下四个定理,优化求解过程,减小运算量, 我们可以表示一个切割顺序,相应于第i次切割的长方体厚度(若为水平切割,该厚度 等于实际切割厚度的1/r) 定理1两次相互平行的切割,比较待切割平面与原长方体的相应表面距离,大的优先 切割(不论这两次平行切割操作是否连续)图的, 例水平切割共有两次,设成品长方体与待加工长方体的底面、顶面相距w,t选择距 离大的优先切割,即 回面,面p 若t1>v2,则两次水平切割操作中,先切割出成品长方体的底面; 若v1<u2,则两次水平切割操作中,先切割出成品长方体的顶面; 若w1=v2,则顺序可任意选择 证若在某种切割顺序(…p…p…)中,两次平行的切割p、P不符合定理1,即p ,则我们交换它们的位置,这不影响p之前和p之后每次切割的切割面积,而对于p与p 之间的每次切割的切割面积只会减小,所以若p:与p不符合定理1则交换与位置后,总的 切割费用不会增加 尽量# 定理2如果水平切割与垂直横向切割是相邻的两个操作,那么三音,高, 若v/>v,则先水平切割,然后再垂直横向切割;一国平为 若/r<v,则先垂直横向切割,再水平切割;d 若u/r=v,则顺序可任意选择, t这里的,用相应的ae1,w2,,v2代入 证设第k,k+1次切割为水平切割与垂直横向切割,当先水平切割,然后再垂直横向 切割,这两次切割的费用为 f+f+1=a4-1b2-1m=a4-1b2-1x+a4-1(c4-1-1) 这里不妨设w为1 当先垂直横向切割,再水平切割,这两次切割的费用为 fi+i+=ar-cHI+ ambers =arIChI ar-I(br-1-vi)r 这里不妨设v为v1 两个费用之差为 fk+f+1=(+/+1) 所以,若v1>v1/r,先垂直横向切割,然后再水平切割,费用减小;其他情形同理可证 定理3如果水平切割与垂直纵向切割是相邻的两个操作,那么 若wr>u,则先水平切割,然后再垂直纵向切割;若v<n,则先垂直纵向切割,再 水平切割,若v/r=a,则顺序可任意选择
截断切割的最优方案 这里的v,a用相应的1,t2,M1,a1代人,证明与定理2相似 解法一按u1,u2,1/r,w2/r,v1,v1非升序排列进行切割 例若v2>c1/r>a2>a1>v>2/r,则先切割背面,再切割底面,再切割右侧 面,…,最后切割顶面,也就是按(v2,t1/r,u2,1,v1,2/r)的方式进行切割、“一“中其 定理4若e=0,则按解法一找到的切割方式是最优的,基工 证设解法一得到的切割方式为(p1,p2,p3,p4,p5,p6)因而≥p2≥p3≥p4≥ p≥p6又设(p1,p2,p3,p4,p5,p6)是一最优切割方式,但与解法一得到的切割方式不 致,则其中必然存在;与1,满足i>,,使得A≤P1,分析以下几种情形 11)p:与p一个相应于水平切割,一个相应于垂直切割,此时由定理2和3知交换它 们的次序不导致费用增加 02)p,与P1相应于两个平行的切割由定理1知交换它们的次序不导致费用增加 3)p2与一个相应于垂直横向,一个相应于垂直纵向切割,此时用与定理2相似的 方法,可证明交换p,与P,的次序不导致费用增加 根据上面的分析,在任何情况下,交换p,与P的次序都不导致费用增加,即还是最优 切割,但交换后p2,与p2的次序符合解法一生成的切割方式 结论1若按解法一找到的切割方式只须调整刀具一次,则解法一找到的切割方式是 最优切割方法 证明因为目标函数 f=h+e> of=>f+n 由定理4知在不考虑刀具调整费用时解法一找到的切割方法使∑得达到最小;此外任何 切割方法需调整刀具至少一次,即n≥1,所以按解法一找到的切割方法如果只须调整刀具 次,则此切割方法是最优的 结论2若按解法一找到的切割方法需调整刀具两次,设为切割方法一,费用为q此 外,所有调整次数为1的切割方法的费用分别为q1,q2,…,,则最优切割方法的费用为:f min(qo,q1,q2,…,q)相应的切割方案为最优切割方案 明注意到用方法一切割的费用为q0=∑+2e,此时∑后达到最小,任意一个 两整刀具三次的切割方法的费用为+3且点不>,所以,最优切料方案只需 在方法一和所有调整次数为1的切割方法中寻找,时的 利用定理1,2,3,我们给出下面的方法枚举所有刀具调整次数为1的切割方案 步骤1不妨设u1>#2,v1>v2,1>w2由定理1,当进行垂直纵向切割时,必先 割与左侧相距u1的面,记切割面代号为1;再切割与右侧相距n2的面,记为2;当进行垂直 向切割时,必先切割与正面距v1的面,记为3;再切割与背面相距v2的面,记为4;当进行 平切割时,必先切割与底面相距w1的面,记代号为5,再切割与顶面相距2的面,记为6 步骤2边由于切割过程中调整刀具次数为1,在两次垂直纵向切割中不能插入垂直横 切割;同样,在两次垂直横向切割中不能插入垂直纵向切割这样,只需枚举以下次序:
全国大学生数学建模竞赛优秀论文汇编 5家1—2-3-4卧,图里发(4) 一 一3-4-1-2- (5) 其中,“—”处可插入5,6. 长算出,因定,“, 步骤3在第2步的基础上插入第5个面,0=本宝 对于(4),插入第5个面共有五种情况:中为一资 注国的中0、51234的中两。(6) 5234脚 中(7) 炎的张由都125340平平的 ((8) 12354 尔积费为(9) 12 由定理3可知,第1,5面顺序可确定,故(6),(7)中只需计算一种,由定理4,第3,5面顺序可 确定,故(8),(9)中只需计算一种,故(4)中插入5简化为3种情况 假设简化为(6),(8),(10)三种 步骤4在第3步的基础上插入第6个面第6个面只能在第5个面之后 对于(6),插第6个面共有五种情况 561234沿 (11) 5 (12) 面得目因 2364 (14) 512346 (15) 同理,由定理2和3可简化为3种情况,鼠一,西具数管不电很h原由 对于(8),插第6个面共有三种情况:后,一。图,一至具两需能 图,的为125364 123346时时方 由定理2,3可简化为2种情况,强铁活回 对于(10),插第6个面只有一种情况: 日h共,123456当一出图 综上所述,故对于(4)只需考虑3+2+1=6种插入5,6的方式,对于(5)同理也只需考虑 6种插入5,6的方式,那么枚举次数总计为12种 结论3若按解法一找到的切割方式需调整刀具3次,设为方法一,费用为q0.所有调 整刀具次数为1的切割方式的费用为q1,q2,…,q=;所有调整刀具次数为2的切割方式的费 用为p1,p2,…,pn则最优切割的费用为:< ,画的f=min(q1,q2,…,qm,p1,p2,…,p)面:图达已 相应的切割方式为最优切割方案证明方法与结论2类似,溶 此时,我们枚举所有调整刀具次数为1的切割方式和所有调整刀具次数为2的切割方 式由结论2中的讨论,知在切割过程中调整刀具次数为1的切割方式只需考虑12种下面 讨论切割过程中调整刀具次数为2的切割方式,不中和录两,问;旧
截断切割的最优方案 291 若切割过程中调整刀具次数为2,则可能先垂直纵向,然后垂直横向,再垂直横向,最后 垂直纵向切割;或者先垂直横向,然后垂直纵向,再垂直纵向,最后垂直横向切割.这样,只需 枚举以下顺序: (16) 或=以以具[ ,的最的面 3-1-2-4 正=(17) 其中,“一”处可插入5,6,插入方式类似调整刀具次数为1的情形 基于上述讨论,下面我们对截断切割问题给出解法二 解法二首先用解法一求解,然后做下面三步之 1)若只调整刀具一次,则最优解已定 2)若调整刀具两次,则从该切割方式与所有只调整一次的切割方式中找最优解 3)若调整刀具三次,则从该切割方式与所有只调整刀具一次和两次的切割方式中找最 优解 0,由前面结论1至3讨论,易知解法二至多需比较25种不同切割方式, (二)模型二的建立与解法(略) 民 六、问题回答三 0:1,,C (一)不同的切割方式的总数: 量图, 在假设条件下,切割方式总数为P6=6!=720种 若考虑要求最后切割底面,则切割方式为P3=5!=120种若考虑到待加工长方体和 成品长方体可能共面,则切割方式总数为P3=3!=6(三个面共面);P4=4!=24(二个面 共面);P=5!=120(一个面共面)等 若每次选择一个加工费用最少的待切割面进行切割,假设单位面积的切割费用为 1,即简化为寻找面积最小的待割面:Ak-min(ak=1b-1r,a4-1k-1,b4-1ck-1),将找到的面 切割,得到下一个待加工长方体,用同样规则进行切割根据这规则我们给出了程序(附录二 略).用这个程序我们随机选取80种情况进行求解并对比,同时与模型所得最优解(附录略) 进行了比较 优点:规则考虑到了优化的思想,每次切割找最佳割面,通过与最优解比较,有些值就是 最优解,例如a0=10,b0=14.5,c0=19,a6=3,b6=2,c6=4,a1=6,v1=7,v1=9, =1.5时,得到minf=540.5,与最优解一致,次序同为(3,5,1,4,6,2) 缺点:规则不是最优的,这是因为 min( a 而忽略了厚度的影响和换刀具的费用ne,因此造成了一定的小差别,通过对比80组数据的 比较统计(以最优费用为分母),得平均比值p=1.0266. 个至淑只 不是最优解的情况举例:a0=20,b0=15,c0=20,a6=4,b6=5,c6=6,a1=6,v1 =7,1=8,e=1,r=1.5时,按此规则得到min=797,而最优解为783,此时比值p 1.0189 (三)对c=0的情形有简明的优化准则,见模型中的定理4,量,验 (四)实例数据出正中溶