1、2012山東科技大學數學建模競賽承 諾 書我們仔細閱讀了山東科技大學數學建模競賽說明。我們完全明白，在競賽開始后參賽隊員不能以任何方式（包括電話、電子郵件、網上咨詢等）與隊外的任何人（包括指導教師）研究、討論與賽題有關的問題。我們知道，抄襲別人的成果是違反競賽規則的, 如果引用別人的成果或其他公開的資料（包括網上查到的資料），必須按照規定的參考文獻的表述方式在正文引用處和參考文獻中明確列出。我們鄭重承諾，嚴格遵守競賽規則，以保證競賽的公正、公平性。如有違反競賽規則的行為，我們將受到嚴肅處理。我們參賽選擇的題號是（從A/B/C/D/E中選擇一項填寫）： D 我們的參賽報名號為： 2005 所屬學

2、院（請填寫完整的全名）： 理學院 參賽隊員 (打印并簽名) ：1. 孫旭 2. 宋賓賓 3. 柴利云 日期： 2011 年 5 月 5日2012山東科技大學數學建模競賽編 號 專 用 頁評閱記錄（可供評閱人評閱時使用）：評閱人評分備注最終成績：打孔機生產效能的提高摘要 過孔是印刷線路板（也稱為印刷電路板）的重要組成部分之一，本問題旨在提高某類打孔機的生產效能。打孔機的生產效能主要取決于以下幾方面：（1）單個過孔的鉆孔作業時間（2）打孔機在加工作業時，鉆頭的行進時間；（3）針對不同孔型加工作業時，刀具的轉換時間。本文將求最少工作時間轉化為最小總工作量，建立數學模型。一、問題重述：印刷電路板的制板

3、費用的30%到40%是用在過孔上，合理的過孔方案可以提高效率，節約成本。打孔機生產效能提高可從鉆頭行進時間、鉆頭轉換時間考慮。鉆頭有8種刀具a，b，c， , h，依次排列呈圓環狀，只能順時針或者逆時針轉換。題目給出了10種孔型所需加工刀具及加工次序，對于須用兩種或兩種以上刀具加工的過孔，只要保證所需刀具加工次序正確即可。問題一：附件1提供了某塊印刷線路板過孔中心坐標的數據，單位是密爾（mil）（也稱為毫英寸，1 inch=1000 mil），請給出單鉆頭作業的最優作業線路（包括刀具轉換方案）、行進時間和作業成本。問題二：為提高打孔機效能，現在設計一種雙鉆頭的打孔機（每個鉆頭的形狀與單鉆頭相同）

4、，兩鉆頭可以同時作業，且作業是獨立的，即可以兩個鉆頭同時進行打孔，也可以一個鉆頭打孔，另一個鉆頭行進或轉換刀具。為避免鉆頭間的觸碰和干擾，在過孔加工的任何時刻必須保持兩鉆頭間距不小于3cm（稱為兩鉆頭合作間距）。為使問題簡化，可以將鉆頭看作質點。（1） 針對附件1的數據，給出雙鉆頭作業時的最優作業線路、行進時間和作業成本，并與傳統單鉆頭打孔機進行比較，其生產效能提高多少？（2） 研究打孔機的兩鉆頭合作間距對作業路線和生產效能產生的影響。2、 問題分析：本題是一個求打孔機完成目標任務所需費用最小的多目標優化問題。打孔機的生產效能取決于單個過孔的鉆孔作業時間、打孔機在加工作業時鉆頭的行進時間和針對

5、不同孔型加工作業時，刀具的轉換時間。根據題意，打所有孔時間是不變的，提高打孔機的生產效能即要求打孔機鉆頭行進時間盡可能短，同時鉆頭轉換次數盡量少。而打孔機鉆頭行進時間與行進路程有關，即轉換為求最短路徑的問題。第一問中最優路線是打孔機鉆頭行進最短距離與鉆頭轉換次數最少結合的多目標優化問題。將題目所給各孔型坐標導入MATLAB，繪制出了所有孔的分布圖。再根據分布規律建立模型求出打孔機鉆頭行進最短距離和路線。然后考慮刀具轉換次數最少的情況，由題意，可以用一種刀具把需要打的孔全部打完再換刀，建立模型得到此情況下的最優轉換順序。最后列出兩個目標的目標函數和約束條件，用LINGO求解，得到最優解，進而找到

6、單鉆頭作業的最優作業線路（包括刀具轉換方案）、行進時間和作業成本。第二問三、模型假設1、假定對于同一孔型鉆孔作業時間都是相同的，作業時間不影響問題的分析，則求解時只分析鉆頭行進最短距離與鉆頭轉換次數。2、假定打孔機連續工作，行進期間無停留時間。3、假定打孔機鉆頭行進時只在任意兩點間做直線運動。4、四、符號說明Pi 第i個垃圾中轉站(i=1,238)P(xi，yi) 第i個垃圾中轉站的坐標Qi 第i個垃圾中轉站的垃圾量 t（噸）M 大型垃圾中心的個數P(xlj,ylj) 大型垃圾中心坐標(j=1,2M )N 小型垃圾中心的個數P(xsk,ysk) 小型垃圾中心坐標(k=1,2N )Silj 第i

7、個垃圾中轉站到大型垃圾中心的路程 百公里Sisk 第i個垃圾中轉站到小型垃圾中心的路程 百公里Ol 大型拖車的均噸公里耗油量 L百公里Os 小型收集車的均噸公里耗油量 L百公里a 大型拖車的數量 輛b 小型收集車的數量 輛Zab 拖車總運輸費用 元Za 大型拖車的運費 元Zb 小型收集車的運費 元Zm 大型垃圾中心的費用 元Zn 小型垃圾中心的費用 元 Z 垃圾處理總費用 元m 垃圾總質量 噸mi i站垃圾的質量 噸v 大型拖車的行駛速度 公里時ni 拖車每天去i站的次數 次r 大型設備的使用年限 年五、模型建立5.1 問題一5.1.1打孔機行進最短路程此種情況單考慮打孔機鉆頭行進完所有點的最

8、短路程，不考慮刀具轉換次數，即打孔機行進到哪點即打完這點。打孔機所要打的全部孔的相對位置和孔型見圖1。圖1 （二）名詞定義：定點距離最小法：在某片區域中，若存在c個點，兩點間路程可用x+y表示時，有以下結論：當c為奇數時，在x軸上，在第（c+1）/2個點處，到各點的距離和最小；同理在y軸上，在第（c+1）/2個點處，到各點的距離和最小。當c為偶數時，在x軸上，在第c/2c/2+1區域處，到各點的距離和最小；同理在y軸上，在第c/2c/2+1區域處，到各點的距離和最小。證明：已知A,B,C三點，求在x上取一點p使得p點到三點的距離和最小。從圖上可知，當P點位于A點與C點之間，則AP+PC=AC為

9、固定最小距離。BP取最小值0時，AP+PC+BP最小，即P點位于B點（第（c+1）/2個點）時, p點到三點的距離和最小。根據之前的分析，P應位于A，C點之間，進一步應在B，E之間，進一步，接近于D點。當已知點的數量c變大，P點要進一步縮小范圍取c值較大時，即可推斷出一下結論：當c為偶數時，P位于中間兩點之間的任意位置是等效的。當c為奇數時，P應位于第（c+1）/2個點處。同理，在y軸上，也可以確定出所求目標的y軸坐標。由所給信息新型垃圾轉運站垃圾轉運量等情況統計表得知：每日經轉運站需要運送到垃圾處理中心的垃圾數量為804噸。一個大型廚余垃圾處理設備的運行能力為200噸/日。廚余垃圾占總垃圾數

10、量的40%，即一個垃圾處理中心每日容納垃圾總量最多為500噸。因此，至少需要兩個大型廚余垃圾處理設備。不配置小型廚余垃圾處理設備處理設備，證明如下：證明：假設離大型處理設備較遠的一個中轉站Pi ，它到垃圾中心的距離為Si=5公里，垃圾數為5噸，用大型設備拖車要運一次，考慮到可能會浪費（拖車每次運10噸），用小型設備要5/0.2=25個，每天每臺機器費用280000/(10*365)=76元，設能用10年，則每天處理5噸的費用為Zmi=（76+200*0.2）*25=2900元。若用大型設備，費用為Zni=運費+機器每天成本+處理成本運費Zai=(5/100)*25*7.51*5=47元機器每天

11、成本+處理成本=(48000000/(365*10)/200+150)*5=1078元Zni=47+1078=1025元<2900元，故不用小型設備。證畢。因此，設置兩個大型處理設備，設置的兩個垃圾處理中心，應符合以下條件。要求：每個區域中垃圾總量不得多于500噸。垃圾處理中心的選址應符合環境要求，不得位于市中心或小區內，不得在水資源附近。交通便利，周圍有交通路線，便于穿梭于各小區之間。車輛在各轉運站到垃圾處理中心運行的總路程，應取得較小路程。司機個數的確定：a=總路程/（工作時間*速度）（三）垃圾處理中心位置的確定：確定保證總路程最小的位置P(xlj,ylj) 所分割的兩區域如圖所示

12、域一 含有的點為11,31,32,33,34, 5,25,38,3,4,19,26,37,7,13,29,20,8,28, 35,40,這些點運到垃圾中心1 ，坐標為P(xl1,yl1) 。各個轉運站運輸次數為 i點可以看做有i個坐標相同的點，總的點數為=33（i=11,31,32,33,34,5,25,38,3,4,19,26,37,7,13,29,20,8,28,35,40，）將這個點的橫坐標xi，縱坐標yi列出后通過“定點距離最小法”求得垃圾中心1的坐標為。其中橫坐標為第/2+1=16個點即地圖上第6個中轉站的橫坐標，縱坐標為第26個點的縱坐標。同理求出垃圾中心2的坐標。利用MATLAB

13、對南山地圖進行取點，得到各回收站的坐標，再對這些坐標進行繪圖，畫出點陣圖。MATLAB程序如下：a=imread('nanshan.jpg')；imshow(a)xy=ginput得出各轉運站的坐標。（表1）初步劃分后，兩個垃圾中心的各轉運站數據如下表所示： （比例尺100:3公里）垃圾中心1垃圾中心2轉運站iXY轉運站iXY3307.5286520.3856223208.4387157.055934310.5313494.862433698.8392164.562745197.9292590.9496124212.9428178.074937178.4114434.80791

14、10137.8747257.647138230.9591404.7807122167.9019277.1649211236.9646643.497316196.4278277.1649213310.5313424.2984221256.4823289.1757219263.9891503.8706214166.4005293.6798220266.9918406.282330185.9183301.1866325412.624527.8924116321.0409316.2003326282.0054490.3583215167.9019319.203228333.0518359.739831

15、8238.4659325.2084229355.5722418.292929157.3924335.718331282.0054657.0095135411.1226338.7207732242.97620.9768127283.5068347.7289433357.0736602.960531170.9046352.233234456.1635532.3965117140.8774361.2411237265.4905452.824322218.9482368.748338417.1281515.8815112146.8828371.75074將這個點的橫坐標xi，縱坐標yi列出后通過“定點

16、距離最小法”求得垃圾中心1的坐標為（307.5286,490.3583）。其中橫坐標為第/2+1=16個點即地圖上第6中轉站的橫坐標，縱坐標為第26個點的縱坐標。同理求出垃圾中心2的坐標（196.4278,319.203）Matlab程序：x=282.0054 236.9646 242.97 197.9292 357.0736 307.5286 412.624 456.1635 417.1281 263.9891 282.0054 310.5313 265.4905 178.4114 230.9591 266.9918 310.5313 355.5722 146.8828 140.8774 1

17、70.9046 157.3924 218.9482 283.5068 333.0518 411.1226 238.4659 321.0409 408.1199 185.9183 166.4005 167.9019 196.4278 256.4823 137.8747 212.9428 208.4387 98.8392 44.7902 167.9019;y=657.0095 643.4973 620.9768 590.9496 602.9605 520.3856 527.8924 532.3965 515.8815 503.8706 490.3583 494.8624 452.8243 434.

18、8079 404.7807 406.282 424.2984 418.2929 371.7507 361.2411 352.233 335.718 368.748 347.7289 359.7398 338.7207 325.2084 316.2003 310.1948 301.1866 293.6798 277.1649 277.1649 289.1757 257.6471 178.0749 157.0559 164.5627 163.0613 319.2030;plot(x,y,'*k');hold;a=307.5286 196.4278;b=490.3583 319.20

19、3;plot(a,b,'ok');垃圾處理中心（圖中“”）計算位置圖 優化后垃圾處理中心的位置圖根據地理位置，對兩個點選址進行修正。按要求，垃圾處理中心應遠離小區，附近無水資源，交通便利。在已求出的兩點附近分別找到最合適點，求出其坐標（重復找坐標的程序）：P1（305.5 ,443.75） 留仙大道南沙河西路東的紅花嶺林地P2（233.5 ,268.25） 學府路與科園路交匯處東北空地 垃圾處理中心1 垃圾處理中心2找出兩個垃圾處理中心的中垂線，定位處理中心管理范圍的交界線。運送至垃圾處理中心1的轉運站有（每個序號對應一轉運站）：3,4,5,7,8,11,13,19,20,25

20、,26,28,29,31,32,33,34,35,37,38運送至垃圾處理中心2的轉運站有：1,2,6,9,10,12,14,15,16,17,18,21,22,23,24,27,30,36。（四）驗證：計算各垃圾處理中心所收集的垃圾總重量：Q1=356噸Q2=448噸在垃圾處理中心的處理容量范圍（500噸）之內。計算兩區域大型拖車總路程：通過分析地圖發現，拖車所走路線幾乎都為如圖水平豎直折現，故拖車在兩點間所走的路程可表示為 =x+y 其中 x為兩點間水平距離，y為兩點間豎直距離。往返垃圾中心1的拖車總路程S1=2=2=2往返垃圾中心2的拖車總路程S2=2=2=2S1=11000.7828S

21、2=17177.4548S=S1+S2=28178.2376每日耗油總費用ZS=S*（3/100）*0.25L/km*7.51元/L=1587元設備每日運行費用Zd=150元/噸*804噸*0.4=48240元設備每日折損費用Zb=4.5*107/(r年*365)*2若r取10年，Zb= 24657元 Z=ZS+Zd+Zb=74484元一個大型設備的每日折損費用為12329元，遠大于耗油費用。說明，若以增加大型設備的量來減少耗油總費用是不可取的，假設中設立兩個大型垃圾處理設備是比較合適的。（五）結論：在現有轉運站規模與位置不變的條件下，選用兩個大型設備，分別分布在上圖中所示位置，即留仙大道南沙

22、河西路東的紅花嶺林地（1）、學府路與科園路交匯處東北空地（2）。運送至垃圾處理中心1的轉運站有：動物園站，平山村站，牛城村站，同樂村站，松坪山（二）站，陽光(白芒關外)站，光前站，官龍村站，松坪山站，福光站，新圍村站，沙河市場站，龍井，麻勘站，白芒站，大石磡站，長源村站，華僑城站。運送至垃圾處理中心2的轉運站有：九街站，玉泉站，科技園站，大新小學站，南山村站，月亮灣大道站，北頭站，涌下村站，白石洲南站，前海公園站，深圳大學站，南光站，南園站，望海路站，花果路站，大沖站，南山市場，疏港小區站，西麗路站，塘朗站。問題二：（一）轉運站重新設計規劃經分析地圖上的各轉運站，分布有其合理性，但有很多分布欠

23、妥，如在垃圾較少的地區分布較多，有些地區轉運站分布較密，肯定給附近小區運往轉運站造成不便。于是經分析將部分不合理的轉運站進行拆除、合并、新建，并調整轉運站的大型廂配備，形成更合理的轉運站分布。具體改變情況如圖所示：25、34、38三個垃圾站合并為一個新的，記為P41（438.1471，524.8896），P12移動到P42（202.4332，385.2629），P14與P30合并到P30，P22與P21合并為P21，在（227.9564，229.1213）出新建P43。（二）確定垃圾處理中心的位置如第一步，先暫時將地圖分為如圖兩部分，用“定點距離最小法”求出兩垃圾中心的坐標。得出區域一的新垃圾

24、中心的坐標為Pl1(282.0054,490.3583),區域二的新垃圾中心的坐標為Pl2(212.9428,316.2003)。連接兩點畫出中垂線作為兩區域的邊界線，發現P42，P2，P27，P7，P8離垃圾中心二較近，應運往二，則對新的分布求垃圾中心。得到新的垃圾中心坐標Pl1''(310.5313,494.8624)Pl2''(208.4387,325.2084)經查看地圖發現新的垃圾中心處理站和上題中確定的垃圾中心處理站地點大致相同，考慮到具體地形及選址要求最終確定垃圾中心處理站與上題結果一致。P1''（305.5 ,443.75） 留仙

25、大道南沙河西路東的紅花嶺林地P2''（233.5 ,268.25） 學府路與科園路交匯處東北空地運送至垃圾處理中心1的轉運站有：28,20,29,13,37,26,4,19,3,41,5,33,32,11,31,運送至垃圾處理中心2的轉運站有：36,10,17,9,15,1,7,30,6,42,23,24,2,43,8,18,21,27,16,35,（三）驗證并矯正：計算各垃圾處理中心所收集的垃圾總重量：Q1=274噸Q2=530噸因Q2不在垃圾處理中心的處理容量范圍（500噸）之內。故將在分界處的本屬于垃圾站2的P8，P27劃到垃圾中心站1。（由于該兩點位于中垂線附近，故移動

26、后對垃圾中心站幾乎沒有影響）Q1=319噸Q2=485噸其容量在垃圾處理中心處理的容量范圍之內。運送至垃圾處理中心1的轉運站有：28,20,29,13,37,26,4,19,3,41,5,33,32,11,31,8,27,運送至垃圾處理中心2的轉運站有：36,10,17,9,15,1,7,30,6,42,23,24,2,43,18,21,16,35,往返垃圾中心1的拖車總路程S1=2=2=2往返垃圾中心2的拖車總路程S2=2=2=2S1=8542.7522S2=12638.4684S=S1+S2=21181.2206每日耗油總費用ZS=S*（3/100）*0.25L/km*7.51元/L=11

27、93.元設備每日運行費用Zd=150元/噸*804噸*0.4=48240元設備每日折損費用Zb=4.5*107/(r年*365)*2若r取10年，Zb= 24657元Z=ZS+Zd+Zb=74090元（較1題中省394元）（四）結論： 經過對25、34、38三個垃圾站合并為一個新的，記為P41（438.1471，524.8896），P12移動到P42（202.4332，385.2629），P14與P30合并到P30，P22與P21合并為P21，在（227.9564，229.1213）出新建P43后，同題1中的過程，求解出兩個垃圾處理中心的位置與其結果相同：選用兩個大型設備，分別分布在上圖中所示

28、位置，即留仙大道南沙河西路東的紅花嶺林地（1）、學府路與科園路交匯處東北空地（2）。運送至垃圾處理中心1的轉運站有：松坪山站,沙河市場站,龍井,光前站,新圍村站,西麗路站,動物園站,平山村站,官龍村站,牛城村站,大石磡站,41站,白芒站,麻勘站,陽光(白芒關外)站,松坪山（二）站,大沖站。運送至垃圾處理中心2的轉運站有：南山村站,前海公園站,疏港小區站,九街站,大新小學站,涌下村站,科技園站,同樂村站,南山市場,望海路站,花果路站,玉泉站,42站,深圳大學站,南光站,43站,白石洲南站,華僑城站。6、 優化改進：1、司機個數優化開車走完總路程所需時間：S*（3/100）km/(40km/h)=

29、21h假設司機每天開車和裝運時間分別為3h和3h大型拖車需要的司機數量為a=21h/3h=7每日司機工資支出費用3500/30*a=817元假如16輛大型拖車都用上，會多出9個司機的工資，共1050元/天。2、 小型設備用來處理大量垃圾很不合適，建議將小型設備安置在廚余垃圾產量較大的餐館等場所。3、 各轉運站的大型廂數量應根據垃圾產量合理分配。參考文獻：1生活垃圾處理技術指南 住房和城鄉建設部國家發展和改革委員會 2孫向軍,馮蒂,吳冰思,等.上海市泔腳垃圾的處理及管理J.環境衛生工程,2002,10(3):130-132.3劉躍勇,任福民,汝宜紅,等.北京市生活垃圾成分及理化特性分析J.北方交通大學學報,2002,26(4):50-52.附錄：表1序號垃圾轉運站名稱廂數垃圾轉運 量(噸/日)x坐標y坐標1九街站120170.90