全国大学生《数学建模》竞赛：1997B

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种切割方式,顶国区方 若a2<b1,则a1a2b1b2中,a1≥a2,a2<b1,b≥b2,有两个坡a1a2…b1b2 c1c2插入a1a2b1b2,共有C32=3种方法;而b1b2a1a2中,当b2≥a1时有一个坡,对应 1种方法,当b2<a1时有两个坡,对应3种方法所以a2<b1时共需考虑4种或6种切割 方式 这样,我们把k=1时的考虑范围由30种缩小为1种或4种或6种,世1徐 用同样的方法,k=2时,考虑范围由30种缩小为1种或6种,k=3时,考虑范围由 30种缩小为1种或6种.因此,这样总的考虑范围就不超过6+6+618种,的71 综上,引入坡的概念后,用我们的方法,极大地缩小了考虑范围,用手工计算也能很快 求得最优解,世回实 4.具体问题求解 下面用题目中所给的实例来验证我们的方法,实例中的数据在我们的模型中体现为 1,b1=7,b25 9,c2 按照定理二,我们可以求出a题、b题、c题这三种e=0情况下的最优解三只共 题号题日条件费用最少的切方式最少切费用八门) c1b1a1czbnay 1.5, 0 baiC b3 b b2 再来看d题,条件为r=1.5,2≤c≤15是属于e>0的情况我们对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>15时仍是最优的由此,可观察到当e增加时调 刀次数逐步减小 我们建立的模型可以推广到一般n面体的截断切割问题,并可进一步推广到连续加工若干 个待加工多面体的问题我们建立的模型具有清晰简明的数学表达式,计算简单,优化方便 问题重述(略 时量比长同直垂已平 基本假设 1.与水平工作台接触的长方体底面是事先指定的,因此长、宽、高位置一定,但是这 影响切割方案的讨论,即并不因为底面已经被指定,而要求最后切割底面 2.“截断切割”如问题中所定义的为“将物体沿某个切割平面分成两部分” 3.成品长方体与待加工长方体没有公共面即:成品长方体必须由待加工长方体经 次截断切割后得到