algorithm - Python中的运输算法

Question

在 google 上进行了大量搜索后，我无法在 python 中找到任何交通算法求解器。我希望在 Scipy 中找到一些东西，但没有用。有人可以指导我找到正确的来源吗？

不知道在哪里发布这个问题，我知道一些策展人会向我索要代码或说这不是一个合适的地方。在那种情况下，请不要忘记指引我到正确的地方。

我的问题:

Max(Sum_{i,j}( Cij*Xij) )

x11 + x12 + x13 = D1
X21 + X22 + x23 = D2
X11<10
X23 <100

我通常会有 100,000 个汇(创造需求)和大约 1000 个源(供应需求)。

Answer 1

我将在 pulp 的帮助下使用线性规划 技术，一个 python 线性编程 API。与 pulp 一起分发的默认求解器是 cbc (你可以切换到商业的)。

我只是展示一些代码，它适合您的问题/问题描述((“玩具问题”)。在 pulp 的 github 存储库中有一些示例。

# Import PuLP modeler functions
from pulp import *

# INSTANCE
EDGES = [ (0,10), (0,20), (0,50), (0,30), (0,10), (0,40) ] # lower/upper flow
COSTS = [0.3, 0.7, 0.2, 0.6, 0.2, 0.5]
D1, D2 = [24, 10]

# MODEL
prob = LpProblem("Problem",LpMaximize)
# VARS
x11, x12, x13 = LpVariable("x11", *EDGES[0]), LpVariable("x12", *EDGES[1]), LpVariable("x13", *EDGES[2])
x21, x22, x23 = LpVariable("x21", *EDGES[3]), LpVariable("x22", *EDGES[4]), LpVariable("x23", *EDGES[5])
# OBJECTIVE FUNCTION -> added before constraints => important ,
prob += lpDot(COSTS, [x11,x12,x13,x21,x22,x23]), "Costs"
# CONSTRAINTS
prob += x11 + x12 + x13 == D1
prob += x21 + x22 + x23 == D2

# SOLVE
status = prob.solve()

# PRINT SOLUTION
print LpStatus[status]
for var in [x11,x12,x13]:
    print value(var)
print
for var in [x21,x22,x23]:
    print value(var)
print("Total Costs = ", value(prob.objective))

输出:

Optimal
4.0
20.0
0.0

10.0
0.0
0.0
('Total Costs = ', 21.2)