数学建模优秀论文

一、 问题重述

过孔是印刷线路板（也称为印刷电路板）的重要组成部分之一，打孔机主要用于在制造印刷线路板流程中的打孔作业。目前，实际采用的打孔机普遍是单钻头作业，即一个钻头进行打孔。本问题旨在解决某类打孔机的生产效能问题。

打孔机的生产效能主要取决于：（1）单个过孔的钻孔作业时间，由生产工艺决定；（2）打孔机加工作业时，钻头的行进时间；（3）针对不同孔型加工作业时，刀具的转换时间。

某种钻头装有8种刀具，8种刀具的顺序固定，不能调换。加工作业时，一种刀具使用完毕后，可转换使用另一种刀具。相邻两刀具的转换时间是18 s。作业时，可顺时针旋转转换刀具，如刀具a?刀具b；也可逆时针旋转转换刀具，如刀具a?刀具h。将任两个刀具转换，所需时间是相应转换时间的累加。假定钻头的行进速度相同，为180 mm/s，行进成本为0.06元/mm，刀具转换的时间成本为7元/min。刀具行进过程中可同时转换刀具，但相应费用不减。

不同的刀具加工不同的孔型，有的只需一种刀具来完成，有的需要多种刀具及规定的加工次序来完成。表1为10种孔型所需加工刀具及加工次序（*表示该孔型不限制加工次序）。

表1：10种孔型所需加工刀具及加工次序

孔型 所需刀具 A a B b C a, c D d, e* E c, f F G H h I e, c J f, c g, h* d, g, f 同一线路板上的过孔不要求加工完毕一个孔，再加工另一个孔，即对于须用多种刀具加工的过孔，只要保证所需刀具加工次序正确即可。

建立相应的数学模型，并完成以下问题：

（1）由附件1提供的某块印刷线路板过孔中心坐标的数据，请给出单钻头作业的最优作业线路（包括刀具转换方案）、行进时间和作业成本。

（2）为提高打孔机效能，现在设计一种双钻头的打孔机（钻头形状与单钻头相同），两钻头可以同时作业，也可一个钻头打孔，另一个钻头行进或转换刀具。为避免钻头间的触碰和干扰，在过孔加工的任何时刻必须保持两钻头间距不小于3cm的合作间距。

（i）针对附件1的数据，给出双钻头作业时的最优作业线路、行进时间和作业成本，并与传统单钻头打孔机进行比较，其生产效能提高多少？

（ii）研究打孔机的两钻头合作间距对作业路线和生产效能产生的影响。

二、 问题分析

2.1 问题1分析：

本问题可看作为动态规划与图论的组合问题，即求取由起始状态到终点状态的最优单向路径问题，主要是运用运筹学的排序理论、图论中的Hamilton路径的相关理论知识解决问题。经分析，T1—钻头的行进时间、T2—加工不同孔型的刀具的转换时间，是本题的目标规划量。行进速度u恒定，故目标规划量可转化为等效最短路径。

首先，由分析，异型孔中最远两点距离dij小于等效换刀距离lij，故我们建立换刀、路线分立优化原则，邻近换刀原则。在该两个原则下，我们确定了运用工序优化算法总体优化换刀次序，同型孔中计算路径最优的问题的思路，将问题分成两部分进行求解。其次，为解决在同型孔中求解最优路径，由优化的最邻近算法我们求解出初始的Hamilton回路，通过二边逐次修正算法对其进行优化，而后删去虚拟点得最优单向路径。最后，通过与最小生成树计算所得下界进行比较，对结果进行验证。

2.2 问题2分析

问题二中，双钻头J1,J2对孔群进行加工的互相干扰，使本问题的时序性更突出，故不能简单使用求Hamilton回路法，即使用动态规划的思想，该问题这也是个典型的NP-难问题，故我们将采用改进的蚁群算法进行近似求解。我们将采取建立于蚁群算法的蚁对群算法，全局搜索出两条最短路径，以达到目标时间最短，使生产效能最高。

对于（i），由于其他条件不变，故决定性条件仍为换刀时间T1，对此我们沿用问题一的

?,T?的一致性，对总换刀次数两个原则。为使目标时间最小，基于两刀加工时间TJ1J2N?NJ1?NJ2?2k?1,k?Z?，令N?N?1，并使两钻头换刀次数NJ1,NJ2尽可能相同。

在优化问题上，由于存在合作间距??3cm的约束条件，问题变为在连续时间内，时刻加入两钻孔J1,J2间距离d(J1,J2)?3cm的判断。对于（ii），将在统一模型算法下，通过改变合作间距?，定量研究其对生产效能的影响。

在模型验证中，将所求的路径与基于最小生成树的路径做误差分析。同时，单纯对于提高生产效能而言，与问题一结果相较，若单孔作业总时间Ts?Td，Td为双孔作业时间，则该模型的建立是失败的。

三、 模型假设

1. 忽略钻头的形状、材料、加工工艺等因素对钻孔作业的影响，将钻头视为质点； 2. 忽略所打孔的大小，将孔视为质点，以圆心坐标表示； 3. 假定打孔机8种刀具单独钻孔作业时间相同； 4. 假定对于同一孔型钻孔作业时间都是相同的；

5. 在问题一中，假定所有孔型的钻孔作业时间相同，经查阅资料，取该时间为0.4s； 6. 在问题二的(i)中，假定合作距离为3cm。

四、 符号说明

符号 说明 赋权图 点集 边集 从E从正实数集的函数 G V E W w(vi,vj) G上边vivj的权 初始得Hamilton圈 由二边逐次优化算法所得的Hamilton圈 单个孔的加工时间 钻头的行进总时间 异型孔作业换刀总时间 表示点集V中的点 H Hij t0T1 T2vi Wm?mQ1?m 等效距离矩阵 激活矩阵 关系矩阵 状态矩阵 等效点的个数，2814 点vi到点vj的等效距离 点vi到点vj的实际距离 点vi到点vj的等效换刀距离 点vi到点vj的换刀次数 等效距离矩阵中第i行中，所有满足的R1?m C1?m m wij sij tij nij dmini tr qj,cj?1的点的对应值中最小值 刀具转换时间，18s 刀具行进速度，180mm/s u

五、 模型准备

5.1 Hamilton路径（回路）与TSP问题

1. 定义 在无向图G=中，穿程于G的每个节点依次且仅一次的路径称为

Hamilton路径。穿程于G的每个节点依次且仅一次的回路称为Hamilton回路。

2. TSP(旅行商问题)

有n个城市v1,v2?vn，其相互间距离v12,v13,v23,?,为已知，求合理的路线使得每个城市都被经过一次，且总路径为最短。TSP的数学模型为：

ms.t.?Xij=1，i?1,2?n (1)

j?1min?dijXij (2)

i?j

?Xi?1mij?1,j?1,2?n (3)

i,j?n?Xij?s?1,2?s?n?2,s?{1,2?n} (4)

Xij??0,1?,i,j?1,2?n,i?j (5)

式(8)中Xij?1表示旅行商经历vivj的路径，Xij?0表示不经过该路径；式(5)(6)要求旅行商经过vi,vj点有且仅有一次；(8)在任何一个城市的子集中不行成圈。

5.2 最邻近算法

定理1 G??V,E,W?是n个顶点的无向完全图，W为从E到正实数集的函数，对在V中任意三点vi,vj,vk，满足

W(i,j)?W(j,k)?W(i,k) (6)

则可将实际问题转化为求取赋权图上的Hamilton回路问题。 具体算法如下：

1) 在G中取一点v0?V为起始点，找出一个与始点最近的点，形成一条边的初始路径。 2) 设x表示最新加到这条路径上的点，从不在路径上的所有点中，选一个与x最邻近

的点，把连接x与此点边加到这条路径中。重复直至G中的所有顶点包含在路径中 3) 把始点和最后加入的顶点之间的边放入，即得出一个回路。

5.3 蚁群算法：

(1) 状态转移规则

?[?ij(t)]??[?ik(t)]?,若j?Allowedk? (7) pi???[?ij(t)]??[?ik(t)]??0,else?式中Pijk(t)一在t时刻蚂蚁k由元素i转移到元素j的概率；Allowedk——表示蚂蚁k下一步允许选择的城市；?——信息启发式因子，表示轨迹的相对重要性；?一期望启发式因子，表示能见度的相对重要性；?ij(t)——启发函数，?ij(t)?1/dij；?ij——残留信息量。

(2) 信息素修正规则

?ij(t?n)?(1??)??ij(t)???ij(t) (8)

??ij(t)????ij(t) (9)

k?1m?Q?,若k只在本次循环中（i,j）??ij(t)??Lk

?0,else?式中,?——信息素挥发系数；??ij(t)一表示第k只蚂蚁在本次循环中留在路径?i,j?上的信息量；Q——信息素强度，设为常数；Lk——第后只蚂蚁在本次循环中所走过的路径的长度。

(3) 禁忌表tabuk的修改和表Allowed蚂蚁数后有一个表tabuk和表Allowed。初始时可以把tabu中的元素都设为0，把的元素都设为l。如果蚂蚁第1次选择了城市j，则把tabu表中第1元素赋值为j，并把表Allowed总第j?1个元素赋值为0，表示此城市已经走过。

算法实现步骤如下：

(1) 参数初始化。令循环次数Nc?0，将m只蚂蚁随机放在n个元素(城市)上，

?ij(t)?const,?ij(0)?0;；

(2) 循环次数Nc?Nc?1 (3) 蚂蚁数k?k?1；

(4) 对第k只蚂蚁，根据公式(1)选择城市j，并前进；

本文来源：https://www.bwwdw.com/article/ea9t.html