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.

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')
node1 node2 capacity weight flow
0 0 1 2 1 1
1 0 3 2 2 1
2 0 4 2 2 2
3 4 5 2 1 1

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

Recommended Posts

Optimisation de la combinaison - problème typique - problème de flux de coût minimal
Optimisation de la combinaison - problème typique - problème de débit maximal
Optimisation de combinaison - problème typique - problème d'arborescence de surface minimale
Optimisation de combinaison - problème typique de problème de sac à dos
Optimisation de combinaison - problème typique de conditionnement n-dimensionnel
Problème de correspondance stable aux problèmes typique d'optimisation de combinaison
Optimisation de combinaison - problème typique d'allocation généralisé
Problème d'optimisation de combinaison-problème typique d'emballage de bac
Optimisation de combinaison - problème typique de correspondance de problème maximum
Optimisation des combinaisons - Problème typique - Problème d'allocation secondaire
Combinaison d'optimisation-problème typique-problème de chemin le plus court
Optimisation combinée - problème typique d'enchères combinées
Combinaison d'optimisation-problème typique de couverture d'agrégat
Problème de correspondance typique de problème-poids par optimisation de combinaison
Problème d'optimisation de combinaison-problème typique de placement des installations
Optimisation de la combinaison - problème typique de l'atelier de travail
Optimisation de la combinaison - problème typique - problème de coupe maximale
Optimisation de combinaison - Problème typique - Problème de vendeur circulaire
Problème d'ordonnancement de travail-problème typique d'optimisation de combinaison
Combinaison optimisation-problème typique-problème d'ensemble stable maximum
Optimisation de combinaison-problème typique-problème de livraison postale chinoise
Optimisation des combinaisons - Problème typique - Problème d'itinéraire de transport (optimisation de la livraison)
Optimisation des combinaisons - Problème typique - Problème de placement des installations sans contrainte de capacité
Problème d'optimisation de la combinaison - coupe minimale