打孔机论文.doc

福建工程学院2012年第九届数学建模竞赛答卷论文D题打孔机生产效能的提高小组成员： 陈晓星 男 邱振涛 男 留雅珊 女 日期:2012-5-20打孔机生产效能的提高摘要 本文就打孔机生产效能的提高，运用jave和分析法建立数学模型，针对实际问题，分别考虑两条原则：，路径和转换方式最优原则，时间最优原则建立模型。由于两个问题都为优化问题，我们用类似最小生成树方法求解钻头行进路程的最短路径，以图论结合的方法分析最优刀具转换方式。针对问题一，根据题目提供的印刷线路板过孔中心坐标数据，我们利用matlab 画出了坐标分布图（见附录）。分析其点分布，发现defghabcdef 这种刀具转换方式不仅能保证每个点都打到且转换次数最少，这样就不仅降低了转换成本,而且也使转换时间缩小到最少的。运用java 程序模仿最小生成树设计快速算法，求出各种孔型各自分布点的最短路径及路径的首尾坐标。根据各种孔型之间的打孔顺序将前一种孔型求出的最短路径的最后一点坐标与后一孔型的第一点坐标相连，即得到钻头行进的最优路径。经过我们的反复计算，最终行进总路程为1633.72cm，行进时间为1727.21，作业成本为1001.23元。对于问题一，我们仿照问题二分区域的方法，进行了优化，用牺牲刀具的转动时间来做到减短钻头所行总路线，将其划分为三个区域，钻头根据区域依次行走，经过计算得出最终行进总路程为1475.96 cm，行进时间为2086.33s，作业成本为948.58元，相比原本的方法，此种方法虽时间稍微多一些，但钻头行进路程变短了，也降低了成本。针对问题二，由于是双钻头的打孔机，且作业是独立的，但为避免钻头间的触碰和干扰，我们采取了分区域的做法，即两个钻头分开作业。根据分析，决定将其分为四个区域并根据各个区域各种孔型分布特点，求出最短刀具转换方式，除了其中第二个区域是fghabcdef，其余皆为defghabcdef，求解方法与问题一相似，经过统计和计算，最终行进总路程为1407.86cm，行进时间为1534.32s，作业成本为924.516元。与单钻头比较时间效率提高了552.01s，缩短了钻头的行进路程，成本降低了24.06元。关键字: java matlab 最小生成树 1问题的提出 打孔机主要用于制造印刷线路板流程中的打孔作业。为提高生产效能，需进行合理的作业安排，设计加工一块线路板的最优计划，需考虑以下几个方面：(1)单个过孔的钻孔作业时间，这是由生产工艺决定；(2)打孔机在加工作业时，钻头的行进时间；(3)针对不同孔型加工作业时，刀具的转换时间。在给定的某种砖头，上面装有8种刀具a,b.c ,h,依次排列呈圆环状，如图 1所示： 图1：某种钻头8种刀具的分布情况而且8种刀具的顺序固定，不能调换。加工作业时，一种刀具使用完毕后，可以转换使用另一种刀具。相邻两刀具的转换时间为18s。作业时，可采用顺（逆）时针旋转的方式转换刀具。将任一刀具转换至其它刀具处，所需时间是相应转换时间的累加。为简化问题，假定钻头的行进速度是相同的，为180mm/s，行进成本为0.06元/mm，刀具转换的时间成本为7元/min。刀具在行进过程中可以同时进行刀具转换，但相应费用不减。 不同刀具加工不同孔型，表一列出了10种孔型所需加工刀具及加工次序（标*者表示该孔型对刀具加工次序没有限制）。表1：10种孔型所需加工刀具及加工次序孔型ABCDEFGHIJ所需刀具aba, cd, e*c, fg, h*d, g, fhe, cf, c 同一线路板上的过孔不要求加工完毕一个孔，再加工令一个孔，即对于须用两种或两种以上刀具加工的过孔，只要保证所需刀具加工次序正确即可。要求：根据提供的数据给出单钻头的最优作业线路（包括刀具转换方案）、行进时间和作业成本；(2)设计一种双钻头的打孔机，（每个钻头的形状与单钻头相同），两钻头可以同时作业，且作业是独立的，即可以两个钻头同时进行打孔，也可以一个钻头打孔，另一个钻头行进或转换刀具。为避免钻头间的触碰和干扰，在过孔加工的任何时刻必须保持两钻头间距不小于3cm（称为两钻头合作间距）。为使问题简化，可以将钻头看作质点。(i)针对附件1的数据，给出双钻头作业时的最优作业线路、行进时间和作业成本，并与传统单钻头打孔机进行比较，其生产效能提高多少？(ii)研究打孔机的两钻头合作间距对作业路线和生产效能产生的影响。2问题分析问题（一）分析： 本题为优化问题，主要是考虑钻头行进的成本和时间，以及转换刀具的成本和时间，找到走遍所有点的最优路径，使得打孔机的生产效能达到最高。根据题目提供了印刷线路板过孔中心坐标的数据，我们利用matlab画出了坐标分布图（见附录1）。发现同种孔型，有分布集中的，也有分布较为分散的。又由于钻头行进速度，行进成本和刀具转换时间成本不变，因此只要尽可能找到钻头行进的最短路程及求出刀具的最少转换次数即可。为确定钻头行进的行进路程，我们采用了类似最小生成树的方法，求出各种孔型各自分布点的最短路径及路径的首尾坐标。通过画图与分析，找到了最优的刀具转换方式，并因此确定各种孔型之间的打孔顺序。最后根据各种孔型之间的打孔顺序将前一种孔型求出的最短路径的最后一点坐标与后一孔型的第一点坐标相连，即得到钻头行进的最优路径。问题（二）分析：本题的主要问题与问题一差不多，也是要求打孔机的最高生产效能。印刷线路板过孔中心坐标的数据与问题一一样，不同的是，本题是双钻头的打孔机（每个钻头的形状与单钻头相同），且作业是独立的，但为避免钻头间的触碰和干扰，在过孔加工的任何时间必须保持两钻头间距不小于3cm。基于这两个条件，我们采取了分区域的做法，即两个钻头分开作业，这样就能够很好地避免钻头间的触碰和干扰。由点的分布图分析，最终分成四块区域，按照区域分布特点，确定刀具转换方式与各种孔型之间的打孔顺序。按照问题一的方法依次求出各个区域最短行进路程，加总即为最路程。3.模型假设(1)打孔时的时间设为每打一次为0.5s；(2)钻头行进过程平稳，不发生故障；(3)钻头行进灵活，可自由改变方向；(4)钻头行进速度是相同的；(5)相邻刀具转换时间是固定的；(6)钻头看作质点。 4.定义与符号说明 .钻头行进的路程 . 加工一块板所需时间 .加工一块板总的成本 .钻头行进的成本 .刀具的转换成本 .刀具的转换次数 打一个孔所用时间，设为常量0.5秒.表示打孔的次数 .刀具行进的单价(元/mm).转换刀具的单价(元/min) .钻头行进的速度 .对应下标区域钻头的行进成本i=1，2，3 对应区域内钻头的行进路程k=1，2，3 .按顺序不同刀具行进的路程 第i个刀具转到第j个刀具时所走的路程.第k个钻头所走的路程.第k个钻头的刀具转换时间k=1,2.第k个刀具打到的钻孔的个数k=1,2 .转换刀具所花费的时间 .钻头的行进时间 .打孔时间5.模型建立与求解问题一：（一）模型的分析与建立： 求最短距离时，我们采用了类似最小生成树的原理。例如：若有五个顶点1,2,3,4,5，原理如下：45321原理说明：从图A各条路径中选出最短路径，即2，顶点为3和4，标记顶点3和顶点4，连接最短路，得到图B；接着以顶点3和4为顶点，找出与顶点3和4相连的最短路，即为3，顶点为2和3，并作标记，连接最短路，得到图C；如此一来，顶点3被标记两次，视为无效点（即不可再被标记），接着以顶点2和4为顶点同理可得图D，图E，最终最短路径为或相反方向。最优化刀具转换方式分析：虽然孔型A和孔型B的数量占据了很大一部分，但是由于它们都是单刀具型的，对钻头转换方式没什么影响。另外，虽然钻型D和钻型F需要两种刀具，但是它们并没有要求顺序，对钻头转换方式也基本没有什么大的影响，所以我们去除了孔型A、B、D和F，优先考虑其他孔型。在不考虑单钻头和没有次序限制的钻孔下，对剩下的钻孔的钻头转换进行详细列出，得图2：C: abc ahgfedcE: cdef cbahgfG: defg gf dcbahg ghabcdefI: efghabc 有很大的相似之处 edcJ: fghabc fedc表示箭头尾部的钻头方式属于箭头指向方式的一部分图2：钻头转换方式分析图孔型G需要有三种刀具，所以我们选择优先考虑孔型G的钻头转换方式，通过与其他钻孔钻头进行比较（由图2中箭头体现），我们确定了一条比较理想的钻头转换方式线路：defghabcdef又根据确定的刀具转化方式，我们可以确定各种孔型之间的打孔顺序，如图3所示：图3：打孔顺序排列因为在刀具转换的时候，钻头本身还可以保持移动，且钻头的移动速度非常快，所以图上两个空方框之间就无需再考虑时间问题，即只需考虑其转换时间。因此：成本=转换刀具的花费+每个时期对应刀具的钻头行进路程的花费即：Min （二）模型的求解： 运用类似最小生成树的方法，用java设计程序（见附录2），求得钻头行走各种孔型最短路径的各个端点坐标及路程，见表1：表1：各种孔型最短路径的端点坐标及路径的相关信息孔型端点一坐标(x,y)（cm）端点二坐标(x,y)（cm）路程（cm）时间（s）A-3.082.526.8518.92153.998.5B-5.99-1.50-7.3818.94304.2816.9C8.0613.758.92-1.66217.2312.1D-7.1112.872.2623.36134.027.5E-1.0521.382.243.2597.985.4F0.1221.262.3421.2666.173.68G-8.16-1.585.1422.6734.131.89H8.062.78-8.119.9423.731.32I12.4515.5712.4521.5136.392.02J-6.82-1.6611.3714.54144.406.36通过比较坐标图中所有钻孔线路的端点，获得每种刀具及转换时所走的路程，如下表所示：表二：使用各刀具所走路程及其他相关信息刀具为孔型所需要最短路程（所有孔点及不同孔点之间的和）(cm)转换下一刀具的路程(cm)路程之和(cm)时间（s）打的孔数(个)dGD153.330153.338.51232eDI155.6112.68168.299.34222fJ114.4010.08124.486.9129gGF77.812.9280.734.4854hFH71.609.2680.864.4940aAC320.771.11321.8817.881030bB304.284.40308.6817.14787cCJIE278.330278.3315.46404d-000e000fEG117.140117.146.5115合计：-1633.7290.712913结果：t1=18*10=180st2=90.71st3=2913*0.5=1456.5sT=t1+t2+t3=1727,21sS=1633.72cmQ=0.06*10*1633.72+（10*18）/60*7=1001.23（元）问题一的优化： 为了优化问题：我们设计了分区域打孔，从坐标图我们肉眼直观的分为三个区域，第一区域为x-5cm,y不限制的长方形区域，第二部分为-5cmx，且y15cm的长方形区域。第三部分为-5cm15cm的长方形区域。min 每个区域的刀片转动的顺序还是d-e-f-g-h-a-b-c-f，我们用牺牲刀具的转动时间来做到减短钻头所行总路线，下面是我们针对每个区域所求的时间和所行的最短径。表三：第一区域路程及时间刀具所需大的孔点最短路程（所有孔点及不同孔点之间的和）(cm)转换下一刀具的路程(cm)路程之和(cm)时间（s）打的孔数(个)dGD56.26056.263.12101eDI46.966.1453.12.9591fJ29.2110.9140.122.2210gGF8.840.359.190.51120hFH12.9211.7524.671.376aAC40.461.1241.582.3155bB65.704.4170.113.89167cCIJE49.861.0650.922.8377d-0000e0000fEG21.083.9825.061.3927合计：-371.0120.59654刀具所需大的孔点最短路程（所有孔点及不同孔点之间的和）(cm)转换下一刀具的路程(cm)路程之和(cm)时间（s）打的孔数(个)dGD50.74050.742.8254eDI50.7410.0160.753.3754fJ42.0010.1652.162.8914gGF6.3613.4619.821.1010hFH30.283.0033.281.8514aAC189.8111.04200.8511.16838bB188.571.34189.9110.55588cCIJE127.975.49133.467.41259d-0000e0000fEG48.8811.6960.573.3659合计：-801.5444.511890 表四：第二区域路程及时间刀具所需大的孔点最短路程（所有孔点及不同孔点之间的和）(cm)转换下一刀具的路程(cm)路程之和(cm)时间（s）打的孔数(个)dGD30.245.7339.972.2277eDI39.497.5847.079.3477fJ23.013.5426.552.625gGF17.983.3821.361.1924hFH14.366.3420.801.1620aAC32.565.3837.942.1137bB16.615.3421.951.2132cCIJE56.487.0063.483.5368d-0000e0000fEG24.29024.291.3529合计：-303.4124.73369表五：第三区域的路程及时间结果：t1=18*10*3=540st2=20.59+44.51+24.73=89.83st3=（654+1890+369）*0.5=1456.5sT=t1+t2+t3=2086.33sS=371.01+801.54+303.41=1475.96 cmQ=0.06*10*1475.96+3*（10*18）/60*7=948.58（元）问题二：（一） 模型的分析与建立： 由于是双钻头的打孔机，且作业是独立的，但为避免钻头间的触碰和干扰，在过孔加工的任何时刻必须保持两钻头间距不小于3cm，因此我们采取了分区域的做法，即两个钻头分开作业，这样能够很好地避免钻头间的触碰和干扰。根据分析，决定将其分为四个区域，设两个钻头为钻头A和钻头B，钻头A行走区域一（x-5）和区域二（5x0），钻头B行走区域三（0x5），当钻头A走区域一时，钻头B走区域三，并根据各个区域各种孔型分布特点，得出各个区域刀具转换形式，见下列各表：区域一、三、四的刀具转换方式：区域二的刀具转换方式：目标函数：min （二） 模型的求解：同样地运用类似最小生成树的方法，用java设计程序（见附录3），求得各个区域钻头A，B行走各种孔型最短路径的各个端点坐标及路程，结果见下列各表： 表六：区域一（x-5）钻头A所走的路程及时间刀具所需大的孔点最短路程（所有孔点及不同孔点之间的和）(cm)转换下一刀具的路程(cm)路程之和(cm)时间（s）打的孔数(个)dGD48.27048.272.68101eDI40.978.0048.972.7291fJ29.218.3437.552.0910gGF9.6409.640.5420hFH12.930.8713.800.776aAC34.464.4138.872.1655bB55.7010.4065.103.62167cCIJE40.47040.472.2571d-0000e0000fEG21.08021.081.1727合计：- 323.7518.00548表七：区域二（-5x0）钻头A所走的路程及时间刀具所需大的孔点最短路程（所有孔点及不同孔点之间的和）(cm)转换下一刀具的路程(cm)路程之和(cm)时间（s）打的孔数(个)fJ18.926.2625.181.403g00000hH09.769.760.541a AC89.088.0797.155.40424bB96.052.7298.775.49336cJIEC41.992.4054.393.0299dD12.87012.870.7119eD12.874.0616.840.9419f E20.99020.991.1616合计：-335.9518.66917表八：区域三(0x5)钻头B所走的路程及时间刀具所需大的孔点最短路程（所有孔点及不同孔点之间的和）(cm)转换下一刀具的路程(cm)路程之和(cm)时间（s）打的孔数(个)dGD42.06042.062.3419eDI40.611.2441.852.3218/fJ25.305.9731.271.748gGF22.70022.701.2631hFH6.300.737.030.3929aAC26.265.7331.991.78276bB50.844.9155.753.10154cCIJE63.21063.213.51117d-0000e-0000fEG27.13027.131.5147合计：-322.9917.95699t1=18*10*3+18*8=684s；t2=23.66+18.66=42.32s；t3=（699+917）*0.5=808s；T=t1+t2+t3=1534.32sS= 323.75+335.95+425.17+322.99=1407.86 cm Q=0.06*10*1407.86+（10*18*3+18*8）/60*7=924.516（元）6.模型评价与推广优点：由于打孔的数量太多,如果以传统的遗传算法或者是蚂蚁算法去求解问题，这将会花费非常多的时间在计算孔点的距离。通过我们自行设计的快速算法，可以在较短时间内得到孔点间相对较优的路程。另外，通过分析刀具转换方式与孔点的关系，我们设计的刀具转换方式也大大缩小了加工钢板的时间，这对于加工厂来说，就能过大大地提高产量。缺点：虽然我们缩短了计算孔点之间的距离，但由于我们算法也存在一定的缺陷，所以在获得最短路程上，我们可能得不到最短的路径，导致加工钢板的成本会比较高。参考文献：1刘焕彬 库在强，数学模型与实验，北京：科学出版社，2008 2姜启源，谢金星等，数学模型，北京：高等教育出版社，20113 肖华勇，数学建模竞赛优秀 论文精选与点评，西北工业大学出版社，20074 Fred Buckley等（著），李慧霸等（译）图论简明教程，清华大学出版社，2005 5韩明等，数学实验，同济大学出版社，2009附录一（孔点分布图）：孔点分布图：附录二（程序）：（一）：public class T public T() / TODO Auto-generated constructor stubpublic String row1()return ./bin/three/AC1.txt;public String row2()return ./bin/three/AC2.txt;void min()int p1=new Zh().read(new T().row1(); /读取文件 我们要的是个数int p2=new Zh().read(new T().row2(); /读取文件 我们要的是个数int p=new intp1.length; /储存位置（多少点）的数组/int q=new intp1.length;for(int i=0;ip1.length;i+) pi=i+1;/qi=i+1;/* * 规划坐标的位置（点数） 例：第五个坐标我们设为5 */int k=new int2; /定义储存在运行的点的数组int dox=0; /表示被定义为无效点的个数double sum=0; /路程值int m1=0,m2=0,m = 0; /临时值，储存临时的位置double w=new Zh().row(); /获得两点之间的距离for(int i=0;ip1.length;i+)for(int j=0;jp1.length;j+)if(wij=0)wij=99999999999.9999999;/设为无穷大/* * 将无效距离（既自己与自己的距离设为无穷大） */System.out.println(wij);double min=w00; /设一开始的最短距离为无穷大for(int i=0;ip1.length;i+)for(int j=0;jp1.length;j+)if(wijmin)min=wij;k0=i;k1=j;/* * 在存有众多距离的数组中找出最短距离，作为开始 */sum=sum+min;/System.out.println(sum);while(doxp1.length-2)for(int i=0;ip.length;i+)if(pi!=0)m=pi;break;/* * 找出运行到还有效的位置；无效为0 */min=wk0m-1;m1=k0;m2=m-1;/* * 设循环这一次最初的最小距离min； * 临时的m1和m2位置（既它有可能成为k数组的值） */for(int j=0;jp.length;j+)if(pj!=0) /排除为0的无效位置 if(pj-1)!=k1&wk0pj-1min) /排除路线会围成一圈 min=wk0pj-1; m1=k0; m2=pj-1; /* * 得到临时的min值和它的位置； */ if(pj-1)!=k0&wk1pj-1min) /排除路线会围成一圈min=wk1pj-1;m1=k1;m2=pj-1;/* * 得到临时的min值和它的位置； */ sum+=min;/当前路程if(m1=k0)dox+; /无效位置个数循环一次加一pk0=0; /无效位置设为0k0=m2; /替换被围绕运行的位置else dox+; /无效位置个数循环一次加一pk1=0; /无效位置设为0k1=m2; /替换被围绕运行的位置for(int i=0;ip.length;i+)if(pi!=0)System.out.println(p1pi-1*0.0000254+ +p2pi-1*0.0000254);/* * 得到最后还有效的两个位置，确定起点和终点 */System.out.println(sum*0.0000254); /* * param args */public static void main(String args) / TODO Auto-generated method stubnew T().min();（二）：import java.io.BufferedReader;import java.io.FileReader;public class Zh /* * */public Zh() / TODO Auto-generated constructor stubpublic int read(String s) BufferedReader dos=null;StringBuffer s2=new StringBuffer();trydos=new BufferedReader(new FileReader(s);String fos=null;s2.append(dos.readLine();while(fos=dos.readLine()!=null)s2.append( +fos);/System.out.print(s2);catch(Exception e)e.printStackTrace();finallytrydos.close();catch(Exception e)e.printStackTrace();String s3=s2.toString().split( );int s4=new ints3.length;for(int i=0;is3.length;i+)s4i=Integer.parseInt(s3i);return s4;public double row()Zh zh=new Zh();int p1=zh.read(new T().row1();int p2=zh.read(new T().row2();int p=new intp1.length;int q=new intp1.length;double w=new doublep1.lengthp2.length;for(int i=0;ip1.length;i+)pi=i+1;qi=i+1;for(int i=0;ip1.length;i+)for(int j=0;jp2.length;j+)wij=Math.sqrt ( (Math.pow(p1i-p1j), 2)+Math.pow(p2i-p2j), 2) );return w;/* * param args */public static void main(String args) / TODO Auto-generated method stubnew Zh().row();（三）：public class Xz public static void main(String args) / TODO Auto-generated method stubint p1=new Zh().read(new T().row1(); int p2=new Zh().read(new T().row2(); StringBuffer s=new StringBuffe