定流值比例的最小雙費用流算法研究

趙禮峰，劉艷清

(南京郵電大學 理學院，江蘇 南京 210003)

定流值比例的最小雙費用流算法研究

趙禮峰，劉艷清

(南京郵電大學 理學院，江蘇 南京 210003)

現有最小雙費用流算法只能求解網絡的最大雙流問題，并不能得到定流值比例。為此，提出了一種定流值比例的最小雙費用流新算法，在求解最小雙流和最小費用的基礎上，在調整雙流值保證定流值比例的同時得到最小費用流。所提出的新算法定義了余網絡和費用差，以鄰接矩陣為網絡數據存儲結構，使用Ford算法分別得到兩費用的最短增廣鏈，選擇費用最小的增廣鏈增廣并求出其對應的費用差，從費用差最小的開始調整流值就得到定流值比例下的最小費用。應用該新算法構建定流值比例的最小雙費用流算法的運輸網絡模型，就可以獲得最優運輸方案。邏輯推理和仿真實驗結果均表明，所提出的算法可行、有效，能較好地解決稀疏網絡以及復雜網絡中定流值比例的最小雙費用流問題。

最小雙費用流算法；余網絡；鄰接矩陣；Ford算法；費用差

0 引 言

最小雙費用流問題是網絡優化中的一個核心問題，許多網絡優化問題都可歸結為最小雙費用流問題的特例，如最短路[1-2]、最大流[3-5]以及最小費用最大流[6-8]問題，這些網絡優化問題都可歸為單可行流算法研究。隨著物流運輸的發展，這些單可行流算法研究已經滿足不了運輸行業不斷發展的需要。由此，謝政和湯澤瀅根據一個實例建立了在容量—費用雙流網絡中求最小費用最大雙流的模型[9]，提出了最小費用最大雙流和雙流增量網絡的充要條件，該算法證明了最小費用最大雙流算法的正確性。……