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

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

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