Bereiten Sie vor, was Sie brauchen.

python

import random, numpy as np, pandas as pd, networkx as nx, matplotlib.pyplot as plt
from itertools import chain, combinations
from pulp import *

def draw(g):
    """Zeichnung"""
    nx.draw_networkx_labels(g, pos=pos)
    nx.draw_networkx_nodes(g, node_color='w', pos=pos)
    nx.draw_networkx_edges(g, pos=pos)
    plt.show()
def addvar(cnt=[0], *args, **kwargs):
    """Variablenerstellung"""
    cnt[0] += 1
    return LpVariable('v%d'%cnt[0], lowBound=0, *args, **kwargs)

Lassen Sie uns zufällig ein Problem erstellen. Die Nachfrage wurde nur zwischen einigen Knoten eingestellt.

python

n = 16 #Anzahl der Knoten
g = nx.random_graphs.fast_gnp_random_graph(n, 0.26, 8) #Graph
rn = g.nodes() #Knotenliste
pos = nx.spring_layout(g, pos={i:(i/4, i%4) for i in rn}) #Knotenposition
for i, j in g.edges():
    v = pos[i] - pos[j]
    g[i][j]['dist'] = np.sqrt(v.dot(v)) #Entfernung
dems = random.sample(list(combinations(rn, 2)), 10) #Nachfrage
draw(g)

Ich werde versuchen, den minimalen Gesamtflächenbaum zu finden.

python

h = nx.minimum_spanning_tree(g, 'dist')
draw(h)

Ich werde versuchen, es zu lösen.

python

rved = [(j, i) for i, j in g.edges()] #Rückseite
#Durchflussrate pro Bedarf
a = pd.DataFrame([(df, dt, ef, et, g.edge[ef][et]['dist'], addvar()) 
                  for df, dt in dems for ef, et in chain(g.edges(), rved)], 
                 columns=['DeFr', 'DeTo', 'EdFr', 'EdTo', 'Dist', 'Var'])
#Gibt an, ob eine Seite installiert werden soll
b = pd.DataFrame([(fr, to, g.edge[fr][to]['dist'], addvar(cat=LpBinary)) 
                  for fr, to in g.edges()], columns=['Fr', 'To', 'Dist', 'Var'])
res = [] #Lösung(Einrichtungskosten,Bequemlichkeit,Graph)
mxcst = 999 #Obergrenze für Installationskosten
while True:
    m = LpProblem() #Mathematisches Modell
    m += lpDot(a.Dist, a.Var) + lpDot(b.Dist, b.Var)*1e-6 #Zielfunktion(Bequemlichkeit)
    m += lpDot(b.Dist, b.Var) <= mxcst #Obergrenze für Installationskosten
    for _, r in a.iterrows():
        i, j = r.EdFr, r.EdTo
        if i > j: i, j = j, i
        #Installieren Sie, wenn der Durchfluss fließt
        m += r.Var <= lpSum(b.query('Fr==%s & To==%s'%(i,j)).Var)
    for (df, dt), c in a.groupby(('DeFr', 'DeTo')):
        for nd in rn:
            z = 1 if nd == df else -1 if nd == dt else 0
            #Flow-Speicher
            m += lpSum(c.query('EdFr == %s'%nd).Var) == \
                 lpSum(c.query('EdTo == %s'%nd).Var) + z
    m.solve() #Lösung
    if m.status != 1: break
    a['Val'] = a.Var.apply(lambda v: value(v)) #Ergebnis(Fließrate)
    b['Val'] = b.Var.apply(lambda v: value(v)) #Ergebnis(Ob installiert werden soll)
    cst = value(lpDot(b.Dist, b.Var)) #Einrichtungskosten
    val = value(m.objective) #Bequemlichkeit
    mxcst = cst - 1e-3 #Obergrenze für die nächsten Installationskosten
    h = nx.Graph()
    h.add_edges_from([(r.Fr, r.To) for _, r in b[b.Val == 1].iterrows()])
    res.append((cst, val, h))

Mal sehen, das Ergebnis. Je höher die Installationskosten sind, desto besser ist der Komfort.

python

plt.rcParams['font.family'] = 'IPAexGothic'
plt.plot([r[0] for r in res], [r[1] for r in res])
plt.xlabel('Einrichtungskosten')
plt.ylabel('Bequemlichkeit')

Dies ist die Grafik für den bequemsten Fall.

python

draw(res[0][2])

Ich habe versucht, eine GIF-Animation des Übergangs der Installationskosten zu erstellen.

das ist alles