前面我們學習了圖與網(wǎng)絡(luò)分析的基礎(chǔ)知識及經(jīng)典問題，大家是否已經(jīng)學會了呢？接下來小編和大家學習最后一個經(jīng)典問題——最小費用最大流問題。

最小費用最大流問題是經(jīng)濟學和管理學中的一類典型問題。在一個網(wǎng)絡(luò)中每段路徑都有“容量”和“費用”兩個限制的條件下，此類問題的研究試圖尋找出：流量從A到B，如何選擇路徑、分配經(jīng)過路徑的流量，可以達到所用的費用最小的要求。

如n輛卡車要運送物品，從A地到B地。由于每條路段都有不同的路費要繳納，每條路能容納的車的數(shù)量有限制，最小費用最大流問題指如何分配卡車的出發(fā)路徑可以達到費用最低，物品又能全部送到。

下面，讓我們從實際問題出發(fā)，學習如何解決最小費用最大流問題吧！

一、問題描述及求解原理

01 問題描述

網(wǎng)絡(luò)G=(V,E,C)，每一弧(vi,vj)∈E，給出(vi,vj)上單位流的費用d(vi,vj)≥0（簡記dij），記G=(V,E,C,d)。

最小費用最大流問題：

求一個最大流f，使流的總費用取最小值。

02 求解原理

設(shè)對可行流f存在增廣鏈??，當沿??以θ=1調(diào)整f，得新的可行流f'時，顯然V(f')=V(f)+1，兩流的費用之差d(f)-d(fx27;)：

稱為增廣鏈??的費用。

原理依據(jù)：

若f是流值為V(f)的所有可行流中費用最小者，而??是關(guān)于f的所有增廣鏈中費用最小的增廣鏈，則沿??以θ去調(diào)整f，得可行流f'，f'就是流量為V(f)+θ的所有可行流中費用最小的可行流。這樣，當f'是最大流時，f'就是所求的最小費用最大流。

如果已知f是流量為V(f)的最小費用流→求出關(guān)于f的最小費用增廣鏈。

在構(gòu)造最小費用增廣鏈時，會將網(wǎng)絡(luò)中的每一條條弧(vi,vj)都變成一對方向相反的弧，以形成四通八達的“路”，因此對于有向邊(vi,vj)權(quán)wij按如下方法取值：

取值說明如下圖所示：

構(gòu)造賦權(quán)有向圖W(f)，它的頂點是G的頂點，W(f)中弧及其權(quán)wij按弧(vi,vj)在G中的情形分為：

新網(wǎng)絡(luò)W(f)成為流f的（費用）長度網(wǎng)絡(luò)。

由增廣鏈費用的概念及網(wǎng)絡(luò)W(f)的定義，知在網(wǎng)絡(luò)G中尋求關(guān)于可行流f的最小費用增廣鏈，等價于在網(wǎng)絡(luò)W(f)中尋求從vs到vt的最短路。

03 算法步驟

（1）根據(jù)網(wǎng)絡(luò)中的費用首先確定費用最小的長度網(wǎng)絡(luò)，將該長度網(wǎng)絡(luò)確定為初始可行流f0=0，令k=0；

（2）應用流量網(wǎng)絡(luò)對增廣鏈進行調(diào)整，記經(jīng)k次調(diào)整得到的最小費用流為fk，構(gòu)造增量網(wǎng)絡(luò)W(fk)；

（3）在W(fk)中，尋找vs到vt的最短路。若不存在最短路（即最短路路長是∞），則fk就是最小費用最大流；若存在最短路，則此最短路即為原網(wǎng)絡(luò)G中相應的可增廣鏈??，轉(zhuǎn)入第4步。

（4）在增廣鏈??上fk按下式進行調(diào)整，調(diào)整量θ為：

得新的可行流fk+1，返回第2步

二、實例應用

01 例題求解

例1：求下圖所示網(wǎng)絡(luò)的最小費用最大流?；∨詳?shù)字為(dij,cij)。

解：

（1）取初始可行流；

（2）按算法要求構(gòu)造長度網(wǎng)絡(luò) ；

（3）在原網(wǎng)絡(luò)G中，與這條最短路對應的增廣鏈為 ；

（4）在原網(wǎng)絡(luò)D中，與這條最短路對應的增廣鏈為 ：

按照上述算法依次得 ，流量依次為 ，構(gòu)造相應的增量網(wǎng)絡(luò)為 ，如圖(a)，(e)，(g)，(i)所示。

圖（i）中，不存在從 到 的最短路，所以 為最小費用最大流。

02 拓展延伸

最小費用最大流問題還可以使用線性規(guī)劃方法進行求解，思路如下：

（1）通過運籌說第78期相關(guān)介紹可以求出最大流量。

（2）在保證總流量等于最大流量的條件下，以最小化總費用為目標求出每條弧上的流量。

例2：某公司有一個管道網(wǎng)絡(luò)如下圖所示，使用這個網(wǎng)絡(luò)可以將石油從產(chǎn)地v1送到銷地v7，給出了每一段管道的容量cij（單位為：萬加侖/小時），此外還給出了每段弧上的單位流量的費用dij（單位為：百元/萬加侖），(cij,dij)在圖的弧上已標出，如果使用這個網(wǎng)絡(luò)從產(chǎn)地v1向銷地v7運送石油，問怎樣運送才能運送最多的石油且使總運費最?。?/p>

通過標號算法可以求出最大流量為10。然后，在保證總流量等于10的條件下，以最小化總費用為目標求出每條弧上的流量，如下所示：

后續(xù)步驟使用線性規(guī)劃求解方法如單純形法求解即可。

以上就是最小費用最大流問題的全部內(nèi)容了，通過本節(jié)學習大家是否對該問題有了一個初步的認識呢，是否可以求解最小費用最大流問題呢？下一次小編將帶大家學習第九章——網(wǎng)絡(luò)計劃，敬請關(guān)注！

作者 | 張宇 齊鵬

責編 | 劉文志

審核 | 徐小峰文章來源地址http://www.zghlxwxcb.cn/news/detail-792363.html

到了這里，關(guān)于運籌說 第80期 | 最小費用最大流問題的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！