2025年中国大学生数学建模挑战赛赛事

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

承诺书

我们仔细阅读了山东科技大学数学建模竞赛阐明。

我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网

上征询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。

我们懂得，抄袭他人的成果是违反竞赛规则的，假如引用他人的成果或其他公开的

资料（包括网上查到的资料），必须按照规定的参照文献的表述方式在正文引用处和参

照文献中明确列出。

我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规

则的行为，我们将受到严厉处理。

我们参赛选择的题号是（从A/B/C/D中选择一项填写）：D

我们的参赛报名号为：___________________________________________

所属学院（请填写完整的全名）：理学院

参赛队员（打印并签名）：1.____________孙旭__________________________

2._____________宋宾宾________________________

3._____________柴利云________________________

日期：年5月5日

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

编号专用页

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

评

阅

人

评

分

备

注

最终成绩:

打孔机生产效能的提高

摘要

本文是有关提高打孔机效能的问题，对钻头行进路线做出安排，使得成本降到最低。

我们对附件中的坐标进行分类编号整顿，在不一样的状况下，单一化求解条件，使问题

得到简化。

打孔机的作业成本包括钻头作业、钻头行进成本和刀具转换的时间成本，其中钻头

作业成本为固定值，将刀具转换成本降到最低的状况下寻求行进旅程最短的方式建立模

型1;在行进总路线最短的状况下，计算出刀具转换成本建立模型2；将以上两方式结

合起来寻求最佳方案建立模型3。

问题一：

模型1：近来邻点法模型，分析刀具转换的时间成本最低的状况，可知刀具转换次

序为：逆时针dcbahgfcdc,共转换9次。按每次换刀对应的刀具给钻孔分类，使用近来

邻点法构建途程，然后运用2-opt法改善途程。

模型2：遗传基因组合模型，在不考虑换刀的状况下，运用遗传算法将每个点看做

染色体中的一种基因，生成若干群体，模仿生物进化，进行交叉，建立适应函数，求出

函数的最优解，就是最短路线的方案。

模型3：多目的优化模型，采用环节法（STEM法）处理多目的优化问题。两个目的

函数分别求至少道具转换和最小旅程，通过整合得到最优解。

问题二：采用分区作业和互补合作的方式结合。先分别讨论分区作业和不一样刀具

合作的效率，再将两者结合，看其效率。分区作业即沿用问题一的3个模型即可求解，

与问题一无异，用不一样刀具互补则将两钻头沿对角线两端相对行进的方式打完整版。

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

次序。最终列出两个目的的目的函数和约束条件，用LINGO求解.，得到最优解，进而找

到单钻头作业的最优作业线路（包括刀具转换方案）、行进时间和作业成本。

第二问双钻头问题将机器效率提高了，同步也使问题复杂了。

有两种措施：一种是洛两钻头看作互无联络的独立个体,把电路板平均提成两块区

域1和2,两钻头从两区域同侧开始工作，像同一侧行进，即可一直保持一定的相对距离,

而不会发生碰撞影响工作；另一种是两钻头合作但用不一样的道具互补，尽量减少转换

次数，用最邻近算法计算各自的路线，同步出发将两钻头看作是两个半径R=l.5cm的圆,

圆心沿路线行进，找出两圆相交的点的时刻和相对坐标，到中间将要相遇点时用提前算

好的时间向不一样方向拐开后再继续行进，进行多次修正和迭代，直到不产生相交点。

三、模型假设

1、假定对于同一孔型钻孔作业时间都是相似的，作业时间不影响问题的分析，则

求解时只分析钻头行进最短距离与钻头转换次数。

2、假定打孔机持续工作，行进期间无停留时间c

3、假定打孔机钻头行进时只在任意两点间做直线运动。

4、假定打孔机钻头转换灵活，持续转换无异常c

5、假定打每个孔时间极短。

四、符号阐明

符号阐明单位

a~h种孔型的一种

匕第」个孔的坐标l/100mil

町第」个孔的横坐标l/100mil

也•第」个孔的纵坐标l/100mil

转换次数

Sj过孔旅程mil

力0=1,2）的权系数

匹

P,交叉率

变异率

五、模型建立

5.1问题一

5.1.1打孔机行进最短旅程

此种状况单考虑打孔机钻头行进完所有点的最短旅程，不考虑刀具转换次数，即打

孔机行进到哪点即打完这点。将题目所给点的坐标导入MATLAB,并将各孔型用不一样点

区别开，打孔机所要打的所有孔的相对位置和孔型见图1。

9

8

7

6

5型A

型B

4型C

型D

3

型E

型F

2

型G

型H

1

型I

型J

0

-1

-6-4-20246

x105

图1

经记录共有2124个点，规定钻头通过所有点一次，并且总旅程最短。

此问题是一种旅行商问题(TSP)：旅行商问题要从图G的所有环游路线中求取最小

成本的环游路线，而从初始点出发的环游路线一共有(nT)!条，即等于除初始结点外的

nT个结点的排列数，因此旅行商问题是一种排列问题。排列问题比子集合的选择问题

一般要难于求解得多，这是由于n个物体有n!种排列，只有n!个子集合(n!)0())。

通过枚举(n-l)!条环游路线，从中找出一条具有最小成本的环游路线的算法，其计算时

间显然为0(n!).

我们将2124个点看作2124个成市，求解此TSP问题。为此建立3个模型分别求解:

(1)模型一：途程构建法

刀具转换成本最小方案

刀具的次序固定，不能调换。要使刀具转换至少，可以排列刀具的使用次序，在至

少的转换次数中，满足每个孔型所需刀具及使用次序的条件。转换方式有两种：顺时针

转换、逆时针转换。

孔型ABCDEFGHIJ

所需刀具ba,cd,e*g,h*d,g,fhe,cf,c

表1

根据如下刀型换刀次序GId,g,f)、E(c,f)和J(f,c)可知刀具至少要转一周,

只需一种刀具和对次序没有限制的孔型可以不作考虑

孔型CEGIJ

所需刀具a,cc,fd，g，fe,cf,c

表2

顺时针:

使序列包括不一样的5个线段，至少的转换次数为10,用刀次序为defghabcdef

逆时针：

使序列包括不一样的5个线段，至少的转换次数为9,用刀次序为dcbahgfedc

因此，按照逆时针的dcbahgfedc次序时转换次数至少，刀具转换的成本最小。

每次打点为:

dcbahgfed2c2

DGEBACFHFGEGJDICIJ

表3

此处以钻头a为例阐明行进方案，其他钻头方案解法相似，只列成果。

设用a刀的点660+27刃930个点分别为ala2a3……a930

钻头a要打的孔如图：

xIO*

xIO1

图2

使用途程构建法：

①近来邻点法(NearestNeighborProcedure)：一开始以寻找离场站近来的需求点为起始

路线的第一种顾客，此后寻找离最终加入路线的顾客近来的需求点，直到最终C

程序：

设一种定点：找出它近来邻的点，然后找该点的近来邻点，直至最终一种点。

对数组同进行排列：第一种点定为al,查找近来邻点ai,并删除al,查找下一种点aj,

并删除ai……直至第n个点，使他们按次序排列为[aa]

取最小值rli

最邻近点发求最短途径示意图见图3：

t00•.00

000V00

00

00

0

V\0

00

00

W\

…(

0”

图3

②途程改善法

K-Opt(2Opt)：把尚未加入途径的2条节线临时取代目前途径中2条节线，并计算其成本

(或距离)，假如成本减少(距离减少)，则取代之，直到无法改善为止。

经改善后处理的状况数大量简化，由于本题所给点数众多，算法复杂度过大，对100

点以内状况合用的措施在比不合用，由于建模时间问题，未能给出完整答案，只摆出了

措施。

(2)模型二：遗传算法

遗传算法是一种模拟生命进化机制的搜索和优化措施，是把自然遗传学和计算机科

学结合起来的优化方程，有很强的处理问题的能力和广泛的适应性。其假设常描述为二

进制位串，位串的含义依赖于详细应用。搜索合适的假设从若干初始假设的群体集合

开始。目前种群组员通过模仿生物进化的方式来产生下一代群体，如随机变异和交叉。

每一步，根据给定的适应度评估目前群体的假设，而后使用概率措施选出适应度最高的

假设作为产生下一代的种子。

在本程序的TSP问题中一共有2124个都市，也就是在图模型中有2124个顶点，因

此一种染色体的长度为2124。

定义：适应函数f(i)

对具有n个顶点的图，已知各顶点之间(匕，〃)的边长度d(匕.，〃)，把心到山间的

一条通路的途径长度定义为适应函数：

n-1

f(i)=W

r=l

对该最优化问题，就是要寻找解乙,使f(乙)值最小八

旅行商问题的遗传算法的详细环节

解最短途径的遗传算法如下：

第一：Gcncrate[p(n)];表达程序开始时要首先产生一种群体，群体个数为n。

第二：Evaluate[p(h)];表达计算每个个体适应度，h是种群中的一种个体。

第三：RepeatroofGenerationstimes;反复下面的操作，直到满足条件为止。

第四：Selectp(h)fromp(nT);表达从前一代群体中选择一对双亲，用于交叉、

变异操作，P(n)代表第n代群体。

第五：Crossoverandmutationp(n);进行交叉和变异操作

第六；Lcarning[p(n)];自学习过程。

第七：Evaluate[p(h)];计算新生成的种群中每个个体的适应度。

试验测试成果

交叉率2不可选择过小，否则，延缓获得最优解的过程，本程序选择2=0.85。

变异率P,”的选择对规模大的优化问题影响很大，本程序选化”0.晨

群体中的个体数的选用是算法中一种很重要的参数，群体中的个体数目越大，算法

就越能找到更好的解，个体数目过小，有也许找不到最优解。本程序种群大小为30000。

由于有2124个都市，每个都市作为染色体中的一种基因，因此在本程序中染色体

的长度为2124(程序见附录5.1.1)0

(3)模型三：多目的优化

将题目的最优解转化为多目的优化问题，本文采用环节法(STEM法)处理多目的优化

问题。环节法的基本思想是，首先需规定出原多目的问题的一组理想解

(fl*,f2*，…，fp*)。实际上,这些解fi*(i=l,2,…,p)无法同步到达，但可以当作一组

理想的最优值。以理想解作为一种原则，可以估计有效解，然后通过对话，不停修改目

的值，并把减少规定的目的作为新的约束条件加入本来的约束条件中去重新计算，直到

决策者得到满意的解。

第一步：分别求出考虑转换次数至少的状况下总成本和不考虑道具转换次数的状况下，

只考虑钻头行进途径最短状况下的成本问题的最优解。

转换次数最小：

10n

min力(1)=(匕，匕+])*0.06*0.0245*0.01+10*7*18/60

坐标单位是1/100密尔(mil)

lmil=O.00245cm=0.0245mm

(i=l,2,3....,^=a,b,c,d,e,f,g,h)

n二各道具要打孔的数量

处")=10

s.t/S;(x)>0

d(WjWQ=—限)+(0"一”厅

总旅程最小：

2124

minf2(x)=2d(匕，匕川)*0.06*0.0245*0.01+gk(x)*7*18/60

月

g式>0

“S'f(x)>0

S.t..(匕,，夕门)=J(少加—-j>+(">->

得到最优解M”(i=1,2)其对应目的值为f，i=1,2)

第二步：求解

min4

一£(X))«Zi=l,2,...,p

,XeS

2>0

a

肛二三一

其中W,

这里'3T'

ZcJ，力”。

Ji3T/

第三步：将上述模型的解X0与对应的目的值门(X0),f2(X0),…，fp(XO)交给决策者

去判断。假如与模型一和二相差太大就不符合，舍去解，保留符合条件的。再从符合条

件的解中找出最优的作为结论方案。

5.2问题二

5.2.1方案一:分区工作

将两钻头看作互无联络的独立个体,把电路板平均提成两块区域1和2,两钻头从两区域

同侧开始工作，像同一侧行进，即可一直保持一定的相对距离，而不会发生碰撞影响工

作。如图4所示：

9

8

7

6

5型A

型B

4型C

型D

3

型E

型F

2

型G

型H

1

型I

型J

0

-1

-6-4-20246

x105

图4

详细分派各自路线、转换方案的解法同问题1,只是区域和点有所变动。可以设中心线

为直线x=x"=l,2,3……假设采用模型一：

10n

1区钻头最小成本min=（匕，匕川）*。06*。，02^*0.01+10*7*18/60

g,(x)=10

S.(x)>0

s.t.<

dBjWQ=J一小厅斗一忤尸

x<xf

)0n

d060245

类似的，2区最小成本minf2(x)=JL^j)*^*O-*0.01+10*7*18/60

*=ij=i

gj(x)=10

5,(x)>0

d(Wj，WQ=J-尸+(小加一汐j>

x>xf

得到最优解/(i=1,2)其对应目的值为f(i=1,2)

5.2.2方案二：互补合作

所谓互补合作就是两钻头不再孤立，而是分别在整个版上行进一遍。互补即互相补充对

方没有使用的道具，两钻头平分几种道具的使用权限而不反复，例如甲钻头使用道具

a,c,e,g,乙钻头使用道具b,d,f,h。由于同步作业整版，就要考虑向碰撞问题。处理此

问题的方案采用对角线相对行进的方式，即两钻头分别沿对角线两端出发相向行进，用

最邻近算法计算各自的路线，同步出发将两钻头看作是两个半径R=L5cm的圆，圆心沿

路线行进，找出两圆相交的点的时刻和相对坐标，到中间将要相遇点时用提前算好的时

间向不一样方向拐开后再继续行进，进行多次修正和迭代，直到不产生相交点c

流程图如下:

参照文献：

[1]解可新，韩健，林友联，最优化措施[M].天津:天津大学出版社，1997

[2]米凯利维茨Z.演化程一一遗传算法和数据编码的结合[M]北京:科学出版社，

[3]李飞，白艳萍，LIFei,BAIYan-ping中北大学,理学院，山西，太原,C30051

中北大学学报(自然科学版)用遗传算法求解旅行商问题

附录

5.1.1

%遗传算法求解旅行商问题

务初始化

a=[13042312;36391315;41772244;37121399;34881535;33261556;...

32381229;41961044;4312790;2864570;19271970;25621756;...

27881491;23811676;1332695;37151678;39182179;40612370;...

37802212;36762578;15372838;27452931;34291908;35072376;...

]；%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个都市的坐标，在初始化时设定

9C:停止代数

考m:适值淘汰加速指数，不适宜太大(5如下)

%Pc：交叉概率

%Pm：变异概率

%R：最短途径，Rlength：途径长度

function[R,Rlength]=GeneTSP(D,a,n,C,m,Pc,Pn)

[N,NN]=size(D);%(31*31)

farm=zeros(nzN);名存储种群

省随机生成初始种群，随机产生从1到N的N个初始值，例如，RANDPERM(6)，也许成果

为：[245613].

fori=l:n

farm(i,:)=randperm(N);

end

R=fArm(1z:);3一种随机解(个体)

scatter(a(:,1),a(:,2),*x');告画出所有点，a(:,1):X坐标,a(:,2):Y坐标

holdon

pause(1)

%画出随机解得途径图

figure;

plotaiwa(a,R);

holdon

pause(1)

阳输出随机的解得途径和总距离

disp(,初始种群中的一种随机值:')

Rlength=myLength(D,R)

当计算各个个体总距离和适配置

len=zeros(n,1);%存储途径长度

fitness=zeros(n,1);当存储适配值

counter=0;

whilecounter<0

fori-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),:;3更新最短途径

FARM=farm;%优胜劣汰，rm记录了复制的个数

先选择

K=23;

[aa,bbj=size(FARM);

FARM2=FARM;

len2=len;

[len]=sort(len);

fori=l:aa

tt=find(len2==len(iz1));

FARM(iz:)=FARM2(tt(1,1),:);

end

fori=l:K

FARM(j,:)=FARM(iz:);

end

%交叉操作

[aa,bb]=size(FARM);

FARM2=FARM;

fori=l:2:aa

ifPc>rand&&i<aa急交叉概率Pc

A=FARM(i,:);

B=FARM(i+l,:);

[A,B]=cross(A,B)—交叉算法采用部分匹配交叉

FARM(i,:)=A;

FARM(i+l,:)=B;

end

end

为变异

FARM2=FARM;

fori=l:aa

ifPm>=rand

FARM(i,:)=mutate(FARM(i,:));

end

end

FARM=[R;FARM]将随机产生的n-aa个体加入从背面种群，将上次迭代的最优解从

前面加入种群

[aa,bb]-size(FARM);

为保持种群规模为n

ifaa>n

FARM=FARM(l:n,:);

end

当更新farm

farm=FARM;

clearFARM

务更新迭代次数

counter=counter+l;

end

带成果输出

Rlength=myLength(D,R)

figure

plotaiwa(a,R)务画图

disp「迭代次数c";

disp(C);

disp(,迭代后成果,);

Rlength=myLength(D,R)售成果输;Il

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

会计算邻接矩阵

%输入参数a是中国31个都市的坐标

%输出参数D是无向图的赋权邻接矩阵

functionD=distance(a)

[c,d]=si7A(a);东此例中c=?4,d=2

D=zeros(c,c);*申请一种0阵

fori=l:c

forj=i:c

AA

bb=(a(izl)-a(jzl)).2+(a(i,2)-a(jz2)).2;

D(i,j)=bb-(0.5);钎十算第i个都市到j都市的距离

D(j,i)