深圳杯全国大学生数学建模D题答案

1、打孔机生产效能的提高中文摘要：基于过孔是印刷线路板（也称为印刷电路板）的重要组成部分之一，过孔的加工费用通常占制板费用的30%到40%，打孔机主要用于在制造印刷线路板流程中的打孔作业。打孔机在加工作业时，钻头的行进时间和刀具的转换时间是影响生产效益的两个因素。因此在完成一个电路板的过孔加工时，钻头行进时间和刀具转换总时间越短，生产效益就越高。钻头行进总时间由钻头进行路线决定，而刀具转换总时间由线路板上由各孔的位置以及钻头行进方案决定。首先对刀具行进路径进行建模，应用蚁群算法对行进的最优线路进行求解，并得出刀具行进时间。考虑刀具转换一次的时间均大于一块电路板上任意某个孔型的打孔总时间，而若对所有

2、的孔求最优路线，刀具转换的总时间将非常大（不符合实际生产），故采用刀具转换次数最少的方案作为刀具转换方案，通过刀具转换方案求的最优行进路经的总和，同时求得刀具转换的最优时间。再根据钻头行进总成本和刀具转换总成本，可得单钻头作业成本。当打孔机设计成双钻头时，由于作业时各钻头相互独立，且有合作间距的限制，因此在解决双钻头最优作业方案时，我们在单钻头作业的基础上，对双钻头的孔群加工优化路径进行数学建模，采用遗传算法双质点操作对行进的最优线路进行求解，得出双转头行进的最优时间，同时保证两转头行进间距在要求范围之内。利用分析单钻头的行进时间和作业成本的方法，得出双钻头的在最优作业路线条件下的行进时间和作

3、业成本。 关键字：打孔机 生产效能 蚁群算法 最短路径问题重述：1. 附件1提供了某块印刷线路板过孔中心坐标的数据，单位是1/100密尔（mil）（也称为毫英寸，1 inch=1000 mil），请给出单钻头作业的最优作业线路（包括刀具转换方案）、行进时间和作业成本。2. 为提高打孔机效能，现在设计一种双钻头的打孔机（每个钻头的形状与单钻头相同），两钻头可以同时作业，且作业是独立的，即可以两个钻头同时进行打孔，也可以一个钻头打孔，另一个钻头行进或转换刀具。为避免钻头间的触碰和干扰，在过孔加工的任何时刻必须保持两钻头间距不小于3cm（称为两钻头合作间距）。为使问题简化，可以将钻头看作质点。（i）

4、针对附件1的数据，给出双钻头作业时的最优作业线路、行进时间和作业成本，并与传统单钻头打孔机进行比较，其生产效能提高多少？（ii）研究打孔机的两钻头合作间距对作业路线和生产效能产生的影响。打孔机生产效能的提高1. 问题分析本文就提高某打孔机的生产效能而做出分析，所谓生产效能就是指单位时间内的生产能力、加工效率。所以要提高打孔机的生产效能，我们可以使钻头行进时间和刀具转换总时间尽量短，所得到的生产效益会更高。对于单钻头，我们首先画出所有点的分布图，确定该电路板的对角线大概是，而且行进速度是，粗略估计行进的时间不会很长。对行进的速度和刀具的转换时间考虑，发现刀具的转换时间要比行进时间大得多，所以我们

5、便想做到刀具的转换时间最短，才是最优的方法。所以我们使用蚁群算法，计算出所有点的最短距离和刀具转换次数最少所要走的最短距离，将两者进行比较，得到最优结果。对于双钻头，因为两钻头可以同时作业，且作业是独立的，即可以两个钻头同时进行打孔，也可以一个钻头打孔，另一个钻头行进或转换刀具。为避免钻头间的触碰和干扰，现假设在过孔加工的任何时刻必须保持两钻头间距等于（称为两钻头合作间距），我们运用遗传算法做出最优作业线路图，计算得出最优结果。2. 模型假设1) 单个过孔的钻孔作业时间，这是由生产工艺决定，为了简化问题，现假定对于同一孔型钻孔作业时间都是相同的； 2) 为了计算行进费用，需要计算行进时间，为了

6、简化问题，这里假定打孔机的行进是匀速的运动。3) 假定针对不同孔型加工作业时，刀具的转换时间相同； 4) 在计算两孔之间距离时，为简化问题，假设打孔机的钻头为一质点。5) 为避免钻头间的触碰和干扰，假定保持两钻头间距不小于3. 模型建立1、单钻头模型： 对于其一给定尺寸的孔，调整好对应的刀具后，从下刀点开始沿着使该刀具总路程最短的轨迹，从一个孔移动到另一个孔，直到该类孔中的所有对象都被加工完毕，再转换刀具进行下一尺寸的其它孔的加工，如此安排。把问题描述成以下优化模型：1) 变量设计。设有n个孔的集合，设表示集合中任意两孔、表示集合中两孔之间的距离、M为行进总路程。2) 目标函数。需要在孔集合中

7、，找到一个不重复的全排列，令，求M的最小值。3) 约束条件：加工路径从一个孔出发，对每一个孔只加工一次遍历每一个孔，最后回到起点，包括刀具转换在内。4) 优化算法：蚁群算法。EGFGJBDGDIACdegfhabcfCEIJFH1次1次1次1次1次1次1次3次图一：刀具的转换流程及刀具对应的打孔孔型2、双钻头模型：双钻头在孔群加工中，两个钻头同时加工，每个钻头加工时间并不确定，那么单一工间的加工时间由耗时较长的钻头决定。假设两个钻头的对刀点分别为 和，和分别表示第一个钻头加工的第i 个孔和第2 个钻头加工的第j 个孔，则两条加工路径、分别为 约束条件：任意一个待加工的孔必须包括在其中一条加工路

8、径中，且加工过程中两个钻头不发生碰撞。4. 模型求解4.1单钻头问题结果分析对于单钻头生产方式，钻孔方式上采用一种刀具钻完对应的全部孔在转换刀具进行下一种刀具对其对应孔型的钻取方式，工作路线采用蚁群算法，通过MATLAB进行数据处理，得出相应路径最优图形如下（按顺序依次为刀具:dàeàfàgàhàaàbàcàf孔型:DGàDIàJàFGàHFàACàBàCEIJàEG）。图1-DG孔型路线图2-DI孔型路线图3-J孔型路线图4-FG孔型

9、路线图5-FH孔型路线图6-AC孔型路线图7-B孔型路线图8-CEIJ孔型路线图9-EG孔型路线图10-电路板上所有点的路线图11-所有孔型的分布图下表为各刀具的行程（单位： mil）刀具defghabcf行程5.92575.95274.66613.23753.094112.58611.57311.1234.8309时间/s8.3618218.3999216.5843864.5684724.36611917.7602416.3307915.695796.816937依上表可知，在单钻头作业的最优线路条件下，可得各种刀具作业路程总和为：62.989e+004 mil。以下为我们为各刀具设定的始终

10、点（1/100mil）：defghabcfx-267400-257400-222047-301300-311300-202800-197600-202800199800y1845181845181000008430074300190200180800190200203200上表各点距离和为选取转换前进的路程1.2471e+004mil，则加上前进的路程，可知该路线总路程为 Shortest_Length= 64.2361e+004(mil)=16315.97（mm）所有钻头的行进速度都是相同的，为，且所有钻头的刀具钻换时间为12*18=216（s）时间方面：作业行进时间=最短距离/钻头行进速度

11、=90.64427（s）作业总时间=钻头行进时间+钻头转换时间=306.64（s）成本方面：行进成本=行进时间*行进成本=978.9594(元)作业转换成本=转换次数*转换成本=25.2（元）作业总成本=行进成本+作业转换成本=1004.159（元）即：此法生产，需用时306.64（s），耗费1004.159（元）。4.2双钻头问题结果分析我们现在在模型建立上有一些想法，但是在利用算法实现想法的过程中遇到一些困难，因此并没有成功通过算法把更优的解算出。5. 模型评价与改进该模型的分析过程清晰、简单易行，且经得住实践的考验。在单钻头问题上，此模型采取了单刀具对应孔型完成再进入下一道具的方式，即任

12、一种刀具，先完成其所能钻取的孔型后，再进入下一孔型的钻取，而每种刀具的工作路线都是通过蚁群算法方式得出的最优解。如此操作，既减少了道具不断转换带来的时间损耗，提高了作业效率，又可以尽可能降低作业的成本。本模型是一比较高效率的生产模型，却不是一个十分省钱的生产模型，1000多元的生产成本确实是高了些。而对于双钻头模型问题，此模型采用遗传算法，以遗传算法双质点操作优化的优势，取代了单钻头问题中蚁群算法只能单质点优化路线的缺陷，是较为优化的。本文只通过一组试验数据分析得出结果，会有误差，所以在此基础上，用多组数据分析，会更好的减小误差，也可以对做模型进行进检验。总的来说该模型还是能比较完整的解决问题

13、的！参考文献【1】 姜启源等，数学模型（第四版），北京：高等教育出版社，2011【2】 韩明，王家宝等，数学实验，上海：同济大学出版社，2009【3】 罗万成，大学生数学建模案例精选，成都：西南交通大学出版社，2007【4】 周明, 孙树栋，遗传算法原理及应用，北京：国防工业出版社，2005【5】 李士勇，陈永强，蚁群算法及其应用，哈尔滨：哈尔滨工业大学出版社，2004【6】 曾峰等，印刷电路板（PCB）设计与制作，北京：电子工业出版社，2002附录：m=10;Alpha=1;Beta=5;Rho=0.1;NC_max=200;Q=100; %为使程序运行速度更快，取蚂蚁数为10c=x,y;n

14、=size(c,1); %n表示问题的规模（电路板上孔的个数）D=zeros(n,n); %D表示完全图的赋权邻接矩阵for i=1:n for j=1:n if i=j D(i,j)=(c(i,1)-c(j,1)2+(c(i,2)-c(j,2)2)0.5; else D(i,j)=eps; %i=j时不计算，应该为0，但后面的启发因子要取倒数，用eps（浮点相对精度）表示 end D(j,i)=D(i,j); %对称矩阵 endendEta=1./D; %Eta为启发因子，这里设为距离的倒数Tau=ones(n,n); %Tau为信息素矩阵Tabu=zeros(m,n); %存储并记录路径的

15、生成NC=1; %迭代计数器，记录迭代次数R_best=zeros(NC_max,n); %各代最佳路线L_best=inf.*ones(NC_max,1); %各代最佳路线的长度L_ave=zeros(NC_max,1); %各代路线的平均长度while NC<=NC_max %停止条件之一：达到最大迭代次数，停止 % 蚁群算法MATLAB程序第二步：将m只蚂蚁放到n个孔上 Randpos=; %随即存取 for i=1:(ceil(m/n) Randpos=Randpos,randperm(n); end Tabu(:,1)=(Randpos(1,1:m)'% 蚁群算法MAT

16、LAB程序第三步：m只蚂蚁按概率函数选择下一个孔，完成各自的周游 for j=2:n %所在孔不计算 for i=1:m visited=Tabu(i,1:(j-1); %记录已打过的孔，避免重复访问 J=zeros(1,(n-j+1); %待打的孔 P=J; %待打孔的选择概率分布 Jc=1; for k=1:n if length(find(visited=k)=0 %开始时置0 J(Jc)=k; Jc=Jc+1; %打过的孔个数自加1 end end% 下面计算蚁群算法MATLAB程序待打孔的概率分布 for k=1:length(J) P(k)=(Tau(visited(end),J(

17、k)Alpha)*(Eta(visited(end),J(k)Beta); end P=P/(sum(P);% 按概率原则选取下一个孔 Pcum=cumsum(P); %cumsum，元素累加即求和 Select=find(Pcum>=rand); %若计算的概率大于原来的就选择这条路线 to_visit=J(Select(1); Tabu(i,j)=to_visit; end end if NC>=2 Tabu(1,:)=R_best(NC-1,:); end% 蚁群算法MATLAB程序第四步：记录本次迭代最佳路线 L=zeros(m,1); %开始距离为0，m*1的列向量 fo

18、r i=1:m R=Tabu(i,:); for j=1:(n-1) L(i)=L(i)+D(R(j),R(j+1); %原距离加上第j个孔到第j+1个孔的距离 end L(i)=L(i)+D(R(1),R(n); %一轮下来后走过的距离 end L_best(NC)=min(L); %最佳距离取最小 pos=find(L=L_best(NC); R_best(NC,:)=Tabu(pos(1),:); %此轮迭代后的最佳路线 L_ave(NC)=mean(L); %此轮迭代后的平均距离 NC=NC+1 %迭代继续% 蚁群算法MATLAB程序第五步：更新信息素 Delta_Tau=zeros(n,n); %开始时信息素为n*n的0矩阵 for i=1:m for j=1:(n-1) Delta_Tau(Tabu(i,j),Tabu(i,j+1)=Delta_Tau(Tabu(i,j),Tabu(i,j+1)+Q/L(i); %此次循环在路径（i，j)上的信息素增量 end Delta_Tau(Tabu(i,n),Tabu(i,1)=Delta_Tau(Tabu(i,n),Tabu(i,1)+Q/L(i); %此次循环在整个路径上的信息素增量 end Tau=(1-Rho).*Tau+Delta_Tau; %考虑信息素挥