2023年深圳杯數(shù)學建模競賽D題打孔機生產(chǎn)效能的提高參考答案

２023深圳杯數(shù)學建模競賽Ｄ題——打孔機生產(chǎn)效能的提高參考答案摘要本文對印刷電路板過孔的生產(chǎn)效益如何提高進行了研究。打孔機在加工作業(yè)時,鉆頭的行進時間和刀具的轉換時間是影響生產(chǎn)效益的兩個因素。在完畢一個電路板的過孔加工時,鉆頭行進時間和刀具轉換總時間越短，生產(chǎn)效益越高。鉆頭行進總時間由鉆頭進行路線決定，而刀具轉換總時間由線路板上由各孔的位置以及鉆頭行進方案決定。鉆頭行進的路線的擬定我們用遺傳算法模擬。令，當示在得到的最優(yōu)途徑上;當表達不在得到的最優(yōu)途徑上。通過這個變量建立起路線與費用的橋梁關系，進而寫出總費用的表達式，建立最優(yōu)模型,用遺傳算法求解。當打孔機設計成雙鉆頭時，由于作業(yè)時各鉆頭互相獨立，且有合作間距的限制，因此在解決雙鉆頭最優(yōu)作業(yè)方案時，我們在單鉆頭作業(yè)的基礎上再加上另一個鉆頭作業(yè)所需的各種費用并增長約束條件,保證合作間距在規(guī)定范圍之內。關鍵詞:遺傳算法;優(yōu)化模型;印刷線路板；生產(chǎn)效益問題的重述過孔是印刷線路板（也稱為印刷電路板)的重要組成部分之一,過孔的加工費用通常占制板費用的30％到４0％,打孔機重要用于在制造印刷線路板流程中的打孔作業(yè)。本問題旨在提高某類打孔機的生產(chǎn)效能。打孔機的生產(chǎn)效能重要取決于以下幾方面：(1)單個過孔的鉆孔作業(yè)時間,這是由生產(chǎn)工藝決定,為了簡化問題，這里假定對于同一孔型鉆孔作業(yè)時間都是相同的;（２)打孔機在加工作業(yè)時，鉆頭的行進時間；（3)針對不同孔型加工作業(yè)時,刀具的轉換時間。目前,實際采用的打孔機普遍是單鉆頭作業(yè)，即一個鉆頭進行打孔。現(xiàn)有某種鉆頭,上面裝有8種刀具a,b,c,…,h,依次排列呈圓環(huán)狀，并且8種刀具的順序固定,不能調換。在加工作業(yè)時，一種刀具使用完畢后，可以轉換使用另一種刀具。相鄰兩刀具的轉換時間是１８s，例如，由刀具a轉換到刀具b所用的時間是１8s，其他情況以此類推。作業(yè)時，可以采用順時針旋轉的方式轉換刀具，例如，從刀具a轉換到刀具b；也可以采用逆時針的方式轉換刀具,例如，從刀具a轉換到刀具h。將任一刀具轉換至其它刀具處，所需時間是相應轉換時間的累加,例如,從刀具a轉換到刀具ｃ,所需的時間是3６s(采用順時針方式)。為了簡化問題，假定鉆頭的行進速度是相同的，為１8０mm/s，行進成本為0.06元/ｍｍ，刀具轉換的時間成本為7元/min。刀具在行進過程中可以同時進行刀具轉換,但相應費用不減。不同的刀具加工不同的孔型，有的孔型只需一種刀具來完畢,如孔型A只用到刀具a。有的孔型需要多種刀具及規(guī)定的加工順序來完畢,如孔型C需要刀具a和刀具c，且加工順序為a,ｃ。表1列出了10種孔型所需加工刀具及加工順序（標*者表達該孔型對刀具加工順序沒有限制）。表1:10種孔型所需加工刀具及加工順序孔型ABＣDEFＧHIJ所需刀具aba，cd,ｅ*c，ｆg,h*ｄ,g,fhe,cf，c一塊線路板上的過孔所有加工完畢后，再制作另一線路板。但在同一線路板上的過孔不規(guī)定加工完畢一個孔,再加工另一個孔,即對于須用兩種或兩種以上刀具加工的過孔，只要保證所需刀具加工順序對的即可。請建立相應的數(shù)學模型,并完畢以下問題：(１)附件１提供了某塊印刷線路板過孔中心坐標的數(shù)據(jù)，單位是密爾（mil)（也稱為毫英寸,1iｎｃh=１0０0ｍil)，請給出單鉆頭作業(yè)的最優(yōu)作業(yè)線路(涉及刀具轉換方案）、行進時間和作業(yè)成本。(2）為提高打孔機效能，現(xiàn)在設計一種雙鉆頭的打孔機(每個鉆頭的形狀與單鉆頭相同），兩鉆頭可以同時作業(yè)，且作業(yè)是獨立的,即可以兩個鉆頭同時進行打孔,也可以一個鉆頭打孔，另一個鉆頭行進或轉換刀具。為避免鉆頭間的觸碰和干擾，在過孔加工的任何時刻必須保持兩鉆頭間距不小于3cm(稱為兩鉆頭合作間距）。為使問題簡化，可以將鉆頭看作質點。(i)針對附件1的數(shù)據(jù),給出雙鉆頭作業(yè)時的最優(yōu)作業(yè)線路、行進時間和作業(yè)成本，并與傳統(tǒng)單鉆頭打孔機進行比較,其生產(chǎn)效能提高多少？(ii)研究打孔機的兩鉆頭合作間距對作業(yè)路線和生產(chǎn)效能產(chǎn)生的影響。問題的分析印刷線路板過孔加工費用有以下三個因素決定:單個過孔的做空作業(yè)時間；打孔機鉆頭行進時間;針對不同孔型加工作業(yè)時,刀具轉換時間；給出最優(yōu)作業(yè)方案,就要使總加工費用最小。而單個過孔的鉆孔作業(yè)時間是由生產(chǎn)工藝決定的，在不同打孔方式下不變。因此，最優(yōu)作業(yè)方案由2、３兩個因素決定。鉆頭行進時間和刀具轉換時間越小,加工總費用越小,作業(yè)路線最優(yōu)。并且加工總費用=刀具行進費用＋刀具轉換費用。對此,我們建立優(yōu)化模型，通過遺傳算法能較為準確的求出最優(yōu)解，進而擬定最優(yōu)路線，行進時間和作業(yè)成本。當打孔機設計成雙鉆頭時,由于作業(yè)時各鉆頭互相獨立,且有合作間距的限制，因此在解決雙鉆頭最優(yōu)作業(yè)方案時，我們在單鉆頭作業(yè)的基礎上再加上另一個鉆頭作業(yè)所需的各種費用并增長約束條件，保證合作間距在規(guī)定范圍之內?；炯僭O單個過孔的鉆孔作業(yè)時間，這是由生產(chǎn)工藝決定，為了簡化問題,這里假設對于同一孔型鉆孔作業(yè)時間都是相同的；在計算兩孔之間距離時,為了簡化問題，這里假設打孔機的鉆頭看作一個質點;為了計算行進費用，需要計算行進時間，為了簡化問題，這里假設打孔機的行進是一個勻速運動。符號說明模型的建立與求解問題一單鉆頭打孔作業(yè)為了提高打孔機的生產(chǎn)效能,就要使印刷線路板的過孔的總費用最小。而總費用=鉆孔作業(yè)費用+鉆頭行進費用+刀具轉換費用，并且本題中,生產(chǎn)工藝決定同一孔型作業(yè)時間相同，因此線路板的鉆空作業(yè)費用一定。所以要使鉆頭行進費用、刀具轉換費用之和最小。

(1)鉆頭行進費用其中，，當表達在得到的最優(yōu)途徑上;當表達不在得到的最優(yōu)途徑上。(2）刀具轉換費用①由附件所給數(shù)據(jù)，我們可以建立各孔的位置坐標與其相應孔型的映射，即若已知某孔的坐標為，則其孔型為;②考慮從孔到孔的道具轉換的方式,所有也許的轉換方法為表達打孔需要種刀具;表達打孔需要種刀具。把刀具依次標為。已知轉換相鄰兩個刀具的時間為；③再由鉆頭上的８種刀具的位置關系可求出由一種刀具轉換成另一種刀具所需要的最短時間為，其中是由刀具位置關系構造出的函數(shù)綜合①②③的討論，道具的轉換費用(3)根據(jù)題目所給說明，我們知道同種鉆孔作業(yè)費用是一定，并且印刷線路板上的孔的屬性一定，所以完畢一個印刷線路板的過孔加工總費用為于是，求單鉆頭作業(yè)的最優(yōu)方案就是如下的優(yōu)化問題?問題二雙鉆頭打孔作業(yè)設計雙鉆頭打孔機,兩鉆頭可以同時作業(yè)并且兩鉆頭作業(yè)互相獨立,要使印刷線路板的過孔的總費用最小，只要使鉆頭行進費用、作業(yè)費用之和最小,給出最優(yōu)作業(yè)方案。由于兩個鉆頭工作是互相獨立的，且合作間距已知不小于３cm。因此在解決雙鉆頭最優(yōu)作業(yè)方案時,我們在單鉆頭作業(yè)的基礎上再加上另一個鉆頭作業(yè)所需的各種費用并增長約束條件，保證合作間距在規(guī)定范圍之內。若鉆頭1打孔時鉆頭2打孔,記孔與孔之間的距離為用遺傳算法原理求解遺傳算法是模擬生物在自然環(huán)境中的遺傳和進化過程而形成的一種自適應全局優(yōu)化概率算法。對于本問題我們用Mａt(yī)ｌaｂ軟件進行求解。1.建立M文獻i孔橫坐標構成向量,縱坐標構成向量，j孔橫坐標構成向量,縱坐標構成向量2.運用缺省參數(shù)運營遺傳算法在Matlab里以下面語句調用ga運營函數(shù),返回值反映出了鉆頭所走最優(yōu)線路及刀具轉換方案。模型的評價與改善為了提高打孔機過孔效能,我們使打孔機作業(yè)路線最優(yōu),作業(yè)費用最小,并且加工總費用＝刀具行進費用＋刀具轉換費用,我們建立了優(yōu)化模型,該模型可以很好的描述NP不可解問題。但是對于模型的求解,理論上是把非線性模型化為線性模型,但是實際操作發(fā)現(xiàn)無法做到，我們又運用“遺傳算法”程序求解，又發(fā)現(xiàn)結果不是非常的準確。為此,我們對優(yōu)化模型進行改善。我們通過查閱資料，得知“貪婪算法”對此類問題模型的求解較為準確，因此采用該算法對模型進行求解并檢查。參考文獻[1］姜啟源,邢文訓,謝金星,楊頂輝.大學數(shù)學實驗，北京：清華大學出版社，202３.［2]楊啟帆,何勇,談之奕．數(shù)學建模競賽,杭州:浙江大學出版社,2023．［３］朱道元.數(shù)學建模案例精選,北京：科學出版社，２023．[4］韓中庚.數(shù)學建模方法及其應用,北京:高等教育出版社，2023.[5]周正武,丁同梅.基于TSP和ＧA孔群加工途徑優(yōu)化問題的研究,組合機床與自動化加工技術,2０23(7）:３０-3２.［６]周明，孫樹棟．遺傳算法原理及應用，北京:國防工業(yè)出版社，199９．附錄:（部分數(shù)據(jù)）孔型Ａ孔型B孔型ＣＸ1000Y2436００X-１0020０Ｙ3608０0X-１１０００0Y4２0230Ｘ-１0000Y30100０X-101０0０Y2０2３00Ｘ-1２3２00Y5２3800X-1０020０Ｙ246000Ｘ-1０1000Y2078００Ｘ-123600Y420230Ｘ-１00200Ｙ3224００Ｘ-10１０00Ｙ212８00X-1２8600Y４7１500X－1０1２０0Ｙ1２2800X-1０１00０Y21７８00X130600Y320４0０X-1０1３24Y265１74X-101００0Y2２3200Ｘ-1３06０0Y443200Ｘ-１01324Y2683２4X101000Y355000X13０800Y262６0０X-１013２4Y２71474X-10120０Y15000X－1３2２00Y４０920０X-10１3２4Y2７４623X-10１200Y２28４00Ｘ－141４00Y465８00X-１01324Ｙ２７777３X－101200Y－300０X14５000Y3３1800X-１01３24Y28４072Ｘ－101200Y８400０X1４5600Y24６000X-1013２４Y２8７222X-10１60０Y１５56０0X-1４8４00Y479200Ｘ－１０1324Ｙ2９3５2１Ｘ-10１600Y1６５5００Ｘ-152023Y227200X-101３24Y2９667０X-１0170０Y1４9700X１540０Y4858００X－１0１3２４Y２99８２０Ｘ－１01７０0Y17１4０0X-156800Y４6５８00Ｘ－101400Y３０620０X－101800Y14３80０X-16３200Y203600Ｘ-101４０0Y３１5600X-１0１９０0Y1773０0X1６7200Y12７40０Ｘ10２00Y242６00X102６0０Y６27４０0X167200Ｙ14２02３X１02023Y２4600０X-10３2００Y860００X－16７600Y443２０0Ｘ102０2３Y２6９60０X10420０Y6776０0X-１６８200Y222023X102023Y２97２０0Ｘ-105０00Y83８0０X-177600Y467０00X１020２３Ｙ30１２00X-106600Y373４00X-18７２00Y47920０X10２02３Y30５00０Ｘ-106６０0Y３７8200X1８8400Y42３４0０Ｘ102023Ｙ309000X-1０660０Y4４790０X-１91８0０Y1９4６０0X102023Y312８0０X-10７0０0Y8600０X－193400Y4６7４０0X102023Ｙ316８00X－１0８0０Y27０60０Ｘ-1９48０0Y43260０X1０20２3Y3２0800X108００Ｙ43202３Ｘ１98200Y127４00X1０2023Y324800X－10820０Y３9０000X19820０Ｙ142０2３X102023Y３286００X-1１000Y2770００X207200Ｙ48060０Ｘ102023Y3３2600Ｘ－110000Ｙ132００X－208２00Y19460０X１0２0２3Y336400X-11００00Y-2０23Ｘ2１7６0０Y４89400X１02０23Ｙ３40４00X-110３0０Y47１５00X224400Y３７６200Ｘ102023Ｙ34440０X１1０60０Y633４00X２2980０Y18６00０X１０2023Ｙ348４00X-１12200Y-1７４0０Ｘ-239000Ｙ3４260０孔型D孔型E孔型FＸ-１7400Ｙ4４100X1０２00Y8000０0X-31１3０0Y334０0X-17４00Y54100X10420０Y７686０0X－3１1300Y－5２400Ｘ22400Y４4０0０X106800Y83７200X－3１1３0０Y７430０X2２４00Y５4０0０X114６00Ｙ４５４00Ｘ-3１13０0Y-9200Ｘ－２74０0Ｙ4４１0０X1254０0Y2８000X29７80Y78７1０0X-27４０0Ｙ54１0０X1262０0Y845600Ｘ29７80Y８３7100Ｘ-2900Y4４100X127600Y8９3４00Ｘ29９80Y７0６90０X-2900Ｙ5４１０0X13０60０Ｙ3０14０0X2９9８０Y７5６900X324０0Y44０00X１30800Y282０23Ｘ4２30０Y7871０0X3２40０Y５４0０0Ｘ1356０0Ｙ721200X4230０Y８3７10０X-415０0Y4４１00X－1３60０Y７７3400X4250０Y7０6900Ｘ-4１500Ｙ5410０X137０00Ｙ899400X425００Y７5６9００Ｘ-5１5０0Ｙ4４100Ｘ－1380０Ｙ６89800Ｘ４780Ｙ7８710０Ｘ－515０0Ｙ５4１00Ｘ１４3000Ｙ１66０0X4780Ｙ８37１00Ｘ-6560０Y4４１００Ｘ143０00Y2820０X4980Y70690０X-６５６０0Y54100Ｘ14400Y720４0０X4９80Y756900Ｘ71０0Ｙ441０0X1４5000Y3016００X５48１9Y7８71０0X７100Y5４1０0X145600Y２8２02３X5481９Y83７100Ｘ－756００