編者按：本文整理自休語的知乎文章，文章主要圍繞最小流問題進行闡述，結構主要為問題描述，模型建立，解的性質，特殊案例及網絡單純形法的求解。
問題描述
（1）網絡：有向且連通。
（2）邊：根據邊上的流量，我們可以分為
- 最大流問題：容量限制
- 最短路徑問題：費用作為邊的權重
（3）節點：至少有一個（可以有多個）節點是供應點（supply node）或者需求點（demand node）
（4）其他：
- 弧的容量充分，支持供應點到需求點的所有流
- 每條弧上的費用與流量成正比。
（5）目標：給定需求，通過網絡發送的總成本最小。
輸入整個網絡的流量是不變的，但是中間節點可以看成是處理設施，處理的費用累加在邊的運輸費用上。
模型建立
解的性質
因為cost
不在約束裡面，所以所有BF解都是整數解只要求約束中出現的兩類量為整數，即
和
為整數。
特殊案例
以下四個問題是特殊的最小費用流問題
- 運輸問題：沒有中間節點，邊的流量沒有上界約束。
- 指派問題：每個節點的 為+1或-1
- 轉運問題（Transshipment Problem）：沒有上界約束
- 最短路徑問題：
- 除了起點（source）出發和匯入目的地（target）的邊，其它邊變成雙向邊
- 距離是cost ，沒有容量（capacity）限制
- 最大流問題
- 不考慮費用，
- 選一個網絡最大流量的上界 ，設Supply node為 ，demand node為
- 從supply node到demand node畫一條“分流線”，分走多出來的流量 。“分流線”的 ，容量無窮大。
具體案例
前面我們已經對最小流費用問題做了簡單的敘述，對於這類問題到底如何解，下面我們對一種經典解法進行描述，即網絡單純性法。
基礎：上界法（Upper Bound Technique）
在運籌學建模中，我們經常有約束
。通常地，把該約束當做非負約束（nonnegative constraints）處理，會比當成函數式約束（functional constraints）處理節省計算量。我們可以做如下替換：
經過上述處理後，單純形法中出基條件則變為了超出上界或者下界。當入基變量不斷增大以至於某個
達到上界
時，用
替換。
那麼上界法和最小費用流問題有什麼聯繫呢？最小費用流問題中的約束通常分有兩種：節點約束和邊約束。節點約束是函數式約束，通常可以表示為
，邊約束表示為
。我們可以用上界法對約束進行轉換，提高計算效率。
網絡單純形法——上界法轉換
網絡單純形狀法和上界法的思路類似。對於
這樣的增補決策變量（complementary decision variables）有一個很好的解釋，如下圖所示。
如下公式所示，
和
的變化其實就是上界法中把
代入到
，導致等式右側
的變化。
最終網絡流如下圖所示：
是從i到j能夠減少的流量，
是表示每減少單位流量，就能節省
的成本，
的上界
，是因為最多隻能減少10（
流量分配了10）。
如上所述，只適用於有上界約束的情況，對於邊上的流量沒有上界約束的情況來說沒有必要。
網絡單純形法——求解
對一個網絡圖來說，找到一個生成樹就是找到了一組基解。
將非基變量置為0，可以解出每條弧上的流量，滿足
和
的生成樹就是可行生成樹，對應基可行解。
網絡單純形法計算示例：
入基變量的選擇
那麼在求解中，哪個非基變量從0開始增加，會使得目標函數Z增加得最快？且在網絡單純形法中，每增加一個非基變量（一個arc），會形成一個環。環中同向arc增大，反向arc減小。如下圖所示：
對這個變化，求一個整體的變化量
。對於每個可以加入的arc，找到這樣的一個環，假設入基arc增加的流量為
，看整體的
是多少。其中能夠增加單位流量，
下降最大的非基變量（arc）是我們需要選擇的。
迭代選擇出基變量和下一個可行解。注意，根據上界法，當某一條arc達到上界時，通過
代換得到反向arc，這樣
，正常出基。
原文鏈接
https://zhuanlan.zhihu.com/p/73401547
https://zhuanlan.zhihu.com/p/73527137
閱讀更多 運籌OR帷幄 的文章
