點和邊有容量約束的網絡最小費用最大流算法

摘要：分析了目前網絡最小費用最大流算法存在的問題，提出網絡最小費用最大流新算法。概括出條件約束下的網絡最小費用最大流問題的兩目標優化數學模型，針對點和邊有容量約束的網絡最小費用最大流問題特點，定義了有向路徑、有向路徑單位流費用和殘量網絡的概念。依據可行流分解定理，以鄰接矩陣為網絡數據存儲結構，使用數據結構中的遍歷方法，實現了網絡最小費用最大流新算法。該算法在不破壞平面性條件下，可以求解點和邊有容量約束的網絡最小費用最大流。最后，通過實例進行了算法測試和比較。算法測試表明：點和邊有容量約束的網絡最小費用最大流算法是完全可行和有效的。

關鍵詞：網絡最小費用最大流；鄰接矩陣；容量約束；殘量網絡

中圖分類號：TP301.6 文獻標志碼：A 文章編號：1001－3695(2010)08－3112－03