有預(yù)算限制多物資流問題的研究.pdf

1、網(wǎng)絡(luò)流問題在理論研究和實(shí)際應(yīng)用中都受到廣泛的關(guān)注，多物資流問題是網(wǎng)絡(luò)流問題中的一個重要研究領(lǐng)域．多物資流的迅速發(fā)展及其廣泛的應(yīng)用領(lǐng)域?qū)е略絹碓蕉嗟娜酥铝τ趯ζ溥M(jìn)行理論研究．多物資流問題大多都可以用線性規(guī)劃描述，雖然他們都可以得到最優(yōu)解，但在許多實(shí)際問題中，這些問題的規(guī)模相當(dāng)大，得到最優(yōu)解要花費(fèi)很長時間．目前的算法都是近似算法．如何既能減少算法的時間復(fù)雜性，又能使得近似解接近最優(yōu)解，是當(dāng)前多物資流問題的一個研究熱點(diǎn)．有預(yù)算限制的多物資流問

2、題是在多物資流問題基本問題的基礎(chǔ)上，添加費(fèi)用約束得到的．本文分別從兩方面對有預(yù)算限制的多物資流問題的兩個常見模型進(jìn)行了深入研究． 對于有預(yù)算限制的最大多物資流問題，給出了時間復(fù)雜性不依賴于物資數(shù)k的算法．由于求解有預(yù)算限制的多物資流問題的算法大都要以調(diào)用最短路為子程序，目前，求解最短路的最好的算法是改進(jìn)后的狄杰斯特拉算法，我們不能再對該算法進(jìn)行改進(jìn)使得其運(yùn)行時間更少，所以，我們試圖減少調(diào)用最短路的次數(shù)來減少有預(yù)算限制的多物資流問

3、題算法的時間復(fù)雜性．本文通過將發(fā)點(diǎn)相同的所有物資匯聚到共同的源點(diǎn)的方法來減少迭代的次數(shù)，從而減少調(diào)用最短路的次數(shù)，使得算法的時間復(fù)雜性減少．對此給出嚴(yán)格的理論證明． 對于有預(yù)算限制的最大并行流問題，本文詳細(xì)地描述了算法的執(zhí)行過程．該問題算法的時間復(fù)雜性已經(jīng)不依賴于物資數(shù)k，我們從使得算法求出的近似值更加接近最優(yōu)值的角度入手，對該算法的參數(shù)進(jìn)行調(diào)整，使得用調(diào)整參數(shù)后的算法求解得到的近似值較以前的算法得到的近似值能更加接近最優(yōu)值，同