ortools系列：網路最大流問題
ortools系列：網路最大流問題
1. 網路流問題
網路流問題有點像之前講的路由問題，但是更加寬泛。計算機科學中的許多問題都可以用由節點和節點之間的鏈路組成的圖來表示。例如網路流問題，它涉及到跨網路運輸貨物或材料，如鐵路系統。你可以用一個圖來表示網路流，該圖的節點是城市，其弧是它們之間的鐵路線。(它們被稱為流動，因為它們的性質類似於流經管網的水。)
網路流中的一個關鍵約束條件是每個弧都有一個容量，在固定的時間內可以通過弧傳輸的最大容量。最大流量問題是在容量限制的條件下，確定網路中所有弧段的最大總輸送量。
OR-Tools在其圖庫中為網路流問題提供了幾個解決方案:
- 最大流Maximum-Flows
- 最小成本流Minimum-Cost-Flows
2. 網路最大流問題
問題定義如下圖所示，表示一個交通網路:
我們希望將材料從節點0(源)傳輸到節點4(匯聚)。圓弧旁邊的數字是它們的容量，圓弧的容量是在一段固定時間內能夠通過圓弧的最大容量容量是問題的約束條件。
一個流是一個非負數分配給每個弧(流量)，滿足以下流動守恆規則：在每個節點上，除了源節點或匯聚節點外，所有通向該節點的弧的總流量等於所有從該節點流出的弧的總流量，簡單說就是流入等於流出。
最大流量問題是找到一個流，其中整個網路的流量之和儘可能大。
我們來看代碼：
"""From Taha Introduction to Operations Research, example 6.4-2."""
from ortools.graph import pywrapgraph
def main():
"""MaxFlow simple interface example."""
# Define three parallel arrays: start_nodes, end_nodes, and the capacities
# between each pair. For instance, the arc from node 0 to node 1 has a
# capacity of 20.
# 定義從 start->end 的弧的容量
# 即 start_node[i] -> end_node[i] = capacities[i]
start_nodes = [0, 0, 0, 1, 1, 2, 2, 3, 3]
end_nodes = [1, 2, 3, 2, 4, 3, 4, 2, 4]
capacities = [20, 30, 10, 40, 30, 10, 20, 5, 20]
# Instantiate a SimpleMaxFlow solver.
# 創建簡單流
max_flow = pywrapgraph.SimpleMaxFlow()
# Add each arc.
# 添加節點和弧
for i in range(0, len(start_nodes)):
max_flow.AddArcWithCapacity(start_nodes[i], end_nodes[i], capacities[i])
# Find the maximum flow between node 0 and node 4.
# 最後就是求解了
if max_flow.Solve(0, 4) == max_flow.OPTIMAL:
print(Max flow:, max_flow.OptimalFlow())
print()
print( Arc Flow / Capacity)
for i in range(max_flow.NumArcs()):
print(%1s -> %1s %3s / %3s % (
max_flow.Tail(i),
max_flow.Head(i),
max_flow.Flow(i),
max_flow.Capacity(i)))
print(Source side min-cut:, max_flow.GetSourceSideMinCut())
print(Sink side min-cut:, max_flow.GetSinkSideMinCut())
else:
print(There was an issue with the max flow input.)
if __name__ == __main__:
main()
# 結果
Max flow: 60
Arc Flow / Capacity
0 -> 1 20 / 20
0 -> 2 30 / 30
0 -> 3 10 / 10
1 -> 2 0 / 40
1 -> 4 20 / 30
2 -> 3 10 / 10
2 -> 4 20 / 20
3 -> 2 0 / 5
3 -> 4 20 / 20
Source side min-cut: [0]
Sink side min-cut: [4, 1]
3. 參考
- google_ortools_guide
大家看完記得關注點贊.
master蘇.
推薦閱讀：