2023年山东科技大学数学建模竞赛2.doc

山东科技大学数学建模竞赛

承 诺 书

咱们仔细阅读了山东科技大学数学建模竞赛阐明。
咱们完全明白，在竞赛开始后参赛队员不能以任何方式（波及 、电子邮件、网上征询等）与队外任何人（波及指导教师）研究、讨论与赛题有关问题。
咱们懂得，抄袭他人成果是违反竞赛规则，假如引用他人成果或其她公开资料（波及网上查到资料），必要按照规定参照文献表述方式在正文引用处和参照文献中明确列出。
咱们郑重承诺，严格遵守竞赛规则，以保证竞赛公正、公平性。如有违反竞赛规则行为，咱们将受到严厉处理。

咱们参赛选用题号是（从A/B/C/D中选用一项填写）： D
咱们参赛报名号为：
所属学院（请填写完整全名）： 理学院
参赛队员 (打印并签名) ：1. 孙旭
2. 宋宾宾
3. 柴利云

日期： 年 5 月 5日

山东科技大学数学建模竞赛

编 号 专 用 页

评阅记录（可供评阅人评阅时使用）：

评
阅
人

评
分

备
注

最终成绩：

打孔机生产效能提高
摘要
本文是有关提高打孔机效能问题，对钻头行进路线做出安排，使得成本降到最低。咱们对附件中坐标进行分类编号整顿，在不一样状况下，单一化求解条件，使问题得到简化。
打孔机作业成本波及钻头作业、钻头行进成本和刀具转换时间成本，其中钻头作业成本为固定值，将刀具转换成本降到最低状况下寻求行进旅程最短方式建立模型1；在行进总路线最短状况下，计算出刀具转换成本建立模型2；将以上两方式结合起来寻求最佳方案建立模型3。
问题一：
模型1：近来邻点法模型，分析刀具转换时间成本最低状况，可知刀具转换次序为：逆时针dcbahgfedc，共转换9次。按每次换刀对应刀具给钻孔分类，使用近来邻点法构建途程，然后运用2-opt法改善途程。
模型2：遗传基因组合模型，在不考虑换刀状况下，运用遗传算法将每个点看做染色体中一种基因，生成若干群体，模仿生物进化，进行交叉，建立适应函数，求出函数最优解，就是最短路线方案。
模型3：多目旳优化模型，采用环节法（STEM法）处理多目旳优化问题。两个目旳函数分别求至少道具转换和最小旅程，通过整合得到最优解。
问题二：采用分区作业和互补合作方式结合。先分别讨论分区作业和不一样刀具合作效率，再将两者结合，看其效率。分区作业即沿用问题一3个模型即可求解，与问题一无异，用不一样刀具互补则将两钻头沿对角线两端相对行进方式打完整版。

关键词： 近来邻点法 遗传算法 环节法 2-opt改善途程 TSP

一、问题重述：
过孔是印刷线路板重要构成某些之一，印刷电路板制板费用30%到40%是用在过孔上，合理过孔方案可以提高效率，节省成本。打孔机生产效能重要取决于如下几方面：单个过孔钻孔作业时间、打孔机在加工作业时，钻头行进时间、针对不一样孔型加工作业时，刀具转换时间。
钻头有8种刀具，依次排列呈圆环状，只能顺时针或者逆时针转换。题目给出了10种孔型所需加工刀具及加工次序，对于须用两种或两种以上刀具加工过孔，只要保证所需刀具加工次序对旳即可。
问题一：
附件1提供了某块印刷线路板过孔中心坐标数据，单位是1/100密尔（mil）（也称为毫英寸，1 inch=1000 mil），请给出单钻头作业最优作业线路（波及刀具转换方案）、行进时间和作业成本。
问题二：
为提高打孔机效能，目前设计一种双钻头打孔机，两钻头可以同步作业，且作业是独立，即可以两个钻头同步进行打孔，也可以一种钻头打孔，另一种钻头行进或转换刀具。为防止钻头间触碰和干扰，在过孔加工任何时刻必要保持两钻头间距不不不小于3cm（称为两钻头合作间距）。为使问题简化，可以将钻头看作质点。
（1） 针对附件1数据，给出双钻头作业时最优作业线路、行进时间和作业成本，并与老式单钻头打孔机进行比较，其生产效能提高多少？
（2） 研究打孔机两钻头合作间距对作业路线和生产效能产生影响。

二、 问题分析
本题是一种求打孔机完毕目旳任务所需费用最小多目旳优化问题。打孔机生产效能取决于单个过孔钻孔作业时间、打孔机在加工作业时钻头行进时间和针对不一样孔型加工作业时，刀具转换时间。根据题意，打所有孔时间是不变，提高打孔机生产效能即规定打孔机钻头行进时间尽量短，同步钻头转换次数尽量少。而打孔机钻头行进时间与行进旅程有关，即转换为求最短途径问题。
第一问中最优路线是打孔机钻头行进最短距离与钻头转换次数至少结合多目旳优化问题。可以建立三种模型求解：打孔机作业成本波及钻头作业、钻头行进成本和刀具转换时间成本，其中钻头作业成本为固定值，将刀具转换成本降到最低状况下寻求行进旅程最短方式建立模型1；在行进总路线最短状况下，计算出刀具转换成本建立模型2；将以上两方式结合起来寻求最佳方案建立模型3。
将题目所给各孔型坐标导入MATLAB，绘制出了所有孔分布图。再根据分布规律建立模型求出打孔机钻头行进最短距离和路线。然后考虑刀具转换次数至少状况，由题意，可以用一种刀具把需要打孔所有打完再换刀，建立模型得到此状况下最优转换次序。最终列出两个目旳目旳函数和约束条件，用LINGO求解，得到最优解，进而找到单钻头作业最优作业线路（波及刀具转换方案）、行进时间和作业成本。
第二问双钻头问题将机器效率提高了，同步也使问题复杂了。
有两种措施：一种是将两钻头看作互无联络独立个体,把电路板平均提成两块区域1和2,两钻头从两区域同侧开始工作,像同一侧行进,即可一直保持一定相对距离,而不会发生碰撞影响工作；另一种是两钻头合作但用不一样道具互补，尽量减少转换次数，用最邻近算法计算各自路线，同步出发将两钻头看作是两个半径R=1.5cm圆，圆心沿路线行进，找出两圆相交点时刻和相对坐标，到中间将要相遇点时用提前算好时间向不一样方向拐开后再继续行进，进行多次修正和迭代，直到不产生相交点。

三、模型假设
1、假定对于同一孔型钻孔作业时间都是相似，作业时间不影响问题分析，则求解时只分析钻头行进最短距离与钻头转换次数。
2、假定打孔机持续工作，行进期间无停留时间。
3、假定打孔机钻头行进时只在任意两点间做直线运动。
4、假定打孔机钻头转换灵活，持续转换无异常。
5、假定打每个孔时间极短。

四、符号阐明
符号
阐明
单位

a~h种孔型一种

第j个孔坐标
1/100mil

第j个孔横坐标
1/100mil

第j个孔纵坐标
1/100mil

转换次数

过孔旅程
mil

权系数

交叉率

变异率

五、模型建立

5.1 问题一
5.1.1打孔机行进最短旅程
此种状况单考虑打孔机钻头行进完所有点最短旅程，不考虑刀具转换次数，即打孔机行进到哪点即打完这点。将题目所给点坐标导入MATLAB，并将各孔型用不一样点区别开，打孔机所要打所有孔相对位置和孔型见图1。

图1

经记录共有2124个点，规定钻头通过所有点一次，并且总旅程最短。
此问题是一种旅行商问题（TSP）：旅行商问题要从图G所有环游路线中求取最小成本环游路线，而从初始点出发环游路线一共有(n-1)!条，即等于除初始结点外n-1个结点排列数，因而旅行商问题是一种排列问题。排列问题比子集合选用问题一般要难于求解得多，这是由于n个物体有n!种排列，只有n！个 子集合(n!>O( ))。通过枚举(n-1)!条环游路线，从中找出一条具有最小成本环游路线算法，其计算时间显然为O(n!)。
咱们将2124个点看作2124个成市，求解此TSP问题。为此建立3个模型分别求解：
（1）模型一：途程构建法
刀具转换成本最小方案
刀具次序固定，不能调换。要使刀具转换至少，可以排列刀具使用次序，在至少转换次数中，满足每个孔型所需刀具及使用次序条件。转换方式有两种：顺时针转换、逆时针转换。
孔型
A
B
C
D
E
F
G
H
I
J
所需刀具
a
b
a，c
d，e*
c，f
g，h*
d，g，f
h
e，c
f，c
表1

根据如下刀型换刀次序G（d，g，f）、E（c，f）和J（f，c）可知刀具至少要转一周，只需一种刀具和对次序没有限制孔型可以不作考虑。
孔型
C
E
G
I
J
所需刀具
a，c
c，f
d，g，f
e，c
f，c
表2

顺时针：
……a→b→c→d→e→f→g→h→a→b→c→d→e→f→g→h→a→b→c→d→e→f→g→h……

使序列包括不一样5个线段，至少转换次数为10，用刀次序为defghabcdef
逆时针：
……h→g→f→e→d→c→b→a→h→g→f→e→d→c→b→a→h→g→f→e→d→c→b→a……

使序列包括不一样5个线段，至少转换次数为9，用刀次序为dcbahgfedc
因而，按照逆时针dcbahgfedc次序时转换次数至少，刀具转换成本最小。

每次打点为：
d
c
b
a
h
g
f
e
d2
c2
DG
E
B
AC
FH
FG
EGJ
DI

CIJ
表3

此处以钻头a为例阐明行进方案，其她钻头方案解法相似，只列成果。
设用a刀点660+270=930个点分别为a1 a2 a3……a930
钻头a要打孔如图：

图2

使用途程构建法：
①近来邻点法（Nearest Neighbor Procedure）：一开始以寻找离场站近来需求点为起始路线第一种顾客，此后寻找离最终加入路线顾客近来需求点，直到最终。
程序：
设一种定点：找出它近来邻点，然后找该点近来邻点，直至最终一种点。
对数组[a]进行排列：第一种点定为a1，查找近来邻点ai，并删除a1，查找下一种点aj，并删除ai……直至第n个点，使她们按次序排列为[aa]
取最小值r1i
最邻近点发求最短途径示意图见图3：

图3
②途程改善法
K-Opt(2 Opt)：把尚未加入途径2条节线临时取代目前途径中2条节线，并计算其成本（或距离），假如成本减少（距离减少），则取代之，直到无法改善为止。
经改善后处理状况数大量简化，由于本题所给点数众多，算法复杂度过大，对100点以内状况合用措施在此不合用，由于建模时间问题，未能给出完整答案，只摆出了措施。

（2）模型二：遗传算法
遗传算法是一种模仿生命进化机制搜索和优化措施，是把自然遗传学和计算机科学结合起来优化方程，有很强处理问题能力和广泛适应性。其假设常描述为二进制位串，位 串含义依赖于详细应用。搜索合适假设从若干初始假设群体集合开始。目前种群组员通过模仿生物进化 方式来产生下一代群体，如随机变异和交叉。每一步，根据给定适应度评估目前群体假设，而后使用概率措施选出适应度最高假设作为产生下一代种子。
在本程序TSP问题中一共有2124个都市，也就是在图模型中有2124个顶点，因而一种染色体长度为2124。

定义：适应函数f(i)
对具有n个顶点图，已知各顶点之间(,)边长度d(,)，把到间一条通路途径长度定义为适应函数：

对该最优化问题，就是要寻找解，使f()值最小。、
旅行商问题遗传算法详细环节
解最短途径遗传算法如下：
第一：Generate[p(n)];体现程序开始时要首先产生一种群体，群体个数为n。
第二：Evaluate[p(h)];体现计算每个个体适应度，h是种群中一种个体。
第三：Repeat roof Generations times;反复下面操作，直到满足条件为止。
第四：Select p(h) from p(n-1);体现从前一代群体中选用一对双亲，用于交叉、变异 操作，P(n)代表第n代群体。
第五：Crossover and mutation p(n);进行交叉和变异操作
第六：Learning[p(n)];自学习过程。
第七：Evaluate[p(h)];计算新生成种群中每个个体适应度。
试验测试成果
交叉率不可选用过小，否则，延缓获得最优解过程，本程序选用=0.85。
变异率选用对规模大优化问题影响很大，本程序选=0.1。
群体中个体数选用是算法中一种很重要参数，群体中个体数目越大，算法就越能找到更好解，个体数目过小，有也许找不到最优解。本程序种群大小为30000。
由于有2124个都市，每个都市作为染色体中一种基因，因而在本程序中染色体长度为2124(程序见附录5.1.1）。

（3）模型三：多目旳优化
将题目最优解转化为多目旳优化问题，本文采用环节法（STEM法）处理多目旳优化问题。环节法基本思想是，首先需规定出原多目旳问题一组理想解(f1*,f2*,…,fp*)。实际上，这些解fi*(i=1,2,…,p)无法同步到达，但可以当作一组理想最优值。以理想解作为一种原则，可以估计有效解，然后通过对话，不停修改目旳值，并把减少规定目旳作为新约束条件加入本来约束条件中去重新计算，直到决策者得到满意解。
第一步：分别求出考虑转换次数至少状况下总成本和不考虑道具转换次数状况下，只考虑钻头行进途径最短状况下成本问题最优解。
转换次数最小：

坐标单位是1/100密尔（mil）
1mil=0.00245cm=0.0245mm
(i=1，2，3……，=a,b,c,d,e,f,g,h)
n=各道具要打孔数量

总旅程最小：

s.t.
得到最优解其对应目旳值为
第二步：求解

其中
这里
第三步：将上述模型解X0与对应目旳值f1(X0)，f2(X0)， …,fp(X0) 交给决策者去判断。假如与模型一和二相差太大就不符合，舍去解，保留符合条件。再从符合条件解中找出最优作为结论方案。

5.2 问题二
5.2.1方案一:分区工作
将两钻头看作互无联络独立个体,把电路板平均提成两块区域1和2,两钻头从两区域同侧开始工作,像同一侧行进,即可一直保持一定相对距离,而不会发生碰撞影响工作。如图4所示:

图4

详细分派各自路线、转换方案解法同问题1，只是区域和点有所变动。可以设中心线为直线假设采用模型一：
1区钻头最小成本

类似，2区最小成本

得到最优解其对应目旳值为

5.2.2方案二：互补合作
检查两圆与否相切
所谓互补合作就是两钻头不再孤立，而是分别在整个版上行进一遍。互补即互相补充对方没有使用道具，两钻头平分几种道具使用权限而不反复，例如甲钻头使用道具a,c,e,g,乙钻头使用道具b,d,f,h。由于同步作业整版，就要考虑向碰撞问题。处理此问题方案采用对角线相对行进方式，即两钻头分别沿对角线两端出发相向行进，用最邻近算法计算各自路线，同步出发将两钻头看作是两个半径R=1.5cm圆，圆心沿路线行进，找出两圆相交点时刻和相对坐标，到中间将要相遇点时用提前算好时间向不一样方向拐开后再继续行进，进行多次修正和迭代，直到不产生相交点。

两钻头同步出发
记录任一时刻相对位置
流程图如下：

否

是
找到切点时刻及相对位置，对路线做微小修正

此路线L即为两钻头共同作业路线

示意图如下：

图5

六、 模型评价
模型一和模型二都只考虑单方面变量，计算简化了，但不是最优解。模型三考虑到了多目旳规划，将两个变量都考虑到了，最为充足，离最优解最靠近。

参照文献：
[1] 解可新，韩健，林友联，最优化措施[M].天津:天津大学出版社,1997
[2] 米凯利维茨Z.演化程——遗传算法和数据编码结合[M]北京:科学出版社,
[3] 李飞， 白艳萍， LI Fei， BAI Yan-ping 中北大学,理学院,山西,太原,030051中北大学学报（自然科学版）用遗传算法求解旅行商问题

附录
5.1.1
%遗传算法求解旅行商问题
%初始化
a=[1304 2312;3639 1315;4177 2244;3712 1399;3488 1535;3326 1556;...
3238 1229;4196 1044;4312 790;2864 570;1927 1970;2562 1756;...
2788 1491;2381 1676;1332 695;3715 1678;3918 2179;4061 2370;...
3780 2212;3676 2578;1537 2838;2745 2931;3429 1908;3507 2376;...
];%a：假定24个都市坐标

n=100;%n：种群个数
C=200;%C：停止代数
m=2;%m：适配值淘汰加速指数,不合适太大
Pc=0.9;%Pc：交叉概率
Pm=0.2;%Pm： 变异概率
D=distance(a);%生成距离矩阵
[R,Rlength]=GeneTSP(D,a,n,C,m,Pc,Pm);
%返回值：最优途径R
% 总距离Rlength
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%D：距离矩阵
%n：种群个数
%a：31个都市坐标，在初始化时设定
%C:停止代数
%m:适值淘汰加速指数,不合适太大(5如下)
%Pc：交叉概率
%Pm：变异概率
%R：最短途径，Rlength：途径长度
function [R,Rlength]=GeneTSP(D,a,n,C,m,Pc,Pm)

[N,NN]=size(D)； %(31*31)
farm=zeros(n,N)； %存储种群
%随机生成初始种群，随机产生从1到NN个初始值，例如，RANDPERM(6) ,也许成果为：[2 4 5 6 1 3].
for i=1:n
farm(i,:)=randperm(N)；
end
R=farm(1,:)； %一种随机解(个体)
scatter(a(:,1),a(:,2),'x')；%画出所有点,a(:,1):X坐标,a(:,2):Y坐标
hold on
pause(1)
%画出随机解得途径图
figure;
plotaiwa(a,R);
hold on
pause(1)
%输出随机解得途径和总距离
disp('初始种群中一种随机值:')
Rlength=myLength(D,R)
%计算各个个体总距离和适配置
len=zeros(n,1);%存储途径长度
fitness=zeros(n,1);%存储适配值
counter=0;

while counter<C
for i=1:n
len(i,1)=myLength(D,farm(i,:));%计算途径长度
end
minlen=min(len);
rr=find(len==minlen);%返回是在len中途径最短途径坐标(i,1)
R=farm(rr(1,1),:);%更新最短途径
FARM=farm;%优胜劣汰，nn记录了复制个数
%选用
K=23;
[aa,bb]=size(FARM);
FARM2=FARM;
len2=len;
[len]=sort(len);
for i=1:aa
tt= find(len2==len(i,1));
FARM(i,:)=FARM2(tt(1,1),:);
end
for i=1:K
j=aa+1-i;
FARM(j,:)=FARM(i,:);

end
%交叉操作
[aa,bb]=size(FARM);
FARM2=FARM；
for i=1:2:aa
if Pc>rand&&i<aa %交叉概率Pc
A=FARM(i,:);
B=FARM(i+1,:);
[A,B]=cross(A,B);%交叉算法采用某些匹配交叉
FARM(i,:)=A;
FARM(i+1,:)=B;
end
end

%变异
FARM2=FARM;
for i=1:aa
if Pm>=rand
FARM(i,:)=mutate(FARM(i,:));
end
end

FARM=[R;FARM];%将随机产生n-aa个体加入从背面种群,将上次迭代最优解从前面加入种群
[aa,bb]=size(FARM);

%保持种群规模为n
if aa>n
FARM=FARM(1:n,:);
end
%更新farm
farm=FARM;
clear FARM
%更新迭代次数
counter=counter+1 ；
end
%成果输出

Rlength=myLength(D,R)
figure
plotaiwa(a,R)%画图
disp('迭代次数c')；
disp(C);
disp('迭代后成果')；
Rlength=myLength(D,R)%成果输出
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%计算邻接矩阵
%输入参数a是中华人民共和国31个都市坐标
%输出参数D是无向图赋权邻接矩阵

function D=distance(a)
[c,d]=size(a);%此例中c=24,d=2
D=zeros(c,c);%申请一种0阵
for i=1:c
for j=i:c
bb=(a(i,1)-a(j,1)).^2+(a(i,2)-a(j,2)).^2;
D(i,j)=bb^(0.5);%计算第i个都市到j都市距离
D(j,i)=D(i,j);
end
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%总途径len
function len=myLength(D,p)
[N,NN]=size(D);
len=D(p(1,N),p(1,1));
for i=1:(N-1)
len=len+D(p(1,i),p(1,i+1));
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%绘制途径示意图 R记录途径
%a：假定24个都市坐标
%R：最短途径
function plotaiwa(a,R)
scatter(a(:,1),a(:,2),'x')
hold on
plot([a(R(1),1),a(R(24),1)],[a(R(1),2),a(R(24),2)])
hold on
for i=2:length(R)
x0=a(R(i-1),1);
y0=a(R(i-1),2);
x1=a(R(i),1);
y1=a(R(i),2);
xx=[x0,x1];
yy=[y0,y1];
plot(xx,yy)
hold on
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%交叉算法采用某些匹配交叉
function [a,b]=cross(a,b)
L=length(a);
if L<=10 %确定交叉宽度
W=9;
elseif ((L/10)-floor(L/10))>=rand&&L>10
W=ceil(L/10)+8;
else
W=floor(L/10)+8;
end
p=unidrnd(L-W+1);
%随机选用交叉范围，从p到p+W
% UNIDRND Random arrays from the discrete uniform distribution.
% R = UNIDRND(N) returns an array of random numbers chosen uniformly
% from the set {1，2，3，... ,N}. The size of R is the size of N.
%
% R = UNIDRND(N,MM,NN,...) or R = UNIDRND(N,[MM,NN,...]) returns an
% MM-by-NN-by-... array.
for i=1:W
%交叉
x=find(a==b(1,p+i-1));
y=find(b==a(1,p+i-1));
[a(1,p+i-1),b(1,p+i-1)]=exchange(a(1,p+i-1),b(1,p+i-1));
[a(1,x),b(1,y)]=exchange(a(1,x),b(1,y))；
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%变异算法
function a=mutate(a)
L=length(a);
rray=randperm(L);
[a(rray(1)),a(rray(2))]=exchange(a(rray(1)),a(rray(2)));