數(shù)學(xué)建模優(yōu)秀論文_第1頁(yè)
已閱讀1頁(yè),還剩20頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

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

2、2)打孔機(jī)加工作業(yè)時(shí),鉆頭的行進(jìn)時(shí)間;(3)針對(duì)不同孔型加工作業(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)過(guò)程中可同時(shí)轉(zhuǎn)換刀具,但相應(yīng)費(fèi)用不減。</p><p>  不同的刀具加工不同的孔型,有的只需一種刀具來(lái)完成,有的需要多種刀具及規(guī)定的加工次序來(lái)完成。表1為10種孔型所需加工刀具及加工次序(*表示該孔型不限制加工次序)。</p><p>  表1:10種孔型所需加工刀具及加工次序</p><p&

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

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

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

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

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

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

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

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

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

13、個(gè)節(jié)點(diǎn)依次且僅一次的路徑稱(chēng)為路徑。穿程于的每個(gè)節(jié)點(diǎn)依次且僅一次的回路稱(chēng)為回路。</p><p>  TSP(旅行商問(wèn)題)</p><p>  有n個(gè)城市,其相互間距離,為已知,求合理的路線(xiàn)使得每個(gè)城市都被經(jīng)過(guò)一次,且總路徑為最短。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)過(guò)該路徑;式(5)(6)要求旅行商經(jīng)過(guò)點(diǎn)有

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

16、問(wèn)題。</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ā)式因子,表示軌跡的相對(duì)重要性;一期望啟發(fā)式因子,表示能見(jiàn)度的相對(duì)重要性;——啟發(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)中所走過(guò)的路徑的長(zhǎng)度。</p><p>  禁忌表的修改和表螞蟻數(shù)后有一個(gè)表和表。初始時(shí)可以把中的元素都設(shè)為0,把的元素都設(shè)為l。如果螞蟻第1次選擇了城市,則把tabu表中第1元素賦值為,并把表總第個(gè)元素賦值為0,表示此城市已經(jīng)走過(guò)。</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>  對(duì)第只螞蟻,根據(jù)公式(1)選擇城市,并前進(jìn);&

21、lt;/p><p>  把選擇的城市加入到第屜只螞蟻的表中,并修改表;</p><p>  對(duì)于第只螞蟻若沒(méi)有游歷完所有個(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步,若滿(mǎn)足結(jié)束條件則結(jié)束循環(huán),并輸出計(jì)算結(jié)果。</p><p><b>  數(shù)據(jù)處理</b></p><p>  將10種孔型按所需刀具重新編號(hào),其中分別代表8種刀具、10種孔型中某一種,故得18類(lèi)孔(共2814個(gè))如下表。</p>

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

24、<p>  由公式,將題目中縮短行進(jìn)、換刀時(shí)間問(wèn)題,轉(zhuǎn)化為求解最短距離問(wèn)題。</p><p>  首先,將5.3數(shù)據(jù)處理中所得到的2814個(gè)點(diǎn),,記作賦權(quán)圖中點(diǎn)集,其中。</p><p>  針對(duì)上步中的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(旅行商問(wèn)題)的最短路程模型:</p><p><b>  最短等效路徑:</b></p><p><b>  刀具行進(jìn)路徑:</b></p>

27、<p>  從先前位置移動(dòng)到當(dāng)前位置的成本。設(shè)兩個(gè)位置之間的實(shí)際距離為單位長(zhǎng)度的刀具行進(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)間的等效換刀路徑 (處理方法,見(jià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>  在換刀、路線(xiàn)分立優(yōu)化原則,鄰近換刀原則下,我們將用語(yǔ)言編寫(xiě)工序優(yōu)化算法實(shí)現(xiàn)總體工序優(yōu)化,通過(guò)優(yōu)化的最鄰近算法求得初始回路,而后用二邊逐次修正算法

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

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

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>  對(duì)于已有18類(lèi)孔,必然有,其中表

33、示步驟總數(shù),18步之內(nèi)總能打完所有的點(diǎn)。故對(duì)工序進(jìn)行優(yōu)化時(shí),我們引入步驟矩陣,激活矩陣,狀態(tài)矩陣,以總次數(shù)最小為目標(biāo),</p><p><b>  (19) </b></p><p>  其中,為要打第類(lèi)孔時(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類(lèi)新型孔的刀具分布情況,步驟矩陣,由某確定起始孔型開(kāi)始,,若,則向左尋找最近的的孔型,并將對(duì)應(yīng)的關(guān)系矩陣尋找下線(xiàn)孔型,并使,。</p><

35、p>  根據(jù),的值,重復(fù)對(duì)的操作。并判斷是否,。 若滿(mǎn)足則結(jié)束,若不滿(mǎn)足則重復(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)),對(duì)應(yīng)將,,若,則由值查找下線(xiàn)點(diǎn),跳轉(zhuǎn)至步驟3;若,則繼續(xù)對(duì)點(diǎn)重復(fù)對(duì)的操作,直至轉(zhuǎn)至步驟3。</p><p>  由第二步所確定的點(diǎn)對(duì)于除外的所有點(diǎn)滿(mǎn)足相應(yīng)的點(diǎn),并在等效距離矩陣中的第行中,對(duì)于滿(mǎn)足要求的

37、點(diǎn)對(duì)應(yīng)的值尋找最小值,并對(duì)點(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>  對(duì)所得圈,對(duì)所有適合的,判斷對(duì)某一對(duì)和,是否有</p><p><b>  (20)</b></p><p>  若有,刪去邊和,添加邊和得;</p><p>  重復(fù)1)2)兩步,直至不可再用此方法繼續(xù)進(jìn)行,則求得一個(gè)較優(yōu)的圈</p><p>  為了得到更

39、高的精度,該程序可以重復(fù)幾次,每次都以不同的圈開(kāi)始。</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>  工序流程表及對(duì)應(yīng)路徑長(zhǎng)度:</p><p><b>  工序流程為:</b></p><p>  該

42、流程實(shí)際為刀具轉(zhuǎn)換的流程,也即工序圖,其中表示某一種刀具,表示換刀。該流程為,由刀具開(kāi)始,將所有用到刀具的孔全部打完后,刀具換轉(zhuǎn),將即需刀具的型所有孔打完,再轉(zhuǎn)換。同理,以該流程打完所有孔。</p><p>  工序流程表及對(duì)應(yīng)長(zhǎ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)的下界與其比較。利用最小生成樹(shù)可以得到最佳圈的一個(gè)

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

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

46、們提出了蟻群對(duì)算法。具體步驟如下:</p><p>  隨機(jī)產(chǎn)生對(duì)螞蟻,將該對(duì)中的螞蟻平均分別置于將行路線(xiàn)上;</p><p>  對(duì)于螞蟻對(duì)的起始孔加入到禁忌表; </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)記變量,對(duì)于平行存在;</p><p>  若,并且,則螞蟻移至孔處,返回步驟4);若,,則螞蟻均不可移動(dòng),直接返回4);</p><p>  對(duì)螞蟻均完成1次行進(jìn),則根據(jù)修正信息素規(guī)則,修改信息素(見(jiàn)模型準(zhǔn)備5.4);</p><p>  當(dāng)循環(huán)次數(shù)時(shí),結(jié)束。</p><p><b>  具體流程圖如圖3:</

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

50、道具僅打型孔,對(duì)道具所打型孔,對(duì)兩鉆頭進(jìn)行近似平均分配。</p><p><b>  點(diǎn)分布路線(xià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>  軸路線(xiàn)

53、圖</b></p><p><b>  軸路線(xiàn)圖</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>  模型評(píng)價(jià)</b></p><p>  對(duì)模型一,考慮到所需

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

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

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

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

59、 算法分析:</b></p><p>  由于尋找回路問(wèn)題為問(wèn)題,并沒(méi)有成熟的算法解決該問(wèn)題。為解決尋找有向路徑,我們將最鄰近算法進(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ì)在于,在時(shí)間復(fù)雜度較低的情況下求解出近似的有向最優(yōu)回路。同時(shí),沒(méi)有矩陣的迭代,則不會(huì)產(chǎn)生由迭代深度引起的空間復(fù)雜度過(guò)大的問(wèn)題。</p><p><b>  模型推廣</b></p><p><b>  拓展一:遺傳算法</b></p><p>  遺傳算法是模擬生

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

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

63、離與合作間距之間的大小,若滿(mǎn)足該條件則螞蟻分別可達(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>  盧開(kāi)澄, 盧華明,《組合數(shù)學(xué)》,第3 版, 北京:清華大學(xué)出版社,2002: 473 ~ 478.</p><p>  《運(yùn)籌學(xué)》教材編寫(xiě)組,《運(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)問(wè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>  張毅華,鄭長(zhǎng)江,丁金學(xué). 基于螞蟻尋徑原理的最優(yōu)路徑選擇算法,系統(tǒng)

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 眾賞文庫(kù)僅提供信息存儲(chǔ)空間,僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論