D题论文 ,2012深圳杯数学建模

1、封一答卷编号（参赛学校填写）：答卷编号（竞赛组委会填写）：论文题目： （标明A、B、C、D之一） D 组 别：(填写研究生、本科生、专科生或中学生) 本科生 参赛队员信息(必填)： 姓 名学 号联系电话参赛队员1参赛队员2参赛队员3 参赛学校： 黑龙江工程学院 封二答卷编号（参赛学校填写）：答卷编号（竞赛组委会填写）：评阅情况（学校评阅专家填写）：学校评阅1.学校评阅2.学校评阅3. 评阅情况（联赛评阅专家填写）：联赛评阅1.联赛评阅2.联赛评阅3.打孔机生产效能的提高摘要在现代电子设备中印刷电路板占有重要地位，是集成各种电子元器件的信息载体，在各个领域得到了广泛的应用。近年来，随着电子、信息

2、、通讯等产业的蓬勃发展，使得对印刷电路板的需求快速增加，更带动了印刷电路板产业的加速成长。然而，印刷电路板制造过程相当繁琐、耗时，并且制造过程中常会出现不确定性的变异，进而影响制造时间，制作成本及产品质量，甚至延误交货期。而现有的打孔机的操作系统虽然具有自动生成钻孔NC程序的功能，但是其生成的走刀路径并没有足够优化，这样会影响打孔机的生产效率，对于大批量生产的厂商来说，其影响相当明显从而造成制造商的损失。鉴于钻孔作业在印制电路板的制造过程中耗费时间最长、制造过程变异最多。因此，钻孔作业常常成为整个印制电路板的生产瓶颈。本次研究以印刷电路板制作过程中的生产效能即打孔机钻孔的作业线路作为研究对象，

3、经过对本问题的深入研究，利用遗传算法可以快速得出最优方案。但鉴于求解过程中涉及大量计算，而遗传算法在大规模计算中很容易陷入“早熟”，即遗传算法在计算过程中会过早的收敛于局部最优解，从而使得结果的误差偏大。鉴于遗传算法可扩展性强，容易与其他算法结合利用的优点，并采用1stOpt软件及其所开发的最大继承法最终得出多目标并行的打孔机钻头的最优作业线路（包括刀具转换方案），进而提高打孔机的生产效能，达到生产线平衡、提升整体产量和质量。(针对问题一,针对问题二,写具体的解决方案,不要泛泛的说!把你以上说的东西拿到模型的优缺点中去!)关键字: 遗传算法、 1stOpt、 最大继承法 (再加两个) 一、问题

4、重述1、问题背景在现代电子设备中印刷电路板占有重要的地位，是集成各种电子元器件的信息载体，在各个领域得到了广泛的应用。随着技术的不断发展和工业的持续进步，使得对印刷电路板的需求快速增加。打孔机主要用于在制造印刷线路板流程中的打孔作业。所以提高某类打孔机的生产效能成为生产厂商增加利润的主要途径。根据打孔机打孔作业原理，通过改善钻头的作业线路（包括刀具转换方案）可以提高印刷线路板的生产效能。附件1和表1提供了该块线路板的各孔的分布和十种孔型所需的加工刀具和加工次序。 2、问题提出（1）在单钻头作业条件下，根据该块线路板的各孔的分布和十种孔型所需的加工刀具和加工次序，给出最优作业线路（包括道具转换方

5、案），并且求出单钻头在最优作业线路下的行进时间和作业成本。（2）在两个钻头同时作业时（各自的作业孤立），两钻头间距不小于3cm的条件下给出双钻头作业时的最优作业线路、行进时间和作业成本，并与传统单钻头打孔机进行比较，其生产效能提高多少，并研究打孔机的两钻头合作间距对作业路线和生产效能产生的影响。二、问题的分析问题一针对打孔机单钻头作业，其最优作业线路是由印刷线路板上各孔型的分布及其所需加工刀具和加工次序所决定。1stOpt软件在基于遗传算法上开发的最大继承法可以更好的应用于组合优化问题，综合钻头的作业线路，为了简化模型，将该块印刷电路板上的所有孔划分为若干个区域，这样就可以针对每一个区域，都是

6、相同孔的点，这样就可以在钻头作业时只需考虑路径最短，进而可归结为旅行商问题（TSP问题），最终可得出各区域的最优作业线路，然后对各个区域间的路径进行分析并结合刀具转换方案，最终可以得到单孔作业的最优作业线路。而在印刷线路板上的孔共有n个，每个孔都可以用l，2，3n中唯一的编号表示。假设钻头按照2，5，7。4，3，6，8，9，1顺序进行加工，则这条走刀路径就可以被表示为(2，5，7。4，3，6，8，9，1)。最终的钻头作业线路就可以用孔的编号进行表示。问题二鉴于两个钻头单独工作并且钻头间距离不得小于3cm的条件，应利用用直线划分的方案，将整块的印刷电路板分为三个区域，中间区域宽度略大于合作间距。

7、两个钻头分别负责左右两个区域，中间区域最后加工。进而求解最优作业线路、行进时间和作业成本。3 符号说明与模型假设1.符号说明(这一块整体东西少,再加东西)n：各区域内孔的个数Xi：第i个孔的横坐标Yi：第i个孔的纵坐标Xj：第j个孔的横坐标Yj：第j个孔的横坐标 根据附件1中给定的孔的坐标顺序，把所有的孔从先至后按从1到2124的顺序依次进行编号2.模型假设1.为了问题简化，假设打孔机钻头从一个孔移动到下一个孔，其路径就是两点之间的连线。2.假设打孔机钻头加工单个孔的成功率为百分之百。3.假设打孔机在作业过程中，不会出现机器停止运转的情况。 四问题求解问题（1）将附件1给出的某块印刷电路板上所

8、有孔的坐标及孔型将孔进行划分，划分原则为相同孔型划分为一个区域，考虑到1stOpt软件的字符上限，每个区域最多的孔数目为220。则可划分为以下区域划分区域孔的编号孔型一1200A二221440三441660四661860B五8611060六10611260七12611448八14491648C九16491718十17191930D十一19312025E十二20262059F十三20602079G十四20802085H十五20862095I十六20962124J 第一个区域是编号1220的孔，第二个区域是编号221440的孔，第三个区域是编号441660的孔。在第一个区域内，因为A型孔只需用刀具

9、a加工，那么，钻头的最优作业线路只需满足路径最短即可，不必考虑刀具转换问题。那么这就可以归结为旅行商问题（TSP问题）。即有个孔，从某一孔出发，每个孔访问一次，最后回到起始孔，试求最短距离的访问路线。(这些原理所用的数学表达式写上,整篇论文没有什么数学表达式,给人直观印象不好)那么就可以利用旅行商问题的算法的解决钻头作业线路最短问题，结合1stOpt软件及其所开发的最大继承法，通过编辑程序代码和参数设置，就可以得出最优作业线路，具体如下：程序代码：NewDivision;/33894.Constant n = 220; /number of holesConstantxData(0:n-1)=

10、100,-10000,-100200,-100200,-100200,-101324,-101324,-101324,-101324,-101324,-101324,-101324,-101324,-101324,-101324,-101400,-101400,10200,102000,102000,102000,102000,102000,102000,102000,102000,102000,102000,102000,102000,102000,102000,102000,102000,-103200,103400,103400,103600,103600,103600,103600,1

11、03600,103600,103600,103600,103600,103600,103600,103600,103600,103600,103600,-10400,-104474,-104474,-104474,-104474,-104474,-104474,-104474,-104474,-104474,-104474,-10474,-104800,-105000,-107000,-107000,-107600,-107623,-107623,-107623,-107623,-107623,-107623,-107623,-107623,-107623,-107623,-107623,-1

12、07700,-107700,-108800,-109000,11000,-11000,-110688,-110700,-110773,-110773,-110733,-110773,-110773,-110773,-110773,-110800,-110800,-111000,-112000,-113000,-113922,-113922,-113922,-113922,-113922,-113922,-113922,-113922,-113922,-113922,114000,114000,114000,114000,114000,114000,114000,114000,114000,11

13、4000,114000,114000,114000,114000,-115000,-11600,116000,116000,116000,116000,116000,116000,116000,116000,116000,116000,116000,116000,116000,116000,-116800,-117000,-117072,-117072,-117072,-117072,-117072,-117072,-117072,-117072,-117072,-117072,-117072,-118800,1200,-120200,-120200,-120222,-120222,-1202

14、22,-120222,-120222,-120222,-120222,-120222,-120222,-120222,-120222,-120222,-120222,-120530,-120800,-121400,-121400,-122000,-122600,-122800,-123371,-123371,-123371,-12400,-12400,-12400,12400,12400,-124467,-124800,-126400,-126521,-126521,-126521,-126521,-126521,-126521,-126521,-126521,-126521,-126521,

15、-126521,-126800,12800,12800,-128800,-129600,-129670,-129670,-129670,-129670,-129670,-129670,-129670,-129670,-129670,-129670,-129670,-129670,-129670,-129670,-130600,13200;Constant yData(0:n-1) = 243600,301000,246000,322400,122800,265174,268324,271474,274623,277773,284072,287222,293521,296670,299820,3

16、06200,315600,242600,246000,269600,297200,301200,305000,309000,312800,316800,320800,324800,328600,332600,336400,340400,344400,348400,121200,247800,271600,295200,299200,303000,307000,311000,314800,318800,322800,326600,330600,334400,338400,342400,346200,350200,318600,265174,271474,274623,280922,287222,

17、293521,296670,299820,306119,309269,312418,233400,122800,121200,383400,312400,265174,268324,271500,274623,277773,281000,287222,296670,299820,306119,309269,284000,293500,248000,122800,123000,267000,246000,271500,265174,268324,274623,293521,296670,299820,309269,290200,306000,121200,518600,122800,268324

18、,284072,287222,293521,296670,299820,302970,306119,309269,312418,137600,141600,145600,149400,153400,157200,161400,169200,173200,177000,181000,185000,188800,192800,121200,320600,135800,139600,143600,147600,151400,155400,159400,167200,171200,175000,179000,183000,187000,190800,122800,268400,271474,27777

19、3,284072,287222,293521,296670,299820,302970,306119,309269,312418,121200,111600,274500,281000,262025,268324,271474,277773,284072,287222,293521,296670,299820,302970,306119,309269,312418,246000,122800,109000,99200,515200,248000,121200,268324,309269,312418,211200,223200,251600,400800,403000,246000,12280

20、0,248000,274623,280922,284072,287222,293521,296670,299820,302970,306119,309269,312418,121200,221600,250800,122800,265200,268324,271474,274623,277773,280922,284072,287222,293521,296670,299820,302970,306119,309269,312418,121200,123000;Parameter Holes(0:n-1)0,n-1;Minimum = True;Exclusive = True;StartPr

21、ogram;Var TemSum : Double; i : integer;Begin TemSum := 0; for i := 0 to n-2 do TemSum := temSum + sqrt(sqr(xDataHolesi+1-xDataHoles i)+ sqr(yDataHolesi+1-yDataHolesi); FunctionResult := temSum + sqrt(sqr(xDataHolesn-1-xDataHoles0)+ sqr(yDataHolesn-1-yDataHoles0);end;EndProgram参数设置：打孔顺序12345678910孔编号

22、136120137121138122139123140124打孔顺序11121314151617181920孔编号19362037383940422543打孔顺序21222324252627282930孔编号26442745484932313029打孔顺序31323334353637383940孔编号2846475033513452184185打孔顺序41424344454647484950孔编号99175684176469806316打孔顺序51525354555657585960孔编号15141312115859607782打孔顺序61626364656667686970孔编号768175

23、747288143156160159打孔顺序71727374757677787980孔编号1421019015818818617617131打孔顺序81828384858687888990孔编号1820218386253126244123打孔顺序919293949596979899100孔编号2221201181182671190191194打孔顺序101102103104105106107108109110孔编号195196197216215214213212193147打孔顺序111112113114115116117118119120孔编号148149106107951091101531

24、70169打孔顺序121122123124125126127128129130孔编号168167166165164163162157161144打孔顺序131132133134135136137138139140孔编号91735655789105761打孔顺序141142143144145146147148149150孔编号627997108151152179180199218打孔顺序151152153154155156157158159160孔编号2171981509478931051049296打孔顺序161162163164165166167168169170孔编号10310214514

25、6192211210209208189打孔顺序171172173174175176177178179180孔编号2072062052041788970548387打孔顺序181182183184185186187188189190孔编号658498100125141154172177187打孔顺序191192193194195196197198199200孔编号2002032191731746766355155打孔顺序201202203204205206207208209210孔编号85220111127128112129113130114打孔顺序21121221321421521621721

26、8219220孔编号131115132116133117134118135119 则在A型孔的第一段区域内，打孔机钻头最优作业线路为：因为A孔型只需一种刀具加工，所以不涉及刀具转换。钻头在该区域内的作业成本只包括行进成本。孔编号（1220）作业成本P1（元 ）作业时间为T1（秒）3583.48331.80 经过深入分析只需一种刀具加工的孔型所在区域均可以利用第一个区域求解最优作业线路的算法，求出钻头的最优作业线路。每个区域内不涉及刀具转换问题，这些区域包括区域二，区域三，区域四，区域五，区域六，区域七，区域十四，通过1stOpt软件及其所开发的最大继承法即可算出每个区域内钻头的最佳作业线路，行

27、进成本及作业时间。具体结果见附件一。对于需要两个或两个以上刀具加工的孔型，最优作业线路取决于钻头路径与刀具转换。鉴于上述，采钻头优先加工完毕作业孔，再继续加工下一个孔，以此类推，按照此方案实现加工区域内所有的孔。对于区域十三，就可利用上述方案求解钻头作业的最优作业线路（刀具转换方案），行进时间和作业成本。当加工完一个孔时在加工下一个空。对于相同孔型的孔，加工每个孔时道具的的转换次数为4，并且每次加工完毕一个孔时，向下一个孔移动，中间转换的刀具次数为2。并且每个孔都是遵循上述的刀具转换数量。 根据下列公式： a1a2a3n (|a1-a2|+ |a2-a3|)×n+ |a3-a1| &

28、#215;(n-1) |a1-a2|4, |a2-a3|4, |a3-a1|4 (8-|a1-a2|+ |a2-a3|)×n+ |a3-a1| ×(n-1) |a1-a2|>4, |a2-a3|4, |a3-a1|4 (8+|a1-a2|- |a2-a3|)×n+ |a3-a1| ×(n-1) |a1-a2|4, |a2-a3|>4, |a3-a1|4 (|a1-a2|+ |a2-a3|)×n+ (8-|a3-a1|)× (n-1) |a1-a2|4, |a2-a3|4, |a3-a1|>4 (16-|a1-a2|-

29、 |a2-a3|)×n+ |a3-a1| ×(n-1) |a1-a2|>4, |a2-a3|>4, |a3-a1|4 (8-|a1-a2|+ |a2-a3|)×n+ (8-|a3-a1|)×(n-1) |a1-a2|>4, |a2-a3|4, |a3-a1|>4 (8+|a1-a2|- |a2-a3|)×n+ (8-|a3-a1|)×(n-1) |a1-a2|4, |a2-a3|>4, |a3-a1|>4 (16-|a1-a2|- |a2-a3|)×n+(8-|a3-a1|)×(

30、n-1) |a1-a2|>4, |a2-a3|>4, |a3-a1|>4 计算出钻头在G孔作业过程中刀具转换的次数,经运算得到转换刀具的次数为118次。由于孔型相同，那么在作业过程中刀具转换是固定的，所以钻头在这个区域内的最优作业线路取决于钻头的的行进路径，因此采取旅行商问题的算法并利用1stOpt软件及其所开发的最大继承法，就可以解决路径最短问题，从而可得出最佳作业线路具体程序代码及参数设置如下：NewDivision;/33894.Constant n = 20; /number of HolesConstant xData(0:n-1) = -301300,-30130

31、0,-301300,-301300,-301300,-301300,-301300, -301300,-321300,-321300,-321300,-321300,-321300,-321300, -321300,-321300,153000,173000,193000,213000;ConstantyData(0:n-1)=-301300,-301300,-301300,-301300,-301300,-301300,-301300, -301300,-321300,-32,-321300,-321300,-321300, -321300,-321300,153000,173000,193

32、000,213000;Parameter Holes(0:n-1)0,n-1;Minimum = True;Exclusive = True; StartProgram;Var TemSum : Double; i : integer;Begin TemSum := 0; for i := 0 to n-2 do TemSum := temSum + sqrt(sqr(xDataHolesi+1-xDataHolesi)+ sqr(yDataHolesi+1-yDataHolesi); FunctionResult := temSum + sqrt(sqr(xDataHolesn-1-xDat

33、aHoles0)+ sqr(yDataHolesn-1-yDataHoles0);end;EndProgram参数设置： 则可以得出最优作业线路为：打孔顺序12345678910孔编号2079206720652074206920712070207220752073打孔顺序11121314151617181920孔编号2068206620612060206220632064207620772078则作业成本极其作业时间为：孔编号（20602079）作业成本P13（元 ）作业时间为T13（秒） 2511.0122337.25 经过深入分析需要两种或两种以上刀具加工的孔型所在区域均可以利用第十三个区

34、域求解最优作业线路的算法，每个区域内涉及刀具转换问题，但是对于同一个区域内的空来说转换刀具的次数是相同的，所以只需求解区域内的钻头最短运行路径即可。故以利用旅行商问题的并算法通过1stOpt软件及其所开发的最大继承法即可算出每个区域内钻头的最佳作业线路（包括刀具转换方案），行进成本及作业时间。具体结果见附件。 以上求出了十六个区域各自的钻头最优作业线路（包括刀具转换方案），且对于每一个区域，钻头的起始位置和最终位置都已经确定。钻头在加工整块印刷电路板时，加工完一个区域内的孔向另一个区域移动时，这十六个区域只是通过各自内部的起始点与终点进行连接，与其他的点无关，所以为了简化模型，这十六个区域可以

35、看作是三十二个点，那么，只需求解钻头在这三十二个点之间的最优作业线路，根据遗传算法可以解决多目标规划的线路调度问题可得出最优的作业线路(包括刀具转换方案)，行进成本及作业时间。 所有的孔作业成本P （元 ）作业时间为T（秒） 97594.87 60513.67 再结合附表中的各区域最优作业线路，行进成本及作业时间可得出在该块印刷线路板上打孔机钻头的最优作业线路为：2079206720652074206920712070207220752073 2068206620612060206220632064207620772078 19491940195020112013201520172018202

36、02022 2024202520232021201920162014201220102008 2009200720062005200219471938193919482001 2004200319341945195819781979198019861985 1984198319821977197619621961195919551953 1944193519991997196919571960199219982000 1956196319741965197019711972197319681967 1966197519961943198119461988199319941991 1941198

37、919951990198719311964193319361937 19421952195419511932 20332037204520422034 2030203820392031203520432047204620492048 2044203620322028202620292027205720502052 2055205620542053205120592058204020411668 1670166917051706170417031651165016831684 1685168616581657167216731674167516761678 1677167116641663165

38、916601661166216821649 1710171117131715171617181692169016871699 1652165616551654165316971695169817021696 1701170016941689168816931691171717141712 1680167916811709170817071665166616671840 1839183818371827182619031907190219011906 1905190419001899183219241831183418331830 18731872185618571858187418891888

39、18841883 1891189218931894189518961897189818901887 1886188518691870187118551854185318521868 1867185117381737173317341732173117291730 1724172317191720172617251735173617221721 1727172818491850175417531752183618351909 1915191319121908191019141916191119261921 1744174017411756175717421745174618421843 1792

40、180917931776175917751758175517491748 1747191919201923192219271928192919301925 1844184518461847184817431739175017511763 1780177917621761176017771794181018111795 1778179618121813179718141815179817811764 1765178217991816181718001783176617671784 1801181818021819182018031785176817691770 17861804182118221

41、80517871771178817721789 1773179017741791180818071806182318241825 1841191819171866188218811865186418801879 1878186318621861187718761860185918751829 1828208320842085208120802082163016351642 1645163914741467145614511449153415361462 1545160516141604161916231458145314551459 162216271621161815491554155716

42、3816411647 1648164616001599159315941592159115891583 1584158015761572157015741578158215881587 1581157715731569156515661586159815961560 1564155915951597158516011561156216021568 1464146114681472147814821483149214911516 1515151816441632159015791575157115671563 1612161716111606160316131465146614751476 14

43、81148414941509151715211540154415411530 1535152515221520151915061499149815031500 1486148714881489149314901496149715241523 1526153915381542153115271528153315321529 1546154315371512150214851480162816241471 1477147915511548155015531609161016161505 1511151015081504151415131507162916261620 162516151607160

44、8155215471631163715011495 1643163614501556155515581454145214571460 1463146914701473163316401634209220882090 2091208920932095209420872086211821032102 2099209821192108210421202116211421002101 2115211220962097211721132122210721232124 2111212121062105211021091423142414351414 1415141614171418133213331319

45、133013311408 1407140914101406143814191412134712671265 1404139813971396140114001429142814361393 1384136913551364137114391437137413811380 1379137813771376137513951394138613821372 1370136613651363136013531320134013571373 1427142614411411140213901356136814401430 1446143114421432142014431444142113591358

46、1329138513131361133913361324132313221413 1272126112761277127413071312130513041300 1283127912691262127012801284129113011308 1316131813111310130212941293130312901285 1287128812891295126412711278128212921298 1315131413211317130612991286128112751268 1263127312661362134113251328132713511447 1448142514051

47、387135213381337134513461334 1335134913891388139914031392138313501344 1342132613671297129613541309139113481343 1422144514331434136 120137 121 138122139123 140 1241936 203738394042254326442745484932 313029284647503351345218418599175684176469 80631615141312115859607782768175747288 143 15616015914210190

48、1581881861761713118202183 86 253 126 2441232221201181182671190191194195196197216215 214 21321219314714814910610795109110153170169168167166165164 16316215716114491735655789105761627997108 1511521791801992182171981509478931051049296103102145 14619221121020920818920720620520417889705483876584 98 100125141154172177187200203219173174676635515585220111 127128112129113130114131115132116133117134118135119 528520 4995105195275335425505565675695