《2012山东科技大学数学建模竞赛》由会员分享，可在线阅读，更多相关《2012山东科技大学数学建模竞赛（20页珍藏版）》请在金锄头文库上搜索。
1、2012山东科技大学数学建模竞赛承 诺 书我们仔细阅读了山东科技大学数学建模竞赛说明。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）： D 我们的参赛报名号为： 2005 所属学院（
2、请填写完整的全名）： 理学院 参赛队员 (打印并签名) ：1. 孙旭 2. 宋宾宾 3. 柴利云 日期： 2012 年 5 月 5日2012山东科技大学数学建模竞赛编 号 专 用 页评阅记录（可供评阅人评阅时使用）：评阅人评分备注最终成绩：打孔机生产效能的提高摘要本文是关于提高打孔机效能的问题，对钻头行进路线做出安排，使得成本降到最低。我们对附件中的坐标进行分类编号整理，在不同的情况下，单一化求解条件，使问题得到简化。打孔机的作业成本包括钻头作业、钻头行进成本和刀具转换的时间成本，其中钻头作业成本为固定值，将刀具转换成本降到最低的情况下寻求行进路程最短的方式建立模型1；在行进总路线最短的情况下
3、，计算出刀具转换成本建立模型2；将以上两方式结合起来寻求最佳方案建立模型3。问题一：模型1：最近邻点法模型，分析刀具转换的时间成本最低的情况，可知刀具转换次序为：逆时针dcbahgfedc，共转换9次。按每次换刀对应的刀具给钻孔分类，使用最近邻点法构建途程，然后利用2-opt法改善途程。模型2：遗传基因组合模型，在不考虑换刀的情况下，利用遗传算法将每个点看做染色体中的一个基因，生成若干群体，模仿生物进化，进行交叉，建立适应函数，求出函数的最优解，就是最短路线的方案。模型3：多目标优化模型，采用步骤法（STEM法）解决多目标优化问题。两个目标函数分别求最少道具转换和最小路程，通过整合得到最优解。
4、问题二：采用分区作业和互补合作的方式结合。先分别讨论分区作业和不同刀具合作的效率，再将二者结合，看其效率。分区作业即沿用问题一的3个模型即可求解，与问题一无异，用不同刀具互补则将两钻头沿对角线两端相对行进的方式打完整版。关键词： 最近邻点法 遗传算法 步骤法 2-opt改善途程 TSP一、问题重述：过孔是印刷线路板的重要组成部分之一，印刷电路板的制板费用的30%到40%是用在过孔上，合理的过孔方案可以提高效率，节约成本。打孔机的生产效能主要取决于以下几方面：单个过孔的钻孔作业时间、打孔机在加工作业时，钻头的行进时间、针对不同孔型加工作业时，刀具的转换时间。钻头有8种刀具，依次排列呈圆环状，只能
5、顺时针或者逆时针转换。题目给出了10种孔型所需加工刀具及加工次序，对于须用两种或两种以上刀具加工的过孔，只要保证所需刀具加工次序正确即可。问题一：附件1提供了某块印刷线路板过孔中心坐标的数据，单位是1/100密尔（mil）（也称为毫英寸，1 inch=1000 mil），请给出单钻头作业的最优作业线路（包括刀具转换方案）、行进时间和作业成本。问题二：为提高打孔机效能，现在设计一种双钻头的打孔机，两钻头可以同时作业，且作业是独立的，即可以两个钻头同时进行打孔，也可以一个钻头打孔，另一个钻头行进或转换刀具。为避免钻头间的触碰和干扰，在过孔加工的任何时刻必须保持两钻头间距不小于3cm（称为两钻头合作
6、间距）。为使问题简化，可以将钻头看作质点。（1） 针对附件1的数据，给出双钻头作业时的最优作业线路、行进时间和作业成本，并与传统单钻头打孔机进行比较，其生产效能提高多少？（2） 研究打孔机的两钻头合作间距对作业路线和生产效能产生的影响。二、 问题分析本题是一个求打孔机完成目标任务所需费用最小的多目标优化问题。打孔机的生产效能取决于单个过孔的钻孔作业时间、打孔机在加工作业时钻头的行进时间和针对不同孔型加工作业时，刀具的转换时间。根据题意，打所有孔时间是不变的，提高打孔机的生产效能即要求打孔机钻头行进时间尽可能短，同时钻头转换次数尽量少。而打孔机钻头行进时间与行进路程有关，即转换为求最短路径的问题
7、。第一问中最优路线是打孔机钻头行进最短距离与钻头转换次数最少结合的多目标优化问题。可以建立三种模型求解：打孔机的作业成本包括钻头作业、钻头行进成本和刀具转换的时间成本，其中钻头作业成本为固定值，将刀具转换成本降到最低的情况下寻求行进路程最短的方式建立模型1；在行进总路线最短的情况下，计算出刀具转换成本建立模型2；将以上两方式结合起来寻求最佳方案建立模型3。将题目所给各孔型坐标导入MATLAB，绘制出了所有孔的分布图。再根据分布规律建立模型求出打孔机钻头行进最短距离和路线。然后考虑刀具转换次数最少的情况，由题意，可以用一种刀具把需要打的孔全部打完再换刀，建立模型得到此情况下的最优转换顺序。最后列
8、出两个目标的目标函数和约束条件，用LINGO求解，得到最优解，进而找到单钻头作业的最优作业线路（包括刀具转换方案）、行进时间和作业成本。第二问双钻头问题将机器效率提高了，同时也使问题复杂了。有两种方法：一种是将两钻头看作互无联系的独立个体,把电路板平均分成两块区域1和2,两钻头从两区域同侧开始工作,像同一侧行进,即可始终保持一定的相对距离,而不会发生碰撞影响工作；另一种是两钻头合作但用不同的道具互补，尽量减少转换次数，用最邻近算法计算各自的路线，同时出发将两钻头看作是两个半径R=1.5cm的圆，圆心沿路线行进，找出两圆相交的点的时刻和相对坐标，到中间将要相遇点时用提前算好的时间向不同方向拐开后
9、再继续行进，进行多次修正和迭代，直到不产生相交点。三、模型假设1、假定对于同一孔型钻孔作业时间都是相同的，作业时间不影响问题的分析，则求解时只分析钻头行进最短距离与钻头转换次数。2、假定打孔机连续工作，行进期间无停留时间。3、假定打孔机钻头行进时只在任意两点间做直线运动。4、假定打孔机钻头转换灵活，连续转换无异常。5、假定打每个孔时间极短。四、符号说明符号 说明单位 ah种孔型的一种第j个孔的坐标1/100mil第j个孔的横坐标1/100mil第j个孔的纵坐标1/100mil转换次数过孔路程mil的权系数交叉率变异率五、模型建立5.1 问题一5.1.1打孔机行进最短路程此种情况单考虑打孔机钻头
10、行进完所有点的最短路程，不考虑刀具转换次数，即打孔机行进到哪点即打完这点。将题目所给点的坐标导入MATLAB，并将各孔型用不同点区别开，打孔机所要打的全部孔的相对位置和孔型见图1。图1 经统计共有2124个点，要求钻头经过所有点一次，并且总路程最短。 此问题是一个旅行商问题（TSP）：旅行商问题要从图G的所有周游路线中求取最小成本的周游路线，而从初始点出发的周游路线一共有(n-1)!条，即等于除初始结点外的n-1个结点的排列数，因此旅行商问题是一个排列问题。排列问题比子集合的选择问题通常要难于求解得多，这是因为n个物体有n!种排列，只有n! 个 子集合(n!O( )。通过枚举(n-1)!条周游
11、路线，从中找出一条具有最小成本的周游路线的算法，其计算时间显然为O(n!)。 我们将2124个点看作2124个成市，求解此TSP问题。为此建立3个模型分别求解： （1）模型一：途程构建法 刀具转换成本最小方案 刀具的顺序固定，不能调换。要使刀具转换最少，可以排列刀具的使用顺序，在最少的转换次数中，满足每个孔型所需刀具及使用次序的条件。转换方式有两种：顺时针转换、逆时针转换。孔型ABCDEFGHIJ所需刀具aba，cd，e*c，fg，h*d，g，fhe，cf，c表1根据以下刀型换刀次序G（d，g，f）、E（c，f）和J（f，c）可知刀具至少要转一周，只需一种刀具和对次序没有限制的孔型可以不作考虑
12、。孔型CEGIJ所需刀具a，cc，fd，g，fe，cf，c表2顺时针：abcdefghabcdefghabcdefgh使序列包含不同的5个线段，最少的转换次数为10，用刀顺序为defghabcdef逆时针：hgfedcbahgfedcbahgfedcba使序列包含不同的5个线段，最少的转换次数为9，用刀顺序为dcbahgfedc因此，按照逆时针的dcbahgfedc次序时转换次数最少，刀具转换的成本最小。每次打点为：dcbahgfed2c2DGEBACFHFGEGJDICIJ表3此处以钻头a为例说明行进方案，其他钻头方案解法相同，只列结果。设用a刀的点660+270=930个点分别为a1 a2
13、 a3a930钻头a要打的孔如图： 图2使用途程构建法：最近邻点法（Nearest Neighbor Procedure）：一开始以寻找离场站最近的需求点为起始路线的第一个顾客，此后寻找离最后加入路线的顾客最近的需求点，直到最后。程序：设一个定点：找出它最近邻的点，然后找该点的最近邻点，直至最后一个点。对数组a进行排列：第一个点定为a1，查找最近邻点ai，并删除a1，查找下一个点aj，并删除ai直至第n个点，使他们按顺序排列为aa取最小值r1i最邻近点发求最短路径示意图见图3：图3途程改善法K-Opt(2 Opt)：把尚未加入路径的2条节线暂时取代目前路径中2条节线，并计算其成本（或距离），如果成本降低（距离减少），则取代之，直到无法改善为止。 经改善后处理的情况数大量简化，由于本题所给点数众多，算法复杂度过大，对100点以内情况适用的方法在此不适用，由于建模时间问题，未能给出完整答案，只摆出了方法。 （2）模型二：遗传算法遗传算法是一种
