0

我正在尝试使用 networkX 库解决交通问题。由于我的需求和供应值是浮动的，我的问题似乎无法通过 networkX 包解决？请参阅第 377 页上的文档。 https://networkx.org/documentation/stable/_downloads/networkx_reference.pdf

有什么解决方法吗？我的问题是由于舍入错误造成的，因为我的浮点数非常小。

有没有其他支持浮点数的库来解决python中的最小成本流问题？

import networkx as nx

#inputdata
producerDict = {'p1': 3.88, 'p2': 4.3225, 'p3': 24.41575}
consumerDict = {'c1':46.63775, 'c2': 85.44925, 'c3': 71.92425, 'c4': 
84.1755}

totalDemand = sum(consumerDict.values())
totalSupply = sum(producerDict.values())

#graph
G = nx.DiGraph()
G.add_edge("C1", "P1", weight=3)
G.add_edge("C1", "P2", weight=1)
G.add_edge("C1", "P3", weight=4)

G.add_edge("C2", "P1", weight=2)
G.add_edge("C2", "P2", weight=4)
G.add_edge("C2", "P3", weight=5)

G.add_edge("C3", "P1", weight=6)
G.add_edge("C3", "P2", weight=2)
G.add_edge("C3", "P3", weight=2)

G.add_edge("C4", "P1", weight=1)
G.add_edge("C4", "P2", weight=6)
G.add_edge("C5", "P3", weight=3)

#balancing the problem as demand > supply
newConsumerDict = {}
for consumer, demand in consumerDict.items():
    newDemand = (demand / totalDemand) * totalSupply
    newConsumerDict[consumer] = newDemand


# this sum has to be equal to total supply which 
# is not the case due to rounding errors
print(sum(newConsumerDict.values()))

flowCost, flowDict = nx.network_simplex(G)

干杯

4

1 回答 1

1

您链接到的文档说：

如果边缘权重或需求是浮点数（溢出和舍入错误可能导致问题），则不保证此算法有效。作为一种解决方法，您可以通过将相关边缘属性乘以一个方便的常数因子（例如 100）来使用整数。

我对此的解释是，可能存在舍入误差是一个问题的情况。我希望该算法很可能会正常工作，除非您有很多仅在 10^{-10} 大小上不同的权重。但出于实际目的，我希望您只需将权重乘以 100（或 100000）然后取整数部分就可以了。

于 2021-05-31T11:23:25.150 回答