全局最短路徑規(guī)劃的非線性優(yōu)化方法研究.pdf

1、分類號(hào)密級(jí)UDC編號(hào)碩士學(xué)位論文全局最短路徑規(guī)劃的非線性優(yōu)化方法研究全局最短路徑規(guī)劃的非線性優(yōu)化方法研究學(xué)位申請(qǐng)人：人：徐麗麗指導(dǎo)教師：師：楊宗霄教授學(xué)科專業(yè)：業(yè)：應(yīng)用數(shù)學(xué)學(xué)位類別：別：理學(xué)2012年4月摘要I論文題目：論文題目：全局最短路徑規(guī)劃的非線性優(yōu)化方法研究全局最短路徑規(guī)劃的非線性優(yōu)化方法研究專業(yè)：業(yè)：應(yīng)用數(shù)學(xué)應(yīng)用數(shù)學(xué)研究生：生：徐麗麗徐麗麗指導(dǎo)教師：指導(dǎo)教師：楊宗霄楊宗霄教授教授摘要系統(tǒng)全局最短路徑規(guī)劃作為非線性組合優(yōu)化中的一

2、個(gè)經(jīng)典問(wèn)題，在現(xiàn)實(shí)生活中有著廣泛的應(yīng)用，最小Steiner樹(shù)問(wèn)題是全局最短路徑研究的理論基礎(chǔ)。因此研究最小Steiner樹(shù)的全局優(yōu)化算法具有重要的理論意義和廣泛的應(yīng)用價(jià)值。由于最小Steiner樹(shù)問(wèn)題已被證明是NPhard問(wèn)題，除非P=NP，否則Steiner樹(shù)問(wèn)題不存在多項(xiàng)式時(shí)間算法，因此尋找合適的智能優(yōu)化方法是求解此問(wèn)題的有效途徑。本文在最小Steiner樹(shù)的理論基礎(chǔ)上結(jié)合可視化實(shí)驗(yàn)探討系統(tǒng)全局最短路徑的求解方法。以物理可視化實(shí)驗(yàn)為

3、依托，采用實(shí)驗(yàn)→算法→實(shí)驗(yàn)→工程應(yīng)用的技術(shù)研究路線，對(duì)可視化實(shí)驗(yàn)結(jié)果進(jìn)行分析，探索了可以構(gòu)造出滿最小Steiner樹(shù)的簡(jiǎn)單系統(tǒng)的固定點(diǎn)集特征，結(jié)合Melzak的幾何構(gòu)圖原理設(shè)計(jì)長(zhǎng)邊消去法構(gòu)造出簡(jiǎn)單系統(tǒng)——F凸路上點(diǎn)集的最短路徑即滿最小Steiner樹(shù)。由于復(fù)雜系統(tǒng)的滿最小Steiner樹(shù)不一定是最短路徑，本文設(shè)計(jì)分塊消邊算法在固定點(diǎn)的最小生成樹(shù)上分解出包含長(zhǎng)度較長(zhǎng)的邊的若干個(gè)F凸路，按照長(zhǎng)邊消去法構(gòu)造個(gè)各個(gè)F凸路上固定點(diǎn)的滿最小Stei

4、ner樹(shù)并刪除原有F凸路，從而構(gòu)造出系統(tǒng)的全局最短路徑。最小生成樹(shù)在其它算法中常被作為最優(yōu)解來(lái)檢驗(yàn)算法結(jié)果，而分塊消邊算法則是對(duì)固定點(diǎn)的最小生成樹(shù)進(jìn)行優(yōu)化，以求得到比其更短的線路長(zhǎng)度，所以優(yōu)化效果是非常有效的，本文得到的結(jié)果與可視化實(shí)驗(yàn)結(jié)果近似比例最高達(dá)99.84％。本文通過(guò)簡(jiǎn)單的圖形實(shí)例驗(yàn)證了算法的可行性，并通過(guò)具體如實(shí)例河南省主要城市高速公路設(shè)計(jì)、最優(yōu)通訊網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題和海陽(yáng)市電網(wǎng)設(shè)計(jì)，將利用分塊消邊算法得到的數(shù)據(jù)與最小生成樹(shù)進(jìn)行對(duì)比