数学建模优秀论文

一、 问题重述过孔是印刷线路板（也称为印刷电路板）的重要组成部分之一，打孔机主要用于在制造印刷线路板流程中的打孔作业。目前，实际采用的打孔机普遍是单钻头作业，即一个钻头进行打孔。本问题旨在解决某类打孔机的生产效能问题。打孔机的生产效能主要取决于：（1）单个过孔的钻孔作业时间，由生产工艺决定；（2）打孔机加工作业时，钻头的行进时间；（3）针对不同孔型加工作业时，刀具的转换时间。某种钻头装有8种刀具，8种刀具的顺序固定，不能调换。加工作业时，一种刀具使用完毕后，可转换使用另一种刀具。相邻两刀具的转换时间是18 s。作业时，可顺时针旋转转换刀具，如刀具a刀具b；也可逆时针旋转转换刀具，如刀具a刀具h。将任两个刀具转换，所需时间是相应转换时间的累加。假定钻头的行进速度相同，为180 mm/s，行进成本为0.06元/mm，刀具转换的时间成本为7元/min。刀具行进过程中可同时转换刀具，但相应费用不减。不同的刀具加工不同的孔型，有的只需一种刀具来完成，有的需要多种刀具及规定的加工次序来完成。表1为10种孔型所需加工刀具及加工次序（*表示该孔型不限制加工次序）。表1：10种孔型所需加工刀具及加工次序孔型ABCDEFGHIJ所需刀具aba, cd, e*c, fg, h*d, g, fhe, cf, c同一线路板上的过孔不要求加工完毕一个孔，再加工另一个孔，即对于须用多种刀具加工的过孔，只要保证所需刀具加工次序正确即可。建立相应的数学模型，并完成以下问题：（1）由附件1提供的某块印刷线路板过孔中心坐标的数据，请给出单钻头作业的最优作业线路（包括刀具转换方案）、行进时间和作业成本。（2）为提高打孔机效能，现在设计一种双钻头的打孔机（钻头形状与单钻头相同），两钻头可以同时作业，也可一个钻头打孔，另一个钻头行进或转换刀具。为避免钻头间的触碰和干扰，在过孔加工的任何时刻必须保持两钻头间距不小于3cm的合作间距。（i）针对附件1的数据，给出双钻头作业时的最优作业线路、行进时间和作业成本，并与传统单钻头打孔机进行比较，其生产效能提高多少？（ii）研究打孔机的两钻头合作间距对作业路线和生产效能产生的影响。二、 问题分析2.1 问题1分析：本问题可看作为动态规划与图论的组合问题，即求取由起始状态到终点状态的最优单向路径问题，主要是运用运筹学的排序理论、图论中的路径的相关理论知识解决问题。经分析，钻头的行进时间、加工不同孔型的刀具的转换时间，是本题的目标规划量。行进速度恒定，故目标规划量可转化为等效最短路径。首先，由分析，异型孔中最远两点距离小于等效换刀距离，故我们建立换刀、路线分立优化原则，邻近换刀原则。在该两个原则下，我们确定了运用工序优化算法总体优化换刀次序，同型孔中计算路径最优的问题的思路，将问题分成两部分进行求解。其次，为解决在同型孔中求解最优路径，由优化的最邻近算法我们求解出初始的回路，通过二边逐次修正算法对其进行优化，而后删去虚拟点得最优单向路径。最后，通过与最小生成树计算所得下界进行比较，对结果进行验证。2.2 问题2分析问题二中，双钻头对孔群进行加工的互相干扰，使本问题的时序性更突出，故不能简单使用求回路法，即使用动态规划的思想，该问题这也是个典型的NP-难问题，故我们将采用改进的蚁群算法进行近似求解。我们将采取建立于蚁群算法的蚁对群算法，全局搜索出两条最短路径，以达到目标时间最短，使生产效能最高。对于（i），由于其他条件不变，故决定性条件仍为换刀时间，对此我们沿用问题一的两个原则。为使目标时间最小，基于两刀加工时间的一致性，对总换刀次数，令，并使两钻头换刀次数尽可能相同。在优化问题上，由于存在合作间距的约束条件，问题变为在连续时间内，时刻加入两钻孔间距离的判断。对于（ii），将在统一模型算法下，通过改变合作间距，定量研究其对生产效能的影响。在模型验证中，将所求的路径与基于最小生成树的路径做误差分析。同时，单纯对于提高生产效能而言，与问题一结果相较，若单孔作业总时间，为双孔作业时间，则该模型的建立是失败的。三、 模型假设1. 忽略钻头的形状、材料、加工工艺等因素对钻孔作业的影响，将钻头视为质点；2. 忽略所打孔的大小，将孔视为质点，以圆心坐标表示；3. 假定打孔机8种刀具单独钻孔作业时间相同；4. 假定对于同一孔型钻孔作业时间都是相同的；5. 在问题一中，假定所有孔型的钻孔作业时间相同，经查阅资料，取该时间为；6. 在问题二的(i)中，假定合作距离为3cm。四、 符号说明符号说明赋权图点集边集从从正实数集的函数上边的权初始得圈由二边逐次优化算法所得的圈单个孔的加工时间钻头的行进总时间异型孔作业换刀总时间表示点集中的点等效距离矩阵激活矩阵关系矩阵状态矩阵等效点的个数，2814点到点的等效距离点到点的实际距离点到点的等效换刀距离点到点的换刀次数等效距离矩阵中第行中，所有满足的的点的对应值中最小值刀具转换时间，刀具行进速度，五、 模型准备5.1 路径（回路）与TSP问题1. 定义 在无向图中，穿程于的每个节点依次且仅一次的路径称为路径。穿程于的每个节点依次且仅一次的回路称为回路。2. TSP(旅行商问题)有n个城市，其相互间距离,为已知，求合理的路线使得每个城市都被经过一次，且总路径为最短。TSP的数学模型为： (1) (2) (3) (4) (5)式(8)中表示旅行商经历的路径，表示不经过该路径；式(5)(6)要求旅行商经过点有且仅有一次；(8)在任何一个城市的子集中不行成圈。5.2 最邻近算法定理1 是个顶点的无向完全图，为从到正实数集的函数，对在中任意三点，满足 (6)则可将实际问题转化为求取赋权图上的回路问题。具体算法如下：1) 在中取一点为起始点，找出一个与始点最近的点，形成一条边的初始路径。2) 设表示最新加到这条路径上的点，从不在路径上的所有点中，选一个与最邻近的点，把连接与此点边加到这条路径中。重复直至中的所有顶点包含在路径中3) 把始点和最后加入的顶点之间的边放入，即得出一个回路。5.3 蚁群算法：(1) 状态转移规则 (7)式中一在时刻蚂蚁由元素转移到元素的概率；表示蚂蚁下一步允许选择的城市；信息启发式因子，表示轨迹的相对重要性；一期望启发式因子，表示能见度的相对重要性；启发函数，；残留信息量。(2) 信息素修正规则 (8) (9)式中,信息素挥发系数；一表示第只蚂蚁在本次循环中留在路径上的信息量；信息素强度，设为常数；第后只蚂蚁在本次循环中所走过的路径的长度。(3) 禁忌表的修改和表蚂蚁数后有一个表和表。初始时可以把中的元素都设为0，把的元素都设为l。如果蚂蚁第1次选择了城市，则把tabu表中第1元素赋值为，并把表总第个元素赋值为0，表示此城市已经走过。算法实现步骤如下：(1) 参数初始化。令循环次数，将只蚂蚁随机放在个元素(城市)上，；(2) 循环次数(3) 蚂蚁数；(4) 对第只蚂蚁，根据公式(1)选择城市，并前进；(5) 把选择的城市加入到第屉只蚂蚁的表中，并修改表；(6) 对于第只蚂蚁若没有游历完所有个城市，则转到第4步，若游历完所有城市，则执行第7步；(7) 若蚂蚁数k小于蚂蚁总数，则转到第3步，直到只蚂蚁都游历完个城市，再执行第8步；(8) 根据式(2)、式(3)更新每条路上的信息量，并找出只蚂蚁中，所走的最短路径的值，并保存；(9) 若循环次数未达到最大循环次数，则转到第2步，若满足结束条件则结束循环，并输出计算结果。5.4 数据处理1. 将10种孔型按所需刀具重新编号，其中分别代表8种刀具、10种孔型中某一种，故得18类孔（共2814个）如下表。表格 1 18种新孔分类列表原孔ABCDEFGHIJ新孔另外，为叙述简便，将新的18种孔型做统一再命名，对应表格如下表格 2 18种新孔识记表新孔标记同时我们作出了相应的18种新孔的刀具分布情况，如下图。图 1 18种新型孔的刀具分布情况2. 由公式，将题目中缩短行进、换刀时间问题，转化为求解最短距离问题。(1) 首先，将5.3数据处理中所得到的2814个点，记作赋权图中点集，其中。(2) 针对上步中的2814个点，依次求出两点间最短距离；(3) 不同的孔型需换刀具，两点间的换刀等效距离 (10)其中 (11)为两刀具之间所需的换刀时间，为点与点换刀次数。六、 模型的建立与求解6.1 两个原则下的单向路径的图论模型6.1.1 模型建立6.1.1.1 基于TSP(旅行商问题)的最短路程模型：1. 最短等效路径：1) 刀具行进路径：从先前位置移动到当前位置的成本。设两个位置之间的实际距离为单位长度的刀具行进成本为n，则完成个孔加工的刀具行进成本为： (12)孔和孔之间距离；该路径在优化路径上。2) 换刀等效路径：设打孔机为加工孔后再加工不同孔型所需的等效换刀距离，为单位路径的换刀成本，则完成个孔加工的换刀成本为： (13)两点间的等效换刀路径 （处理方法，见数据处理5.3）；两点之间的换刀次数。则最小化总目标： (14)2. 模型求解思路：在换刀、路线分立优化原则，邻近换刀原则下，我们将用语言编写工序优化算法实现总体工序优化，通过优化的最邻近算法求得初始回路，而后用二边逐次修正算法对路径进行优化，并将虚拟点删去得单向路径。解决步骤如图2。 图 2模型一流程图u 两个原则下的工序、路径优化 两个原则：1) 换刀、路线分立优化原则：换刀情况下，最小等效换刀距离 (15) (16)其中，对行进距离的平均值。故需将同一类型的孔打完再换刀，则本问题转化为异类点工序（换刀）优化、同类点之内的路径优化问题。2) 邻近换刀原则：为减小等效，换刀时应尽量进行临近刀具转换进行打孔作业，如，或孔作业完毕，则优先或孔的作业，在邻近换刀条件下，最大程度上减少。 工序优化算法：对于已有18类孔，必然有，其中表示步骤总数，18步之内总能打完所有的点。故对工序进行优化时，我们引入步骤矩阵，激活矩阵，状态矩阵，以总次数最小为目标， (17) 其中，为要打第类孔时，所需的换刀次数。1) 初始化步骤矩阵，；激活矩阵，；状态矩阵，；其中，代表相应的新型孔。2) 根据图4 ,18类新型孔的刀具分布情况，步骤矩阵，由某确定起始孔型开始，若，则向左寻找最近的的孔型，并将对应的关系矩阵寻找下线孔型，并使，。3) 根据，的值，重复对的操作。并判断是否，。 若满足则结束，若不满足则重复3)的操作。则可得工序的最优解。 最邻近算法求初始回路具体步骤如下：1) 建立等效距离矩阵，其中第行、第列的元素，为点到点的等效距离；建立激活矩阵，其中；建立关系矩阵，其中；建立状态矩阵，其中；2) 确a定点（时为起始点），对应将，若，则由值查找下线点，跳转至步骤3；若，则继续对点重复对的操作，直至转至步骤3。3) 由第二步所确定的点对于除外的所有点满足相应的点，并在等效距离矩阵中的第行中，对于满足要求的点对应的值寻找最小值，并对点重复步骤二，直至所有元素为零，故所得路径为优化的有向回路。4) 在路径中加入虚拟点，令任一点到得距离=0，则与路径中所有的点都相连接，则最终去掉边权最大的两点中间的路径，则得到有向路径。具体算法流程如下： 二边逐次修正算法1) 对所得圈，对所有适合的，判断对某一对和，是否有 (18)2) 若有，删去边和,添加边和得;3) 重复1)2)两步，直至不可再用此方法继续进行，则求得一个较优的圈为了得到更高的精度，该程序可以重复几次，每次都以不同的圈开始。6.1.2 模型求解1. 总路径示意图：1) 打孔路径图：2) 打孔路径图：3) 打孔路径图：4) 打孔路径图5) 打孔路径图：6) 打孔路径图：7) 打孔路径图：8) 打孔路径图：9) 打孔路径图：2. 工序流程表及对应路径长度：工序流程为：该流程实际为刀具转换的流程，也即工序图，其中表示某一种刀具，表示换刀。该流程为，由刀具开始，将所有用到刀具的孔全部打完后，刀具换转，将即需刀具的型所有孔打完，再转换。同理，以该流程打完所有孔。工序流程表及对应长度如下：孔型dc(E)bahgfec总时间7.285.1213.7815.393.483.269.077.3611.5276.24路长1310.51920.712479.512769.64626.71587.691631.861324.462072.9713724.053. 总时间计算： (19)4. 总费用计算： (20)6.1.3 模型检验有向圈的求解并不能找到确定的最优解，但可以用最佳圈的权的下界与其比较。利用最小生成树可以得到最佳圈的一个下界，方法如下。设是的一个最佳圈，则对的任一顶点，是的路，也是的生成树。如果是的最小生成树，且和是与关联的边中权最小的两条边，则将是的一个下界。6.2 问题二6.2.1 模型建立在问题一的基础上，我们由双钻头工序优化算法优化出双钻头的换刀方案，在两个原则下，我们可认为双钻头在满足的约束条件下在两块独立且重合的板上进行独立打孔作业。针对此问题，我们将平面问题转化加入时间轴为空间问题，轴为坐标轴，轴为时间轴，并提出了基于蚁群算法的蚁对群算法。1. 蚁对群算法：在蚁群算法的基础上，为解决双打孔机的作业线路设计问题，我们提出了蚁群对算法。具体步骤如下：1） 随机产生对蚂蚁，将该对中的蚂蚁平均分别置于将行路线上；2） 对于蚂蚁对的起始孔加入到禁忌表； 3） 计算，其中为蚂蚁到剩余点的概率，为蚂蚁到剩余点的概率；4） 用赌轮方法选择蚂蚁各自在该次行进中将要到达的孔；5） 计算蚂蚁第次行进时间，蚂蚁第次行进时间， (21) (22) (23)其中为从蚂蚁从到的等效行进时 间，为的实际行进时间，为两个孔之间是否要换刀的标记变量，对于平行存在;6） 若，并且，则蚂蚁移至孔处，返回步骤4）；若，则蚂蚁均不可移动，直接返回4）；7） 对蚂蚁均完成1次行进，则根据修正信息素规则，修改信息素（见模型准备5.4）；8） 当循环次数时，结束。具体流程图如图3：图 3蚁对群算法流程图其中目标点确定方法为蚁对群算法中的（3）（4）（5）（6）。6.2.2 模型求解1. 最优作业线路图在双钻头按照，其中，道具仅打型孔，对道具所打型孔，对两钻头进行近似平均分配。 点分布路线图：1) 1100点2) 101200点3) 201300点4) 301350点5) 351480点6) 481680点7) 681800点8) 801900点9) 9011180点10) 11811300点11) 13011350点12) 13511410点13) 轴路线图14) 轴路线图2. 行进时间（单个空作业时间为）1) 钻头路径中共1407个顶点，b点数为268 个，（含作业时间）2) 钻头路径中共1407个顶点，（含作业时间）3) 行进总时间：，（含作业时间）3. 作业成本七、 模型评价对模型一，考虑到所需作业的孔的数据庞大，邻近换刀条件、刀具转换次序限制条件混合，问题复杂性较高。首先，我们通过优化的最邻近算法下，求出新分类的18种孔型下的所有孔的近似最短回路问题。其次，在已有的结果的基础上，对问题进行分析。同时，基于结果分析后提出的两个原则，运用二边逐次修正算法、工序优化算法，分别对同类孔之间行进路径、工序进行优化。该模型的建立中，我们对问题逐层求解，所提出的求解有向回路的算法即在最邻近算法的基础上引入激活、状态、关系矩阵，运算量相对图论的经典算法较小，应用范围广。在问题二的解答中延续了问题一的思想，两处基础算法都是基于问题一已实现的程序，即由最邻近算法求解同型孔之内的最优路径问题。故而在已有的基础上减少了运行时间，提高了效率。八、 灵敏度分析1 单个孔的作业时间：考虑到单个孔的的作业时间若置为变量，使问题更加复杂。经查阅资料，我们将打孔时间设为。实际，在问题二中，由于两个打孔机独立作业，由于有合作间距的限制，单个孔打孔时间，会对的作业情况有较大的影响。如，若在某时刻打孔，而按预定路程本应向的孔行进，但，故需等待作业完毕后进行。则对双打孔机作业的影响可能较大，下面我们将对的取值对整体结果的影响进行具体讨论。由于实际工程中条件约束，分别故取将，代入问题的程序求解，则结果如表格3：单孔作业行进时间总时间作业成本（元）0.31086.61090.50.41040.20.51585.941039.9表格 3单孔作业时间对比表格由表格3可知，当分别取，说明取值不同时，差异不大。总时间包含了作业时间，故取值不同时，变化较大。故的取值对本问题影响不大，且问题二的模型有较好的弹性，可以满足咋一定范围内的波动。2 算法分析：由于寻找回路问题为问题，并没有成熟的算法解决该问题。为解决寻找有向路径，我们将最邻近算法进行改进，具体分析如下。 优化的最邻近算法：由起始点进行路径的扩充，基于最邻近的思想，只添加最小的边。同时我们引入的等效距离矩阵，的激活矩阵，关系矩阵，状态矩阵，其计算时间复杂度为，其中为总节点数。算法优势在于，在时间复杂度较低的情况下求解出近似的有向最优回路。同时，没有矩阵的迭代，则不会产生由迭代深度引起的空间复杂度过大的问题。九、 模型推广1 拓展一：遗传算法遗传算法是模拟生物在自然界中遗传和进化过程而形成的一种向适应全局优化概率搜索算法。遗传算法在优化孔群的加工路径中，染色体一般为一个代加工孔的序列，所以染色体的长度与孔的数量相等。直接采用孔的标号