2023年山东科技大学数学建模竞赛2.doc
《2023年山东科技大学数学建模竞赛2.doc》由会员分享,可在线阅读,更多相关《2023年山东科技大学数学建模竞赛2.doc(31页珍藏版)》请在咨信网上搜索。
1、山东科技大学数学建模竞赛承 诺 书咱们仔细阅读了山东科技大学数学建模竞赛阐明。咱们完全明白,在竞赛开始后参赛队员不能以任何方式(波及 、电子邮件、网上征询等)与队外任何人(波及指导教师)研究、讨论与赛题有关问题。咱们懂得,抄袭他人成果是违反竞赛规则,假如引用他人成果或其她公开资料(波及网上查到资料),必要按照规定参照文献表述方式在正文引用处和参照文献中明确列出。咱们郑重承诺,严格遵守竞赛规则,以保证竞赛公正、公平性。如有违反竞赛规则行为,咱们将受到严厉处理。咱们参赛选用题号是(从A/B/C/D中选用一项填写): D 咱们参赛报名号为: 所属学院(请填写完整全名): 理学院 参赛队员 (打印并签
2、名) :1. 孙旭 2. 宋宾宾 3. 柴利云 日期: 年 5 月 5日山东科技大学数学建模竞赛编 号 专 用 页评阅记录(可供评阅人评阅时使用):评阅人评分备注最终成绩:打孔机生产效能提高摘要本文是有关提高打孔机效能问题,对钻头行进路线做出安排,使得成本降到最低。咱们对附件中坐标进行分类编号整顿,在不一样状况下,单一化求解条件,使问题得到简化。打孔机作业成本波及钻头作业、钻头行进成本和刀具转换时间成本,其中钻头作业成本为固定值,将刀具转换成本降到最低状况下寻求行进旅程最短方式建立模型1;在行进总路线最短状况下,计算出刀具转换成本建立模型2;将以上两方式结合起来寻求最佳方案建立模型3。问题一:
3、模型1:近来邻点法模型,分析刀具转换时间成本最低状况,可知刀具转换次序为:逆时针dcbahgfedc,共转换9次。按每次换刀对应刀具给钻孔分类,使用近来邻点法构建途程,然后运用2-opt法改善途程。模型2:遗传基因组合模型,在不考虑换刀状况下,运用遗传算法将每个点看做染色体中一种基因,生成若干群体,模仿生物进化,进行交叉,建立适应函数,求出函数最优解,就是最短路线方案。模型3:多目旳优化模型,采用环节法(STEM法)处理多目旳优化问题。两个目旳函数分别求至少道具转换和最小旅程,通过整合得到最优解。问题二:采用分区作业和互补合作方式结合。先分别讨论分区作业和不一样刀具合作效率,再将两者结合,看其
4、效率。分区作业即沿用问题一3个模型即可求解,与问题一无异,用不一样刀具互补则将两钻头沿对角线两端相对行进方式打完整版。关键词: 近来邻点法 遗传算法 环节法 2-opt改善途程 TSP一、问题重述:过孔是印刷线路板重要构成某些之一,印刷电路板制板费用30%到40%是用在过孔上,合理过孔方案可以提高效率,节省成本。打孔机生产效能重要取决于如下几方面:单个过孔钻孔作业时间、打孔机在加工作业时,钻头行进时间、针对不一样孔型加工作业时,刀具转换时间。钻头有8种刀具,依次排列呈圆环状,只能顺时针或者逆时针转换。题目给出了10种孔型所需加工刀具及加工次序,对于须用两种或两种以上刀具加工过孔,只要保证所需刀
5、具加工次序对旳即可。问题一:附件1提供了某块印刷线路板过孔中心坐标数据,单位是1/100密尔(mil)(也称为毫英寸,1 inch=1000 mil),请给出单钻头作业最优作业线路(波及刀具转换方案)、行进时间和作业成本。问题二:为提高打孔机效能,目前设计一种双钻头打孔机,两钻头可以同步作业,且作业是独立,即可以两个钻头同步进行打孔,也可以一种钻头打孔,另一种钻头行进或转换刀具。为防止钻头间触碰和干扰,在过孔加工任何时刻必要保持两钻头间距不不不小于3cm(称为两钻头合作间距)。为使问题简化,可以将钻头看作质点。(1) 针对附件1数据,给出双钻头作业时最优作业线路、行进时间和作业成本,并与老式单
6、钻头打孔机进行比较,其生产效能提高多少?(2) 研究打孔机两钻头合作间距对作业路线和生产效能产生影响。二、 问题分析本题是一种求打孔机完毕目旳任务所需费用最小多目旳优化问题。打孔机生产效能取决于单个过孔钻孔作业时间、打孔机在加工作业时钻头行进时间和针对不一样孔型加工作业时,刀具转换时间。根据题意,打所有孔时间是不变,提高打孔机生产效能即规定打孔机钻头行进时间尽量短,同步钻头转换次数尽量少。而打孔机钻头行进时间与行进旅程有关,即转换为求最短途径问题。第一问中最优路线是打孔机钻头行进最短距离与钻头转换次数至少结合多目旳优化问题。可以建立三种模型求解:打孔机作业成本波及钻头作业、钻头行进成本和刀具转
7、换时间成本,其中钻头作业成本为固定值,将刀具转换成本降到最低状况下寻求行进旅程最短方式建立模型1;在行进总路线最短状况下,计算出刀具转换成本建立模型2;将以上两方式结合起来寻求最佳方案建立模型3。将题目所给各孔型坐标导入MATLAB,绘制出了所有孔分布图。再根据分布规律建立模型求出打孔机钻头行进最短距离和路线。然后考虑刀具转换次数至少状况,由题意,可以用一种刀具把需要打孔所有打完再换刀,建立模型得到此状况下最优转换次序。最终列出两个目旳目旳函数和约束条件,用LINGO求解,得到最优解,进而找到单钻头作业最优作业线路(波及刀具转换方案)、行进时间和作业成本。第二问双钻头问题将机器效率提高了,同步
8、也使问题复杂了。有两种措施:一种是将两钻头看作互无联络独立个体,把电路板平均提成两块区域1和2,两钻头从两区域同侧开始工作,像同一侧行进,即可一直保持一定相对距离,而不会发生碰撞影响工作;另一种是两钻头合作但用不一样道具互补,尽量减少转换次数,用最邻近算法计算各自路线,同步出发将两钻头看作是两个半径R=1.5cm圆,圆心沿路线行进,找出两圆相交点时刻和相对坐标,到中间将要相遇点时用提前算好时间向不一样方向拐开后再继续行进,进行多次修正和迭代,直到不产生相交点。三、模型假设1、假定对于同一孔型钻孔作业时间都是相似,作业时间不影响问题分析,则求解时只分析钻头行进最短距离与钻头转换次数。2、假定打孔
9、机持续工作,行进期间无停留时间。3、假定打孔机钻头行进时只在任意两点间做直线运动。4、假定打孔机钻头转换灵活,持续转换无异常。5、假定打每个孔时间极短。四、符号阐明符号 阐明单位 ah种孔型一种第j个孔坐标1/100mil第j个孔横坐标1/100mil第j个孔纵坐标1/100mil转换次数过孔旅程mil权系数交叉率变异率五、模型建立5.1 问题一5.1.1打孔机行进最短旅程此种状况单考虑打孔机钻头行进完所有点最短旅程,不考虑刀具转换次数,即打孔机行进到哪点即打完这点。将题目所给点坐标导入MATLAB,并将各孔型用不一样点区别开,打孔机所要打所有孔相对位置和孔型见图1。图1 经记录共有2124个
10、点,规定钻头通过所有点一次,并且总旅程最短。 此问题是一种旅行商问题(TSP):旅行商问题要从图G所有环游路线中求取最小成本环游路线,而从初始点出发环游路线一共有(n-1)!条,即等于除初始结点外n-1个结点排列数,因而旅行商问题是一种排列问题。排列问题比子集合选用问题一般要难于求解得多,这是由于n个物体有n!种排列,只有n!个 子集合(n!O( )。通过枚举(n-1)!条环游路线,从中找出一条具有最小成本环游路线算法,其计算时间显然为O(n!)。 咱们将2124个点看作2124个成市,求解此TSP问题。为此建立3个模型分别求解: (1)模型一:途程构建法 刀具转换成本最小方案 刀具次序固定,
11、不能调换。要使刀具转换至少,可以排列刀具使用次序,在至少转换次数中,满足每个孔型所需刀具及使用次序条件。转换方式有两种:顺时针转换、逆时针转换。孔型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逆时针:hgfedcbahgfedcb
12、ahgfedcba使序列包括不一样5个线段,至少转换次数为9,用刀次序为dcbahgfedc因而,按照逆时针dcbahgfedc次序时转换次数至少,刀具转换成本最小。每次打点为:dcbahgfed2c2DGEBACFHFGEGJDICIJ表3此处以钻头a为例阐明行进方案,其她钻头方案解法相似,只列成果。设用a刀点660+270=930个点分别为a1 a2 a3a930钻头a要打孔如图: 图2使用途程构建法:近来邻点法(Nearest Neighbor Procedure):一开始以寻找离场站近来需求点为起始路线第一种顾客,此后寻找离最终加入路线顾客近来需求点,直到最终。程序:设一种定点:找出它
13、近来邻点,然后找该点近来邻点,直至最终一种点。对数组a进行排列:第一种点定为a1,查找近来邻点ai,并删除a1,查找下一种点aj,并删除ai直至第n个点,使她们按次序排列为aa取最小值r1i最邻近点发求最短途径示意图见图3:图3途程改善法K-Opt(2 Opt):把尚未加入途径2条节线临时取代目前途径中2条节线,并计算其成本(或距离),假如成本减少(距离减少),则取代之,直到无法改善为止。 经改善后处理状况数大量简化,由于本题所给点数众多,算法复杂度过大,对100点以内状况合用措施在此不合用,由于建模时间问题,未能给出完整答案,只摆出了措施。 (2)模型二:遗传算法遗传算法是一种模仿生命进化机
14、制搜索和优化措施,是把自然遗传学和计算机科学结合起来优化方程,有很强处理问题能力和广泛适应性。其假设常描述为二进制位串,位 串含义依赖于详细应用。搜索合适假设从若干初始假设群体集合开始。目前种群组员通过模仿生物进化 方式来产生下一代群体,如随机变异和交叉。每一步,根据给定适应度评估目前群体假设,而后使用概率措施选出适应度最高假设作为产生下一代种子。 在本程序TSP问题中一共有2124个都市,也就是在图模型中有2124个顶点,因而一种染色体长度为2124。 定义:适应函数f(i)对具有n个顶点图,已知各顶点之间(,)边长度d(,),把到间一条通路途径长度定义为适应函数:对该最优化问题,就是要寻找
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 2023 山东 科技大学 数学 建模 竞赛
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【w****g】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【w****g】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。