給出節點具體值的最小流量

Question

圖論中是否有已知算法解決使用最小流量離開具有特定值的節點的問題？換句話說，有多個來源和匯，需要留下一定數額的赤字和信貸。謝謝！

Answer 1

當然有。它實際上被稱爲最小成本流算法。 我正在爲此算法提供永久鏈接： Minimum Cost Flow 您將需要一個LP解算器來生成解決方案。

Answer 2

您可以將其制定爲「Transportation Problem」 - 債務人是（貨幣）供應商，需求來自債權人。目標是將資金從一邊「運」到另一邊。

要處理目標（「貨幣量最少」），我們可以假設債務人希望儘可能少地支付債權人，債權人希望儘可能減少債務人的錢。

要有「小號」節點，一個用於每個供應商（debitor）和「噸」節點，一個用於每個債權人。有向弧將每個供應商連接到每個需求節點。在任何弧線（邊緣）上移動貨幣的成本爲1.（所有邊線的容量都很高）。

在平衡運輸問題總需求等於總供給，但這是一個理想情況。通過引入虛擬節點和虛擬邊緣，我們可以處理信用和借方總量的不平衡。

因爲我們要使用的虛擬邊緣少則可以，我們可以將那些邊緣較高的性價比。因此，該模型將僅使用這些邊緣作爲最後的手段。

圖示地，

此運輸問題的製劑：

X_st是從節點s的錢（流量）的量，以節點T

目的：Min（sum_over_edges）Cost_st * X_st

個

約束

(Sum over all edges incoming to demand node t) X_st >= Demand_t (for each t) 
(Sum over all edges outbound from supply node s) X_st >= Supply_s (for each s) 
Xst >= 0 

一對夫婦的其他注意事項：

1. 這個問題可以或者也可以配製成transshipment problem。你有中間分期點（資金交換所）。
2. 當你有多個的源和匯中，可以創建一個「超級源極」和「超匯」節點，邊從常規來源和匯聚節點這些超級節點連接到，和重新創建分鐘流問題。

配方完成後，您可以使用您有權訪問的任何MILP解算器，以獲得債務人與債權人的最佳匹配。

希望有所幫助。