El costo mínimo (costo mínimo) está estrechamente relacionado con el problema del flujo máximo. de flujo en el que cada arco del gráfico tiene un costo unitario de transporte material adicional. El problema es encontrar un flujo con el menor costo total.
El problema de flujo de costo mínimo también tiene nodos especiales, denominados nodos de suministro que son similares a la fuente y al receptor del problema de flujo máximo. El material se transporta desde los nodos de suministro hasta los nodos de demanda.
- En un nodo de suministro, se suma una cantidad positiva (el suministro) al el flujo. Por ejemplo, un suministro podría representar la producción en ese nodo.
- En un nodo de demanda, se toma una cantidad negativa, es decir, la demanda. del flujo. Una demanda podría representar el consumo en ese nodo, por ejemplo.
Para mayor comodidad, supondremos que todos los nodos, excepto los de suministro o demanda, que no tienen suministro (ni demanda).
Para el problema de flujo de costo mínimo, tenemos la siguiente regla de conservación del flujo, que toma en cuenta los suministros y las demandas:
En el siguiente gráfico, se muestra un problema de flujo de costo mínimo. Los arcos se etiquetan con pares de números: el primer número es la capacidad y el segundo es el costo. Los números entre paréntesis junto a los nodos representan los suministros o las demandas. Nodo 0 es un nodo de suministro con 20 de suministro, mientras que los nodos 3 y 4 son de demanda, con exige -5 y -15, respectivamente.
Importa las bibliotecas
Con el siguiente código, se importa la biblioteca requerida.
Python
import numpy as np from ortools.graph.python import min_cost_flow
C++
#include <cstdint> #include <vector> #include "ortools/graph/min_cost_flow.h"
Java
import com.google.ortools.Loader; import com.google.ortools.graph.MinCostFlow; import com.google.ortools.graph.MinCostFlowBase;
C#
using System; using Google.OrTools.Graph;
Cómo declarar la herramienta de resolución
Para resolver el problema, usamos el SimpleMinCostFlow de resolución de problemas.
Python
# Instantiate a SimpleMinCostFlow solver. smcf = min_cost_flow.SimpleMinCostFlow()
C++
// Instantiate a SimpleMinCostFlow solver. SimpleMinCostFlow min_cost_flow;
Java
// Instantiate a SimpleMinCostFlow solver. MinCostFlow minCostFlow = new MinCostFlow();
C#
// Instantiate a SimpleMinCostFlow solver. MinCostFlow minCostFlow = new MinCostFlow();
Define los datos
El siguiente código define los datos para el problema. En este caso, hay cuatro arrays para los nodos de inicio, los nodos finales, las capacidades y los costos unitarios. Nuevamente, la longitud de los arrays es el número de arcos en el gráfico.
Python
# Define four parallel arrays: sources, destinations, capacities, # and unit costs between each pair. For instance, the arc from node 0 # to node 1 has a capacity of 15. start_nodes = np.array([0, 0, 1, 1, 1, 2, 2, 3, 4]) end_nodes = np.array([1, 2, 2, 3, 4, 3, 4, 4, 2]) capacities = np.array([15, 8, 20, 4, 10, 15, 4, 20, 5]) unit_costs = np.array([4, 4, 2, 2, 6, 1, 3, 2, 3]) # Define an array of supplies at each node. supplies = [20, 0, 0, -5, -15]
C++
// Define four parallel arrays: sources, destinations, capacities, // and unit costs between each pair. For instance, the arc from node 0 // to node 1 has a capacity of 15. std::vector<int64_t> start_nodes = {0, 0, 1, 1, 1, 2, 2, 3, 4}; std::vector<int64_t> end_nodes = {1, 2, 2, 3, 4, 3, 4, 4, 2}; std::vector<int64_t> capacities = {15, 8, 20, 4, 10, 15, 4, 20, 5}; std::vector<int64_t> unit_costs = {4, 4, 2, 2, 6, 1, 3, 2, 3}; // Define an array of supplies at each node. std::vector<int64_t> supplies = {20, 0, 0, -5, -15};
Java
// Define four parallel arrays: sources, destinations, capacities, and unit costs // between each pair. For instance, the arc from node 0 to node 1 has a // capacity of 15. // Problem taken From Taha's 'Introduction to Operations Research', // example 6.4-2. int[] startNodes = new int[] {0, 0, 1, 1, 1, 2, 2, 3, 4}; int[] endNodes = new int[] {1, 2, 2, 3, 4, 3, 4, 4, 2}; int[] capacities = new int[] {15, 8, 20, 4, 10, 15, 4, 20, 5}; int[] unitCosts = new int[] {4, 4, 2, 2, 6, 1, 3, 2, 3}; // Define an array of supplies at each node. int[] supplies = new int[] {20, 0, 0, -5, -15};
C#
// Define four parallel arrays: sources, destinations, capacities, and unit costs // between each pair. For instance, the arc from node 0 to node 1 has a // capacity of 15. // Problem taken From Taha's 'Introduction to Operations Research', // example 6.4-2. int[] startNodes = { 0, 0, 1, 1, 1, 2, 2, 3, 4 }; int[] endNodes = { 1, 2, 2, 3, 4, 3, 4, 4, 2 }; int[] capacities = { 15, 8, 20, 4, 10, 15, 4, 20, 5 }; int[] unitCosts = { 4, 4, 2, 2, 6, 1, 3, 2, 3 }; // Define an array of supplies at each node. int[] supplies = { 20, 0, 0, -5, -15 };
Agrega los arcos
Para cada nodo inicial y final, creamos un arco desde el nodo inicial hasta el nodo final con la capacidad y el costo unitario especificados mediante el método AddArcWithCapacityAndUnitCost.
El solucionador de problemas SetNodeSupply crea un vector de suministros para los nodos.
Python
# Add arcs, capacities and costs in bulk using numpy. all_arcs = smcf.add_arcs_with_capacity_and_unit_cost( start_nodes, end_nodes, capacities, unit_costs ) # Add supply for each nodes. smcf.set_nodes_supplies(np.arange(0, len(supplies)), supplies)
C++
// Add each arc. for (int i = 0; i < start_nodes.size(); ++i) { int arc = min_cost_flow.AddArcWithCapacityAndUnitCost( start_nodes[i], end_nodes[i], capacities[i], unit_costs[i]); if (arc != i) LOG(FATAL) << "Internal error"; } // Add node supplies. for (int i = 0; i < supplies.size(); ++i) { min_cost_flow.SetNodeSupply(i, supplies[i]); }
Java
// Add each arc. for (int i = 0; i < startNodes.length; ++i) { int arc = minCostFlow.addArcWithCapacityAndUnitCost( startNodes[i], endNodes[i], capacities[i], unitCosts[i]); if (arc != i) { throw new Exception("Internal error"); } } // Add node supplies. for (int i = 0; i < supplies.length; ++i) { minCostFlow.setNodeSupply(i, supplies[i]); }
C#
// Add each arc. for (int i = 0; i < startNodes.Length; ++i) { int arc = minCostFlow.AddArcWithCapacityAndUnitCost(startNodes[i], endNodes[i], capacities[i], unitCosts[i]); if (arc != i) throw new Exception("Internal error"); } // Add node supplies. for (int i = 0; i < supplies.Length; ++i) { minCostFlow.SetNodeSupply(i, supplies[i]); }
Invocar el solucionador
Ahora que se definieron todos los arcos, solo falta invocar
de resolución y muestra los resultados. Invocamos el método Solve().
Python
# Find the min cost flow. status = smcf.solve()
C++
// Find the min cost flow. int status = min_cost_flow.Solve();
Java
// Find the min cost flow. MinCostFlowBase.Status status = minCostFlow.solve();
C#
// Find the min cost flow. MinCostFlow.Status status = minCostFlow.Solve();
Cómo mostrar los resultados
Ahora, podemos mostrar el flujo y el costo de cada arco.
Python
if status != smcf.OPTIMAL: print("There was an issue with the min cost flow input.") print(f"Status: {status}") exit(1) print(f"Minimum cost: {smcf.optimal_cost()}") print("") print(" Arc Flow / Capacity Cost") solution_flows = smcf.flows(all_arcs) costs = solution_flows * unit_costs for arc, flow, cost in zip(all_arcs, solution_flows, costs): print( f"{smcf.tail(arc):1} -> {smcf.head(arc)} {flow:3} / {smcf.capacity(arc):3} {cost}" )
C++
if (status == MinCostFlow::OPTIMAL) { LOG(INFO) << "Minimum cost flow: " << min_cost_flow.OptimalCost(); LOG(INFO) << ""; LOG(INFO) << " Arc Flow / Capacity Cost"; for (std::size_t i = 0; i < min_cost_flow.NumArcs(); ++i) { int64_t cost = min_cost_flow.Flow(i) * min_cost_flow.UnitCost(i); LOG(INFO) << min_cost_flow.Tail(i) << " -> " << min_cost_flow.Head(i) << " " << min_cost_flow.Flow(i) << " / " << min_cost_flow.Capacity(i) << " " << cost; } } else { LOG(INFO) << "Solving the min cost flow problem failed. Solver status: " << status; }
Java
if (status == MinCostFlow.Status.OPTIMAL) { System.out.println("Minimum cost: " + minCostFlow.getOptimalCost()); System.out.println(); System.out.println(" Edge Flow / Capacity Cost"); for (int i = 0; i < minCostFlow.getNumArcs(); ++i) { long cost = minCostFlow.getFlow(i) * minCostFlow.getUnitCost(i); System.out.println(minCostFlow.getTail(i) + " -> " + minCostFlow.getHead(i) + " " + minCostFlow.getFlow(i) + " / " + minCostFlow.getCapacity(i) + " " + cost); } } else { System.out.println("Solving the min cost flow problem failed."); System.out.println("Solver status: " + status); }
C#
if (status == MinCostFlow.Status.OPTIMAL) { Console.WriteLine("Minimum cost: " + minCostFlow.OptimalCost()); Console.WriteLine(""); Console.WriteLine(" Edge Flow / Capacity Cost"); for (int i = 0; i < minCostFlow.NumArcs(); ++i) { long cost = minCostFlow.Flow(i) * minCostFlow.UnitCost(i); Console.WriteLine(minCostFlow.Tail(i) + " -> " + minCostFlow.Head(i) + " " + string.Format("{0,3}", minCostFlow.Flow(i)) + " / " + string.Format("{0,3}", minCostFlow.Capacity(i)) + " " + string.Format("{0,3}", cost)); } } else { Console.WriteLine("Solving the min cost flow problem failed. Solver status: " + status); }
Este es el resultado del programa de Python:
Minimum cost: 150 Arc Flow / Capacity Cost 0 -> 1 12 / 15 48 0 -> 2 8 / 8 32 1 -> 2 8 / 20 16 1 -> 3 4 / 4 8 1 -> 4 0 / 10 0 2 -> 3 12 / 15 12 2 -> 4 4 / 4 12 3 -> 4 11 / 20 22 4 -> 2 0 / 5 0
Completar programas
Haciendo una revisión general, estos son los programas completos.
Python
"""From Bradley, Hax and Maganti, 'Applied Mathematical Programming', figure 8.1.""" import numpy as np from ortools.graph.python import min_cost_flow def main(): """MinCostFlow simple interface example.""" # Instantiate a SimpleMinCostFlow solver. smcf = min_cost_flow.SimpleMinCostFlow() # Define four parallel arrays: sources, destinations, capacities, # and unit costs between each pair. For instance, the arc from node 0 # to node 1 has a capacity of 15. start_nodes = np.array([0, 0, 1, 1, 1, 2, 2, 3, 4]) end_nodes = np.array([1, 2, 2, 3, 4, 3, 4, 4, 2]) capacities = np.array([15, 8, 20, 4, 10, 15, 4, 20, 5]) unit_costs = np.array([4, 4, 2, 2, 6, 1, 3, 2, 3]) # Define an array of supplies at each node. supplies = [20, 0, 0, -5, -15] # Add arcs, capacities and costs in bulk using numpy. all_arcs = smcf.add_arcs_with_capacity_and_unit_cost( start_nodes, end_nodes, capacities, unit_costs ) # Add supply for each nodes. smcf.set_nodes_supplies(np.arange(0, len(supplies)), supplies) # Find the min cost flow. status = smcf.solve() if status != smcf.OPTIMAL: print("There was an issue with the min cost flow input.") print(f"Status: {status}") exit(1) print(f"Minimum cost: {smcf.optimal_cost()}") print("") print(" Arc Flow / Capacity Cost") solution_flows = smcf.flows(all_arcs) costs = solution_flows * unit_costs for arc, flow, cost in zip(all_arcs, solution_flows, costs): print( f"{smcf.tail(arc):1} -> {smcf.head(arc)} {flow:3} / {smcf.capacity(arc):3} {cost}" ) if __name__ == "__main__": main()
C++
// From Bradley, Hax and Maganti, 'Applied Mathematical Programming', figure 8.1 #include <cstdint> #include <vector> #include "ortools/graph/min_cost_flow.h" namespace operations_research { // MinCostFlow simple interface example. void SimpleMinCostFlowProgram() { // Instantiate a SimpleMinCostFlow solver. SimpleMinCostFlow min_cost_flow; // Define four parallel arrays: sources, destinations, capacities, // and unit costs between each pair. For instance, the arc from node 0 // to node 1 has a capacity of 15. std::vector<int64_t> start_nodes = {0, 0, 1, 1, 1, 2, 2, 3, 4}; std::vector<int64_t> end_nodes = {1, 2, 2, 3, 4, 3, 4, 4, 2}; std::vector<int64_t> capacities = {15, 8, 20, 4, 10, 15, 4, 20, 5}; std::vector<int64_t> unit_costs = {4, 4, 2, 2, 6, 1, 3, 2, 3}; // Define an array of supplies at each node. std::vector<int64_t> supplies = {20, 0, 0, -5, -15}; // Add each arc. for (int i = 0; i < start_nodes.size(); ++i) { int arc = min_cost_flow.AddArcWithCapacityAndUnitCost( start_nodes[i], end_nodes[i], capacities[i], unit_costs[i]); if (arc != i) LOG(FATAL) << "Internal error"; } // Add node supplies. for (int i = 0; i < supplies.size(); ++i) { min_cost_flow.SetNodeSupply(i, supplies[i]); } // Find the min cost flow. int status = min_cost_flow.Solve(); if (status == MinCostFlow::OPTIMAL) { LOG(INFO) << "Minimum cost flow: " << min_cost_flow.OptimalCost(); LOG(INFO) << ""; LOG(INFO) << " Arc Flow / Capacity Cost"; for (std::size_t i = 0; i < min_cost_flow.NumArcs(); ++i) { int64_t cost = min_cost_flow.Flow(i) * min_cost_flow.UnitCost(i); LOG(INFO) << min_cost_flow.Tail(i) << " -> " << min_cost_flow.Head(i) << " " << min_cost_flow.Flow(i) << " / " << min_cost_flow.Capacity(i) << " " << cost; } } else { LOG(INFO) << "Solving the min cost flow problem failed. Solver status: " << status; } } } // namespace operations_research int main() { operations_research::SimpleMinCostFlowProgram(); return EXIT_SUCCESS; }
Java
// From Bradley, Hax, and Maganti, 'Applied Mathematical Programming', figure 8.1. package com.google.ortools.graph.samples; import com.google.ortools.Loader; import com.google.ortools.graph.MinCostFlow; import com.google.ortools.graph.MinCostFlowBase; /** Minimal MinCostFlow program. */ public class SimpleMinCostFlowProgram { public static void main(String[] args) throws Exception { Loader.loadNativeLibraries(); // Instantiate a SimpleMinCostFlow solver. MinCostFlow minCostFlow = new MinCostFlow(); // Define four parallel arrays: sources, destinations, capacities, and unit costs // between each pair. For instance, the arc from node 0 to node 1 has a // capacity of 15. // Problem taken From Taha's 'Introduction to Operations Research', // example 6.4-2. int[] startNodes = new int[] {0, 0, 1, 1, 1, 2, 2, 3, 4}; int[] endNodes = new int[] {1, 2, 2, 3, 4, 3, 4, 4, 2}; int[] capacities = new int[] {15, 8, 20, 4, 10, 15, 4, 20, 5}; int[] unitCosts = new int[] {4, 4, 2, 2, 6, 1, 3, 2, 3}; // Define an array of supplies at each node. int[] supplies = new int[] {20, 0, 0, -5, -15}; // Add each arc. for (int i = 0; i < startNodes.length; ++i) { int arc = minCostFlow.addArcWithCapacityAndUnitCost( startNodes[i], endNodes[i], capacities[i], unitCosts[i]); if (arc != i) { throw new Exception("Internal error"); } } // Add node supplies. for (int i = 0; i < supplies.length; ++i) { minCostFlow.setNodeSupply(i, supplies[i]); } // Find the min cost flow. MinCostFlowBase.Status status = minCostFlow.solve(); if (status == MinCostFlow.Status.OPTIMAL) { System.out.println("Minimum cost: " + minCostFlow.getOptimalCost()); System.out.println(); System.out.println(" Edge Flow / Capacity Cost"); for (int i = 0; i < minCostFlow.getNumArcs(); ++i) { long cost = minCostFlow.getFlow(i) * minCostFlow.getUnitCost(i); System.out.println(minCostFlow.getTail(i) + " -> " + minCostFlow.getHead(i) + " " + minCostFlow.getFlow(i) + " / " + minCostFlow.getCapacity(i) + " " + cost); } } else { System.out.println("Solving the min cost flow problem failed."); System.out.println("Solver status: " + status); } } private SimpleMinCostFlowProgram() {} }
C#
// From Bradley, Hax, and Magnanti, 'Applied Mathematical Programming', figure 8.1. using System; using Google.OrTools.Graph; public class SimpleMinCostFlowProgram { static void Main() { // Instantiate a SimpleMinCostFlow solver. MinCostFlow minCostFlow = new MinCostFlow(); // Define four parallel arrays: sources, destinations, capacities, and unit costs // between each pair. For instance, the arc from node 0 to node 1 has a // capacity of 15. // Problem taken From Taha's 'Introduction to Operations Research', // example 6.4-2. int[] startNodes = { 0, 0, 1, 1, 1, 2, 2, 3, 4 }; int[] endNodes = { 1, 2, 2, 3, 4, 3, 4, 4, 2 }; int[] capacities = { 15, 8, 20, 4, 10, 15, 4, 20, 5 }; int[] unitCosts = { 4, 4, 2, 2, 6, 1, 3, 2, 3 }; // Define an array of supplies at each node. int[] supplies = { 20, 0, 0, -5, -15 }; // Add each arc. for (int i = 0; i < startNodes.Length; ++i) { int arc = minCostFlow.AddArcWithCapacityAndUnitCost(startNodes[i], endNodes[i], capacities[i], unitCosts[i]); if (arc != i) throw new Exception("Internal error"); } // Add node supplies. for (int i = 0; i < supplies.Length; ++i) { minCostFlow.SetNodeSupply(i, supplies[i]); } // Find the min cost flow. MinCostFlow.Status status = minCostFlow.Solve(); if (status == MinCostFlow.Status.OPTIMAL) { Console.WriteLine("Minimum cost: " + minCostFlow.OptimalCost()); Console.WriteLine(""); Console.WriteLine(" Edge Flow / Capacity Cost"); for (int i = 0; i < minCostFlow.NumArcs(); ++i) { long cost = minCostFlow.Flow(i) * minCostFlow.UnitCost(i); Console.WriteLine(minCostFlow.Tail(i) + " -> " + minCostFlow.Head(i) + " " + string.Format("{0,3}", minCostFlow.Flow(i)) + " / " + string.Format("{0,3}", minCostFlow.Capacity(i)) + " " + string.Format("{0,3}", cost)); } } else { Console.WriteLine("Solving the min cost flow problem failed. Solver status: " + status); } } }