最优切割次序模型 清华大学陈俊倪江李、凌的照同 出,指导教师包维柱已面的料进工 编者按本文对截断切割问题先得到伸缩变换性质与交换引理,再得到=0时的优化准 则,并用于对c>0的情况进行分析、本文结构清晰,使所讨论的问题逐步深化 摘要本文研究了截断切割的最优切割次序模型.利用简单的伸缩变换,我们将r≠1 的情况统一到r=1的情况;我们讨论了切割方式的一些性质,如描述互换相邻切割对费用的 影响的交换引理,同时在此基础上经严格证明给出了=0时的一种十分简明的优化准则:每 次选择切去长度最长的切割;在e>0的情况下,利用我们给出的引理及准则,我们将需考虑 的不同切割方式数由最初的90种减少到不到20种.我们讨论了所建立模型的优缺点,同时也 对另一种“加工费用最少者优先”的准则作了简单评估 一、问题重述(略 单语面式e单为同 题分析 如图1建立直角坐标系,O为坐标原点所谓用截断切割的方法从待加工长方体中加 工 出一个成品长方体,就是以后者的6个面为切割平面各切一刀,使切割后形成的长方体 恰为成品长方体,每次切割使得待加工长方体一分为二,同时移去(舍弃)不含成品长方体 的那一部分面两氧雪济 图1待加工长方体与成品长方体示资,, ) 如果在每次切割之后都将原本应移去的那一部分保留在原处,则很容易就可以知道, 切割的总面积总是等于待加工长方体的表面积2(ab+bc+c),总费用也总是一固定值 (先考虑c=0的情况),而不管6面的加工次序如何.正是由于切割后移去了“无用”的露 分,使得其后的切割面积和费用有可能比不移去的情况少,也使得切割总面积和总费用不 再与加工次序无关,而当e≠0时,切割费用还和垂直换刀的次数有关;这同样表明了切 期费用与切割方式(加工次序)有关。我们的任务,就是找到一种方法来合理地安排各面的 加工次序,使得总费用最小
278: 全国大学生数学建模竞赛优秀论文汇编 由于6个面的加工次序的排列是一有限数(720),因此费用最小的切割方式(或称最优 切割方式)是存在的.而且由于文中将说到的原因,费用最小的切割方式不一定是唯一的 三、问题的假设 1.待加工长方体的表面与成品长方体的表面不相接触,也即切割次数至少为6 2.每次截断切割的切割平面均为成品长方体的某一表面所在的平面,这样保证了没 有多余的切割,也即切割次数一定为6 3.水平切割指的是垂直于长方体的高(见图1)所做的切割;垂直切割指的是垂直于长 方体的长或宽所做的切割,其切割平面与长方体的高平行 4.我们认为加工部门有一种方法来固定加工过程中的长方体,而不需考虑切除长方体 底面后的固定问题 5.由后面所给的定理一的推论可知,任一r≠1的切割模型的求解,可以通过伸缩变换 等价地转换为一个r=1的切割模型的求解因此,除非另有说明,我们假定模型的r=1; 6.在r=1的前提下,我们认为水平切割单位面积费用与垂直切割单位面积费用均为 每平方厘米1元,同时认为费用单位为元、面积单位为cm2.这样,在文中将每次切割的面 积与切割的费用(不包括换刀费用)等同对待 另外,文中用“长方体”表示待加工长方体与正在加工过程中的长方体 四、模型建立及符号说明 建模中所用的符号及一些术语说明如下:个 a,b,c:待加工长方体的长、宽、高 a1(a2,b1,b2,c1,c2):待加工长方体和成品长方体两者的左侧面(右侧面、正面、背 面、底面、顶面)之间的距离,也称为切去长度 a1切割:沿着成品长方体的左侧面所做的使得长方体的长减少a1的切割.切割只表明 切割的方位而和长方体的切割历史无关 a2,b1,b2,c1,c2切割:含义类同a1切割 a(b,c)类切割:a1(b1,c1)切割与a2(b2,c2)切割统称为a(b,c)类切割 同类切割,异类切割:同属于a类切割或b类切割或c类切割的两种切割为同类切割 否则为异类切割 =x12x3x;x3:F表示一种切割方式,x1x2x3x4x5x6为a1,a2 切割的一个排列,x表示第i次切割.当补斗 x=xy:表示x与x(在各自的模型中)同为a1(或a2,b1,b2,c1,c2)切割 f:x;的切割费用(不含换刀费用).生 f(F,e);切割方式r的加工费用,当e=0,时简记为f(r).它是切割费用与换刀 费用的总和,语由为质能 l:x的切去长度 我们在文中还将不加说明地使用这些符号的一些变形(如带撇、带下标等),它们的含义 通过上下文可以容易地确定.例如,我们认为r=x'1x2x'3x'4x'sx6是记号r= x1x2x3x4x5x6的带撇的变形,且l;即为x1的切去长度
最优切割次序模型坐 279 切割模型为M={a,a1,a2,b,b1,b2,c,c1,c2,e,rl,是一个11元的有序序列 模型的求解就是要针对M得到一个切割方式rmm.使得f(rmn,e)=minf(r,e) 五、模型求解 1.伸缩变换 水平切割与垂直切割在费用上有r倍的差别,这是由实际的工艺决定的.但这样却使 切割的模型复杂化了其实,有如下定理: 定理1设某一r≠1的切割模型M={a,a1,a2,b,b1,h2,c,c1,c2,e,r},其 任一切割方式为=x1x2x3x4x5x6;M经如下伸缩变换 a'=ar,a'i=aI, a2=anr b c/r,c=G/Vr, c2=c2// (1) 后得到另一r=1的模型M'={a,a'1,a'2,b,b1,b2,c,c1,c2,e L,r 在M中的对应切割方式为r=x1x2x3x4x'5x6,则有f(r,e)=f(r,c).r与 r互为对应切割方式指的是x=xi,=1,…,6.对应切割方式的存在性与唯一性十 分显然, 证先考虑第一次切割.由变换(1)及x1与x1的对应性,同时考虑到两个模型的r 与r不同,则x1的切割费用f与x1的费用f1有如下关系 'c=bNr (a类切割) =a(b类切割)}=f rab′=aF·bv=mab(c类切割) 由于r是r在模型M中的对应切割方式,由假设2可知模型M与M'在x1与x1切割之 后分别剩余的长方体的尺寸及成品长方体的位置,仍满足(1)的比例关系,因此以上的讨 论适用于所有的六次切割,也即有f1=f(i=1,…,6).另外,显然r和P两个解的垂 直换刀次数是一样的 推论对任一r≠1的切割模型M,存在一个r=1的模型M,使得M的任一最 优切割方式在M中的对应切割方式是M的最优切割方式;反过来,M的任一最优切割方 式在M中的对应切割方式也是M的最优切割方式也即模型M的求解可转化为模型M′ 证取M′为M经伸缩变换后所得的r=1的模型.设r是M的任一最优切割方 式,其在M中的对应切割方式为r.若不是M的最优切割方式,则必存在T1使得 f(1,e)<f(r,e),从而由定理一,n1在M中的对应切割方式r1满足f(r1,e)= f(r1,e)<f(r,e)=f(r,e).这与假设r是M的最优切割方式矛盾.故r也是M 的最优切割方式.同理可证反过来的情形, 由定理一的推论可知,对r≠1的切割模型的求解,可以通过伸缩变换等价地转换为 求解一r=1的切割模型.因此,除非另有说明,在以后的讨论中我们默认模型的r=1. ,2.不考虑刀具调整费用(c=0)文)班
全国大学生数学建模竞赛优秀论文汇编 本节讨论当e=0时模型的求解,此时,切割方式r的加工费用为 )=文 引理1(交换引理)设切割方式r=x1x2x3x4x5x6,T经交换相邻的两次切割 +1后得到另一种切割方式,则有: (1)若x2,x;+1为同类切割,则f(T)=f(r); (2)若x,x+1为异类切割,则 4>l1=f(P)≤f(r) 4如f(P=f(r) 4≤l1f(r)>f(r) 证由费用计算公式(2) f(r)=∑A+f+f…1+∑f, (F)∑/4+f十f+∑f 显然,由r的形式知当1≤k≤i=1时,f=;而且,因为r与r的不同仅在于它 们互换了第i,i+1次切割的顺序,所以采用r的前i+1次切割后得到的长方体与采用r 的前i+1次切割后得到的长方体是相同的,又i+2≤k≤6时xk=x4,所以i+2≤ k≤6时∫=f.这样 f(r)=f(r)=f1+f+1-f,-fa1 第i-1次切割后r得到的长方体的长、宽、高与r得到的长方体的长、宽、高是相同的,设 它们分别为a,b′,c 若x,x+1为同类切割不失一般性,设其为a1,a2切割,则后bc,f+1=b;f 从而f(P=f(). 的,置习品是七只 若x,x+1为异类切割不失一般性,设其为a1,b1切割,则1三2,1:tb,f 从而f(P)-f() b1)c=(a1)c,考虑到c>0,则有 的 a1= b/(r)=f(r) a1<b1曰f(F)>f(r),的 由x,x的一般性,我们可得所求结论曰 1>4=f(P)< ,= li+f(r)=f(r L, <Ii+f(r)>f(r). 定义(正规切割方式)若切割方式r=x1x2x3x4x5x满足当x,x为同类 时≥1#1,Vi 5,则称为正规切割方式,当 定义(等价正规切割方式)根据引理1(交换引理),交换任一切割方式P中相
最优切割次序模型 类切割,加工费用不变,所以我们可以把r化为加工费用相同的正规切割方式rr即称 为r的等价正规切割方式 定义(有序切割方式)若切割方式r满足l1≥l1+1, i=1,…,5,则称r为有序切 割方式.有序切割方式一定是正规切割方式 引理2(最少费用引理)若正规切割方式r=x1x2x3x4x5x6不是有序切割方式, 则r不是费用最少的 证T是正规切割方式,但不是有序切割方式,因此彐i,使得l1<l+1且x,x,1为 异类切割,再由交换引理知存在加工费用更少的切割方式 引理3(有序切割引理)若切割方式和r均为模型M的有序切割方式,则f(r) f(r) 证首先,易知l1=1,Vi=1,…,6.若x;=x1,Vi=1,…,6,则结论显然成立 否则,设k为使x1≠x;成立的最小的讠,即 设j使xy=x1,由于当j<h时xx≠x,j=k时x=x≠x,故j>k,这 时l,=l=l4则由厂是有序切割方式可知 现对r进行一系列相邻交换,使x’在厂中的位置逐次前移,直到其与x交换,这 样得到一个新的有序切割方式r” T=x1…xk-1xxk…x,-1x+1…x6 由引理1,f(r)=f(r),但r与r在序列前部连续相同的切割的数目至少比r与P相 同的数目(即k)大,以r代替r重复上述过程,则经过不超过6次这样的过程,必可得到 r=r,所以 f(r)=f(r)=f(r) 定理2切割方式P=x1x2x3x4x5x6为最少费用切割方式口其等价正规切割方式 =x1x2x3x4x5x6为有序切割方式 证(1)充分性()的证明:采用反证法 设P不是最少费用切割方式,即存在r=x1x2x3x4x5x6,其加工费用最少,且 f(r)<f(r).不妨设r为正规切割方式(否则可考虑r的等价正规切割方式) 若r是有序切割方式,由引理3,f(r)=f(r),与所设f(r)<f(r)及f(r)= f(r)(等价正规切割方式的定义)矛盾.若r不是有序切割方式,则由引理2知r的加工 费用不是最少的,亦矛盾 由此知P是最少费用切割方式 (2)必要性(→)的证明:即为引理2的逆否命题 由定理2可知有序切割序列是最优切割序列,因此在实际的切割操作中,只需考虑有 序切割序列这一种最简单的情形即可.这也就是我们所给出的优化准则,即每次挑选使得 切去长度最长的切割面来切割.这样得到的切割序列必定是有序切割序列,从而也就必是 最优切割序列