打孔机生效能的提高课件

1、12012年“深圳杯”全国大学生数学建模夏令营20120806福建师范大学福清分校数学与计算机科学系打孔机生产效能的提高打孔机生产效能的提高 学生学生: 李欣儿李欣儿 王伟杰王伟杰 杨杨 京京 指导老师指导老师: 林林 娟娟 福建师范大学福清分校数学与计算机科学系福建师范大学福清分校数学与计算机科学系22012年“深圳杯”全国大学生数学建模夏令营20120806福建师范大学福清分校数学与计算机科学系bcdefgha问题重述问题重述1. 单钻头的孔群加工单钻头的孔群加工2. 双钻头的孔群加工双钻头的孔群加工目标：提高打孔机的生产效能目标：提高打孔机的生产效能刀具的旋转方向刀具的旋转方向基本要素：

2、基本要素：相邻刀具的旋转时间：相邻刀具的旋转时间：18s钻头的移动速度：钻头的移动速度：180mm/s钻头的行进成本：钻头的行进成本：0.06元元/mm刀具转换的时间成本：刀具转换的时间成本：7元元/min两钻头合作间距两钻头合作间距32012年“深圳杯”全国大学生数学建模夏令营20120806福建师范大学福清分校数学与计算机科学系影响打孔机的生产效能的因素：影响打孔机的生产效能的因素： 1. 单个过孔的钻孔作业时间2. 钻头的行进时间3. 刀具的转换时间注意注意: 因为同一孔型钻孔作业时间都是相同且刀具旋转一次所花费的时间远大于钻头在任意两孔之间的行进时间，所以要提高打孔机的生产效能首先我们

3、考虑减少刀具的转换时间减少刀具的转换时间(即减少刀即减少刀具的转换次数具的转换次数)其次考虑各个刀具所要打孔型点的最优路线最优路线。问题分析问题分析42012年“深圳杯”全国大学生数学建模夏令营20120806福建师范大学福清分校数学与计算机科学系1. 影响影响刀具转换方案的因素：刀具转换方案的因素：l 刀具的顺序固定，不能调换l 刀具可顺时针和逆时针旋转l 有的孔型需要多种刀具及规定的加工次序来完成如：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为开头时可能为

4、8。 由d g f的顺序可知,以c或f开头时,最小转换次数大于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年“深圳杯”全国大学生数学建模夏令营20120806福建师范大学福清分校数学与计算机科学系孔群加工最优作业路线孔群加工最优作业路线 我们将最优的刀具方案的各个刀具视为一个模块在求各个以刀具为模块的最短路径时,可将问题看作类tsp问题(注意:遍历所有点后不回到原点) 在连接以刀具为模块的各个模块时可看作tsp

5、问题(注意:遍历所有点回到原点)中求得的最优路线去掉去掉此最优路线中相邻两点最大距离相邻两点最大距离的连线62012年“深圳杯”全国大学生数学建模夏令营20120806福建师范大学福清分校数学与计算机科学系刀具转换方案和最优作业路线（双钻头）刀具转换方案和最优作业路线（双钻头）1. 影响影响刀具转换方案的因素：刀具转换方案的因素：l 单钻头孔群加工时包含的所有因素l 双钻头各自完成的时间2. 孔群加工的孔群加工的最优作业路线最优作业路线l 两钻头的合作间距l 两钻头路线同时变化l 固定长的一个钻头的路线,变化另一个钻头的路线l 路线中是否存在等待时间如: c刀具与f刀具72012年“深圳杯”全

6、国大学生数学建模夏令营20120806福建师范大学福清分校数学与计算机科学系模型假设模型假设（1）假设打孔时的时间过小可忽略不计；（2）假设打孔时所耗效能忽略不计；（3）假设不出现断电或器具损坏问题； （4）假设打孔后的等待时间极短可忽略不计；（5）假设将钻头看作质点82012年“深圳杯”全国大学生数学建模夏令营20120806福建师范大学福清分校数学与计算机科学系问题描述：有 n个城市,其相互间距离d为已知, 求合理的路线使得每城市都访问一次,且总路径为最短。tsp的数学模型如下所示的数学模型如下所示: 1 , 0, 2 , 1)5(, 2 , 1,422 , 13121.1min,11ij

7、jjiijniijnjijjiijijxnsjinjinssxxxtsxdtsp(旅行商问题旅行商问题)92012年“深圳杯”全国大学生数学建模夏令营20120806福建师范大学福清分校数学与计算机科学系解决tsp问题的方法l贪心算法l模拟退火算法l改进的蚁群算法lconcorde软件102012年“深圳杯”全国大学生数学建模夏令营20120806福建师范大学福清分校数学与计算机科学系算法简介 模拟退火算法:是模拟物理的退火过程。退火是指将固体加热到足够高的温度,使分子呈随机排列状态,然后逐步降温使之冷 却,最后分子以低能状态排列,固体达到某 种稳定状态。 蚁群算法:是模拟自然界蚂蚁寻找食物时

8、在所经过的路径上留下一种挥发性的物质 (称为信息素), 从而引导后续蚂蚁走最短路径提出的一种算法。112012年“深圳杯”全国大学生数学建模夏令营20120806福建师范大学福清分校数学与计算机科学系设最优转换方案的刀具集合: minkkxxiiikpkpd111| ) 1()(|min最优作业路线的模型最优作业路线的模型,.,21mxxxx 每一个刀具所需打孔的个数:,.,21mnnnn 各个刀具的最优路线的孔的坐标集:,.,1,.,1| )(minkkpixi总最优作业路线的最短路程：总最优作业路线的最短路程：d122012年“深圳杯”全国大学生数学建模夏令营20120806福建师范大学福

9、清分校数学与计算机科学系计算结果（单钻头）计算结果（单钻头）算法类型作业总时间单位：s作业总成本单位：元模拟退火算法250.1881018.81改进的蚁群算法240.19863.11concorde软件235.37868.54132012年“深圳杯”全国大学生数学建模夏令营20120806福建师范大学福清分校数学与计算机科学系结果分析（单钻头）结果分析（单钻头）以上两种方法它们具有以下两个共同特点:该类方法都是从若干解出发,通过对其邻域的不断搜索和当前解的替换来实现优化,一次能够处理大量模式,而且不受搜索空间连续性的限制;该类方法都是在全空间并行搜索,且设有跳出局部最优的机制,具有较强的全局搜

10、索能力。不同点：蚁群算法的搜索能力比模拟退火算法强蚁群算法的搜索能力比模拟退火算法强142012年“深圳杯”全国大学生数学建模夏令营20120806福建师范大学福清分校数学与计算机科学系双钻头孔群最优路径模型假设两个钻头的最优路线的时间分别为t1和t2,则双钻头孔群加工路线优化的目标函数为: 约束条件: 任意一个待加工的孔必须包括在其中一条加工路径中,且加工过程中两个钻头不发生碰撞。212211minttttttt152012年“深圳杯”全国大学生数学建模夏令营20120806福建师范大学福清分校数学与计算机科学系双钻头孔群的合作间距模型双钻头孔群的合作间距模型162012年“深圳杯”全国大学

11、生数学建模夏令营20120806福建师范大学福清分校数学与计算机科学系双钻头的最优转换方案b(b) -j)i,c,c(e, -g)d(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方案，方案，但以下双钻头的计算过程是根据但以下双钻头的计算过程是根

12、据a方案进行的一系列处理。方案进行的一系列处理。172012年“深圳杯”全国大学生数学建模夏令营20120806福建师范大学福清分校数学与计算机科学系双钻头孔群加工的分析和计算过程双钻头孔群加工的分析和计算过程分析步骤：分析步骤：1. 确定哪个钻头的最优路线不变,哪个钻头的最优路线变化根据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)- d(d

13、,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年“深圳杯”全国大学生数学建模夏令营20120806福建师范大学福清分校数学与计算机科学系3. 处理 f1(j)与c2(j)的最优路径问题： 已知: f1(j)要先于c2(j)完成,且受合作间距的影响。 目标: 完成f1(j),c2(j)所花总时间最少即所间隔的 时间t(f1c2)

14、最短 4. 总时间的计算:若更新后的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年“深圳杯”全国大学生数学建模夏令营20120806福建师范大学福清分校数学与计算机科学系1. 经计算得出由f1(j)与c2(j)之前的时间和分别为81.12s 和6

15、7.48s比较得知a(c,a) - h(h,f)-g(g,f) - f1(j)的最短路径不改变.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年“深圳杯”全国大学生数学建模夏令营

16、20120806福建师范大学福清分校数学与计算机科学系图1:从j(f)处逆序开始双钻头路线各个刀具的路程图 可能产生碰撞的e与a区域可能产生碰撞d与h区域红黑曲线是旋红黑曲线是旋转时间所能移转时间所能移动的路程动的路程212012年“深圳杯”全国大学生数学建模夏令营20120806福建师范大学福清分校数学与计算机科学系并用邻近交换算法计算得到路径变化后的d和e如图2,3所示图2 左图为单钻头作业d刀具在d,g孔型处的最优化路径图(需要变化部分) 右图为双钻头作业d刀具在d,g孔型处满足合作间距的新路径图 222012年“深圳杯”全国大学生数学建模夏令营20120806福建师范大学福清分校数学与

17、计算机科学系图3 左图为单钻头作业e刀具在d,i孔型处的最优化路径图(需要变化部分) 右图为双钻头作业e刀具在d,i孔型处满足合作间距的新路径图 232012年“深圳杯”全国大学生数学建模夏令营20120806福建师范大学福清分校数学与计算机科学系3. 根据合作间距的限制求的f刀具与c刀具最小的间隔为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/1

18、80+18.19+4*18 =124.257s 5. 生产效能提高 = (单一钻头花费的时间-双钻头花费的时间)/单一钻头花费的时间 = (250.181-124.257)/250.181 = 0.4973= 49.73%242012年“深圳杯”全国大学生数学建模夏令营20120806福建师范大学福清分校数学与计算机科学系 6. 作业成本作业成本 = 移动成本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路径变更时并没有改变路径的

19、开始孔与结束孔的坐标编号则最优路径中各刀具的开始孔与结束孔的坐标编号如下:(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, d135,e),(c177,c,c231,c)252012年“深圳杯”全国大学生数学建模夏令营20120806福建师范大学福清分校数学与计算机科学系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