什麼是最小成本網流規劃

最小成本網流規劃（Minimum Cost Network Flow Problem）是一種運籌學（Operations Research）問題，其目標是在一個帶有邊權的網絡中，找到一組流動量，使得總成本最小化。這裡的「成本」可以是任意一個可以用數值來表示的函數，例如距離、時間、金錢等。

在一個網絡中，我們有若干個源點（Source）和匯點（Sink），以及連接它們的邊（Edge）。每條邊都有一個容量（Capacity）和一個成本（Cost）。我們需要在滿足網絡流動規則的前提下，找到一組流動量，使得從源點到匯點的總成本最小。

最小成本網流規劃的問題可以表述為以下形式：

給定一個帶有邊權的網絡G = (V, E)，其中V是節點集合，E是邊集合。每條邊e ∈ E有一個容量u(e)和一個成本c(e)。問題是找到一組流動量x(e)，滿足以下條件：

1. 對於每條邊e，0 ≤ x(e) ≤ u(e)，即流動量不超過邊的容量。
2. 對於每個節點v，進出節點的流動量相等，即∑[x(e): e進v] = ∑[x(e): e出v]。
3. 總成本最小化，即∑[c(e) * x(e): e ∈ E]最小。

解決最小成本網流規劃問題的常用方法包括：

1. 梯度下降法：當成本函數是凸函數時，可以使用梯度下降法來尋找最小值。
2. 分支定界法：當問題規模較小時，可以使用分支定界法來找到全局最小值。
3. 整數規劃方法：將網流問題建模為整數規劃問題，並使用整數規劃求解器來解決。
4. 增廣路徑算法：如Edmonds-Karp算法，通過增廣路徑的方式逐步增加流，直到達到最大流或邊界限制。

這些方法中，增廣路徑算法是最常用的解決最小成本網流規劃問題的方法之一，因為它可以在O((VE)^2)的時間內找到一個近似解。對於大規模的問題，通常會使用專門的網絡流求解器來解決。