En las siguientes secciones, se muestra un ejemplo de un problema de flujo máximo (flujo máximo).
Un ejemplo de flujo máximo
El problema se define en el siguiente gráfico, que representa una red de transporte:
Deseas transportar material del nodo 0 (la fuente) al nodo 4 (el receptor). Los números que aparecen junto a los arcos son sus capacidades: la capacidad de un arco es la cantidad máxima que se puede transportar a través de él en un período determinado. Las capacidades son las limitaciones del problema.
Un flujo es una asignación de un número no negativo a cada arco (la cantidad de flujo) que cumple con la siguiente regla de conservación del flujo:
El problema del flujo máximo es encontrar un flujo para el que la suma de las cantidades de toda la red sea lo más grande posible.
En las siguientes secciones, se presentan programas para encontrar el flujo máximo desde la fuente (0) hasta el 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 el solucionador
Para resolver el problema, puedes usar el solucionador de problemas 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
Define el grafo del problema con tres arreglos para los nodos de inicio, los nodos finales y las capacidades de los arcos. La longitud de cada array equivale a la cantidad de arcos en el gráfico.
Para cada i, el arco i va de start_nodes[i] a end_nodes[i], y su capacidad está determinada 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 de inicio y final, debes crear un arco desde el nodo inicial hasta el final con la capacidad determinada mediante el método AddArcWithCapacity. Las capacidades son las restricciones del 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");
}
Cómo invocar el solucionador
Ahora que se definieron todos los arcos, lo único que queda es invocar al agente y mostrar los resultados. Invoca el método Solve() y proporciona la fuente (0) y el 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);
Muestra 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]
Los importes de flujo de cada arco se muestran en Flow.
Programas completos
En resumen, aquí están 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);
}
}
}