Optimisation de la combinaison - problème typique - problème de débit maximal

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

Problème de débit maximum

Quand $ e_ {ij} = (v_i, v_j) \ in E $ a une capacité de $ c_ {ij} $ de chaque côté du graphe $ G = (V, E) $, le point de départ $ v_s \ in V $ (source) Trouvez le flux qui maximise le flux total depuis le point final $ v_t \ in V $ (sink).

Méthode d'exécution

usage


Signature: nx.maximum_flow(G, s, t, capacity='capacity', flow_func=None, **kwargs)
Docstring:
Find a maximum single-commodity flow.

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)[0]
t = nx.maximum_flow(g, 5, 2)
pos = networkx_draw(g)
nx.draw_networkx_edges(g, pos, width=3, edgelist
  =[(k1, k2) for k1, d in t[1].items() for k2, v in d.items() if v])
plt.show()
for i, d in t[1].items():
    for j, f in d.items():
        if f: print((i, j), f)

résultat


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

mxf2.png

python


# pandas.DataFrame
from ortoolpy.optimization import MaximumFlow
MaximumFlow('data/edge0.csv', 5, 2)[1]
node1 node2 capacity weight flow
0 0 2 2 4 2
1 0 3 2 2 2
2 0 4 2 2 2
3 0 5 2 4 2
4 1 2 2 5 2
5 1 5 2 5 2
6 2 3 2 3 2
7 4 5 2 1 2

python


#Données aléatoires
import networkx as nx, matplotlib.pyplot as plt
from ortoolpy import networkx_draw
g = nx.random_graphs.fast_gnp_random_graph(10, 0.3, 1)
for i, j in g.edges():
    g.adj[i][j]['capacity'] = 1
t = nx.maximum_flow(g, 5, 6)
pos = networkx_draw(g, nx.spring_layout(g))
nx.draw_networkx_edges(g, pos, width=3, edgelist
  =[(k1, k2) for k1, d in t[1].items() for k2, v in d.items() if v])
plt.show()

mxf.png

Les données

Recommended Posts

Optimisation de la combinaison - problème typique - problème de débit maximal
Optimisation de combinaison - problème typique de correspondance de problème maximum
Optimisation de la combinaison - problème typique - problème de coupe maximale
Combinaison optimisation-problème typique-problème d'ensemble stable maximum
Optimisation de la combinaison - problème typique - problème de flux de coût minimal
Optimisation de combinaison - problème typique de problème de sac à dos
Optimisation de combinaison - problème typique - problème de couverture de vertex minimum
Problème de correspondance stable aux problèmes typique d'optimisation de combinaison
Problème d'optimisation de combinaison-problème typique d'emballage de bac
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 combinaison - Problème typique - Problème de vendeur circulaire
Problème d'ordonnancement de travail-problème typique d'optimisation de combinaison
Optimisation de combinaison - problème typique - problème d'arborescence de surface minimale
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)
Problème d'optimisation de la combinaison - coupe minimale
Optimisation des combinaisons - Problème typique - Problème de placement des installations sans contrainte de capacité
Combinaison de problèmes typiques d'optimisation et comment le faire