數(shù)學(xué)建模優(yōu)秀論文

1、<p><b>　　問題重述</b></p><p>　　過孔是印刷線路板（也稱為印刷電路板）的重要組成部分之一，打孔機(jī)主要用于在制造印刷線路板流程中的打孔作業(yè)。目前，實(shí)際采用的打孔機(jī)普遍是單鉆頭作業(yè)，即一個(gè)鉆頭進(jìn)行打孔。本問題旨在解決某類打孔機(jī)的生產(chǎn)效能問題。</p><p>　　打孔機(jī)的生產(chǎn)效能主要取決于：（1）單個(gè)過孔的鉆孔作業(yè)時(shí)間，由生產(chǎn)工藝決定；（

2、2）打孔機(jī)加工作業(yè)時(shí)，鉆頭的行進(jìn)時(shí)間；（3）針對不同孔型加工作業(yè)時(shí)，刀具的轉(zhuǎn)換時(shí)間。</p><p>　　某種鉆頭裝有8種刀具，8種刀具的順序固定，不能調(diào)換。加工作業(yè)時(shí)，一種刀具使用完畢后，可轉(zhuǎn)換使用另一種刀具。相鄰兩刀具的轉(zhuǎn)換時(shí)間是18 s。作業(yè)時(shí)，可順時(shí)針旋轉(zhuǎn)轉(zhuǎn)換刀具，如刀具a刀具b；也可逆時(shí)針旋轉(zhuǎn)轉(zhuǎn)換刀具，如刀具a刀具h(yuǎn)。將任兩個(gè)刀具轉(zhuǎn)換，所需時(shí)間是相應(yīng)轉(zhuǎn)換時(shí)間的累加。假定鉆頭的行進(jìn)速度相同，為180 mm

3、/s，行進(jìn)成本為0.06元/mm，刀具轉(zhuǎn)換的時(shí)間成本為7元/min。刀具行進(jìn)過程中可同時(shí)轉(zhuǎn)換刀具，但相應(yīng)費(fèi)用不減。</p><p>　　不同的刀具加工不同的孔型，有的只需一種刀具來完成，有的需要多種刀具及規(guī)定的加工次序來完成。表1為10種孔型所需加工刀具及加工次序（*表示該孔型不限制加工次序）。</p><p>　　表1：10種孔型所需加工刀具及加工次序</p><p&

4、gt;　　同一線路板上的過孔不要求加工完畢一個(gè)孔，再加工另一個(gè)孔，即對于須用多種刀具加工的過孔，只要保證所需刀具加工次序正確即可。</p><p>　　建立相應(yīng)的數(shù)學(xué)模型，并完成以下問題：</p><p>　　（1）由附件1提供的某塊印刷線路板過孔中心坐標(biāo)的數(shù)據(jù)，請給出單鉆頭作業(yè)的最優(yōu)作業(yè)線路（包括刀具轉(zhuǎn)換方案）、行進(jìn)時(shí)間和作業(yè)成本。</p><p>　　（2）為提

5、高打孔機(jī)效能，現(xiàn)在設(shè)計(jì)一種雙鉆頭的打孔機(jī)（鉆頭形狀與單鉆頭相同），兩鉆頭可以同時(shí)作業(yè)，也可一個(gè)鉆頭打孔，另一個(gè)鉆頭行進(jìn)或轉(zhuǎn)換刀具。為避免鉆頭間的觸碰和干擾，在過孔加工的任何時(shí)刻必須保持兩鉆頭間距不小于3cm的合作間距。</p><p>　?。╥）針對附件1的數(shù)據(jù)，給出雙鉆頭作業(yè)時(shí)的最優(yōu)作業(yè)線路、行進(jìn)時(shí)間和作業(yè)成本，并與傳統(tǒng)單鉆頭打孔機(jī)進(jìn)行比較，其生產(chǎn)效能提高多少？</p><p>　　（i

6、i）研究打孔機(jī)的兩鉆頭合作間距對作業(yè)路線和生產(chǎn)效能產(chǎn)生的影響。</p><p><b>　　問題分析</b></p><p><b>　　問題1分析：</b></p><p>　　本問題可看作為動(dòng)態(tài)規(guī)劃與圖論的組合問題，即求取由起始狀態(tài)到終點(diǎn)狀態(tài)的最優(yōu)單向路徑問題，主要是運(yùn)用運(yùn)籌學(xué)的排序理論、圖論中的路徑的相關(guān)理論知識解決

7、問題。經(jīng)分析，—鉆頭的行進(jìn)時(shí)間、—加工不同孔型的刀具的轉(zhuǎn)換時(shí)間，是本題的目標(biāo)規(guī)劃量。行進(jìn)速度恒定，故目標(biāo)規(guī)劃量可轉(zhuǎn)化為等效最短路徑。</p><p>　　首先，由分析，異型孔中最遠(yuǎn)兩點(diǎn)距離小于等效換刀距離，故我們建立換刀、路線分立優(yōu)化原則，鄰近換刀原則。在該兩個(gè)原則下，我們確定了運(yùn)用工序優(yōu)化算法總體優(yōu)化換刀次序，同型孔中計(jì)算路徑最優(yōu)的問題的思路，將問題分成兩部分進(jìn)行求解。其次，為解決在同型孔中求解最優(yōu)路徑，由優(yōu)化

8、的最鄰近算法我們求解出初始的回路，通過二邊逐次修正算法對其進(jìn)行優(yōu)化，而后刪去虛擬點(diǎn)得最優(yōu)單向路徑。最后，通過與最小生成樹計(jì)算所得下界進(jìn)行比較，對結(jié)果進(jìn)行驗(yàn)證。</p><p><b>　　問題2分析</b></p><p>　　問題二中，雙鉆頭對孔群進(jìn)行加工的互相干擾，使本問題的時(shí)序性更突出，故不能簡單使用求回路法，即使用動(dòng)態(tài)規(guī)劃的思想，該問題這也是個(gè)典型的NP-難問

9、題，故我們將采用改進(jìn)的蟻群算法進(jìn)行近似求解。我們將采取建立于蟻群算法的蟻對群算法，全局搜索出兩條最短路徑，以達(dá)到目標(biāo)時(shí)間最短，使生產(chǎn)效能最高。</p><p>　　對于（i），由于其他條件不變，故決定性條件仍為換刀時(shí)間，對此我們沿用問題一的兩個(gè)原則。為使目標(biāo)時(shí)間最小，基于兩刀加工時(shí)間的一致性，對總換刀次數(shù)，令，并使兩鉆頭換刀次數(shù)盡可能相同。在優(yōu)化問題上，由于存在合作間距的約束條件，問題變?yōu)樵谶B續(xù)時(shí)間內(nèi)，時(shí)刻加入兩

10、鉆孔間距離的判斷。對于（ii），將在統(tǒng)一模型算法下，通過改變合作間距，定量研究其對生產(chǎn)效能的影響。</p><p>　　在模型驗(yàn)證中，將所求的路徑與基于最小生成樹的路徑做誤差分析。同時(shí)，單純對于提高生產(chǎn)效能而言，與問題一結(jié)果相較，若單孔作業(yè)總時(shí)間，為雙孔作業(yè)時(shí)間，則該模型的建立是失敗的。</p><p><b>　　模型假設(shè)</b></p><p&

11、gt;　　忽略鉆頭的形狀、材料、加工工藝等因素對鉆孔作業(yè)的影響，將鉆頭視為質(zhì)點(diǎn)；</p><p>　　忽略所打孔的大小，將孔視為質(zhì)點(diǎn)，以圓心坐標(biāo)表示；</p><p>　　假定打孔機(jī)8種刀具單獨(dú)鉆孔作業(yè)時(shí)間相同；</p><p>　　假定對于同一孔型鉆孔作業(yè)時(shí)間都是相同的；</p><p>　　在問題一中，假定所有孔型的鉆孔作業(yè)時(shí)間相同，經(jīng)查

12、閱資料，取該時(shí)間為；</p><p>　　在問題二的(i)中，假定合作距離為3cm。</p><p><b>　　符號說明</b></p><p><b>　　模型準(zhǔn)備</b></p><p>　　路徑（回路）與TSP問題</p><p>　　定義 在無向圖中，穿程于的每

13、個(gè)節(jié)點(diǎn)依次且僅一次的路徑稱為路徑。穿程于的每個(gè)節(jié)點(diǎn)依次且僅一次的回路稱為回路。</p><p>　　TSP(旅行商問題)</p><p>　　有n個(gè)城市，其相互間距離,為已知，求合理的路線使得每個(gè)城市都被經(jīng)過一次，且總路徑為最短。TSP的數(shù)學(xué)模型為：</p><p><b>　　(7)</b></p><p><b

14、>　　(8)</b></p><p><b>　　(9)</b></p><p><b>　　(10)</b></p><p><b>　　(11)</b></p><p>　　式(8)中表示旅行商經(jīng)歷的路徑，表示不經(jīng)過該路徑；式(5)(6)要求旅行商經(jīng)過點(diǎn)有

15、且僅有一次；(8)在任何一個(gè)城市的子集中不行成圈。</p><p><b>　　最鄰近算法</b></p><p>　　定理1 是個(gè)頂點(diǎn)的無向完全圖，為從到正實(shí)數(shù)集的函數(shù)，對在中任意三點(diǎn)，滿足</p><p><b>　　(1)</b></p><p>　　則可將實(shí)際問題轉(zhuǎn)化為求取賦權(quán)圖上的回路

16、問題。</p><p><b>　　具體算法如下：</b></p><p>　　在中取一點(diǎn)為起始點(diǎn)，找出一個(gè)與始點(diǎn)最近的點(diǎn)，形成一條邊的初始路徑。</p><p>　　設(shè)表示最新加到這條路徑上的點(diǎn)，從不在路徑上的所有點(diǎn)中，選一個(gè)與最鄰近的點(diǎn)，把連接與此點(diǎn)邊加到這條路徑中。重復(fù)直至中的所有頂點(diǎn)包含在路徑中</p><p>

17、　　把始點(diǎn)和最后加入的頂點(diǎn)之間的邊放入，即得出一個(gè)回路。</p><p><b>　　蟻群算法：</b></p><p><b>　　狀態(tài)轉(zhuǎn)移規(guī)則</b></p><p><b>　　(2)</b></p><p>　　式中一在時(shí)刻螞蟻由元素轉(zhuǎn)移到元素的概率；——表示螞蟻下一步

18、允許選擇的城市；——信息啟發(fā)式因子，表示軌跡的相對重要性；一期望啟發(fā)式因子，表示能見度的相對重要性；——啟發(fā)函數(shù)，；——?dú)埩粜畔⒘俊?lt;/p><p><b>　　信息素修正規(guī)則</b></p><p><b>　　(3)</b></p><p><b>　　(4)</b></p><

19、;p>　　式中,——信息素?fù)]發(fā)系數(shù)；一表示第只螞蟻在本次循環(huán)中留在路徑上的信息量；——信息素強(qiáng)度，設(shè)為常數(shù)；——第后只螞蟻在本次循環(huán)中所走過的路徑的長度。</p><p>　　禁忌表的修改和表螞蟻數(shù)后有一個(gè)表和表。初始時(shí)可以把中的元素都設(shè)為0，把的元素都設(shè)為l。如果螞蟻第1次選擇了城市，則把tabu表中第1元素賦值為，并把表總第個(gè)元素賦值為0，表示此城市已經(jīng)走過。</p><p>&

20、lt;b>　　算法實(shí)現(xiàn)步驟如下：</b></p><p>　　參數(shù)初始化。令循環(huán)次數(shù)，將只螞蟻隨機(jī)放在個(gè)元素(城市)上，；</p><p><b>　　循環(huán)次數(shù)</b></p><p><b>　　螞蟻數(shù)；</b></p><p>　　對第只螞蟻，根據(jù)公式(1)選擇城市，并前進(jìn)；&

21、lt;/p><p>　　把選擇的城市加入到第屜只螞蟻的表中，并修改表；</p><p>　　對于第只螞蟻若沒有游歷完所有個(gè)城市，則轉(zhuǎn)到第4步，若游歷完所有城市，則執(zhí)行第7步；</p><p>　　若螞蟻數(shù)k小于螞蟻總數(shù)，則轉(zhuǎn)到第3步，直到只螞蟻都游歷完個(gè)城市，再執(zhí)行第8步；</p><p>　　根據(jù)式(2)、式(3)更新每條路上的信息量，并找出只

22、螞蟻中，所走的最短路徑的值，并保存；</p><p>　　若循環(huán)次數(shù)未達(dá)到最大循環(huán)次數(shù)，則轉(zhuǎn)到第2步，若滿足結(jié)束條件則結(jié)束循環(huán)，并輸出計(jì)算結(jié)果。</p><p><b>　　數(shù)據(jù)處理</b></p><p>　　將10種孔型按所需刀具重新編號，其中分別代表8種刀具、10種孔型中某一種，故得18類孔（共2814個(gè)）如下表。</p>

23、<p>　　表格 1 18種新孔分類列表</p><p>　　另外，為敘述簡便，將新的18種孔型做統(tǒng)一再命名，對應(yīng)表格如下</p><p>　　表格 2 18種新孔識記表</p><p>　　同時(shí)我們作出了相應(yīng)的18種新孔的刀具分布情況，如下圖。</p><p>　　圖 1 18種新型孔的刀具分布情況</p>

24、<p>　　由公式，將題目中縮短行進(jìn)、換刀時(shí)間問題，轉(zhuǎn)化為求解最短距離問題。</p><p>　　首先，將5.3數(shù)據(jù)處理中所得到的2814個(gè)點(diǎn)，，記作賦權(quán)圖中點(diǎn)集，其中。</p><p>　　針對上步中的2814個(gè)點(diǎn)，依次求出兩點(diǎn)間最短距離；</p><p>　　不同的孔型需換刀具，兩點(diǎn)間的換刀等效距離</p><p><b&

25、gt;　　(5)</b></p><p><b>　　其中</b></p><p><b>　　(6)</b></p><p>　　為兩刀具之間所需的換刀時(shí)間，為點(diǎn)與點(diǎn)換刀次數(shù)。</p><p><b>　　模型的建立與求解</b></p><p

26、>　　兩個(gè)原則下的單向路徑的圖論模型</p><p><b>　　模型建立</b></p><p>　　基于TSP(旅行商問題)的最短路程模型：</p><p><b>　　最短等效路徑：</b></p><p><b>　　刀具行進(jìn)路徑：</b></p>

27、<p>　　從先前位置移動(dòng)到當(dāng)前位置的成本。設(shè)兩個(gè)位置之間的實(shí)際距離為單位長度的刀具行進(jìn)成本為n，則完成個(gè)孔加工的刀具行進(jìn)成本為：</p><p><b>　　(12)</b></p><p>　　——孔和孔之間距離；——該路徑在優(yōu)化路徑上。</p><p><b>　　換刀等效路徑：</b></p&g

28、t;<p>　　設(shè)打孔機(jī)為加工孔后再加工不同孔型所需的等效換刀距離，為單位路徑的換刀成本，則完成個(gè)孔加工的換刀成本為：</p><p><b>　　(13)</b></p><p>　　——兩點(diǎn)間的等效換刀路徑 （處理方法，見數(shù)據(jù)處理5.3）；</p><p>　　——兩點(diǎn)之間的換刀次數(shù)。</p><p>

29、;<b>　　則最小化總目標(biāo)：</b></p><p><b>　　(14)</b></p><p><b>　　模型求解思路：</b></p><p>　　在換刀、路線分立優(yōu)化原則，鄰近換刀原則下，我們將用語言編寫工序優(yōu)化算法實(shí)現(xiàn)總體工序優(yōu)化，通過優(yōu)化的最鄰近算法求得初始回路，而后用二邊逐次修正算法

30、對路徑進(jìn)行優(yōu)化，并將虛擬點(diǎn)刪去得單向路徑。解決步驟如圖2。</p><p><b>　　圖 2模型一流程圖</b></p><p>　　兩個(gè)原則下的工序、路徑優(yōu)化</p><p><b>　　兩個(gè)原則：</b></p><p>　　換刀、路線分立優(yōu)化原則：</p><p>　

31、　換刀情況下，最小等效換刀距離</p><p><b>　　(17)</b></p><p><b>　　(18)</b></p><p>　　其中，——對行進(jìn)距離的平均值。</p><p>　　故需將同一類型的孔打完再換刀，則本問題轉(zhuǎn)化為——異類點(diǎn)工序（換刀）優(yōu)化、同類點(diǎn)之內(nèi)的路徑優(yōu)化問題。<

32、;/p><p><b>　　鄰近換刀原則：</b></p><p>　　為減小等效，換刀時(shí)應(yīng)盡量進(jìn)行臨近刀具轉(zhuǎn)換進(jìn)行打孔作業(yè)，如，，或孔作業(yè)完畢，則優(yōu)先或孔的作業(yè)，在鄰近換刀條件下，最大程度上減少。</p><p><b>　　工序優(yōu)化算法：</b></p><p>　　對于已有18類孔，必然有，其中表

33、示步驟總數(shù)，18步之內(nèi)總能打完所有的點(diǎn)。故對工序進(jìn)行優(yōu)化時(shí)，我們引入步驟矩陣，激活矩陣，狀態(tài)矩陣，以總次數(shù)最小為目標(biāo)，</p><p><b>　　(19) </b></p><p>　　其中，為要打第類孔時(shí)，所需的換刀次數(shù)。</p><p><b>　　初始化步驟矩陣，；</b></p><p>

34、<b>　　激活矩陣，；</b></p><p><b>　　狀態(tài)矩陣，；</b></p><p>　　其中，代表相應(yīng)的新型孔。</p><p>　　根據(jù)圖4 ,18類新型孔的刀具分布情況，步驟矩陣，由某確定起始孔型開始，，若，則向左尋找最近的的孔型，并將對應(yīng)的關(guān)系矩陣尋找下線孔型，并使，。</p><

35、p>　　根據(jù)，的值，重復(fù)對的操作。并判斷是否，。 若滿足則結(jié)束，若不滿足則重復(fù)3)的操作。則可得工序的最優(yōu)解。</p><p>　　最鄰近算法求初始回路</p><p><b>　　具體步驟如下：</b></p><p>　　建立等效距離矩陣，其中第行、第列的元素，為點(diǎn)到點(diǎn)的等效距離；</p><p>　　建立激活

36、矩陣，其中；</p><p>　　建立關(guān)系矩陣，其中；</p><p>　　建立狀態(tài)矩陣，其中；</p><p>　　確a定點(diǎn)（時(shí)為起始點(diǎn)），對應(yīng)將，，若，則由值查找下線點(diǎn)，跳轉(zhuǎn)至步驟3；若，則繼續(xù)對點(diǎn)重復(fù)對的操作，直至轉(zhuǎn)至步驟3。</p><p>　　由第二步所確定的點(diǎn)對于除外的所有點(diǎn)滿足相應(yīng)的點(diǎn)，并在等效距離矩陣中的第行中，對于滿足要求的

37、點(diǎn)對應(yīng)的值尋找最小值，并對點(diǎn)重復(fù)步驟二，直至所有元素為零，故所得路徑為優(yōu)化的有向回路。</p><p>　　在路徑中加入虛擬點(diǎn)，令任一點(diǎn)到得距離=0，則與路徑中所有的點(diǎn)都相連接，則最終去掉邊權(quán)最大的兩點(diǎn)中間的路徑，則得到有向路徑。</p><p><b>　　具體算法流程如下：</b></p><p><b>　　二邊逐次修正算法&l

38、t;/b></p><p>　　對所得圈，對所有適合的，判斷對某一對和，是否有</p><p><b>　　(20)</b></p><p>　　若有，刪去邊和,添加邊和得;</p><p>　　重復(fù)1)2)兩步，直至不可再用此方法繼續(xù)進(jìn)行，則求得一個(gè)較優(yōu)的圈</p><p>　　為了得到更

39、高的精度，該程序可以重復(fù)幾次，每次都以不同的圈開始。</p><p><b>　　模型求解</b></p><p><b>　　總路徑示意圖：</b></p><p><b>　　打孔路徑圖：</b></p><p><b>　　打孔路徑圖：</b><

40、;/p><p><b>　　打孔路徑圖：</b></p><p><b>　　打孔路徑圖</b></p><p><b>　　打孔路徑圖：</b></p><p><b>　　打孔路徑圖：</b></p><p><b>　　

41、打孔路徑圖：</b></p><p><b>　　打孔路徑圖：</b></p><p><b>　　打孔路徑圖：</b></p><p>　　工序流程表及對應(yīng)路徑長度：</p><p><b>　　工序流程為：</b></p><p>　　該

42、流程實(shí)際為刀具轉(zhuǎn)換的流程，也即工序圖，其中表示某一種刀具，表示換刀。該流程為，由刀具開始，將所有用到刀具的孔全部打完后，刀具換轉(zhuǎn)，將即需刀具的型所有孔打完，再轉(zhuǎn)換。同理，以該流程打完所有孔。</p><p>　　工序流程表及對應(yīng)長度如下：</p><p><b>　　總時(shí)間計(jì)算：</b></p><p><b>　　(21)</

43、b></p><p><b>　　總費(fèi)用計(jì)算：</b></p><p><b>　　(22)</b></p><p><b>　　模型檢驗(yàn)</b></p><p>　　有向圈的求解并不能找到確定的最優(yōu)解，但可以用最佳圈的權(quán)的下界與其比較。利用最小生成樹可以得到最佳圈的一個(gè)

44、下界，方法如下。</p><p>　　設(shè)是的一個(gè)最佳圈，則對的任一頂點(diǎn)，是的路，也是的生成樹。如果是的最小生成樹，且和是與關(guān)聯(lián)的邊中權(quán)最小的兩條邊，則將是的一個(gè)下界。</p><p><b>　　問題二</b></p><p><b>　　模型建立</b></p><p>　　在問題一的基礎(chǔ)上，我們

45、由雙鉆頭工序優(yōu)化算法優(yōu)化出雙鉆頭的換刀方案，在兩個(gè)原則下，我們可認(rèn)為雙鉆頭在滿足的約束條件下在兩塊獨(dú)立且重合的板上進(jìn)行獨(dú)立打孔作業(yè)。針對此問題，我們將平面問題轉(zhuǎn)化加入時(shí)間軸為空間問題，軸為坐標(biāo)軸，軸為時(shí)間軸，并提出了基于蟻群算法的蟻對群算法。</p><p><b>　　蟻對群算法：</b></p><p>　　在蟻群算法的基礎(chǔ)上，為解決雙打孔機(jī)的作業(yè)線路設(shè)計(jì)問題，我

46、們提出了蟻群對算法。具體步驟如下：</p><p>　　隨機(jī)產(chǎn)生對螞蟻，將該對中的螞蟻平均分別置于將行路線上；</p><p>　　對于螞蟻對的起始孔加入到禁忌表； </p><p>　　計(jì)算，其中為螞蟻到剩余點(diǎn)的概率，為螞蟻到剩余點(diǎn)的概率；</p><p>　　用賭輪方法選擇螞蟻各自在該次行進(jìn)中將要到達(dá)的孔；</p><

47、p>　　計(jì)算螞蟻第次行進(jìn)時(shí)間，螞蟻第次行進(jìn)時(shí)間，</p><p><b>　　(23)</b></p><p><b>　　(24)</b></p><p><b>　　(25)</b></p><p>　　其中為從螞蟻從到的等效行進(jìn)時(shí) 間，為的實(shí)際行進(jìn)時(shí)間，為兩個(gè)孔之間

48、是否要換刀的標(biāo)記變量，對于平行存在;</p><p>　　若，并且，則螞蟻移至孔處，返回步驟4）；若，，則螞蟻均不可移動(dòng)，直接返回4）；</p><p>　　對螞蟻均完成1次行進(jìn)，則根據(jù)修正信息素規(guī)則，修改信息素（見模型準(zhǔn)備5.4）；</p><p>　　當(dāng)循環(huán)次數(shù)時(shí)，結(jié)束。</p><p><b>　　具體流程圖如圖3：</

49、b></p><p>　　圖 3蟻對群算法流程圖</p><p>　　其中目標(biāo)點(diǎn)確定方法為蟻對群算法中的（3）（4）（5）（6）。</p><p><b>　　模型求解</b></p><p><b>　　最優(yōu)作業(yè)線路圖</b></p><p>　　在雙鉆頭按照，其中，

50、道具僅打型孔，對道具所打型孔，對兩鉆頭進(jìn)行近似平均分配。</p><p><b>　　點(diǎn)分布路線圖：</b></p><p><b>　　1~100點(diǎn)</b></p><p><b>　　101~200點(diǎn)</b></p><p><b>　　201~300點(diǎn)</

51、b></p><p><b>　　301~350點(diǎn)</b></p><p><b>　　351~480點(diǎn)</b></p><p><b>　　481~680點(diǎn)</b></p><p><b>　　681~800點(diǎn)</b></p><

52、;p><b>　　801~900點(diǎn)</b></p><p><b>　　901~1180點(diǎn)</b></p><p>　　1181~1300點(diǎn)</p><p>　　1301~1350點(diǎn)</p><p>　　1351~1410點(diǎn)</p><p><b>　　軸路線

53、圖</b></p><p><b>　　軸路線圖</b></p><p>　　行進(jìn)時(shí)間（單個(gè)空作業(yè)時(shí)間為）</p><p>　　鉆頭路徑中共1407個(gè)頂點(diǎn)，b點(diǎn)數(shù)為268 個(gè)，</p><p><b>　　，（含作業(yè)時(shí)間）</b></p><p>　　鉆頭路徑中共

54、1407個(gè)頂點(diǎn)，</p><p><b>　　，（含作業(yè)時(shí)間）</b></p><p>　　行進(jìn)總時(shí)間：，（含作業(yè)時(shí)間）</p><p><b>　　作業(yè)成本</b></p><p><b>　　模型評價(jià)</b></p><p>　　對模型一，考慮到所需

55、作業(yè)的孔的數(shù)據(jù)龐大，鄰近換刀條件、刀具轉(zhuǎn)換次序限制條件混合，問題復(fù)雜性較高。首先，我們通過優(yōu)化的最鄰近算法下，求出新分類的18種孔型下的所有孔的近似最短回路問題。其次，在已有的結(jié)果的基礎(chǔ)上，對問題進(jìn)行分析。同時(shí)，基于結(jié)果分析后提出的兩個(gè)原則，運(yùn)用二邊逐次修正算法、工序優(yōu)化算法，分別對同類孔之間行進(jìn)路徑、工序進(jìn)行優(yōu)化。該模型的建立中，我們對問題逐層求解，所提出的求解有向回路的算法——即在最鄰近算法的基礎(chǔ)上引入激活、狀態(tài)、關(guān)系矩陣，運(yùn)算量相

56、對圖論的經(jīng)典算法較小，應(yīng)用范圍廣。</p><p>　　在問題二的解答中延續(xù)了問題一的思想，兩處基礎(chǔ)算法都是基于問題一已實(shí)現(xiàn)的程序，即由最鄰近算法求解同型孔之內(nèi)的最優(yōu)路徑問題。故而在已有的基礎(chǔ)上減少了運(yùn)行時(shí)間，提高了效率。</p><p><b>　　靈敏度分析</b></p><p><b>　　單個(gè)孔的作業(yè)時(shí)間：</b>

57、;</p><p>　　考慮到單個(gè)孔的的作業(yè)時(shí)間若置為變量，使問題更加復(fù)雜。經(jīng)查閱資料，我們將打孔時(shí)間設(shè)為。實(shí)際，在問題二中，由于兩個(gè)打孔機(jī)獨(dú)立作業(yè)，由于有合作間距的限制，單個(gè)孔打孔時(shí)間，會(huì)對的作業(yè)情況有較大的影響。如，若在某時(shí)刻打孔，而按預(yù)定路程本應(yīng)向的孔行進(jìn)，但，故需等待作業(yè)完畢后進(jìn)行。則對雙打孔機(jī)作業(yè)的影響可能較大，下面我們將對的取值對整體結(jié)果的影響進(jìn)行具體討論。</p><p>　

58、　由于實(shí)際工程中條件約束，，分別故取將，代入問題的程序求解，則結(jié)果如表格3：</p><p>　　表格 3單孔作業(yè)時(shí)間對比表格</p><p>　　由表格3可知，當(dāng)分別取，，，說明取值不同時(shí)，差異不大?？倳r(shí)間包含了作業(yè)時(shí)間，故取值不同時(shí)，變化較大。故的取值對本問題影響不大，且問題二的模型有較好的彈性，可以滿足咋一定范圍內(nèi)的波動(dòng)。</p><p><b>　

59、　算法分析：</b></p><p>　　由于尋找回路問題為問題，并沒有成熟的算法解決該問題。為解決尋找有向路徑，我們將最鄰近算法進(jìn)行改進(jìn)，具體分析如下。</p><p><b>　　優(yōu)化的最鄰近算法：</b></p><p>　　由起始點(diǎn)進(jìn)行路徑的擴(kuò)充，基于最鄰近的思想，只添加最小的邊。同時(shí)我們引入的等效距離矩陣，的激活矩陣，關(guān)系

60、矩陣，狀態(tài)矩陣，其計(jì)算時(shí)間復(fù)雜度為，其中為總節(jié)點(diǎn)數(shù)。算法優(yōu)勢在于，在時(shí)間復(fù)雜度較低的情況下求解出近似的有向最優(yōu)回路。同時(shí)，沒有矩陣的迭代，則不會(huì)產(chǎn)生由迭代深度引起的空間復(fù)雜度過大的問題。</p><p><b>　　模型推廣</b></p><p><b>　　拓展一：遺傳算法</b></p><p>　　遺傳算法是模擬生

61、物在自然界中遺傳和進(jìn)化過程而形成的一種向適應(yīng)全局優(yōu)化概率搜索算法。遺傳算法在優(yōu)化孔群的加工路徑中，染色體一般為一個(gè)代加工孔的序列，所以染色體的長度與孔的數(shù)量相等。直接采用孔的標(biāo)號編碼在運(yùn)算中可能出現(xiàn)某些孔未加工的情況，因此可采用編碼方式如下：</p><p>　　每加工一個(gè)孔，就將其從未加工列表中刪除，則列表作為一個(gè)染色體表示代加工孔的序列。假設(shè)某個(gè)待加工孔的序列為，則按照上述方法編碼得到的染色體為（112141

62、311）。而對于雙鉆頭孔群加工路徑問題，每個(gè)孔的加工序列都是兩條加工路徑之間斷開后都可形成兩個(gè)子序列，根據(jù)鉆頭行走時(shí)間和鉆頭所需時(shí)間可算出對應(yīng)加工時(shí)間為和。比較不通斷電的值，值最小的兩個(gè)子序列就是這一染色體代表的雙鉆頭的群加工方案。</p><p>　　合作距離的判斷間距算法：</p><p>　　若在某時(shí)刻，若螞蟻分別在點(diǎn)處，若通過目標(biāo)點(diǎn)確定算法確定出分別將行至點(diǎn)。比較線段，之間的最短距

63、離與合作間距之間的大小，若滿足該條件則螞蟻分別可達(dá)，若否，則由目標(biāo)點(diǎn)確定算法重新確定。</p><p><b>　　參考文獻(xiàn)</b></p><p>　　姜啟源,謝金星,葉俊,《數(shù)學(xué)模型》,北京,高等教育出版社. 2004年4月.</p><p>　　胡運(yùn)權(quán),《運(yùn)籌學(xué)教程》, 北京：清華大學(xué)出版社，1998: 405 ~ 410.</p&

64、gt;<p>　　盧開澄, 盧華明,《組合數(shù)學(xué)》，第3 版, 北京：清華大學(xué)出版社，2002: 473 ~ 478.</p><p>　　《運(yùn)籌學(xué)》教材編寫組,《運(yùn)籌學(xué)》, 北京：清華大學(xué)出版社. 2005年6月.</p><p>　　張銀明，單向最優(yōu)通路的求解新方法及其算法設(shè)計(jì)，華僑大學(xué)學(xué)報(bào)(自然科學(xué)版)，2003，24(3).</p><p>　　

65、周培德, 一種快速求解貨郎擔(dān)問題的方法，計(jì)算機(jī)理論通信，1984(03).</p><p>　　潘金直、顧鐵成等編譯．現(xiàn)代計(jì)算機(jī)常用數(shù)據(jù)結(jié)構(gòu)與算法，南京大學(xué)出版社．1994.</p><p>　　曲晶，肖世德，熊鷹，基于蟻群算法的PCB孔加工路徑優(yōu)化，機(jī)電工程，2007（24）.</p><p>　　張毅華，鄭長江，丁金學(xué). 基于螞蟻尋徑原理的最優(yōu)路徑選擇算法，系統(tǒng)