Strettamente correlato al problema del flusso massimo è il costo minimo (costo minimo). problema di flusso, in cui ogni arco nel grafico ha un costo unitario per il trasporto materiale al suo interno. Il problema è trovare un flusso con il costo totale minimo.
Il problema del flusso di costo minimo ha anche nodi speciali, chiamati nodi di fornitura o domanda. nodi, che sono simili all'origine e al sink problema di flusso massimo. Il materiale viene trasportato dai nodi di fornitura ai nodi di domanda.
- Su un nodo di fornitura, una quantità positiva, l'offerta, viene aggiunta il flusso. Ad esempio, un rifornimento potrebbe rappresentare la produzione in quel nodo.
- Su un nodo di domanda, viene preso un importo negativo, ovvero la domanda lontano dal flusso. Una domanda potrebbe rappresentare il consumo in quel nodo, esempio.
Per praticità, supponiamo che tutti i nodi, ad eccezione di quelli di offerta o domanda, non hanno offerta (e domanda).
Per il problema del flusso di costo minimo, abbiamo la seguente regola di conservazione del flusso: che tiene conto di forniture e richieste:
Il grafico seguente mostra un problema di flusso di costo minimo. Gli archi sono etichettati con coppie di numeri: il primo numero indica la capacità e il secondo il costo. I numeri tra parentesi accanto ai nodi rappresentano le forniture o le richieste. Nodo 0 è un nodo di alimentazione con offerta 20, mentre i nodi 3 e 4 sono nodi di domanda, con richieste rispettivamente -5 e -15.
Importa le librerie
Il codice seguente importa la libreria richiesta.
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;
Dichiara il risolutore
Per risolvere il problema, utilizziamo SimpleMinCostFlow risolutore.
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();
Definisci i dati
Il seguente codice definisce i dati del problema. In questo caso, ci sono quattro array per i nodi iniziali, i nodi finali, le capacità e i costi unitari. Di nuovo, la lunghezza degli array è il numero di archi nel grafico.
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 };
Aggiungi gli archi
Per ogni nodo iniziale e nodo finale, creiamo un arco dal nodo iniziale al nodo finale con la capacità e il costo unitario dati, utilizzando il metodo AddArcWithCapacityAndUnitCost.
Il risolutore SetNodeSupply crea un vettore di forniture per i nodi.
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]); }
Richiama il risolutore
Ora che tutti gli archi sono stati definiti, non rimane altro da richiamare
risolutore e visualizzare i risultati. Richiamo il metodo 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();
Visualizza i risultati
Ora possiamo visualizzare il flusso e il costo in ogni 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); }
Ecco l'output del programma 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
Completa i programmi
Riassumendo, ecco i programmi completi.
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); } } }