本期我們繼續(xù)進行運籌學之圖與網(wǎng)絡分析算法的講解，我們將對圖與網(wǎng)絡分析的基礎知識進行一個簡單的回顧，并介紹求解最大流問題和最小費用最大流的MATLAB和Python相關代碼，以幫助大家利用工具快速求解最大流問題和最小費用最大流問題，做到事半功倍。由于篇幅有限，小編接下來只展示部分代碼，小伙伴們可以關注“運籌說”公眾號→后臺回復“算法介紹之圖與網(wǎng)絡分析（二）”獲取完整代碼。話不多說，我們一起來看看吧！

一、基礎知識

1、最大流問題

★ 最大流有關概念

(1) 可行流：對任一G中的邊(vi, vj)有流量fij，稱集合f={fij}為網(wǎng)絡G上的一個流。且稱滿足容量限制條件和平衡條件的流f為可行流。

①容量限制條件：對G中每條邊(vi, vj)，有0≤fij≤cij；

②平衡條件：對中間點vi有∑j fij =∑k fki，即物資的輸入量與輸出量相等。

(2)總流量：對收、發(fā)點vt，vs，有∑i fsi =∑j fjt=W，W為網(wǎng)絡流的總流量。

(3)可增廣鏈：容量網(wǎng)絡G，若μ為網(wǎng)絡中從vs，vt的一條鏈，給μ定向為從vs到vt，μ上的邊凡與μ同向稱為前向邊，凡與μ反向稱為后向邊，其集合分別用μ+和μ-表示，f是一個可行流，如果滿足

則稱μ為從vs到vt的(關于f的)可增廣鏈。

(4) 可增廣鏈的意義:沿著這條鏈從發(fā)點到收點輸送的流，還有潛力可挖。

★ 最大流-最小割定理

(1) 割集：容量網(wǎng)絡G=(V，E，C)，vs，vt為發(fā)、收點，若有邊集E’為E的子集，將G分為兩個子圖G1，G2，其頂點集合分別記S，S’，S∪S’=V，S∩S’=?，vs，vt分屬S，S’，滿足：①G(V，E- E’)不連通；②E’’為E’的真子集，而G(V，E- E’’)仍連通，則稱E為G的割集，記E’=(S，S’)。

(2) 割集容量：割集(S，S’)中所有始點在S，終點在S’的邊的容量之和，稱為(S，S’)的割集容量,記為C(S，S’)。容量網(wǎng)絡G的割集有多個，其中割集容量最小者稱為網(wǎng)絡G的最小割集容量（簡稱最小割）。

(3) 最大流-最小割定理：任一個網(wǎng)絡G中，從vs到vt的最大流的流量等于分離vs、vt的最小割的容量。

(4) 最小割的意義：網(wǎng)絡從發(fā)點到收點的各通路中，由容量決定其通過能力，最小割則是這些路中的咽喉部分，其容量最小，它決定了整個網(wǎng)絡的最大通過能力。要提高整個網(wǎng)絡的運輸能力，必須首先改造這個咽喉部分的通過能力。

★ 問題描述

求網(wǎng)絡中一個可行流，使其流量達到最大，這種流稱為最大流，這個問題稱為（網(wǎng)絡）最大流問題。

★ 算法流程

2、最小費用流問題

★ 基本概念

(1) 鏈的費用：已知網(wǎng)絡G=(V,E,C,d),f是G上的一個可行流，μ為從vs到vt的(關于f的)可增廣鏈，則鏈μ的費用為

若μ*是從vs到vt所有可增廣鏈中費用最小的鏈，則稱μ*為最小費用可增廣鏈。

(2) 長度網(wǎng)絡：對網(wǎng)絡G=(V,E,C,d)，有可行流f，保持原網(wǎng)絡各點，每條邊用兩條方向相反的有向邊代替，各邊的權l(xiāng)ij按如下規(guī)則：

①當邊(vi, vj)∈E，令

這里＋∞的意義是：這條邊已飽和，不能再增大流量，否則要花費很高的代價，實際無法實現(xiàn)，因此權為＋∞的邊可從網(wǎng)絡中去掉。

②當邊(vj, vi)為原來G中邊(vi, vj)的反向邊，令

這里＋∞的意義是此邊流量已減少到0，不能再減少，權為＋∞的邊也可以去掉。

這樣得到的網(wǎng)絡L(f)稱為長度網(wǎng)絡（將費用看成長度）。

★ 問題描述

已知容量網(wǎng)絡G=(V,E,C),每條邊(vi, vj)除了已給出容量cij外，還給出了單位流量的費用dij(≥0)，記G=(V,E,C,d)。求G的一個可行流f={fij},使得流量W( f )=v,且總費用最小。

特別地，當要求f為最大流時，此問題即為最小費用最大流問題。

★ 算法流程

3、算法對比

二、算法實現(xiàn)

1、最大流問題

（1）例題介紹

給定指定的一個有向圖，v0為起點，v5為起點，每條邊有指定的容量，求滿足條件的從v0到v5的最大流。

（2）平臺實現(xiàn)

我們以上述例題為例，借助MATLAB和Python介紹實現(xiàn)求解最大流問題的相關代碼。

①MATLAB

★ 代碼展示

★ 代碼調(diào)用

代碼運行及最終結(jié)果展示如下，求得v0到v5的最大流為23，其中v0流向v1的流量為11，v0流向v2的流量為12，v2流向到v1的流量為1，v1流向到v3的流量為12，v2流向到v4的流量為11，v4流向v3的流量為7，v3流向v5的流量為19，v4流向v5的流量為4。

②Python

★ 代碼展示

★ 代碼調(diào)用

代碼運行及最終結(jié)果展示如下，求得v0到v5的最大流為23，其中v0流向v1的流量為11，v0流向v2的流量為12，v2流向到v1的流量為1，v1流向到v3的流量為12，v2流向到v4的流量為11，v4流向v3的流量為7，v3流向v5的流量為19，v4流向v5的流量為4。

（3）圖形結(jié)果展示

v0到v5的最大流為23，每條邊的流向及流量如圖所示。

2、最小費用流問題

（1）例題介紹

在如圖所示的運輸網(wǎng)絡上，求流量v為10的最小費用流，邊上括號內(nèi)為(cij, dij)。

（2）平臺實現(xiàn)

我們以上述例題為例，借助MATLAB和Python介紹實現(xiàn)求解最小費用流問題的相關代碼。

①MATLAB

★ 代碼展示

★ 代碼調(diào)用

代碼運行及最終結(jié)果展示如下，本例中MATLAB代碼以1代表起點vs，以5代表終點vt，求得流v為10的最小費用流為48，其中vs到v1的流量為4，vs到v2的流量為8，v2到v1的流量為5，v2到v3的流量為3，v1到v3的流量為0，v3到vt的流量為3，v1到vt的流量為7。

②Python

★ 代碼展示

★ 代碼調(diào)用

代碼運行及最終結(jié)果展示如下，本例中Python代碼以0代表起點vs，以4代表終點vt，求得流量v為10的最小費用流為48，其中vs到v1的流量為4，vs到v2的流量為8，v2到v1的流量為5，v2到v3的流量為3，v1到v3的流量為0，v3到vt的流量為3，v1到vt的流量為7。

（3）圖形結(jié)果展示

流量為10時vs到vt的最小費用流為48，每條邊的流向及流量如圖所示。

三、參考資料

【最大流問題Python實現(xiàn)】

https://blog.csdn.net/anlian523/article/details/81202622

【最小費用流問題Python實現(xiàn)】

https://zhuanlan.zhihu.com/p/103521228

本期的內(nèi)容就介紹到這里，想要進一步了解運籌學，關注本公眾號，快快學起來吧！

作者 | 尹萌娟 王連聚

責編 | 劉文志

審核 | 徐小峰