最大流及最小費用的算法研究.pdf

1、關(guān)于“流”的問題常大量存在于現(xiàn)實生活中，在較為完善的理論基礎(chǔ)上，以及計算機技術(shù)和網(wǎng)絡(luò)技術(shù)的迅速發(fā)展，使得網(wǎng)絡(luò)最大流問題在通信、物理、電力等科學(xué)領(lǐng)域都得到了廣泛的應(yīng)用。網(wǎng)絡(luò)流作為現(xiàn)代通信的基礎(chǔ)框架，主要包括最短路、最小費用最大流、最大流等問題。
　　本文主要研究最小費用最大流算法和最大流算法在實際運輸網(wǎng)絡(luò)中(如天然氣運輸管道)的應(yīng)用，以及對其算法的分析與改進。
　　第一部分主要闡述了最大流以及最小費用的發(fā)展以及國內(nèi)外的研究現(xiàn)狀

2、和研究背景意義。
　　第二部分首先介紹了最大流以及最小費用的基本概念以及相關(guān)定理，介紹了Ford-Fulkerson標(biāo)號算法和最短增廣鏈算法以及預(yù)流推進算法的求解方法，以及對其復(fù)雜度進行分析，再通過實例進一步詳細了解了上述算法。最后簡單介紹了求解最小費用的方法和其復(fù)雜度，其中包括求解最小費用流的負回路算法和最小費用路算法，以及最小費用最大流算法和預(yù)算固定最大流算法。
　　第三部分在現(xiàn)有最大流算法的基礎(chǔ)上，提出了一種新的求解最