En las siguientes secciones, verás un ejemplo de un flujo máximo. (max flow).
Un ejemplo de flujo máximo
El problema se define en el siguiente gráfico, que representa una red:
Quieres transportar material del nodo 0 (el origen) al nodo 4 (el sink). Los números que están junto a los arcos son sus capacidades: capacidad de un arco es la cantidad máxima que se puede transportar a través de él período fijo. Las capacidades son las limitaciones del problema.
Un flujo es la asignación de un número no negativo a cada arco (el importe de flujo) que cumpla con la siguiente regla de conservación del flujo:
El problema de flujo máximo es encontrar un flujo en el que la suma de las cantidades de flujo para que toda la red sea lo más grande posible.
En las siguientes secciones, se presentan programas para encontrar el flujo máximo desde el fuente (0) al receptor (4).
Importa las bibliotecas
Con el siguiente código, se importa la biblioteca requerida.
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;
Cómo declarar la herramienta de resolución
Para resolver el problema, puedes usar la 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();
Define los datos
Defines el grafo del problema con tres arrays: para los nodos de inicio, nodos y capacidades de los arcos. La longitud de cada matriz es igual a la cantidad de arcos en el gráfico.
Para cada i, arco i va de start_nodes[i]
a end_nodes[i]
y su capacidad
es proporcionado por capacities[i]
. En la siguiente sección, se muestra cómo crear los arcos con
estos datos.
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 };
Agrega los arcos
Para cada nodo inicial y final, debes crear un arco desde el nodo inicial hasta el nodo final con la capacidad dada, usando el método AddArcWithCapacity. Las capacidades son las restricciones para resolver el problema.
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"); }
Invocar el solucionador
Ahora que se definieron todos los arcos, solo falta invocar
de resolución y muestra los resultados. Invoca el método Solve()
y proporciona la
fuente (0) y receptor (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);
Cómo mostrar los resultados
Ahora, puedes mostrar el flujo en cada arco.
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); }
Este es el resultado del programa:
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]
Las cantidades de flujo en cada arco se muestran en Flow
.
Completar programas
Haciendo una revisión general, estos son los programas completos.
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); } } }