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、假定打每个孔时间极短。四、符号阐明符号 阐明单位 ah种孔型一种第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）模型一：途程构建法 刀具转换成本最小方案 刀具顺序固定，不能调换。要使刀具转换至少，可以排列刀具使用顺序，在至少转换次数中，满足每个孔型所需刀具及使用顺序条件。转换方式有两种：顺时针转换、逆时针转换。孔型ABCDEFGHIJ所需刀具aba，cd，e*c，fg，h*d，g，fhe，cf，c表1依照如下刀型换刀顺序G（d，g，f）、E（c，f）和J（f，c）可知刀具至少要转一周，只需一种刀具和对顺序没有限制孔型可以不作考虑。孔型CEGIJ所需刀具a，cc，fd，g，fe，cf，c表2顺时针：abcdefghabcdefghabcdefgh使序列涉及不同5个线段，至少转换次数为10，用刀顺序为defghabcdef逆时针：hgfedcbahgfedcbahgfedcba使序列涉及不同5个线段，至少转换次数为9，用刀顺序为dcbahgfedc因而，按照逆时针dcbahgfedc顺序时转换次数至少，刀具转换成本最小。每次打点为：dcbahgfed2c2DGEBACFHFGEGJDICIJ表3此处以钻头a为例阐明行进方案，其她钻头方案解法相似，只列成果。设用a刀点660+270=930个点分别为a1 a2 a3a930钻头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()值最小。、 旅行商问题遗传算法具体环节 解最短途径遗传算法如下： 第一：Generatep(n);表达程序开始时要一方面产生一种群体，群体个数为n。 第二：Evaluatep(h);表达计算每个个体适应度，h是种群中一种个体。 第三：Repeat roof Generations times;反复下面操作，直到满足条件为止。 第四：Select p(h) from p(n-1);表达从前一代群体中选取一对双亲，用于交叉、变异 操作，P(n)代表第n代群体。 第五：Crossover and mutation p(n);进行交叉和变异操作 第六：Learningp(n);自学习过程。 第七：Evaluatep(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.天津:天津大学出版社,19972 米凯利维茨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=2D=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); endend%总途径lenfunction 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 onplot(a(R(1),1),a(R(24),1),a(R(1),2),a(R(24),2)hold onfor 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 onend%交叉算法采用某些匹配交叉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;endp=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);