[PYTHON] Kombinationsoptimierung - typisches Problem - Mindestkostenflussproblem

Typisches Problem und Ausführungsmethode

Problem des minimalen Kostenflusses

In dem gerichteten Graphen $ G = (V, E) $ wird angesichts der Kapazität und des Gewichts jeder Seite und der Nachfrage nach Knoten die Summe der Gewichte für die Durchflussrate jeder Seite minimiert, ohne die Kapazität jeder Seite zu überschreiten. Finde den Fluss.

• An jedem Knoten entspricht "Zufluss - Abfluss" der Nachfrage.
• Wenn die Nachfrage negativ ist, repräsentiert sie das Angebot.
• Die Summe der Anforderungen aller Knoten muss 0 sein.

Ausführungsmethode

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

#CSV-Daten
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)

Ergebnis

(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

#Zufällige Daten
import networkx as nx
g = nx.fast_gnp_random_graph(8, 0.2, 1, True)
g.nodes[1]['demand'] = -2 #Liefern
g.nodes[7]['demand'] = 2 #Nachfrage
g.adj[2][7]['capacity'] = 1 #Kapazität
result = nx.min_cost_flow(g)
for i, d in result.items():
    for j, f in d.items():
        if f: print((i, j), f)

Ergebnis

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

Daten

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