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

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

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

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

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

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