《数学模型打孔机效率提高综述》由会员分享，可在线阅读，更多相关《数学模型打孔机效率提高综述（28页珍藏版）》请在金锄头文库上搜索。
1、福建农林大学计算机与信息学院（数学类课程）课程论文报告课程名称：数学模型课程论文题目：打孔机生产效能的提高姓 名：系：专 业：年 级：学 号：指导教师：职 称：2013年 1月7日福建农林大学计算机与信息学院数学类课程课程论文结果评定评定内容评定指标评分权值评定成绩工作态度工作努力，遵守纪律；工作作风严谨务实；按期完成规定的任务0.1论文格式格式规范、结构合理、内容完整0.1论文质量假设合理；模型正确；求解准确；表述清晰。立论正确，论述充分，结论严谨合理；实验正确，分析处理科学；文字通顺，技术用语准确，符号统一，编号齐全，书写工整规范，图表完备、整洁、正确；论文结果有应用价值；0.6工作创新工
2、作中有创新意识、有见解；对前人工作有改进或突破，或有独特见解；0.1工作量与工作难度工作量饱满，工作难度大0.1成绩：指导教师签字：任务下达日期：2012年12月12日评定日期：2013年1月15日目录摘要1关键词11 问题重述22 问题分析23 模型假设34 模型准备（模拟退火算法简介）35 模型的建立与求解45.1 模型建立45.2 模型求解66 模型分析与评价12参考文献13附录A 单转头优化路线图（部分）14附录B MATLAB程序代码（部分）16打孔机生产效能的提高摘要过孔是印刷线路板（也称为印刷电路板）的重要组成部分之一，过孔的加工费用通常占制板费用的30%到40%，打孔机主要用于
3、在制造印刷线路板流程中的打孔作业。因此打孔机效能的提高是降低制板费用的重要途径之一。本文旨通过建立数学模型，实现刀具转换最优顺序的前提下，运用模拟退火算法找到最优线路，及最短距离。使作业成本和行进时间达到最低，以此减少打孔机总打孔成本。针对单转头的作业方式，先根据刀具转换的约束和孔型的约束，用穷举法得到刀具最优转换顺序，即d-c-b-a-h-g-f-e-d-c，再根据刀具装换方案确定打孔方案，即将孔分成9类，即D,G、E、B、A,C、F,H、F,C、E,G,F、D,I和C,I,J，同一类孔在同一时间段内用同一种刀具进行打孔，没有先后顺序的约束，因此我们对每一类孔都用模拟退火算法进行搜索最优路线
4、，进而得到问题的优化解。经计算得到的结果是：采用单转头加工方式作业成本为95694元，行进时间2小时22分钟。针对双转头的作业方式，由于两个钻头独立工作，两个钻头可以同时进行打孔，也可以一个钻头打孔，另一个钻头行进或转换刀具。但为了避免钻头间的触碰和干扰，在过孔加工的任何时刻必须保持两钻头间距不小于3cm。所以我们就将线路板根据孔数平均分成两个区域（一个转头负责打一块区域的孔），然后再对每一区域里的孔采用单转头打孔方式找出的优化路线即可得到问题的一个优化解；再验证该解是否符合要求（即是否符合任何时刻两钻头间距都不小于3cm），如果不符合，就再求解（由于模拟退火算法求出的是近似解，所以每次求出的
5、解基本都会不一样），再验证，再求解，再验证直到找到符合的解为止。经计算得到的结果是：采用双转头加工方式作业成本为98239元，行进时间1小时24分钟，相对于单转头打孔机，效能提高40%左右。针对打孔机的两钻头合作间距对作业路线和生产效能产生的影响，本文考虑到合作间距太大会影响作业路线；合作间距太小，两转头工作时可能会产生相互影响。因此合作间距控制不合理会浪费资源，降低产品加工质量，进而影响到生产效能。所以，要提高生产效能就得设置一个合理的合作间距。关键词：穷举法；模拟退火算法；TSP问题251 问题重述过孔是印刷线路板（也称为印刷电路板）的重要组成部分之一，其加工费用通常占制板费用的30%到4
6、0%，打孔机主要用于在制造印刷线路板流程中的打孔作业。由于打孔机的生产效能主要取决于以下几方面：（1）单个过孔的钻孔作业时间；（2）打孔机在加工作业时，钻头的行进时间；（3）针对不同孔型加工作业时，刀具的转换时间。而目前实际采用的打孔机普遍是单钻头作业。现有某种钻头，上面装有8种刀具a，b，c， , h，依次排列呈圆环状，而且8种刀具的顺序固定，不能调换。在加工作业时，刀具可以转换，相邻两刀具的转换时间是18 s。将任一刀具转换至其它刀具处，所需时间是相应转换时间的累加。为了简化问题，假定钻头的行进速度是相同的，为180 mm/s，行进成本为0.06元/mm，刀具转换的时间成本为7元/min。
7、刀具在行进过程中可以同时进行刀具转换，但相应费用不减。现有一种线路板，给定上面孔型所需的加工刀具和刀具加工次序。一块线路板上的过孔全部加工完成后，再制作另一线路板。但在同一线路板上的过孔不要求加工完毕一个孔，再加工另一个孔，即对于须用两种或两种以上刀具加工的过孔，只要保证所需刀具加工次序正确即可。请建立相应的数学模型，根据附件给的数据（单位：密尔），完成以下问题：（1）请给出单钻头作业的最优作业线路（包括刀具转换方案）、行进时间和作业成本。（2）为提高打孔机效能，现在设计一种双钻头的打孔机（每个钻头的形状与单钻头相同），两钻头可以同时作业，且作业是独立的，即可以两个钻头同时进行打孔，也可以一个
8、钻头打孔，另一个钻头行进或转换刀具。为避免钻头间的触碰和干扰，在过孔加工的任何时刻必须保持两钻头间距不小于3cm（称为两钻头合作间距）。为使问题简化，可以将钻头看作质点。（i）给出双钻头作业时的最优作业线路、行进时间和作业成本，并与传统单钻头打孔机进行比较，其生产效能提高多少？（ii）研究打孔机的两钻头合作间距对作业路线和生产效能产生的影响。2 问题分析 本题是一题优化问题，目标是总费用最少和总时间最少。 1、针对问题一：考虑到：（2-1）所以想要总费用最少，就得使刀具转换次数最少和行进总路程最少。约束条件是：刀具的转换顺序固定；不同的孔需要不同的刀具。因此我们先根据不同的孔需要不同的刀具，以
9、刀具转换总次数为目标，先得到刀具的转换方案；再根据刀具装换方案确定打孔方案，即将孔根据刀具转换方案进行分类，同一类孔在同一时间段内用同一种刀具进行打孔，没有先后顺序的约束，因此我们对每一类孔都用模拟退火算法进行搜索最优路线，进而得到问题的一个解。2、针对问题二：考虑到双转头，我们就将线路板根据孔横向平均分成两部分，即作一条竖线L1，使两边的孔数差值的绝对值小于或等于1，此时L1称平分分界线。再以1.5cm为距离，在L1两边做平行线L2和L3，若L2、L3之间没有孔，则称L1为最优分界线。若L1不是最优分界线，则适当移动L1使其变成最优分界线。若线路板不存在最优分界线，则以平分分界线L1为界线，
10、将线路板分成两部分，分别用两个转头进行打孔，再利用问题一的方法求出每一部分的优化路线即可得到问题的一个解；再验证L2和L3之间的孔是否符合要求，如果不符合，就再求解（由于模拟退火算法求出的是近似解，所以每次求出的解基本都会不一样），再验证，再求解，再验证直到找到符合的解为止。而本题给的数据经过计算发现存在最优分界线L1，所以就以L1为界线，将线路板分成两部分，分别用两个转头进行打孔，这样两转头之间的距离在任何时刻都会大于3cm。再利用问题一的方法求出每一部分的优化路线即可得到问题的解。3 模型假设1、假设单孔转孔时间都是相同的；2、假设转头的行进速度是匀速的；3、假设所有的孔都是一个点；4 模
11、型准备（模拟退火算法简介）4.1、模拟退火算法原理：模拟退火算法得益于材料的统计力学的研究成果。统计力学表明材料中粒子的不同结构对应于粒子的不同能量水平。在高温条件下，粒子的能量较高，可以自由运动和重新排列。在低温条件下，粒子能量较低。如果从高温开始，非常缓慢地降温（这个过程被称为退火），粒子就可以在每个温度下达到热平衡。当系统完全被冷却时，最终形成处于低能状态的晶体。根据Metropolis规律，如果用粒子的能量定义材料的状态，假设材料在状态之下的能量为，那么材料在温度时从状态进入状态就遵循如下规律：a、如果，接受该状态被转换。 b、如果，则状态转换以如下概率被接受：（4-1）其中是物理学中
12、的波尔兹曼常数，是材料温度。用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解计算目标函数差接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(Cooling Schedule)控制，包括控制参数的初值t及其衰减因子t、每个t值时的迭代次数L和停止条件S。4.2、模拟退火算法解决TSP问题模型：TSP问题，即旅行商问题。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径
13、的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。模拟退火算法描述如下：a、解空间：解空间S可表示为1,2,N的所有固定的起点和终点的循环排列集合，即：（4-2）其中每一个循环排列表示一种行走方案，表示第i次到达j城市。b、目标函数：目标函数为经过所有城市的总路程或称代价函数，我们要求：（4-3）而迭代有下面3步构成：c、新解的产生(2变换法)：任取序号u，v（uv），交换u与v之间的顺序，此时新路径为：（4-4）d、代价函数差：（4-5）e、接受准则：（4-6）如果，则接受新的路径；否则，以概率接受新的路径，即若大于0到1的随
14、机数则接受。f、降温：利用降温系数进行降温，即：得到新的温度，一般取。g、结束条件：用选定的终止温度(一般取)，判断退火过程是否结束。若，算法结束，输出当前状态。5 模型的建立与求解5.1 模型建立目标函数：（5-1）（5-2）其中：表示总成本；表示刀具转换总成本；表示转头行进总成本；n为刀具转换总次数；S为转头行进总路程；为刀具转换单位次的成本；为转头行进单位路程的成本。所以现在就是要计算n的最少值和S的最少值：即。对于，可以这样考虑：从序列a,b,g,h,a,b,g,h,a,b,（刀具的转换顺序，也可以全部逆序）中取出一连续子列（刀具的一种转换方案），再任取一种孔型，得到其所需加工刀具的加
15、工次序，则子列中至少有一对元素（子列中的两个元素组成有序对）的次序与加工次序相同（该转换方案可行），则这个子列的元素个数减1就为n。使得n达到最小的子列以下就称最优子列。用MATLAB进行穷举得到这个最优子列为d,c,b,a,h,g,f,e,d,c，有10个元素，所以最少转换次数n=9。得到转换方案及对应打孔的孔型如图2图2 刀具转换方案及对应加工的孔型根据刀具的转换方案我们将孔型分成9类即D,G，E，B，A,C，F,H，F,C，E,G,F，D,I，C,I,J。每一类型里面的孔在大的时候是没有分先后顺序的，如D,G这一类型中，D孔和G孔打得顺序是无约束的，可以先打D孔也可以先打G孔还可以打了一个D孔再打一个G孔再打一个D孔。对于，可以这样考虑：（5-3）
