Intimamente relacionado ao problema do fluxo máximo é o custo mínimo (custo mínimo) problema de fluxo, em que cada arco no gráfico tem um custo unitário para transportar materiais. O problema é encontrar um fluxo com o menor custo total.
O problema de fluxo de custo mínimo também tem nós especiais, chamados de nós de fornecimento, ou nós, que são semelhantes à origem e ao coletor na problema de fluxo máximo. O material é transportado dos nós de fornecimento para os nós de demanda.
- Em um nó de fornecimento, um valor positivo (o suprimento) é adicionado ao o fluxo. Um fornecimento poderia representar a produção nesse nó, por exemplo.
- Em um nó de demanda, um valor negativo (a demanda) é usado. para longe do fluxo. Uma demanda pode representar o consumo naquele nó, por exemplo.
Para facilitar, vamos presumir que todos os nós, exceto os nós de oferta ou demanda, não têm oferta nem demanda.
Para o problema de fluxo de custo mínimo, temos a seguinte regra de conservação de fluxo, que considera os suprimentos e as demandas:
O gráfico abaixo mostra um problema de fluxo de custo mínimo. Os arcos são identificados com pares em números: o primeiro número é a capacidade e o segundo é o custo. Os números entre parênteses ao lado dos nós representam suprimentos ou demandas. Nó 0 é um nó de fornecimento com fornecimento 20, enquanto os nós 3 e 4 são nós de demanda, com demandas -5 e -15, respectivamente.
Importar as bibliotecas
O código a seguir importa a biblioteca necessária.
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;
Declarar o solucionador
Para resolver o problema, usamos o SimpleMinCostFlow solucionador.
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();
Definir os dados
O código a seguir define os dados do problema. Nesse caso, há quatro matrizes para os nós iniciais, os nós finais, as capacidades e os custos unitários. Mais uma vez, o comprimento das matrizes é o número de arcos no 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 };
Adicionar os arcos
Para cada nó inicial e final, criamos um arco do nó inicial ao final. com a capacidade e o custo unitário fornecidos, AddArcWithCapacityAndUnitCost (em inglês).
O solucionador SetNodeSupply cria um vetor de suprimentos para os nós.
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 o solucionador
Agora que todos os arcos foram definidos, resta invocar o
e exibir os resultados. Invocamos o 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();
Mostrar os resultados
Agora, podemos exibir o fluxo e o custo em 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); }
Esta é a saída do programa 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
Programas completos
Juntando tudo, estes são os 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); } } }