数学建模优秀论文

余年寄山水
905次浏览
2021年02月11日 00:05
最佳经验
本文由作者推荐

-

2021年2月11日发(作者：我爱我夫我爱子)


一、



问题重述



过孔是印刷线路板


（也称为印刷电路板）


的 重要组成部分之一，


打孔机主要用于在制造


印刷线路板流程中的 打孔作业。


目前，


实际采用的打孔机普遍是单钻头作业，


即一个钻头进


行打孔。本问题旨在解决某类打孔机的生产效能问题。< /p>



打孔机的生产效能主要取决于：


（


1


）单个过孔的钻孔作业时间，由生产工艺决定；

< br>（


2


）


打孔机加工作业时，钻头 的行进时间；


（


3


）针对不同孔型加工 作业时，刀具的转换时间。



某种钻头装有

8


种刀具，


8


种刀具的顺序固定， 不能调换。加工作业时，一种刀具使用


完毕后，可转换使用另一种刀具。相邻两刀具的转 换时间是


18 s


。作业时，可顺时针旋转转

< br>换刀具，如刀具


a



刀具


b


；


也可逆时针旋转转换刀具，如刀具


a



刀具


h


。将任两个刀具


转换，所需时间是相应转换时间的累加。假定钻头的行进 速度相同，为


180


mm/s


，行进 成


本为


0.06


元

/mm


，刀具转换的时间成本为


7


元


/min


。刀具行进过程中可同时转换刀具，但


相应费用不减。



不同的刀具加工不同的孔型，


有的只需一种刀具来完成，


有的需要多种刀具及规定的加

< p>
工次序来完成。


表


1


为< /p>


10


种孔型所需加工刀具及加工次序


（< /p>


*


表示该孔型不限制加工次序）


。



表


1


：

< p>
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

< br>提供的某块印刷线路板过孔中心坐标的数据，请给出单钻头作业的最优


作业线路（ 包括刀具转换方案）


、行进时间和作业成本。



（


2


）为提高打孔机效能，


现 在设计一种双钻头的打孔机（钻头形状与单钻头相同）


，两


钻头 可以同时作业，


也可一个钻头打孔，


另一个钻头行进或转换刀具 。


为避免钻头间的触碰


和干扰，在过孔加工的任何时刻必须保持 两钻头间距不小于


3cm


的合作间距。



（


i


）针对附件


1


的数据，给出双钻头作业时的最优作业线路、行进时间和作业成本，


并与传统单钻头打孔机进行比较，其生产效能提高多少？


（


ii


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













二、



问题分析



2.1



问题


1


分析：



本问题可看作为动态规划与图论的组合问题


，

< br>即求取由起始状态到终点状态的最优单向


路径问题


，主要 是运用运筹学的排序理论、图论中的


Hamilton


路径的相 关理论知识解决问


题。


经分析，


T


1


—钻头的行进时间、


T

< br>2


—加工不同孔型的刀具的转换时间，


是本题的目标规< /p>


划量。行进速度


u


恒定，故目标规划量可 转化为等效最短路径。



首先，由分析，异型孔中最远两点距离


d


ij


小于等效换刀距离


l


ij


，故我们建立换刀、路


线分立优化原则，


邻近换刀原则。


在该两个原则下，


我们确定了运用工序优化算法总体优化


换刀次序，


同型孔中计算路径最优的问题的思路，


将问题分成两部分进行求解。其次，

< p>
为解


决在同型孔中求解最优路径，由优化的最邻近算法我们求解出初始的< /p>


Hamilton


回路，通过


二边逐次修 正算法对其进行优化，


而后删去虚拟点得最优单向路径。


最后，


通过与最小生成


树计算所得下界进行比较，对结果进行验证。< /p>




2.2



问题


2


分析



问题二中，双钻头


J


1


,


J


2


对孔群进行加工的互相 干扰，


使本问题的时序性更突出，故不


能简单使用求

< p>
Hamilton


回路法，即使用动态规划的思想，该问题这也是个典型的


NP-


难问


题，


故我们将采用改进的蚁群算法进行近似求解


。


我们将采取建立 于蚁群算法的蚁对群算法，


全局搜索出两条最短路径，以达到目标时间最短，使生产效能 最高。



对于（


i

）


，由于其他条件不变，故决定性条件仍为换刀时间


T


1


，对此我们沿用问题一的


两个原则。为使 目标时间最小，基于两刀加工时间


T


J


1


,


T


J


2< /p>


的一致性，对总换刀次数


N


< p>
N


J


1



N


J


2


2


k



1,


k



Z



， 令


N



N


< /p>


1


，并使两钻头换刀次数


N


J


1


,


N

< br>J


2


尽可能相同。


在优化问题上 ，由于存在合作间距




3

< p>
cm


的约束条件，问题变为在连续时间内，时刻加入


两钻孔


J


1


,


J


2


间距离


d


(


J


1


,


J


2


)



3


cm


的判断。对于（


ii

< br>）


，将在统一模型算法下，通过改变合作


间距

< p>


，定量研究其对生产效能的影响。


< p>
在模型验证中，


将所求的路径与基于最小生成树的路径做误差分析。


同时，


单纯对于提


高生产效能而言，与问题一 结果相较，若单孔作业总时间


T


s


< /p>


T


d


，


T


d


为双孔作业时间，则


该模型的建立是失败的 。




三、



模


型假设



1.



忽略钻头的形状、材料、加工工 艺等因素对钻孔作业的影响，将钻头视为质点；



2.



忽略所打孔的大小，将孔视为质点，以圆心坐标表示；



3.



假定打孔机

8


种刀具单独钻孔作业时间相同；



4.



假定对于同一孔型钻孔作业时间都是相同的；



5.



在问题一中，假定所有孔型的钻 孔作业时间相同，经查阅资料，取该时间为


0.4


s

< p>
；



6.



在问题二的


(i)


中，假定合作距离为


3cm


。



四、



符


号说明



符号



说明



赋权图



点集



边集



从


E< /p>


从正实数集的函数



G



V



E



W



w


(


v


i


,


v


j


)



G


上边


v


i


v


j


的权

< br>


初始得


Hamilton


圈< /p>



由二边逐次优化算法所得的


Hamil ton


圈



单个孔的加工时间



钻头的行进总时间



异型孔作业换刀总时间



表示点集


V


中的点



H



H


ij



t< /p>


0


T


1





T


2


v


i



W


m



m


Q


1



m




等效距离矩阵



激活矩阵



关系矩阵



状态矩阵



等效点的个数，


2814


点


v


i


到点


v

< p>
j


的等效距离



点


v


i


到点


v


j


的实际距离



点


v


i


到点


v


j


的等效换刀距离



点


v


i


到点


v


j


的换刀次数



等


效


距


离


矩


阵


中


第


i


行


中


，


所


有


满


足


的


R


1



m

< br>


C


1



m



m



w


ij



s


ij



t


ij



n


ij



d


min


i



t


r



q


j


,


c


j



1


的点的对应值中最小值


刀具转换时间，


18


s



刀具行进速度，


180


mm


/


s








u
























五、



模型准备



5.1



Hamilton

< p>
路径（回路）与


TSP


问题



1.



定义




< /p>


在无向图


G


=

< br>>


中，穿程于


G


的每个节点依次 且仅一次的路径称为


Hamilton


路径

。


穿程于


G


的每个节点依次且仅一 次的回路称为


Hamilton


回路。



2.



TSP(


旅行商问题


)



有

< br>n


个城市


v


1

< br>,


v


2


v


n


，其相互间距离


v


12

< p>
,


v


13


,


v


23


,


m


,


为已知，求合理的路线使得每


个城市都被经过一次， 且总路径为最短。


TSP


的数学模型为：



s


.


t


.



X


ij


=1


，


i



1,2


j



1


n




























(1)



min



d


i j


X


ij

































(2)



i



j




X


i



1


m


ij


< p>
1,


j



1,2


n


























(3)



n


}



(4)



i


,


j



n



X


ij



s



1,2



s



n



2,


s



{


1,2


X


ij



< p>
0,1



,


i

< p>
,


j



1,2

< p>
n


,


i



j























(5)



式


(8)


中


X


ij



1


表示 旅行商经历


v


i


v

j


的路径，


X


ij



0


表示不经过该路径；式


( 5)(6)


要求旅行商经过


v


i


,


v


j


点有且仅有一 次；


(8)


在任何一个城市的子集中不行成圈。



5.2



最邻近算法



定理


1




G





V


,< /p>


E


,


W



是


n


个顶点的无向完全图，

< br>W


为从


E


到正实数集的函数，对


在


V


中任意三点


v


i


,


v


j


,


v


k


，满足



W


(


i


,


j


)



W


(


j


,


k


)



W

< br>(


i


,


k


)































(6)


则可将实际问题转化为求取 赋权图上的


Hamilton


回路问题。



具体算法如下：



1)



在


G< /p>


中取一点


v


0



V


为起始点，


找出一个与始点最近的点 ，


形成一条边的初始路径。



2)



设


x< /p>


表示最新加到这条路径上的点，从不在路径上的所有点中，选一个与


x


最邻近


的点，


把连接


x


与此点边加到这条路径中。


重复直至


G


中的所有顶点包含在路径中



3)



把始点和最后加入的顶点之间的边放入，即得出一个回路。




5.3



蚁群算法：



(1)



状态转移规则



[



ij


(


t


)]



[



ik


(


t


) ]



,


若


j< /p>



Allowed


k



















(7)



p


i





[



ij


(


t


)]



[



ik


(


t

< p>
)]




0,

< p>
else



式中


P


ij


k


(


t


)


一在


t


时刻蚂蚁


k


由元素


i


转移到 元素


j


的概率；


Allowed


k


——表示蚂蚁


k


下


一步允许选择的城市；



——信息启发 式因子，表示轨迹的相对重要性；



一期望启发


式因子，表示能见度的相对重要性；



ij

< p>
(


t


)


——启发函数，< /p>



ij


(


t


)



1/


d


ij


；



ij


——残留信


息量。



(2)



信息素修正规则



< br>ij


(


t


n


)



(1




)




ij


(


t


)< /p>





ij


(


t


)



(8)





ij


(


t


)< /p>






ij


(


t


)




























(9)



k



1


m



Q



,


若


k


只在本次循环中（


i,


j


）




ij


(


t


)< /p>




L


k




0,


else< /p>



式中


,



——信息素挥发系数；




ij


(


t


)

< br>一表示第


k


只蚂蚁在本次循环中留在路径



i


,


j


上


的信息量；


Q


——信息素强度，


设为常数；


L


k


——第后只蚂蚁在本次循环中所走过的路


径的长度。



(3)



禁忌表< /p>


tabu


k


的修改和表

< br>Allowed


蚂蚁数后有一个表


tabu


k


和表


Allowed


。初 始时


可以把


tabu


中的元素都设为< /p>


0


，把的元素都设为


l

< br>。如果蚂蚁第


1


次选择了城市


j


，则把


tabu


表中第


1


元素赋值为


j


，并把表


Allowed


总第


j


1


个元素赋值为


0


，表示此城市已经


走过。




算法实现步骤如下：



(1)



参数初始化。令循环次数


N


c



0


，将


m


只蚂蚁随机放在


n


个元素


(


城市


)


上，



ij


(


t


)



c onst


,



ij

(0)



0;


；

< br>


(2)



循环次数

< p>
N


c



N


c



1



(3)



蚂蚁数


k



k



1


；



(4)



对第


k


只蚂蚁，根据公式


(1)


选择城市


j


，并前进 ；



(5)



把选择的城市加入到第屉只蚂蚁的表


tabu


中，并修改表


Allowed


；



(6)



对于第


k


只蚂蚁若没有游历完所有


m


个城市 ，


则转到第


4


步，若游历完所有城市，


则


执行第


7


步 ；



(7)



若蚂蚁数


k


小于蚂蚁总数


n

< p>
，则转到第


3


步，直到


n


只蚂蚁都游历完


m


个城市，再执


行第


8


步；



(8)



根据式


(2)


、式


(3)


更新每条路上的信 息量，并找出


n


只蚂蚁中，所走的最短路径的

< br>值，并保存；



(9)



若循环次数未达到最大循环次数，则转到第


2


步，若满足结束条件则结束循环，并输


出计算结果。



5.4



数据处理



1.



将


10


种孔型按所需刀具重新编号


h


H


，其中


h


,


H


分别代表


8


种刀具、


10


种孔型中某


一种，故得


18


类孔（共


2814


个）如下表。



表格



1




18


种新孔分类列表



原孔



新孔



A


A


a



B


B


b



C


a



C


C


c



D


*



D


d


E


D


e


*



F


E


f



G


F


h


*



H


G


f



I


I


e



I


c



J


f



J


J


c



E


c



F


g


*



G


d



G


g



H


h




另外，为叙述简便，将新的


18


种孔型做统 一再命名，对应表格如下



表格



2



18


种新孔识记表



新孔



A


a



B


b



C


a



C


c



*



D


d


D


e


*



E


c



E


f



F


g


*



F


h


*



G


d



G


g



G


f



H


h



I


e



I


c



J


f



J


c



标记



V


1



V


2



V


3



V


4



V


5



V


6



V


7



V


8



V


9



V


10



V


11



V


12



V


13



V


14



V


15



V


16



V


17



V


18



< /p>


同时我们作出了相应的


18


种新孔的刀具 分布情况，如下图。




图



1



18


种新型孔的刀具分布情况




2.



由公 式


d



ut


， 将题目中缩短行进、换刀时间问题，转化为求解最短距离问题。



(1)



首先，


将


5.3


数据处理中所得到的


281 4


个点，


v


1


,


v


2


中点集


V


，其中


m



2814


。



(2)



针对上步中的


2814


个点，依次求出两点间最短距离


s

< p>
ij


；



(3)



不同的孔型需换刀具，两点间的换刀等效距离



记作赋权图


G



V

< p>
,


E



v


m


，


l


ij

< br>


t


r



u































(10)


其中



t


r< /p>



n


ij



18






























(11)


为两刀具之间所需的换刀 时间，


n


ij


为点

v


i


与点


v


j


换刀次数。



六、



模


型的建立与求解



6.1



两个原则下的单向

< p>
Hamilton


路径的图论模型



6.1.1



模型建立



6.1.1.1



基于


TSP(


旅行商问题


)


的最短 路程模型：



1.



最短等效路径


：



1)



刀具行进路径：



从先前位置移动到当 前位置的成本。设两个位置之间的实际距离为


d


ij

< p>
单位长度的


刀具行进成本为


n

，则完成


m


个孔加工的刀具行进成本为：

< br>


f


1



i



1,


j



1


i



j< /p>




d


e


m


m


ij


ij































(12)


d


ij


——孔


i


和孔

< br>j


之间距离；


e


ij

< p>
——该路径在优化路径上。



2)



换刀等效路径：



设

< br>l


ij


打孔机


J


1


为加工孔


i


后再加工不同孔 型


j


所需的等效换刀距离，


b


为单位路径


的换刀成本，则完成


m


个孔加工的换刀成本为：



f


2



i



1 ,


j



1


i< /p>



j




n


l


e


m

< p>
m


ij


ij


ij




























(13)



l


ij


——两点间的等效换刀路径



（处理方法，见数据处理


5.3


）；



n


ij


——两点之间的换刀次数。



则最小化总目标：



d


min



min(


f


1



f


2


)



























(14)



2.



模型求解思路：



在换刀、路线分立优 化原则，邻近换刀原则下，我们将用


C


语言编写工序优化算法实


现总体工序优化，通过优化的最邻近算法求得初始


Hamilt on


回路，而后用二边逐次修正算


法对路径进行优化，并将虚拟 点删去得单向路径。解决步骤如图


2


。




换刀、路径


分立优化原则

< p>
邻近换刀原则


两个原则下，解决


工序，路径问题< /p>


工序优化算法


优化最邻近算法求


解初始路 径


二边逐次修正算法


优化路径


修正工序


去掉虚拟点


确定出入口


优化加工工序< /p>














图



2


模型一流程图






两个原则下的工序、路径优化





两个原则：



1)



换刀、路线分立优化原则：



换刀情况 下，最小等效换刀距离


l


ij


min< /p>



l


ij


min



18



18 0



3240


mm


1275.6


mil



D
















(15)



D



其中，


D


——对行进距离的平均值。



i


,


j



1



r


m


ij

































(16)


故需将同一类型的孔打完 再换刀，则本问题转化为


——


异类点工序（换刀）优化、


同类点之内的路径优化问题。



2)



邻近换刀原则：



为减小等效


l


ij


，


换刀时应尽量 进行临近刀具转换进行打孔作业，


如，


A


a



F


h


,


H


h


，


或


A


a



B


b


孔作业完毕，则优先或孔的作业，在邻近换刀条件下，最大程度上减少


T


2


。





工序优化算法：



对于已有

< p>
18


类孔，必然有


k


< /p>


18


，其中


k


表 示步骤总数，


18


步之内总能打完所有


的点。故对工序进行优化时，我们引入步骤矩阵


P


1

< p>


18


，激活矩阵


Q


1



18


，状态矩 阵


C


1



18


，


以总次数


N


最小为目标，



18


N




n


i































(17)



i



1


其中，


n


i


为要打第


i

类孔时，所需的换刀次数。




1 ,


第


i


步向右


1)



初始化步骤矩阵


P


，


；



p

< br>



i


1



18



0,


第


i


步向左


激活矩阵


Q


1



18

< br>，


q


j






1,


V


j


被激活，可进行作业


；

< p>




0,


V


j


未激活，不可作业


< /p>



1,


V


j


未进行作业


C


状态矩阵

1



18


，


c


j




；



0,


V


已进 行作业



j



其中，


V


j


代表相应的新型孔。



2)



根据图


4


,


18


类新型孔的刀具分布情况


，步骤矩阵，由某确定起始孔型< /p>


V


x


开始，


c< /p>


x



0


，若


p


1



0


，则向左寻找最近的


q


j



1,


c


j



1


的孔型


V


j


，并将对应的关系矩


阵寻找下线孔型


V


i


，并使


q


i



1


，


c< /p>


i



0


。



3)



根据


p


j


，


j

< p>


2,3


18


的值，重复 对


V


x


的操作。并判断是否

< p>
c


j



0


，


j



1,2


18


。



若满足则结束，若不 满足则重复


3)


的操作。则可得工序的最优解。





最邻近算法求初始


Hamilton


回路

< br>


具体步骤如下：



1)



建立等效距离矩阵


W


m



m

< br>，其中第


i


行、第


j

< p>
列的元素


w


ij



s


ij



l


ij


，


w


ij


为点


v


i


到点


v


j


的等效距离；


< /p>


建立激活矩阵


Q


1



m


，其中


q


j




建立关系矩阵


R


1



m

，其中


r


j





1,


v


j


被激活，可进行作业


；



0,


v


未激活，不可 作业



j





k


,


v


j


作业后，


v


k< /p>


才可作业


；



0 ,


v


不影响其他点作业



j




< br>1,


v


j


未进行作业

< p>
；



0,


v


已进行作业



j



建立状态矩阵


C


1


< /p>


m


，其中


c


j< /p>




2)



确


a


定点


v


j


（


j


< p>
1


时为起始点）


，对应将


q


j


置为


1


，


c


j


置为


0< /p>


，若


r


j



0


，则由


r


j


值


查找下线点


v


i


，跳转至步骤


3


；若

< br>r


j



0


，则继续对点


v


j



1


重复对


v


j


的操作，直至


r


k



0


转至步骤


3


。



3)



由第二步所 确定的点


v


i


对于除

< br>v


i


外的所有点满足相应


q


i



1,


c


i



1


的点，并在等 效


距离矩阵中的第


i


行中，对于满足要 求的点对应的值寻找最小值


d


min


i


，并对点


v


x


重复步骤二，直至


C


1



m


所有元素为零，故所得路径为优化的有向


Hami lton


回路。



4)



在路径中加入虚拟点

< p>
v


0


，


令任一点


v


i


到


v


0


得距离


d


i


0


=0


，


则


v


0


与路径中所有的点都


相连 接，则最终去掉边权最大的两点中间的路径，则得到有向


Hamilton


路径。



具体算法流程如下：























二边逐次修正算法



1)



对所得


Hamilton


圈


H



v


1


v


2

< br>一对


i


和


j

，是否有



v


n

< br>v


1


，对所有适合


1

< p>


i



1



j



n

的


i


,


j


，判断对某


w


(


v

i


,


v


j


)



w


(


v< /p>


i



1


,


v


j



1

< p>
)



w



v


i


,


v

i



1




w


(


v


j< /p>


,


v


j



1


)



















(18)


2)


若有，删去边


v


i


v


i



1


和

< br>v


j


v


j



1


,


添加边


v


i


v


j


和


v


i



1


v


j



1


得


H


ij


< p>
v


1


v


2


...


v


i


v


j


...


v


i



1


v


j


1


...


v

n


v


1


;


3)



重复


1 )2)


两步，直至不可再用此方法继续进行，则求得一个较优的


Hamilton


圈



为了得到更高的 精度，该程序可以重复几次，每次都以不同的圈开始。



6.1.2




模型求解



1.



总路径示意图：



1)



d


(< /p>


D


,


G


)


打孔路径图：



c


(


I


)



d



c


(


F


)



e



f



b



a



g



h




2)



c< /p>


(


E


)


打孔路径 图：



c


(


I


)



d



c


(


F


)



e



f



b



a



g



h




3)



b


(< /p>


B


)


打孔路径图：


-


-


-


-


-


-


-


-