網(wǎng)絡(luò)流算法的若干研究與分析.pdf

1、網(wǎng)絡(luò)流問題作為運(yùn)籌學(xué)的一部分，它主要研究的是網(wǎng)絡(luò)最優(yōu)化問題，在工程及科學(xué)等領(lǐng)域均有重要作用。其主要內(nèi)容包括最短路、最大流及最小費(fèi)用流等問題，隨著信息技術(shù)的發(fā)展人們建立了較為完善的理論，提出了一系列相應(yīng)的算法，取得了令人矚目的成績(jī)。本文的研究重點(diǎn)是基于石油運(yùn)輸網(wǎng)絡(luò)模型，對(duì)最大流算法和最小費(fèi)用流相關(guān)問題進(jìn)行分析、比較與改進(jìn)。本文首先介紹了 FordFulkerson標(biāo)記法、最短增廣鏈算法及預(yù)流推進(jìn)算法等求解網(wǎng)絡(luò)最大流的三種主流算法，通過具體

2、實(shí)例驗(yàn)證了上述算法的局限性。在分析以上算法自身特點(diǎn)的基礎(chǔ)上，吸收最大流算法的最新研究成果，提出兩種求最大流的新算法，并通過實(shí)例得以驗(yàn)證。其次，介紹了求最小費(fèi)用流的負(fù)回路算法、最小費(fèi)用路算法，以及預(yù)算固定最大流算法和最小費(fèi)用最大流算法。其中在介紹最小費(fèi)用流算法之前給出了一種求小規(guī)模網(wǎng)絡(luò)兩點(diǎn)之間最短路的簡(jiǎn)單易行的方法。最后，給出了本文所提出的石油運(yùn)輸網(wǎng)絡(luò)的最佳運(yùn)輸方案。本文所有的算法均給出了相應(yīng)的算例，雖然例子不能衡量一種算法的優(yōu)劣，但以幾