打孔机生产效能的提高ppt课件

1、12012年“深圳杯”全国大学生数学建模夏令营打孔机消费效能的提高打孔机消费效能的提高 学生学生: 李欣儿李欣儿 王伟杰王伟杰 杨杨 京京 指点教师指点教师: 林林 娟娟 福建师范大学福清分校数学与计算机科学系福建师范大学福清分校数学与计算机科学系22012年“深圳杯”全国大学生数学建模夏令营bcdefgha问题重述问题重述1. 单钻头的孔群加工单钻头的孔群加工2. 双钻头的孔群加工双钻头的孔群加工目的：提高打孔机的消费效能目的：提高打孔机的消费效能刀具的旋转方向刀具的旋转方向根本要素：根本要素：相邻刀具的旋转时间：相邻刀具的旋转时间：18s钻头的挪动速度：钻头的挪动速度：180mm/s钻头的

2、行进本钱：钻头的行进本钱：0.06元元/mm刀具转换的时间本钱：刀具转换的时间本钱：7元元/min两钻头协作间距两钻头协作间距32012年“深圳杯”全国大学生数学建模夏令营影响打孔机的消费效能的要素：影响打孔机的消费效能的要素： 1. 单个过孔的钻孔作业时间单个过孔的钻孔作业时间2. 钻头的行进时间钻头的行进时间3. 刀具的转换时间刀具的转换时间留意留意: 由于同一孔型钻孔作业时间都是一样且刀具旋由于同一孔型钻孔作业时间都是一样且刀具旋转一次所破费的转一次所破费的时间远大于钻头在恣意两孔之间的行进时间，时间远大于钻头在恣意两孔之间的行进时间，所以要提高打孔所以要提高打孔机的消费效能首先我们思索

3、减少刀具的转换时机的消费效能首先我们思索减少刀具的转换时间间(即减少刀即减少刀具的转换次数具的转换次数)其次思索各个刀具所要打孔型点其次思索各个刀具所要打孔型点的最优道路。的最优道路。问题分析问题分析42012年“深圳杯”全国大学生数学建模夏令营1. 影响刀具转换方案的要素：刀具的顺序固定，不能互换刀具可顺时针和逆时针旋转有的孔型需求多种刀具及规定的加工次序来完成如：C(a,c),E(c,f),G(d,g,f),I(e,c),J(f,c) 由于f,c及c,f有顺序,显然易知会出现f-c-f或c-f-c的情况,最少转换次数大于等于8,且以c或f为开头时能够为8。 由d g f的顺序可知,以c或f

4、开头时,最小转换次数大于8. 最优的刀具转换方案： d(D,G) c(E)b(B)a(A,C)h(F,H)g(F,G) f(E,G,J) e(D,I)c(C,I,J) 最小转换次数:9刀具转换方案单钻头刀具转换方案单钻头bcdefgha52012年“深圳杯”全国大学生数学建模夏令营孔群加工最优作业道路孔群加工最优作业道路 我们将最优的刀具方案的各个刀具视为一个模块在求各个以刀具为模块的最短途径时,可将问题看作类TSP问题(留意:遍历一切点后不回到原点) 在衔接以刀具为模块的各个模块时可看作TSP问题(留意:遍历一切点回到原点)中求得的最优道路去掉此最优道路中相邻两点最大间隔的连线62012年“

5、深圳杯”全国大学生数学建模夏令营刀具转换方案和最优作业道路双钻头刀具转换方案和最优作业道路双钻头1. 影响刀具转换方案的要素：单钻头孔群加工时包含的一切要素双钻头各自完成的时间2. 孔群加工的最优作业道路两钻头的协作间距两钻头道路同时变化固定长的一个钻头的道路,变化另一个钻头的道路道路中能否存在等待时间如: c刀具与f刀具72012年“深圳杯”全国大学生数学建模夏令营模型假设模型假设1假设打孔时的时间过小可忽略不计；假设打孔时的时间过小可忽略不计；2假设打孔时所耗效能忽略不计；假设打孔时所耗效能忽略不计；3假设不出现断电或器具损坏问题；假设不出现断电或器具损坏问题； 4假设打孔后的等待时间极短

6、可忽略不计；假设打孔后的等待时间极短可忽略不计；5假设将钻头看作质点假设将钻头看作质点82012年“深圳杯”全国大学生数学建模夏令营问题描画：有 n个城市,其相互间间隔d为知, 求合理的道路使得每城市都访问一次,且总途径为最短。TSP的数学模型如下所示: 1 , 0, 2 , 1)5(, 2 , 1,422 , 13121.1min,11ijjjiijniijnjijjiijijXnsjinjinssXXXtsXdTSP(游览商问题游览商问题)92012年“深圳杯”全国大学生数学建模夏令营处理TSP问题的方法l贪婪算法l模拟退火算法l改良的蚁群算法lCONCORDE软件102012年“深圳杯”

7、全国大学生数学建模夏令营算法简介 模拟退火算法:是模拟物理的退火过程。退火是指将固体加热到足够高的温度,使分子呈随机陈列形状,然后逐渐降温使之冷 却,最后分子以低能形状陈列,固体到达某 种稳定形状。 蚁群算法:是模拟自然界蚂蚁寻觅食物时在所经过的途径上留下一种挥发性的物质 (称为信息素), 从而引导后续蚂蚁走最短途径提出的一种算法。112012年“深圳杯”全国大学生数学建模夏令营设最优转换方案的刀具集合: minkkxxiiikPkPD111| ) 1()(|min最优作业道路的模型最优作业道路的模型,.,21mxxxX 每一个刀具所需打孔的个数:,.,21mnnnn 各个刀具的最优道路的孔的

8、坐标集:,.,1,.,1| )(minkkPixi总最优作业道路的最短路程：总最优作业道路的最短路程：D122012年“深圳杯”全国大学生数学建模夏令营计算结果单钻头计算结果单钻头算法类型作业总时间单位：s作业总成本单位：元模拟退火算法250.1881018.81改进的蚁群算法240.19863.11concorde软件235.37868.54132012年“深圳杯”全国大学生数学建模夏令营结果分析单钻头结果分析单钻头以上两种方法它们具有以下两个共同特点:该类方法都是从假设干解出发,经过对其邻域的不断搜索和当前解的交换来实现优化,一次可以处置大量方式,而且不受搜索空间延续性的限制;该类方法都是

9、在全空间并行搜索,且设有跳出部分最优的机制,具有较强的全局搜索才干。不同点：蚁群算法的搜索才干比模拟退火算法强142012年“深圳杯”全国大学生数学建模夏令营双钻头孔群最优途径模型假设两个钻头的最优道路的时间分别为T1和T2,那么双钻头孔群加工道路优化的目的函数为: 约束条件: 恣意一个待加工的孔必需包括在其中一条加工途径中,且加工过程中两个钻头不发生碰撞。212211minTTTTTTT152012年“深圳杯”全国大学生数学建模夏令营双钻头孔群的协作间距模型双钻头孔群的协作间距模型162012年“深圳杯”全国大学生数学建模夏令营双钻头的最优转换方案b(B) -J)I,C,c(E, -G)d(

10、D, -I)e(D,J)E,f(G, -F)g(G, -F)h(H,- A)a(C,刀具转换刀具转换A方案：方案：3-3由于由于cf与与fc相互制约的关系相互制约的关系3-3变成了变成了4-3刀具转换刀具转换B方案：方案：4-3c(E)J),I,c(C,-b-a-hf(E)f(G),-g-f(J)-e-d留意：根据单钻头中得到结果可估计出留意：根据单钻头中得到结果可估计出B方案优于方案优于A方案，方案，但以下双钻头的计算过程是根据但以下双钻头的计算过程是根据A方案进展的一系列处置。方案进展的一系列处置。172012年“深圳杯”全国大学生数学建模夏令营双钻头孔群加工的分析和计算过程双钻头孔群加工

11、的分析和计算过程分析步骤：分析步骤：确定哪个钻头的最优道路不变确定哪个钻头的最优道路不变,哪个钻头的最优哪个钻头的最优道路变化根据道路变化根据f1(J)与与c2(J)之前的时间和的之前的时间和的大小关系来判别。大小关系来判别。2. 处置处置e(D,I)- d(D,G) -c1(C,E,I)的最优途径的最优途径问题。问题。 由于由于f1(J)与与c2(J)制约的关系制约的关系,要使时间作业要使时间作业本钱更小本钱更小, 首先先确定首先先确定f1(J)与与c2(J)应坚持的间隔才防应坚持的间隔才防止不碰撞。止不碰撞。 接着思索接着思索 双钻头不相互关扰的根底上双钻头不相互关扰的根底上 e(D,I)

12、- d(D,G) -c1(C,E,I)倒过来的最优化倒过来的最优化作业道路。作业道路。 (由于由于cf与与fc刀具相互制约的关系刀具相互制约的关系, 可以把可以把f(E,G,J)分为分为f1(J)和和f2(E,G), c(E,C,I,J)分为分为c1(C,E,I)和和c2(J), 且要求且要求f1(J)要先于要先于c2(J)完成。完成。)182012年“深圳杯”全国大学生数学建模夏令营3. 处置 f1(J)与c2(J)的最优途径问题： 知: f1(J)要先于c2(J)完成,且受协作间距的影响。 目的: 完成f1(J),c2(J)所花总时间最少即所间隔的 时间T(f1c2)最短 4. 总时间的计

13、算:假设更新后的e(D,I) -d(D,G) - c1(C,E,I)的时间和小于a(C,A) -h(H,F)- g(G,F)的时间和,那么: Ttotal=Ta+Th+Tg+Tf1+Tf1c2+Tb+4*Tturning否那么(此处先不作思索)5. 消费效能的计算: 消费效能提高 =(单一钻头破费的时间-双钻头破费的时间)/单一钻头破费的时间6. 作业本钱的计算 : 作业本钱 = 挪动本钱 + 旋转本钱192012年“深圳杯”全国大学生数学建模夏令营经计算得出由f1(j)与c2(j)之前的时间和分别为81.12s 和67.48s比较得知a(C,A) - h(H,F)-g(G,F) - f1(j

14、)的最短途径不改动.e(D,I) - d(D,G)-c1(C,E,I)的道路受双钻头的协作间距的影响而改动。2. 由图1可知,由于c2-d-e的道路与f1-g-h-a中旋转时间的反复部分很多,重新计算的优化途径只需c2,d与e中的一部分数据。其中c2与f1中的部分的点(由3中可知只需两个点的坐标)时间有能够重叠(计算得知c2的最优途径并没改动)。而d中需求优化的点从f1-g-h-a第二次旋转终了时间开场,e中的点从f1-g-h-a第3次旋转终了时间开场。计算过程计算过程 202012年“深圳杯”全国大学生数学建模夏令营图1:从J(f)处逆序开场双钻头道路各个刀具的路程图 能够产生碰撞的e与a区

15、域能够产生碰撞d与h区域红黑曲线是旋红黑曲线是旋转时间所能挪转时间所能挪动的路程动的路程212012年“深圳杯”全国大学生数学建模夏令营并用临近交换算法计算得到途径变化后的d和e如图2,3所示图2 左图为单钻头作业d刀具在D,G孔型处的最优化途径图(需求变化部分) 右图为双钻头作业d刀具在D,G孔型处满足协作间距的新途径图 222012年“深圳杯”全国大学生数学建模夏令营图3 左图为单钻头作业e刀具在D,I孔型处的最优化途径图(需求变化部分) 右图为双钻头作业e刀具在D,I孔型处满足协作间距的新途径图 232012年“深圳杯”全国大学生数学建模夏令营3. 根据协作间距的限制求的f刀具与c刀具最

16、小的间隔为153mm,即 在出发153/180s后再出发,可保证双钻头相互不干扰。4. 由以上计算可知,作业的总时间比没有随着d-e中途径的改动而发生变化。 Ttotal=Ta+Th+Tg+Tf1+Tf1c2+Tb+4*Tturning = 20.29+3.47+3.36+1097.48/180+153/180+18.19+4*18 =124.257s 5. 消费效能提高 = (单一钻头破费的时间-双钻头破费的时间)/单一钻头破费的时间 = (250.181-124.257)/250.181 = 0.4973= 49.73%242012年“深圳杯”全国大学生数学建模夏令营 6. 作业本钱作业本

17、钱 = 挪动本钱1 + 旋转本钱+挪动本钱2(刀具旋转时挪动 = (124.257-18*4)s*0.06元/mm*180mm/s+7/60元/s*18s*6+575.041mm*0.06元/mm = 611.47元其中e,d途径变卦时并没有改动途径的开场孔与终了孔的坐标编号那么最优途径中各刀具的开场孔与终了孔的坐标编号如下:(D145,d,D123,d),(E51,c,E40,c),(B740,b,B568,b),(C206,a,C166,a),(F14,h,H2,h),(G20,g,F27,g),(J24,f,E51,f),(D21,e, D,e),(C177,c,C231,c)25201

18、2年“深圳杯”全国大学生数学建模夏令营A. 两钻头协作间距对作业道路的影响两钻头协作间距对作业道路的影响协作间距 = 3cm :1. 对d中点的影响: d中受影响部分的点的路程共有226 mm从d40= 185.292mm变到d40 =249.085mm路程差d =d40 d40 = 53.8mm2. 对e中点的影响: e中受影响部分的点的路程共有452.8mm从 e87= 452.11mm变到e87 =519.03mm。路程差 e=e87 e87 = 66.90mm 由数据得知两变化的途径所破费的时间和缺乏1s.262012年“深圳杯”全国大学生数学建模夏令营协作间距的影响272012年“深圳杯”全国大学生数学建模夏令营B. 两钻头协作间距对消费效能两钻头协作间距对消费效能的影响的影响消费效能提高消费效能提高 = (单一钻头破费的时间单一钻头破费的时间-双钻头双钻头破费的时间破费的时间)/单一钻头破费的时单一钻头破费的时间间*100%双钻头的作业时间双钻头的作业时间: Ttotal=Ta+Th+Tg+Tf1+Tf1c2+Tb+4*Tturning