點(diǎn)和邊有容量約束的網(wǎng)絡(luò)最小費(fèi)用最大流算法
2010-12-31 00:00:00厙向陽(yáng)
計(jì)算機(jī)應(yīng)用研究 2010年8期
摘要：分析了目前網(wǎng)絡(luò)最小費(fèi)用最大流算法存在的問題，提出網(wǎng)絡(luò)最小費(fèi)用最大流新算法。概括出條件約束下的網(wǎng)絡(luò)最小費(fèi)用最大流問題的兩目標(biāo)優(yōu)化數(shù)學(xué)模型，針對(duì)點(diǎn)和邊有容量約束的網(wǎng)絡(luò)最小費(fèi)用最大流問題特點(diǎn)，定義了有向路徑、有向路徑單位流費(fèi)用和殘量網(wǎng)絡(luò)的概念。依據(jù)可行流分解定理，以鄰接矩陣為網(wǎng)絡(luò)數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)，使用數(shù)據(jù)結(jié)構(gòu)中的遍歷方法，實(shí)現(xiàn)了網(wǎng)絡(luò)最小費(fèi)用最大流新算法。該算法在不破壞平面性條件下，可以求解點(diǎn)和邊有容量約束的網(wǎng)絡(luò)最小費(fèi)用最大流。最后，通過實(shí)例進(jìn)行了算法測(cè)試和比較。算法測(cè)試表明：點(diǎn)和邊有容量約束的網(wǎng)絡(luò)最小費(fèi)用最大流算法是完全可行和有效的。
關(guān)鍵詞：網(wǎng)絡(luò)最小費(fèi)用最大流；鄰接矩陣；容量約束；殘量網(wǎng)絡(luò)
中圖分類號(hào)：TP301.6 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1001－3695(2010)08－3112－03
