如何計算有多個起終點的最小費用流問題？
一般地，最小費用流問題是這樣的：如圖所示的網路G中，求從v_0到v_4的目標流值為20的最小費用流。圖中弧上括弧內的第一個數字為容量，第二個數字為弧上單位流的費用。
利用現有的演算法（比如逐次逼近法，演算法名字不重要），可以求得最優解如下：
現在問題來了：如果有目標值為20的流從v_0到v_4，同時有目標值為5的流從v_1到v_3，兩支流彼此不可替代，弧上的費用對兩支流相同，弧的容量不變，求使兩支流費用總和最小的方案，該如何求解？
這個問題可以歸結為一個線性規劃問題，然後用單純型求解。基本思路是將多個起終點的流在圖上分層，然後疊加起來進行組合優化，模型如下：
目標函數就是最小化所有的邊上的流量乘其的費用。
約束條件第1組，表示每一支流中，起點出發的流量，等於終點收到的流量，等於預期的流量。
約束條件第2組，表示每一支流中，在除了起終點的中間點上，每個中間點流入的流量等於流出的流量，實現流量平衡。
約束條件第3組，表示多層圖（每一支流）疊加之後，每一個邊的流量之和不大於邊的能力約束。
然後我用CPLEX 求解了一下，按照題主給的圖和數據，得出的最小費用流結果如下圖。
然後……我又用這個模型算了一下題目中的單支流，結果發現結果貌似與題主提供的最優解有所出入……
這個是我的結果，目標是211，而題目中的最優解目標是226，這……
後來我又琢磨了一下，這個模型其實有一個缺陷，就是當圖的各個邊的能力無法滿足需求的流量時，會出現無解的情況。如果要求能夠實現的最小費用最大流，還需要在每對頂點之間構造一條虛擬的邊，設虛擬邊的能力為無窮大，費用為大M，用其來承擔未能被實際的邊輸送的流量。
今天早上去值班，閑著無聊就瞎這麼一搞，模型裡面的公式還有圖難免會有錯的地方，就這麼一看吧。
題主想解得的是minimum cost multi-commodity flow problem即使只有兩種commodity, 求integer flow的問題是NP-complete的 (Multi-commodity flow problem)fractional flow可以用LP解
跟單源單終點的最小費用流問題有什麼本質區別么。。。。。。
加一個超級源不行么
這是一個經典的多物網路流問題，目前唯一的多項式演算法是線性規劃
（算導上講的，記不得第幾頁了，有沒有誰方便的話查一下，大概在線性規劃的例題這個位置，不勝感激）
敲黑板：根本不是NPC啊不要亂說（如果我沒記錯的話）
這個問題我有心得呀，等下回家答
推薦閱讀：
※如何理解benders decomposition在混合整數規劃中的應用？
※動態規劃和貪心的本質區別是什麼？
※希爾排序為什麼會那麼牛那麼快，能夠證明嗎？