不確定條件下若干網(wǎng)絡優(yōu)化問題的模型與算法研究.pdf

1、網(wǎng)絡優(yōu)化問題是生產(chǎn)管理和科學研究中經(jīng)常遇到的問題，它屬于運籌學的一個重要分支，主要研究在一組約束條件下如何有效地設計、安排、管理和控制一個網(wǎng)絡系統(tǒng)，使這個網(wǎng)絡系統(tǒng)總的效益最大化。在經(jīng)濟管理、工業(yè)工程、交通運輸、通訊網(wǎng)絡等諸多領域，網(wǎng)絡優(yōu)化都有廣泛的應用。隨著計算機科學應用和發(fā)展，運籌學與計算機科學相互滲透，推動著網(wǎng)絡優(yōu)化問題的應用范圍不斷擴大和深入。研究網(wǎng)絡優(yōu)化問題，如網(wǎng)絡的最短路問題、最小費用支撐樹問題、最小費用流問題及Steiner

2、 樹問題等的算法設計與分析，己成為多個學科的一個重要研究方向。特別是隨著Internet 各種應用的發(fā)展，電子商務的日益普及，涉及到網(wǎng)絡優(yōu)化設計諸如網(wǎng)絡基礎設施建設、網(wǎng)絡可靠性設計和智能路由設計等問題的研究需求更加迫切。網(wǎng)絡優(yōu)化的關鍵問題是研究面向網(wǎng)絡的組合優(yōu)化問題的求解技術，這方面己成為計算機科學技術領域的一個極為活躍的研究方向。
　　 在實際生活中，由于客觀或主觀的原因，我們所研究的問題存在著各種各樣的不確定性，因而在解決實

3、際問題時，我們必須對這些不確定因素給予考慮。由于不確定性的出現(xiàn)，對原有的網(wǎng)絡優(yōu)化模型提出了挑戰(zhàn)，也為優(yōu)化理論的進一步發(fā)展提供了新的機遇。本文主要就不確定條件下若干網(wǎng)絡優(yōu)化問題進行研究，提出了進一步的不確定性問題的模型，并給出了求解新模型的智能算法和拉格朗日松弛算法。
　　 其主要工作如下：
　　 利用隨機理論研究了有約束的隨機最短路問題，根據(jù)不同的決策準則，建立了三種不同的隨機優(yōu)化模型，提出了求解模型的退火遺傳算法。通過

4、算例驗證了算法的合理性和有效性利用可信性理論和模糊環(huán)境下機會約束規(guī)劃及其相關機會規(guī)劃建模的思想，在模糊環(huán)境下建立了模糊度約束生成樹問題的數(shù)學模型，并討論了特殊情況下的等價問題。同時利用Prüfer數(shù)對生成樹進行編碼，設計了一個求解模糊度約束最小生成樹問題的遺傳算法，并將算法應用于TSP 問題求解。
　　 研究了含隨機變量的固定費用的運輸問題，對運輸問題數(shù)學模型進行了描述，通過Steiner 樹問題的轉(zhuǎn)換證明了該問題是NP 難問題

5、。根據(jù)概率論知識，將不確定性問題轉(zhuǎn)化成確定性的等價模型。利用運輸圖是一個生成樹的特性，設計了基于生成樹的遺傳算法。
　　 研究了網(wǎng)絡優(yōu)化設計問題，提出了利用神經(jīng)網(wǎng)絡評估網(wǎng)絡可靠性的方法，并給出了使用隨機模擬技術產(chǎn)生訓練樣本的過程。在分析了粒子群算法的特性之后，設計了一個二進制粒子群算法求解本文的離散優(yōu)化問題。仿真結果表明，該粒子群方法具有性能穩(wěn)定和收斂速度快的特點，能較好地得到網(wǎng)絡優(yōu)化設計問題中的最優(yōu)解。針對需求和供給不確定的物