Le problème de flux minimum (coût minimal) est étroitement lié au problème du flux maximal, dans lequel chaque arc du graphique a un coût unitaire pour le transport des matériaux. Le problème est de trouver un flux avec le coût total le plus faible.
Le problème de flux de coût minimal présente également des nœuds spéciaux, appelés nœuds de fourniture ou nœuds de demande, qui sont semblables à la source et au récepteur dans le problème de flux maximal. Le matériau est transporté des nœuds d'approvisionnement vers les nœuds de demande.
- Au niveau d'un nœud d'approvisionnement, une quantité positive (l'approvisionnement) est ajoutée au flux. Une fourniture peut représenter la production sur ce nœud, par exemple.
- Au niveau d'un nœud de demande, un montant négatif (la demande) est retiré du flux. Une demande peut représenter la consommation sur ce nœud, par exemple.
Pour plus de commodité, nous partirons du principe que l'offre (et la demande) n'est nulle pour tous les nœuds, à l'exception des nœuds d'offre ou de demande.
Pour le problème de flux de coûts minimal, nous appliquons la règle de conservation de flux suivante, qui prend en compte les stocks et les demandes:
Le graphique ci-dessous illustre un problème lié au flux de coûts minimaux. Les arcs sont étiquetés par des paires de nombres: le premier nombre correspond à la capacité et le second au coût. Les chiffres entre parenthèses à côté des nœuds représentent les fournitures ou les demandes. Le nœud 0 est un nœud d'approvisionnement avec une offre de 20, tandis que les nœuds 3 et 4 sont des nœuds de demande, avec des demandes respectivement de -5 et -15.
Importer les bibliothèques
Le code suivant importe la bibliothèque requise.
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;
Déclarer le résolveur
Pour résoudre le problème, nous utilisons le résolveur SimpleMinCostFlow.
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();
Définir les données
Le code suivant définit les données du problème. Dans ce cas, il existe quatre tableaux pour les nœuds de début, les nœuds de fin, les capacités et les coûts unitaires. Encore une fois, la longueur des tableaux correspond au nombre d'arcs dans le graphique.
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 };
Ajouter les arcs
Pour chaque nœud de début et chaque nœud de fin, nous créons un arc du nœud de début au nœud final avec la capacité et le coût unitaire indiqués, à l'aide de la méthode AddArcWithCapacityAndUnitCost.
La méthode SetNodeSupply du résolveur crée un vecteur de fournitures pour les nœuds.
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]);
}
Appeler le résolveur
Maintenant que tous les arcs ont été définis, il ne vous reste plus qu'à appeler le résolveur et à afficher les résultats. Nous appelons la méthode 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();
Afficher les résultats
Nous pouvons maintenant afficher le flux et le coût pour chaque arc.
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);
}
Voici la sortie du programme 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
Terminer les programmes
En résumé, voici les programmes complets.
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);
}
}
}