Optimisation de la combinaison - problème typique - problème de flux de coût minimal

Problème typique et méthode d'exécution

Problème de flux de coût minimum

Dans le graphe orienté $ G = (V, E) $, étant donné la capacité et le poids de chaque côté et la demande de nœuds, la somme des poids pour le débit de chaque côté est minimisée sans dépasser la capacité de chaque côté. Trouvez le flux.

--A chaque nœud, "inflow --outflow" est égal à la demande.

• Si la demande est négative, elle représente l'offre.
• La somme des demandes de tous les nœuds doit être égale à 0.

Méthode d'exécution

usage

Signature: nx.min_cost_flow(G, demand='demand', capacity='capacity', weight='weight')
Docstring:
Return a minimum cost flow satisfying all demands in digraph G.

G is a digraph with edge costs and capacities and in which nodes
have demand, i.e., they want to send or receive some amount of
flow. A negative demand means that the node wants to send flow, a
positive demand means that the node want to receive flow. A flow on
the digraph G satisfies all demand if the net flow into each node
is equal to the demand of that node.

python

#Données CSV
import pandas as pd, networkx as nx
from ortoolpy import graph_from_table, networkx_draw
tbn = pd.read_csv('data/node0.csv')
tbe = pd.read_csv('data/edge0.csv')
g = graph_from_table(tbn, tbe, directed=True)[0]
result = nx.min_cost_flow(g)
for i, d in result.items():
    for j, f in d.items():
        if f: print((i, j), f)

résultat

(0, 1) 1
(0, 3) 1
(0, 4) 2
(4, 5) 1

python

# pandas.DataFrame
from ortoolpy.optimization import MinCostFlow
MinCostFlow('data/node0.csv','data/edge0.csv')

python

#Données aléatoires
import networkx as nx
g = nx.fast_gnp_random_graph(8, 0.2, 1, True)
g.nodes[1]['demand'] = -2 #La fourniture
g.nodes[7]['demand'] = 2 #demande
g.adj[2][7]['capacity'] = 1 #capacité
result = nx.min_cost_flow(g)
for i, d in result.items():
    for j, f in d.items():
        if f: print((i, j), f)

résultat

(1, 2) 2
(2, 3) 1
(2, 7) 1
(3, 7) 1

Les données

• data/node0.csv
• data/edge0.csv