【文档说明】深圳杯数学建模夏令营D题打孔机生产效能提高的优化课件.ppt，共(47)页，1.262 MB，由小橙橙上传

转载请保留链接：https://www.ichengzhen.cn/view-13465.html

以下为本文档部分文字说明：

打孔机生产效能提高的优化方案汇报人扈诗扬一、问题重述•打孔是印刷线路板的重要组成部分之一，打孔的加工费用通常占制板费用的30%到40%，打孔机主要用于在制造印刷线路板流程中的打孔作业.因此我们要研究的问题旨在提高某类打孔

机的生产效能.•打孔机的生产效能主要取决于三个方面：即单个过孔的钻孔作业时间和钻头的行走时间以及刀具的转换时间.现有某种钻头，上面装有8种刀具a，b，c，„,h，依次排列呈圆环状，如右图所示.bcdefgha某种钻头上8种刀具的分布情况•并且8种刀具的顺

序固定，不能调换.钻孔在加工作业时，一种刀具使用完毕后，可以转换使用另一种刀具.相邻两刀具的转换时间是18s，作业时，可以采用顺时针旋转的方式转换刀具，也可以采用逆时针的方式转换刀具.将任一刀具转换至其它刀具处

，所需时间是相应转换时间的累加，例如，从刀具a转换到刀具c，所需的时间是36s（采用顺时针方式）.•为了简化问题，假定钻头的行走速度是相同的，为180mm/s，行走成本为0.06元/mm，刀具转换的时间成本为7元/min.刀具在行走过程中可以同时进行刀具转

换，但相应费用不减.•不同的刀具加工不同的孔型，有的孔型只需一种刀具来完成，如孔型A只用到刀具a.有的孔型需要多种刀具及规定的加工次序来完成，如孔型C需要刀具a和刀具c，且加工次序为a，c.下表列出了10种孔型所需加工刀具及加工

次序（标*者表示该孔型对刀具加工次序没有限制）.•我们要建立的数学模型需要完成以下问题：•（1）附件1提供了某块印刷线路板过孔中心坐标的数据，单位是密尔（1/100mil）（也称为毫英寸，1inch=1000mil

），计算出单钻头作业的最优作业线路（包括刀具转换方案）、行走时间和作业成本.•（2）为提高打孔机效能，现在设计一种双钻头的打孔机，两钻头可以同时作业，且作业是独立的，即可以两个钻头同时进行打孔，也可以一个钻头打孔，另一个钻头行走或转换刀具.为避免钻头间的触碰和干扰，在过

孔加工的任何时刻必须保持两钻头间距不小于3cm.为使问题简化，我们可以将钻头看作质点.•（i）针对附件1的数据，给出双钻头作业时的最优作业线路、行走时间和作业成本，并与传统单钻头打孔机进行比较，其生产效能提高多少？•（ii）研究打孔机的

两钻头合作间距对作业路线和生产效能产生的影响.10种孔型所需加工刀具及加工次序孔型ABCDEFGHIJ所需刀具aba,cd,e*c,fg,h*d,g,fhe,cf,c二、模型假设•1.假设对于同一孔型钻孔作业时间都是相同的；•2.假设每个孔型加工完后不再加工；•3.假

设钻头在加工同种孔型时不进行刀具转换；•4.假设钻头在孔间以直线方式行走时不走弯路；•5.假设周围环境对钻头和刀具没有干扰；•6.假设加工每块板工作过程中，无刀具磨损、损坏情况，中途无间断.三、符号说明ijx从i孔到j孔的的最短距离ijc从i孔到j孔时

刀具需要转换的格数ijs钻头是否从i孔到j孔T单钻头打孔机打完所有孔加工的总时间1t单钻头打孔机打完所有孔最小行走时间v钻头的行走速度w转头每毫米行走成本h每分钟刀具转换的时间成本打孔机打孔的生产效能Q有刀具转换顺序的孔型中次顺序加工孔型的集合P相

对Q集合主次序加工孔型的集合d两钻头合作限制间距ijk表示刀具转换次序的修正系数0L134类点孔的行走路程1T加工完134类点孔的行走时间m加工完134类点孔的最小成本S加工完2124个点孔的总路程Z总作业成本路径衡量系数四、问题的分析•问题一：•问题一中要研究的是最优

作业线路和行走时间及作业成本这三个问题，很显然这是一个典型的组合优化问题.•由于有的孔型需要多种刀具共同加工，而且有的刀具有转刀顺序，有的转刀没有顺序，这更加剧了问题的复杂性，为此，我们将需要多种刀具加工的一种孔型看成需要单种刀加工的多种孔型，即这些孔的位置相

同但是代表不同的孔型，通过这种孔点拆分思想可以大大简化问题.•考虑到需要处理2124个数据，如果用常规方法很难求解.因此这是一个典型的组合优化问题，所以我们巧妙的利用K-means聚类分析方法将2124个孔的过孔中心坐标分为92类，经过线性回

归分析，这92类点孔很具有代表性.•对于刀具转换顺序问题，通过约束条件建立整数0-1规划模型,以成本为目标函数进行求解，从而求得刀具最优作业路线和行走作业时间及最小成本.最终得到较为合理的分配方案.问题二:•（i）首先在问题一的基础上，我们把双钻头作业路线转化为单钻头二次行走路线问题，为

了得到最大生产效能，又设计两套方案分别进行求解，通过比较三套方案生产效能得出最优作业线路进而得到行走时间和作业成本.•（ii）问题研究的是两钻头合作间距对作业线路和生产效能产生的影响.•考虑到两钻头间距d是一个不定变量，它随着线路改变不断发生变化，因此我们有选择性的选取一组d值，在钻头间距d值不

断变化下，求出对应的最优作业路线和最大生产效能，然后绘制出生产效能随两钻头工作间距随d值变化的曲线.然后利用图像分析法得到最优值d时的最优路线和生产效能.•通过曲线可以研究打孔机的两钻头合作间距对作业路线和生产效能产生的影响.五、模型的建立与求解问题一的解决:根据问题，求最优路线.为

此，我们选用Floyd算法算出任意两个点之间的最短路径矩阵21242124U.Floyd算法为：任意两点（i，j）之间的最短路径等于从i出发到j点的以任意一点为中转点的所有方案，距离最短的一个.即:min(,,

...),1,ijijikkjDDDDknn为节点数。为了便于观察分析数据，我们对进行数据进行处理，做出孔型分布图（图2）.通过上述分析，我们又发现，I孔和J孔比较分散，所以不进行分类，只对有规则的孔分类，先利用聚类分

析的思想进行分类，又基于Floyd算法求出任意孔之间最短路径ijx能够很方便的将2124个孔归类.图25.2问题一的解决5.2.1作业成本的各项费用根据产生关系如下图1：总成本刀具转换费用行走费用刀具转换格数行走路程图1.作业成本的各项费用关系打孔

路径优化问题数学描述如下：，设有n个孔的集合12n12nh{h,h,...,h,h,h,...,h｝分别为这些孔的编号，对于孔ijh,hh从ih到jh记为ijx,要在H中找到一个不从复的全排列i(1)i(2)i(n)h,h,...,h.令1i(),(1)1()D=nijijjdiN

最小，此路线即为所求最优作业路线.通过数据分析，利用Matlab软件实现对2124个孔的中心坐标示意图，如图2所示：图2.2124个孔的中心坐标示意图-4-3-2-1012345x105-20246

810x105孔型分布图返回5.2.2数据分类：通过对分布图像的分析，我们发现，I孔和J孔分布比较分散，为了提高结果的精度，对I、J两种类型孔不予进行分类，只对有规律的孔型分类，利用聚类分析的思想进行分类.聚类分析原理：给定123,,

,...,nxxxx为有序样品，假设1(1)...kii为最优k分割，则1(2)...kii为有序样品，12(2),,...,kxxx的最优k-1分割，满足动态规划的最优型原理.因此可以引入动态规划求解.如下S(J,K)表示有序样品123,,,...,jxxxx最优规划的总变差

P(J,K)表示有序样品123,,,...,nxxxx最优化:20,,1,(;2){}(;){(1;1)}minminjnkjnjjnjjnSnDDSnkSjkD利用动态规划自下向上的方法进行求解.通过上述的聚类分析原理，结合Matlab中提供的数

学工具对样本数据进行分步聚类.然而，Matlab提供的常见系统聚类法只能解决大多简单的聚类问题，但对于数量较大的数据进行聚类，K均值聚类是一个比较好的选择.进行K均值聚类时，函数K-means将数据中的观测量分成K个相互排斥

的类，并返回一个指数向量.K-means函数不用树结构描述数据中的组，而是创建单一水平的类.最后基于上述方法步骤，利用系统提供的4维数据集K-meansDATA检验.K-means函数的聚类效果，得出A、B、C、D、E、F、G、H

、I、J10种类型孔的K均值，如下图3所示：024681012140.10.20.30.40.50.60.70.8kmeans评价指标a-cabc36类25类24类图3.8种类型孔的K均值图123456700.10.20.30.40.

50.60.7kmeans评价指标d-fdef14类15类9类图4.8种类型孔的K均值图K均值曲线分析：从上述曲线可以看出，K均值呈现先上升后下降的趋势，由此我们得出8种孔型的K均值分类如表一所示：•聚类分析的合理性检验：通过上述方法，最终我们将所有点孔归为92类点孔

.利用Matlab软件将这92类点孔绘制成散点图，如图5所示.通过该图可以发现这92类点很具有代表性，能反映所有数据的分布规律.ABCD36252414EFGH15947表一.K均值分类表-4-3-2-1012345x105-10123456789x105

92类散点图图5.92类点孔中心坐标示意图孔点拆分法：由于有的孔型需要多种刀具加工，为了简化加工过程，将需要多种刀具加工的一种孔型转化为仅需要一种刀具的多种孔型.基于此方法，将92类点孔转化为134类

点孔进行加工.•最小成本模型的建立：生产成本=刀具转换费用+行走费用=总的转换格数18760+总路程0.06为了使总成本最小，采用组合优化模型，以ijs表示单钻头是否从i孔到j孔，以总成本为目标函数建立如下优化模型：目标函数：1113

413411134134134134117min(0.0625.418)601,1...1341,1...134..()/,0.02,0.07jijiijijijijijijijijijijijkSxcSiSjstSxDDk

①②③,i,1,,01ijijPjQiPjQS④为，变量•目标函数式为满足

生产总成本最小模型，涵盖了刀具转换费用与行走费用二个阶段的评价指标，其中约束式①,②两式表示所有孔最后均被打完，且不重复.约束式③表示在达到生产成本最小的前提下，尽量使行走路程规定在实际加工的范围内，约束式④中为修正

系数表明在用钻头加工需要多种刀具加工孔型的换刀顺序.六、模型的求解•最小成本模型的求解：•该最小成本模型求解的是组合模型中的0-1规划问题，利用Lingo软件进行求解，以最小成本为衡量标准，单钻头作业的最优作业线路和刀具转换方案如表二所示：路

径刀具方案路径刀具方案路径刀具方案路径刀具方案4203522521150590722882762691332102112743024013931210280430191992672111503238615611207121000819011424926010083258077220011323

8011632208221615745219214711053271106179191166278211834353111735141233361103113228537528911330130360163123180371242

622119345112921343131290312517436431041653路径刀具方案路径刀具方案路径刀具方案262460124094351128110813029210701706829312

10481612140550表二.最优作业线路和刀具转换方案数据分析：根据表二中的数据分析，行进时间=行走时间+刀具转换时间.由Floyd算法得出单转头打孔机加工完134类点孔的行走路程407.5910Lmil，

行走时间123.25st，刀具转换时间2170.81st,最小成本41.25m元，根据模块化思想，由于加工同种孔型不需要换刀，所以，对134类孔型点中每一类孔型点，分配最优作业路线，可不必考虑刀具转换费用.因此，我们又巧妙的利用模拟退火算法，分别得到

每一类点孔具体最优作业路线和最短行走路程，如附表路径及道具转换的具体方案所示.通过将134类点孔的最优作业路线和每一类点孔的具体最优作业路线进行汇总，我们得到了加工完2124个点孔最优作业路线.点孔的总路程:35

1200(...)(357.7000110)4.33582010milnsLLLLLmil总行进时间:54.335820104418889.1818025.4sts总作业成本:702.03元.刀具转换的方案的探究：由于刀具在行走过程中可以

同时进行刀具转换，但相应费用不减.为了减小加工时间我们提出评价指标：加工时间=刀具转换时间+行走时间根据此评价指标建立最小加工时间目标函数：1341341125.425.425.4,i,1,,0,11

,0..0,181,18min(18)ijijijijijijijijijijijijijxvSPjQiPjQAstvvkxxcckSAc①②③根据以上算法，利用Lingo软件进行求解得到优化后的刀具转换方案如下表三

所示：表三路径刀具方案路径刀具方案路径刀具方案路径刀具方案74164310511150352250320路径刀具方案路径刀具方案路径刀具方案1907228827602624601240691821102112729435

15413014013931210106130292280430591992107017068233013111504239312104812156112907126121405501000819011428411114653492601008321223971

7705822001132101141338011622206728717311615721181133112823414711043271108150011247919116686782181812523435

31117020109251212313611031130951132285175289111096092013026018013711101231633712423111262622119345112270198313431090312514

411202表三.最优作业线路和刀具转换方案•由表三数据分析：通过对改进后刀具转换方案的分析，最小加工时间475.18s，与刀具转换方案优化前相比较，加工时间减少u=889.18-475.18=414.00s，不难发现改进后的优化方案更具有实用价值.•问题二：

•双钻头作业时最优作业线路，行走时间和作业成本的讨论：•我们定义了3个评价原则:•１．在打完所有孔的情况下，作业时间最短；•２．在打完所有孔的情况下，成本最小；•３．在打完所有孔的情况下，生产效能最大.•评价标准：生产效能=-总

加工费用×总加工时间•问题二（i）模型的建立：求解单钻头打孔机第一次行走路线：通过对问题的分析，把双钻头作业问题转化为单钻头两次行走作业路线问题，在保证打完所有孔情况下以两次行走路线中最近距离不小于3cm为约束条件,以生产效能最大为目标函数建立模型如下:13413411min(0.0625.41

87)ijijijijijkSxcTs.t.134134111341()/,0.02,0.071,1...134,i,1,,0,31,3ijijjiijiijijijijijSxDDSjPjQkiPj

Qxsx①②③④•其中,•其中目标函数表示单钻头打孔机按第一次行走路线最大生产效能；•约束式②表示单钻头打孔机按第一次行走路线可以不必走完所有点孔；•约束式④表示当两孔型间的距离>3cm时，单钻头没

有从i孔到j孔.•求解单钻头打孔机第二次行走路线：•单钻头打孔机第二次行走路线是在第一次的行走路线的基础上打完剩余的点孔，以最小生产效能为目标函数求解出最优作业路线.134134134134111118ijijijijijijijijijskxATskcv

•模型的求解：通过对模型的分析要研究的问题是0-1的规划问题，因此利用Lingo软件得到单钻头打孔机两次最优作业路线和具体转刀方案，如表四所示：路径刀具方案路径刀具方案路径刀具方案路径刀具方案4203502511151592722880

761691330102112703004013911212281431190992670101503228605611201000809149060101580771200380116222016157252047010502717919116611181415305111

231360132085175213311301600230800726211191450134013119007406411040表四.钻头1最优作业路线和具体转刀方案路径刀具方案路径刀具方案路径刀具方案路径刀具方案7102623718131143943311109183210

81701951113210704419608229314601101921612511262106184130983782122317012021172101121012401030871140128189154111

1229163150097268224218141248112922073155012511303416541101124表五.钻头2最优作业路线和具体转刀方案•双钻头最优作业路线分析：•基于表四，表五中的作业路线和转刀方案，同样用模

拟退火法准确地计算出每一类的数据，经整合后得到表六：行走路程行进时间作业成本单钻头4.34×105mil475.18s702.03元双钻头4.99×105mil358.83s763.02元mil51034.4mil51099.4

表六.单双钻头的对比计算结果表明，双钻头打孔机的生产效能0273794.01H元秒，传统单钻头生产效能1H475.18702.03=-333590.62ZT秒元元秒由此可得与传统单钻头打孔机进行比较，其生产效能提

高值10121.84%HHGH.可见，双钻打孔机比传统的单钻打孔机更有实用价值.•双钻头方案的进一步探究：•方案二：成本最小目标函数：13413411min(0.0625.4187)ijijijijijkSxc..,i,1,,ijstPjQkiPjQ

①0,31,3ijijijxxs②11341,1...134iijijSj③•在上一问的基础上，利用Lingo软件得出双钻头的最优路线及刀具转换方案，如下表：路径刀具方案路径刀具方案路径刀具方案路径刀具方案7201202516913918824227611151330102

1127030240159110522816611909926721015132286056135010008091491611015807712003831162221161572520472121027179191143

11181415305111231361132085175210416416002308007262111914509001311134374213011330表七.钻头1最优路线及刀具转换方案路径刀具方案路径刀具方案路径刀具方案路径刀具方案

71011323711223114294331110911031108111119518121070441960822931460110192161251124210615511010983782263170120211723121

06308308711401290891541702291126150097368124218141248112822073184012511313416541101124表八.钻头2最优路线及刀具转换方案•方案三：加工时间最小目标函数

1341341125.4min(18)ijijijijijijxvkSAc..,i,1,,ijstPjQkiPjQ①0,31,3ijijijxxs②0

,11,0ijijijAcc③11341,1...134iijijSj④数据比较：通过对三种方案的比较，我们准确的得出表九所示的数据,通过数据分析，发现采用方案一生产效能最大，因此在三种方案的比较下，选

用方案一为最佳方案.表九.三种方案的对比行走路程行进时间作业成本生产效能方案一54.9910mil358.83s763.02元273794.01方案二56.1210mil591.23s712.34元42115

6.78方案三54.1810mil340.97s.138209元471251.06•问题二（ii）•由题意可知，两钻头间距对作业路线和生产效能有影响，因此假定两钻头的合作间距为d，则把生产效能看做合作间距的函数.

•然而实际生活中很难直接发现他们的规律，所以我们对此方法做了进一步改进，运用图像统计出不同d值下的生产效能，画出曲线如图6所示：图6.生产效能曲线图11.522.533.544.555.56-5-4.5-4-3.5-3-2.5x105最优值•图像分析

：通过该图像的走向趋势，我们发现如下规律：•当两钻头合作间距大于3cm且小于3.90cm时，生产效能随着两钻头合作间距的增大而增大.•当两钻头合作间距大于3.90cm时，生产效能随着两钻头合作间距的增大而减小.•当两钻头合作间距等于3.90cm时，生产效能最大.•七、模型评价与优化•（1

）优点：•①在建立模型的过程中，做出了一些假设，去掉了一些不合理实际情况的干扰，降低了建模的复杂度.•②在开始建模前的数据预处理中用到了矩阵的相关运算，易于用数学软Matlab求解和验证.•③在部分模型的建立和求解中，考

虑到算法实现时的时间复杂度和空间复杂度，将问题简化处理得到近似最优解，在实际问题的解决中，该处理方法拥有较高的适用性.•④通过两个互补模型的连立复合，对刀具转换顺序进行了合理的限制.•（2）缺点：•①本模型对钻孔

加工的合理范围缺乏描述，造成解出现一些误差.•②由于模拟退火算法需要一些特定的初值.所以初值的选取好坏对最终结果有一定影响.•③由于对模型进行了简化处理，所得结果与实际精确值存在一定误差.•（3）模型优化•1.本文在讨论刀具转换顺序的问题中，假设同一种孔型不需要转换刀具，

对于两种刀具的孔型在现实生产中是需要考虑的，模型可以考虑朝这个方向进行优化.•2．限于本文一些参数为假设数值或自定义，如针对题目中问题的求解结果可能会出现一定误差；文中假设限于本文计算和讨论，针对某一实际印刷线路板，需要更为复杂的模型建立和数值求解.另外，文中

所用的部分数值已将现实问题简化，实际钻刀打孔的影响因素有很多，该模型在应用中需要适当修正或调整部分参数，并加以改进.•八、模型的推广•通过对题目的解读不难发现这是一个组合优化问题，组合优化问题是规划的一个重要分支，

它在解决城市建设、公共设施安置、工业生产选址等中都发挥着重要的作用.•文中建立的“单钻头作业的最优作业线路”算法具有通用性，可以推广至大型超市、医院、小区内居民服务点的设点问题，该模型能够对已知相关数据的区域

或路网，进行合理规划，合理选用给出的优化算法，可实现城市基础设施服务民众的高效性.•参考文献：•[1]姜启源.数学模型[M].北京:高等教育出版社,2011.•[2]科曼.算法导论[M]北京:机械工业出版社,2008.•[3]董文永.

最优化技术与数学建模[M].北京:清华大学出版社2010.•[4]周正武，丁同梅，王晓峰，田毅红.孔群加工路径优化方法的研究[J].机械研究及应用，第03期，2006年.•[5]蒋庆丰，李梓，程晓旭.K-Means聚类算法研究及图形演示的实

现[J].信息技术,第03期,2010.•[6]姚国辉.若干组合优化问题的算法研究[J].计算机软件与理论,2009.衷心感谢！