最优切割次序模型 清华大学陈俊倪江李、凌的照同 出,指导教师包维柱已面的料进工 编者按本文对截断切割问题先得到伸缩变换性质与交换引理,再得到=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) a1f(r),的 由x,x的一般性,我们可得所求结论曰 1>4=f(P)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,使得l1k,这 时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可知有序切割序列是最优切割序列,因此在实际的切割操作中,只需考虑有 序切割序列这一种最简单的情形即可.这也就是我们所给出的优化准则,即每次挑选使得 切去长度最长的切割面来切割.这样得到的切割序列必定是有序切割序列,从而也就必是 最优切割序列
282 全国大学生数学建模竞赛优秀论文汇编 3.考虑刀具调整费用(e>0) A.加工费用曲线 )筑 f(rr,e) fcr,e)=ke+f(r) ef(rse fcr f(r,e 图2加工费用曲线 联 比4, 对于切割方式F,设它的换刀次数为k(1≤k≤3),则有加工费用 从式(3)中可以看出,如果能够得到切割方式P在e=0时的加工费用f(r),则根据r的 垂直换刀次数k就可以计算出任意c值下的加工费用根据式(3)能画出f~c加工费用曲 线,如图2(a),它是一条斜率为k,纵轴截距为f(r)的射线.给定e值,即可由曲线上的 相应点的纵坐标得到该e值下的加工费用 根据上面的讨论,我们可以想象,若是在同一坐标系中画出模型M的所有切割方式的 费用曲线,则对于任意的e值,从图中就能找到该e值下所有曲线的最低点,即为图2(b) 中的点S,S的纵坐标即为该e值下的最小费用,而S所在的曲线即代表了相应的最优切割 方式 考虑到换刀次数k相同的所有切割方式的费用曲线是一组平行射线,因而在寻求最优 解时只需考虑它们中纵轴截距f(P)最小的那条射线如果记为那条射线所对应的切割 方式,则我们在求最优解时就只需考虑切割方式n1,2,r3,而在图上就只需考虑r r2,T3对应的三条射线,而不同e值下的最小费用fmn(e)即为 fmn(e)=minf(r1,e),(r2,e),f(3,e)],3(1) 反映在图形上,即为由三条f~c曲线f(r1,e),f(n2,e),f(3,e)的最靠近e轴的片 断所形成的“包络线”,称为最小费用曲线,其典型形状见图2(b)中的折线PQRK.而三个 截距f(r1),f(r2),f(r3)的相对位置则决定了最小费用曲线是否有突变点(转折点),及 突变点的个数.从图中可以形象地看出,随着e的增大,最优解逐渐经过每个突变点(在突 变点存在的情况下);在两个突变点之间,最优解是固定的,最小费用曲线的斜率也是固定 的;而每经过一个突变点,最小费用曲线的斜率减小,最优解也发生改变突变点处的最优 解,则包括了其左右两侧曲线对应的切割方式.“比 B.c>0时的求最优解的考虑范围 对于同类切割的相互位置对加工费用的影响,我们有如下引理;一发 引理4在切割方式r=x1x2x3x4xsx6中,若x,x为同类切割,且l≤,i<j 则对于
最优切割次序模型学大 283 r=x1x2x3x4xxb=x“x-1xx+1“x1xx+1…x, 有f(r)≥f(C) 个证不失一般性设x,x,为a类切割.首先r,中换刀次数相同,所以可以不考虑 换刀费用的影响.下面我们通过比较两者每次切割的费用来给出证明。 前+1次切割中,每次切割后r,P得到的长方体相同,所以当1≤k≤i-1时 f=fk又,I的第i次切割为同类切割,所以f=f,只共,因, 第次切割后,P,P,得到的长方体的长分别为a-1,a=4,而宽和高分别相同 从第;+1次到第;-1次的切割,均不是a类切割,所以每次切割后r,厂得到的长方体 长仍分别为a-1,al,而宽和高分别相同所以当计+1≤k≤J一1时,:f= (a-l1):(a-4),即f≥fk 第j次切割时,F,r的长方体的宽和高分别相同,所以,=了,, 第次切割后,T,P得到的长方体相同从第j+1次到第6次的切割,每次切割时 r,r的长方体相同,所以当时j+1≤k≤6,f=f,0 综上,可知f(r)≥f(r)由x1,x的一般性,可知命题成立 利用以上引理,我们下面将讨论在e>0时寻求最优解所需考虑的切割方式的范围 换刀次数k与水平切割c1,c2无关,仅与垂直a1,a2,b1,b2切割的顺序有关,不妨设 a1≥a2,b1≥b2,c≥c2,对P=x1x2x3x4x5x6,为了尽量减少加工费用,由引理4 a1切割在P中的位置应在a2切割之前,b1切割应在b2切割之前,c1t切割应在c2切割之前 因此只需考虑这样的切割方式r,其中a1,a2、b1,b2切割的排列为下列六种之一 bi b2, b,b2 ara2,(k a1b1b2a2,b1a1a2b2,(k=2); b1a2b2,b1a1b2a2,(k=3) 当a1,a2,b1,b2的排列确定之后,则可将1,2插入到排列中去,同时保持c1在前2在 后的顺序,这样就可以得到完整的切割方式F例如把c1,c2插入a1a2b1b2,可以为 (2a2b1b2,或a11a21eb,等,可得到(+c=15种切割方式,同样,把a,c2 插入b1b2a1a2也可得15种切割方式,所以对k=1共有30种切割方式需要考虑.同样,对 于k=2,3,亦各有30种切割方式需要考虑.所以,一般说来,我们要考虑90种切割方式 方能确定最优解 下面我们着重分析如何把要考虑的范围尽可能缩小在确定a1,a2,b1,b2的排列后, 我们将它分成几个连续子序列的连接,使得每一子序列中的切割长度是依次(非严格)递减 的,而任意相邻两个子序列的连接却不能满足连续递减的条件,我们称这样的每一个子序 列为“坡”由于在每一个坡内,切割长度的排列是有序的,由引理1可知,只有在c插入某 个坡后形成的子序列仍保持有序性的情况下,才可能使加工费用最少,所以在c插入某个 时,我们只需考虑使插入后形成的子序列仍保持有序性的一种插法对于一个有n个坡 购的a1,a2,b1,b2排列,若是将c1,c2均插入到同一个坡中,则有n种方法;而将c1,c2分 插入到不同的坡中,则有C种方法.故总共有n+C2=C2+1种方法.一般说来,这样所 确定的考虑范围已大大小于原先所说的30种的范围.下面我们具体地来看看此时需考虑范 的大小
全国大学生数学建模竞赛优秀论文汇编 k=1时,需要把c1,c2插入a1a2b1b2b1b2a1a2 若a2≥b1,则a1a2b1b2中,a1≥a2≥b1≥b2,只存在一个坡,把c1,c2插入 a1a2b1b2,只有1种方法;而b1b2a1a2中,因为b2≤b1≤a2≤a,所以存在两个坡 b1b2,a1a2、把c1,c2插入b1b241a2,共有G=3种方法事实上,把c1,c2插入aa2bb2 的那种方法已经是有序切割方式,即已为最优解,所以把c1,c2插入b1b2a1a2的3种方法 其实不用考虑因此,共只需考虑1种切割方式,顶国区方 若a20的情况我们对e>0的情 况的讨论来求解此题,过程如下: (1)e=0时,用“坡”的概念可以求出 量家 r1=b1c1b2a122,f(n1)=44.5,9联面不 f(r2)=456.5 r3=6141(b2c2a2或b1a1b22a2,f(r)=437.5.面 (2)画出三条∫~c曲线(如图3),可以得到突变点为c=2.5,进一步有如下结果 e的取值 费用最少切割方式 2≤ b ct b 2,5<e≤15 L bi ci b2a arc2 42
最优切割次序模型 最团式最3 456 e 442 业升2.5 图3 显把恐 六、模型评价(及改进) 在我们的模型中,首先,我们通过简单的伸缩变换,把r≠1的情况化为r=1的情 ,使得关1的情况和1的情况可以统一处理:然后,我们对c三0的情况进行了深 入讨论,得到了一个经严格证明的极其简明的最优化准则,即每次选择使得切去长度最长 的切割面来切割,或简单地说,“长者优先”在此基础上,我们对e>0的情况给出了一种 需考虑范围较少的解法我们首先从图形上直观地解释了当c增大时,最优的切割方式可 能存在突变,同时指出只需考虑在c=0时三种换刀次数下各自的最优解(及其加工费用) 即可找到e为任意值时的最优解,最后我们给出了一个把考虑范围从90种切割方式缩小为 不超过18种的方法,在附录中我们还给出了切割的“贡献”这一概念,并且利用这种概念的 深刻的物理内涵,证明了全文的基础,即交换引理 总的来说,我们的模型准确地描述了截断切割问题,而我们所引入的若干概念及定 理,使得模型的求解既严密又优美,同时得到了极好的结果.但其对于e>0的情况没有得 到简明的准则,只是把考虑范围缩小为不大于18种相对于原先的720种或是90种,18种 已是一种手工操作可以接收的数,但有时仍显略多 顺便指出(1)题目中的(2)所提出的“每次选择加工费用最少的待切面切割”的切割准 则是没有道理的完全可以设计一种例子,使得即使在c=0的条件下用这种准则求得的 切割方式的费用是最多的如一种例子为a=10,b7,=4,a1=1,a21.5,b1= 1.6,b2=1.7,c1=1.8,c2=1.9,而r=1,e=0.用该准则得到的切割方的费用为171 恰为切割费用的最大值(2)本题没有必要用计算机搜索所有切割方式来求解但如果 实际的切割车间有计算机,则简单的穷举法即可胜任求最优解的任务 我们的模型很容易推广到成品长方体与待加工长方体有重合面的情况.它也容易被推 到水平切割与垂直切割之间需要额外换刀费用的更复杂情形 七、附录(略) 冒的,家,、西宝景面林合 虽面,级艺面不,针案 断斜铁平个,某科”的又中回质” 出是改品;4共公算势补面答式品
截断切割的最优方案 温涛马衍青。徐峰 (华东理工大学,上海2003732 指导教师鲁习文刘朝晖 编者按本文借助于递推形式建立目标函数表达式,对优化准则及推广运用优化准则也 作了研究 摘要我们在充分分析问题的基础上,根据问题的条件和要求建立了模型,讨论了模型 的推广,给出了截断切割问题的最优方案,回答了题目中所有问题,并且对模型进行了评价 当成品长方体位于待加工长方体内部而没有公共面时,需要考虑的不同切割方式总数为P 720种如果有 面可类似计算 从描述连续切割时长方体的形状变化过程出发,在深入研究了不同切割方式特征的基磁 一以找到最优切割方案1,源的 面国2 下对=0的情形,我们得到了相当简明的最优切割准则:按成品长方体各面与待加工长 对应面间加权距离的非增排列顺序进行切割 按照“每次选择一个加工费用最少的待切割面进行切割”的准则进行切割,我们发现一般得 的不到最优解并且,我们随机列举了80个例子进行比较,采用该方法得到的近似最优解与最优 解的平均比值为1.0266 宝对所给的数据,我们进行了实例验证,得到的计算结果如下::,9 5a)最小加工费用为y=374元调整刀具次数均为m=3;因又物一 性81,中b)最小加工费用为f=4375元,调整刀具次数均为n=3: c)最小加工费用为f=540.5元调整刀具次数n=3;身是主 (d)当2≤525时有二种最优切料方案,此时调整刀具3次,单中 白来当+=2.5时有三种最优切割方案,当2,55“15时仍是最优的由此,可观察到当e增加时调 刀次数逐步减小 我们建立的模型可以推广到一般n面体的截断切割问题,并可进一步推广到连续加工若干 个待加工多面体的问题我们建立的模型具有清晰简明的数学表达式,计算简单,优化方便 问题重述(略 时量比长同直垂已平 基本假设 1.与水平工作台接触的长方体底面是事先指定的,因此长、宽、高位置一定,但是这 影响切割方案的讨论,即并不因为底面已经被指定,而要求最后切割底面 2.“截断切割”如问题中所定义的为“将物体沿某个切割平面分成两部分” 3.成品长方体与待加工长方体没有公共面即:成品长方体必须由待加工长方体经 次截断切割后得到