“深圳杯”全国大学生数学建模D题答案.docVIP

打孔机生产效能的提高 中文摘要： 基于过孔是印刷线路板（也称为印刷电路板）的重要组成部分之一，过孔的加工费用通常占制板费用的30%到40%，打孔机主要用于在制造印刷线路板流程中的打孔作业。打孔机在加工作业时，钻头的行进时间和刀具的转换时间是影响生产效益的两个因素。因此在完成一个电路板的过孔加工时，钻头行进时间和刀具转换总时间越短，生产效益就越高。钻头行进总时间由钻头进行路线决定，而刀具转换总时间由线路板上由各孔的位置以及钻头行进方案决定。首先对刀具行进路径进行建模，应用蚁群算法对行进的最优线路进行求解，并得出刀具行进时间。考虑刀具转换一次的时间均大于一块电路板上任意某个孔型的打孔总时间，而若对所有的孔求最优路线，刀具转换的总时间将非常大（不符合实际生产），故采用刀具转换次数最少的方案作为刀具转换方案，通过刀具转换方案求的最优行进路经的总和，同时求得刀具转换的最优时间。再根据钻头行进总成本和刀具转换总成本，可得单钻头作业成本。 当打孔机设计成双钻头时，由于作业时各钻头相互独立，且有合作间距的限制，因此在解决双钻头最优作业方案时，我们在单钻头作业的基础上，对双钻头的孔群加工优化路径进行数学建模，采用遗传算法双质点操作对行进的最优线路进行求解，得出双转头行进的最优时间，同时保证两转头行进间距在要求范围之内。利用分析单钻头的行进时间和作业成本的方法，得出双钻头的在最优作业路线条件下的行进时间和作业成本。 关键字：打孔机 生产效能 蚁群算法 最短路径 问题重述： 附件1提供了某块印刷线路板过孔中心坐标的数据，单位是1/100密尔（mil）（也称为毫英寸，1 inch=1000 mil），请给出单钻头作业的最优作业线路（包括刀具转换方案）、行进时间和作业成本。 为提高打孔机效能，现在设计一种双钻头的打孔机（每个钻头的形状与单钻头相同），两钻头可以同时作业，且作业是独立的，即可以两个钻头同时进行打孔，也可以一个钻头打孔，另一个钻头行进或转换刀具。为避免钻头间的触碰和干扰，在过孔加工的任何时刻必须保持两钻头间距不小于3cm（称为两钻头合作间距）。为使问题简化，可以将钻头看作质点。 （i）针对附件1的数据，给出双钻头作业时的最优作业线路、行进时间和作业成本，并与传统单钻头打孔机进行比较，其生产效能提高多少？ （ii）研究打孔机的两钻头合作间距对作业路线和生产效能产生的影响。 打孔机生产效能的提高 问题分析 本文就提高某打孔机的生产效能而做出分析，所谓生产效能就是指单位时间内的生产能力、加工效率。所以要提高打孔机的生产效能，我们可以使钻头行进时间和刀具转换总时间尽量短，所得到的生产效益会更高。 对于单钻头，我们首先画出所有点的分布图，确定该电路板的对角线大概是，而且行进速度是，粗略估计行进的时间不会很长。对行进的速度和刀具的转换时间考虑，发现刀具的转换时间要比行进时间大得多，所以我们便想做到刀具的转换时间最短，才是最优的方法。所以我们使用蚁群算法，计算出所有点的最短距离和刀具转换次数最少所要走的最短距离，将两者进行比较，得到最优结果。 对于双钻头，因为两钻头可以同时作业，（称为两钻头合作间距），我们运用遗传算法做出最优作业线路图，计算得出最优结果。 模型假设 单个过孔的钻孔作业时间，这是由生产工艺决定，为了简化问题，现假定对于同一孔型钻孔作业时间都是相同的； 为了计算行进费用，需要计算行进时间，为了简化问题，这里假定打孔机的行进是匀速的运动。 假定针对不同孔型加工作业时，刀具的转换时间相同； 在计算两孔之间距离时，为简化问题，假设打孔机的钻头为一质点。 为避免钻头间的触碰和干扰，假定保持两钻头间距于1、单钻头模型： 对于其一给定尺寸的孔，调整好对应的刀具后，从下刀点开始沿着使该刀具总路程最短的轨迹，从一个孔移动到另一个孔，直到该类孔中的所有对象都被加工完毕，再转换刀具进行下一尺寸的其它孔的加工，如此安排。把问题描述成以下优化模型： 变量设计。设有n个孔的集合……，设表示集合中任意两孔、表示集合中两孔之间的距离、M为行进总路程。 目标函数。需要在孔集合中，找到一个不重复的全排列，令，求M的最小值。 约束条件：加工路径从一个孔出发，对每一个孔只加工一次遍历每一个孔，最后回到起点，包括刀具转换在内。 优化算法：蚁群算法。 图一：刀具的转换流程及刀具对应的打孔孔型 2、双钻头模型：双钻头在孔群加工中，两个钻头同时加工，每个钻头加工时间并不确定，那么单一工间的加工时间由耗时较长的钻头决定。 假设两个钻头的对刀点分别为 和，和分别表示第一个钻头加工的第i 个孔和第2 个钻头加工的第j 个孔，则两条加工路径、分别为