在以下部分中,您将获得最大流(最大流)问题的示例。
最大数据流示例
下图定义了问题,该图表示交通网络:
您需要将材料从节点 0(来源)传输到节点 4(接收器)。弧线旁边的数字是它们的容量,弧形的容量是在固定的时间段内可以跨越它的最大容量。容量是问题的约束条件。
流是指向每条弧形分配一个非负数(即流量),它满足以下流守恒规则:
最大流问题是找出整个网络的流量总和尽可能大的流。
以下部分介绍的程序可用于查找从来源 (0) 到接收器 (4) 的最大流。
导入库
以下代码会导入所需的库。
Python
import numpy as np from ortools.graph.python import max_flow
C++
#include <cstdint> #include <vector> #include "ortools/graph/max_flow.h"
Java
import com.google.ortools.Loader; import com.google.ortools.graph.MaxFlow;
C#
using System; using Google.OrTools.Graph;
声明求解器
为了解决这个问题,您可以使用 SimpleMaxFlow 求解器。
Python
# Instantiate a SimpleMaxFlow solver. smf = max_flow.SimpleMaxFlow()
C++
// Instantiate a SimpleMaxFlow solver. SimpleMaxFlow max_flow;
Java
// Instantiate a SimpleMaxFlow solver. MaxFlow maxFlow = new MaxFlow();
C#
// Instantiate a SimpleMaxFlow solver. MaxFlow maxFlow = new MaxFlow();
定义数据
您可以使用三个数组(代表弧形的起始节点、结束节点和容量)定义问题的图。每个数组的长度等于图中的弧形数量。
对于每个 i,弧形 i 从 start_nodes[i]
到 end_nodes[i]
,其容量由 capacities[i]
提供。下一部分将介绍如何使用此数据创建弧线。
Python
# 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_nodes = np.array([0, 0, 0, 1, 1, 2, 2, 3, 3]) end_nodes = np.array([1, 2, 3, 2, 4, 3, 4, 2, 4]) capacities = np.array([20, 30, 10, 40, 30, 10, 20, 5, 20])
C++
// 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. std::vector<int64_t> start_nodes = {0, 0, 0, 1, 1, 2, 2, 3, 3}; std::vector<int64_t> end_nodes = {1, 2, 3, 2, 4, 3, 4, 2, 4}; std::vector<int64_t> capacities = {20, 30, 10, 40, 30, 10, 20, 5, 20};
Java
// 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. // From Taha's 'Introduction to Operations Research', // example 6.4-2. int[] startNodes = new int[] {0, 0, 0, 1, 1, 2, 2, 3, 3}; int[] endNodes = new int[] {1, 2, 3, 2, 4, 3, 4, 2, 4}; int[] capacities = new int[] {20, 30, 10, 40, 30, 10, 20, 5, 20};
C#
// 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. // From Taha's 'Introduction to Operations Research', // example 6.4-2. int[] startNodes = { 0, 0, 0, 1, 1, 2, 2, 3, 3 }; int[] endNodes = { 1, 2, 3, 2, 4, 3, 4, 2, 4 }; int[] capacities = { 20, 30, 10, 40, 30, 10, 20, 5, 20 };
添加弧线
对于每个起始节点和结束节点,您可以使用 AddArcWithCapacity 方法创建一条从起始节点到结束节点具有给定容量的弧形。容量是问题的约束条件。
Python
# Add arcs in bulk. # note: we could have used add_arc_with_capacity(start, end, capacity) all_arcs = smf.add_arcs_with_capacity(start_nodes, end_nodes, capacities)
C++
// Add each arc. for (int i = 0; i < start_nodes.size(); ++i) { max_flow.AddArcWithCapacity(start_nodes[i], end_nodes[i], capacities[i]); }
Java
// Add each arc. for (int i = 0; i < startNodes.length; ++i) { int arc = maxFlow.addArcWithCapacity(startNodes[i], endNodes[i], capacities[i]); if (arc != i) { throw new Exception("Internal error"); } }
C#
// Add each arc. for (int i = 0; i < startNodes.Length; ++i) { int arc = maxFlow.AddArcWithCapacity(startNodes[i], endNodes[i], capacities[i]); if (arc != i) throw new Exception("Internal error"); }
调用求解器
现在,所有弧线均已定义,剩下的工作就是调用求解器并显示结果。调用 Solve()
方法,并提供来源 (0) 和接收器 (4)。
Python
# Find the maximum flow between node 0 and node 4. status = smf.solve(0, 4)
C++
// Find the maximum flow between node 0 and node 4. int status = max_flow.Solve(0, 4);
Java
// Find the maximum flow between node 0 and node 4. MaxFlow.Status status = maxFlow.solve(0, 4);
C#
// Find the maximum flow between node 0 and node 4. MaxFlow.Status status = maxFlow.Solve(0, 4);
显示结果
现在,您可以显示横跨每条弧形的流。
Python
if status != smf.OPTIMAL: print("There was an issue with the max flow input.") print(f"Status: {status}") exit(1) print("Max flow:", smf.optimal_flow()) print("") print(" Arc Flow / Capacity") solution_flows = smf.flows(all_arcs) for arc, flow, capacity in zip(all_arcs, solution_flows, capacities): print(f"{smf.tail(arc)} / {smf.head(arc)} {flow:3} / {capacity:3}") print("Source side min-cut:", smf.get_source_side_min_cut()) print("Sink side min-cut:", smf.get_sink_side_min_cut())
C++
if (status == MaxFlow::OPTIMAL) { LOG(INFO) << "Max flow: " << max_flow.OptimalFlow(); LOG(INFO) << ""; LOG(INFO) << " Arc Flow / Capacity"; for (std::size_t i = 0; i < max_flow.NumArcs(); ++i) { LOG(INFO) << max_flow.Tail(i) << " -> " << max_flow.Head(i) << " " << max_flow.Flow(i) << " / " << max_flow.Capacity(i); } } else { LOG(INFO) << "Solving the max flow problem failed. Solver status: " << status; }
Java
if (status == MaxFlow.Status.OPTIMAL) { System.out.println("Max. flow: " + maxFlow.getOptimalFlow()); System.out.println(); System.out.println(" Arc Flow / Capacity"); for (int i = 0; i < maxFlow.getNumArcs(); ++i) { System.out.println(maxFlow.getTail(i) + " -> " + maxFlow.getHead(i) + " " + maxFlow.getFlow(i) + " / " + maxFlow.getCapacity(i)); } } else { System.out.println("Solving the max flow problem failed. Solver status: " + status); }
C#
if (status == MaxFlow.Status.OPTIMAL) { Console.WriteLine("Max. flow: " + maxFlow.OptimalFlow()); Console.WriteLine(""); Console.WriteLine(" Arc Flow / Capacity"); for (int i = 0; i < maxFlow.NumArcs(); ++i) { Console.WriteLine(maxFlow.Tail(i) + " -> " + maxFlow.Head(i) + " " + string.Format("{0,3}", maxFlow.Flow(i)) + " / " + string.Format("{0,3}", maxFlow.Capacity(i))); } } else { Console.WriteLine("Solving the max flow problem failed. Solver status: " + status); }
程序的输出如下所示:
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]
各弧形的流量显示在 Flow
下。
完成计划
综上所述,以下是完整的计划。
Python
"""From Taha 'Introduction to Operations Research', example 6.4-2.""" import numpy as np from ortools.graph.python import max_flow def main(): """MaxFlow simple interface example.""" # Instantiate a SimpleMaxFlow solver. smf = max_flow.SimpleMaxFlow() # 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_nodes = np.array([0, 0, 0, 1, 1, 2, 2, 3, 3]) end_nodes = np.array([1, 2, 3, 2, 4, 3, 4, 2, 4]) capacities = np.array([20, 30, 10, 40, 30, 10, 20, 5, 20]) # Add arcs in bulk. # note: we could have used add_arc_with_capacity(start, end, capacity) all_arcs = smf.add_arcs_with_capacity(start_nodes, end_nodes, capacities) # Find the maximum flow between node 0 and node 4. status = smf.solve(0, 4) if status != smf.OPTIMAL: print("There was an issue with the max flow input.") print(f"Status: {status}") exit(1) print("Max flow:", smf.optimal_flow()) print("") print(" Arc Flow / Capacity") solution_flows = smf.flows(all_arcs) for arc, flow, capacity in zip(all_arcs, solution_flows, capacities): print(f"{smf.tail(arc)} / {smf.head(arc)} {flow:3} / {capacity:3}") print("Source side min-cut:", smf.get_source_side_min_cut()) print("Sink side min-cut:", smf.get_sink_side_min_cut()) if __name__ == "__main__": main()
C++
// From Taha 'Introduction to Operations Research', example 6.4-2.""" #include <cstdint> #include <vector> #include "ortools/graph/max_flow.h" namespace operations_research { // MaxFlow simple interface example. void SimpleMaxFlowProgram() { // Instantiate a SimpleMaxFlow solver. SimpleMaxFlow max_flow; // 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. std::vector<int64_t> start_nodes = {0, 0, 0, 1, 1, 2, 2, 3, 3}; std::vector<int64_t> end_nodes = {1, 2, 3, 2, 4, 3, 4, 2, 4}; std::vector<int64_t> capacities = {20, 30, 10, 40, 30, 10, 20, 5, 20}; // Add each arc. for (int i = 0; i < start_nodes.size(); ++i) { max_flow.AddArcWithCapacity(start_nodes[i], end_nodes[i], capacities[i]); } // Find the maximum flow between node 0 and node 4. int status = max_flow.Solve(0, 4); if (status == MaxFlow::OPTIMAL) { LOG(INFO) << "Max flow: " << max_flow.OptimalFlow(); LOG(INFO) << ""; LOG(INFO) << " Arc Flow / Capacity"; for (std::size_t i = 0; i < max_flow.NumArcs(); ++i) { LOG(INFO) << max_flow.Tail(i) << " -> " << max_flow.Head(i) << " " << max_flow.Flow(i) << " / " << max_flow.Capacity(i); } } else { LOG(INFO) << "Solving the max flow problem failed. Solver status: " << status; } } } // namespace operations_research int main() { operations_research::SimpleMaxFlowProgram(); return EXIT_SUCCESS; }
Java
package com.google.ortools.graph.samples; import com.google.ortools.Loader; import com.google.ortools.graph.MaxFlow; /** Minimal MaxFlow program. */ public final class SimpleMaxFlowProgram { public static void main(String[] args) throws Exception { Loader.loadNativeLibraries(); // Instantiate a SimpleMaxFlow solver. MaxFlow maxFlow = new MaxFlow(); // 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. // From Taha's 'Introduction to Operations Research', // example 6.4-2. int[] startNodes = new int[] {0, 0, 0, 1, 1, 2, 2, 3, 3}; int[] endNodes = new int[] {1, 2, 3, 2, 4, 3, 4, 2, 4}; int[] capacities = new int[] {20, 30, 10, 40, 30, 10, 20, 5, 20}; // Add each arc. for (int i = 0; i < startNodes.length; ++i) { int arc = maxFlow.addArcWithCapacity(startNodes[i], endNodes[i], capacities[i]); if (arc != i) { throw new Exception("Internal error"); } } // Find the maximum flow between node 0 and node 4. MaxFlow.Status status = maxFlow.solve(0, 4); if (status == MaxFlow.Status.OPTIMAL) { System.out.println("Max. flow: " + maxFlow.getOptimalFlow()); System.out.println(); System.out.println(" Arc Flow / Capacity"); for (int i = 0; i < maxFlow.getNumArcs(); ++i) { System.out.println(maxFlow.getTail(i) + " -> " + maxFlow.getHead(i) + " " + maxFlow.getFlow(i) + " / " + maxFlow.getCapacity(i)); } } else { System.out.println("Solving the max flow problem failed. Solver status: " + status); } } private SimpleMaxFlowProgram() {} }
C#
// From Taha 'Introduction to Operations Research', example 6.4-2. using System; using Google.OrTools.Graph; public class SimpleMaxFlowProgram { static void Main() { // Instantiate a SimpleMaxFlow solver. MaxFlow maxFlow = new MaxFlow(); // 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. // From Taha's 'Introduction to Operations Research', // example 6.4-2. int[] startNodes = { 0, 0, 0, 1, 1, 2, 2, 3, 3 }; int[] endNodes = { 1, 2, 3, 2, 4, 3, 4, 2, 4 }; int[] capacities = { 20, 30, 10, 40, 30, 10, 20, 5, 20 }; // Add each arc. for (int i = 0; i < startNodes.Length; ++i) { int arc = maxFlow.AddArcWithCapacity(startNodes[i], endNodes[i], capacities[i]); if (arc != i) throw new Exception("Internal error"); } // Find the maximum flow between node 0 and node 4. MaxFlow.Status status = maxFlow.Solve(0, 4); if (status == MaxFlow.Status.OPTIMAL) { Console.WriteLine("Max. flow: " + maxFlow.OptimalFlow()); Console.WriteLine(""); Console.WriteLine(" Arc Flow / Capacity"); for (int i = 0; i < maxFlow.NumArcs(); ++i) { Console.WriteLine(maxFlow.Tail(i) + " -> " + maxFlow.Head(i) + " " + string.Format("{0,3}", maxFlow.Flow(i)) + " / " + string.Format("{0,3}", maxFlow.Capacity(i))); } } else { Console.WriteLine("Solving the max flow problem failed. Solver status: " + status); } } }