零件裝配優(yōu)化問題

1、課程論文題 目：零件裝配優(yōu)化問題數(shù)據(jù)模型分析課程：機(jī)械優(yōu)化設(shè)計姓名：專業(yè)：機(jī)械設(shè)計制造及其自動化班 級：學(xué)號：指導(dǎo)教師：職稱: 20012年12月10日零件裝配優(yōu)化問題數(shù)學(xué)模型分析作者：導(dǎo)師：摘要 本文研究了圓盤上19個零件優(yōu)化排序的問題，針對頻率和質(zhì)量要求建立 了 0-1規(guī)劃模型，利用回溯法對模型進(jìn)行了求解，利用剪枝條件簡化了運(yùn)算，并 用遞歸調(diào)用將算法在編程上得以實(shí)現(xiàn)，在較短時間內(nèi)求得了可行解。本文建立的 算法及模型具有通用性，可以在零件數(shù)目增多的情況下推廣。本文還對實(shí)際情況 下某些不存在可行解的零件組進(jìn)行了分析，便于實(shí)際中更換零件的需要。關(guān)鍵字 0-1規(guī)劃，NP難題，回溯，剪枝，遞歸1問題

2、重述：在航空工業(yè)特別是飛機(jī)工業(yè)制造中，由于零件具有一定的固有頻率，相近頻率相 鄰會產(chǎn)生強(qiáng)烈的共振，不僅產(chǎn)生噪音，而且影響整個裝置的性能。因此要使零件 間的干擾對裝置正常工作影響較小，我們要合理安排零件的排序?，F(xiàn)有19個零件均勻裝配在一個圓盤周圍，每個零件具有一定的頻率和質(zhì)量，裝 配時要求滿足以下條件：1）相鄰零件應(yīng)具有頻率差，且為一大一小分布。2）相鄰兩零件頻率差應(yīng)不小于6Hz，允許在不相鄰的三處，相鄰零件頻率差不 小于4Hz。3）整個圓盤上的配重值不大于10g，配重值計算公式為：（360i/19 ） 2 + m sin（360i/19 ）iL i=1-具體要求如下: a：設(shè)計滿足上述要求的優(yōu)

3、化算法；并用所給的表中三組數(shù)據(jù)驗證；表見附錄1。b：如果數(shù)據(jù)可做局部調(diào)整（可換一個零件），分析對裝配效果的影響。2模型假設(shè)及說明：1）零件除重量和頻率不同外，其余參數(shù)均相同。2）零件在調(diào)整順序前能夠準(zhǔn)確知道其重量和頻率。3）所要排列的一組零件存在符合要求的排列。4）按頻率排序時，不考慮零件質(zhì)量及其他因素的影響。5）零件安裝前后參數(shù)不變。6）放在第一個位置上的零件比它相鄰的兩個零件頻率大。由于圓盤上零件分布 均勻，所以此假設(shè)對排序結(jié)果不造成影響。合理性解釋：為簡化問題，突出主要矛盾，我們做出上述假設(shè)，以方便討論。3符號說明：f第i個零件的頻率im.第i個零件的質(zhì)量j矩陣i行j列的元素p整個圓盤的

4、配重值（衡量優(yōu)化排序的一個標(biāo)準(zhǔn)）F圓盤第j個位置的零件的頻率Mj圓盤第j個位置的零件的質(zhì)量問題分析及模型建立：4.1問題分析：我們對題目提供的供驗證的三組數(shù)據(jù)進(jìn)行了分析，用于判斷零件重量和頻率之間的關(guān)系。應(yīng)用Matlab繪制了三組數(shù)據(jù)的質(zhì)量-頻率折線圖（圖1）。由圖，我們可以分 析出頻率與質(zhì)量近似 成線性關(guān)系。即大質(zhì)量 對應(yīng)大頻率，小質(zhì)量對 應(yīng)小頻率。每組的關(guān)系 點(diǎn)都大體集中在對角 區(qū)域。這種分布對我們 的算法設(shè)計提供了導(dǎo) 向作用。圖1三組數(shù)據(jù)的質(zhì)量-頻率折線圖在現(xiàn)有條件下，求全部可行解是不可能的，也是沒有實(shí)際意義的。初步來看，此問題是一個優(yōu)化問題中的一類特殊的線性規(guī)劃問題指派問 題，即一對一

5、的問題。此類問題是經(jīng)典的組合優(yōu)化問題，屬于NP難題，只有用 窮舉法才能找到在所定標(biāo)準(zhǔn)下的最優(yōu)解。在現(xiàn)有條件下，當(dāng)零件個數(shù)n=13時， 用窮舉法就不能求全部可行解。零件不同數(shù)目時在主頻為800MHz的微機(jī)上運(yùn)算所用時間時如圖2所示:零件數(shù)51011121314時間s1105100936049468000失效圖2時間表我們就根據(jù)對數(shù)據(jù)的分析建立一定的模型和算法，求出一部分可行解并經(jīng)過比較 找到比較合理的解。因此，我們用回溯法來尋找可行解。我們將條件一和二綜合考慮，建立0-1規(guī)劃模型用回溯法算法求可行解，合理的 剪枝因為可以減少一些時間上的消耗就顯得格外有意義，所以我們利用剪枝函數(shù) 去掉許多“枝葉”

6、，能夠大大縮短搜索時間。4.1模型建立：模型一：圓盤上零件的次序排好后，每個零件都應(yīng)占有一個確定的位置，即對于圓盤 上某一確定位置來說，任意一個零件是否在此位置是確定的。引入0-1整數(shù)變量建立規(guī)劃模型?！?”由于他在數(shù)學(xué)上的特性可以很好地代表 “無”或“否，而1可以很好地代表“有”或“是”。0-1變量一般可以表示為：1如果決箱為：是或有x = s.一 一i 0如果決策i為：否或無本問題可描述為：首先將19個零件從1到19標(biāo)號，設(shè)其頻率依次為f1 f2 f3 七，質(zhì)量為 m m m m再將圓盤上從某一個位置開始的19個位置從1到19標(biāo)號。設(shè)有一個19 x 19的矩陣，元素用Xj j表示。列數(shù)j表

7、示圓盤上位置的序號，行數(shù) i表示零件的序號。其元素規(guī)定為：1標(biāo)號為i的零件在圓盤第j個位置上x = 6 j = 1,2,.18 6 j = 19由于要求整個圓盤配重值不大于10g，則：p = J 藝 M cos (360i/19 ) 2 + 力 M sin (360i/19 ) 2 4 (j = 1,2,.,18 ) F1 -氣 | 4 (j = 19 )允許有三處相鄰零件的頻率差不小于4Hz，但其余各處相鄰零件間頻率差應(yīng)不小 于6Hz。則:-F +酉-氣 | 16 x 6 + 3 x 4 = 108為F +1j=1由于頻率差不小于4Hz的位置最多有三處，則:且：-F + F - F 10(J

8、 = 1,2,.,17 )j+1j +1jIf -f 1 + If -f | 10 (j = 18)1 1191918 1|F -F| + |F -F 10 (j = 18)21119MaxF - F 1 + |F -F I,11919181918If -Fl+If -f I.21119(j = 1,2,3,.,17 )F+2-fj+1質(zhì)量滿足的條件同模型一，即:fl M cos(360/19 )2 + M sin(360/19 ) 2 20時，進(jìn)行步驟6；若不滿足，則進(jìn)行步驟5。5）i=i-1，在數(shù)組f20中未填入數(shù)組x20中的元素（除去fj）的元素中繼 續(xù)搜索，進(jìn)行步驟3。6）對滿足頻率要

9、求的可行解，用配重值函數(shù)進(jìn)行篩選，若滿足配重值要求， 則輸出數(shù)組x20及元素原序號，并輸出配重值。通過對附錄1中的數(shù)據(jù)求解，我們對第二組和第三組數(shù)據(jù)求出了可行解。模型的推廣與評價：6.1模型的推廣：1）本文對19個零件進(jìn)行了排序，此題中用到的模型和算法還可推廣到更多 的零件排序的問題，在計算機(jī)運(yùn)算許可范圍內(nèi)，前述模型具有通用性。2）本問題我們利用0-1規(guī)劃建立了模型，并利用回溯法求得可行解。但我們的模型是在可行解存在的前提下提出的，實(shí)際情況下，某些零件組其 參數(shù)不存在可行解，因此需對某些參數(shù)進(jìn)行調(diào)整。我們利用所編程序排序時也遇 到這樣的情況。我們采用如下方法來解決這一問題，先弱化題設(shè)條件，排出

10、某些候選解，然 后觀察哪些元素不符合題設(shè)條件，根據(jù)具體情況予以調(diào)整。如我們對第一組數(shù)據(jù) 的處理。7總結(jié)：本文綜上所述的優(yōu)點(diǎn)是對模型進(jìn)行了合理的假設(shè)，抓住主要矛盾，忽略了次 要矛盾，利用0-1規(guī)劃建立了模型，在短時間內(nèi)得出了可行解。1）建立模型過程中，將條件合理地進(jìn)行了綜合和分類，為算法的進(jìn)行創(chuàng)造了 有利條件，對解進(jìn)行層層篩選，得出可行解。2）算法是關(guān)鍵所在，也是難點(diǎn)所在。對可行解搜索時，運(yùn)用了回溯法和剪枝 法，比窮舉法能大大縮短搜索時間。3）在編程過程中，我們利用遞歸調(diào)用實(shí)現(xiàn)了回溯算法，并利用所編程序?qū)Χ?組數(shù)據(jù)列出可行解，并在此基礎(chǔ)上進(jìn)行了比較分析，對更換一個零件某一參數(shù)值對排序的影響進(jìn)行了

11、研究。本模型缺點(diǎn)在于：1）不能求出最優(yōu)解，只能求出符合條件的可行解；2）隨著零件數(shù)的增加，計算時間逐漸讓人無法忍受。參考文獻(xiàn)何堅勇運(yùn)籌學(xué)基礎(chǔ) 清華大學(xué)出版社王譚浩強(qiáng) C程序設(shè)計（第二版） 清華大學(xué)出版社巖冰鄭明春劉弘回溯算法的形式模型計算機(jī)研究與發(fā)展第38卷第 19 期 TP301.6 TP18戴義平江才俊盧世明基于遺傳算法的葉片安裝排序優(yōu)化系統(tǒng)的開發(fā) 及應(yīng)用 汽輪機(jī)技術(shù)第45卷第5期 TK268.+3 TP301.6附錄附錄1序號頻率Hz質(zhì)量g序號頻率Hz質(zhì)量g序號頻率Hz質(zhì)量g111170196391963221086521003221139031128631086231065941003249810496275102505110595100486100366983269641799107982079625810667810874810555998269110499112