如何使用纸浆解决网络流量问题？

Question

考虑到以下网络流量模型，并假设有1000名驾驶员，我们如何通过分配使用每个可能路线的驾驶员数量来计算模型的社会最优值。

我知道这个问题可以用线性规划来解决。但是，我的代码被破坏了

from pulp import *

prob = LpProblem("Network",LpMinimize)
a = LpVariable('A',lowBound=0,upBound=None,cat=LpInteger)
b = LpVariable('B',lowBound=0,upBound=None,cat=LpInteger)
c = LpVariable('C',lowBound=0,upBound=None,cat=LpInteger)

# objective function
prob +=  a * (((a+b)/100) + 20 + 5) + b * (((a+b)/100) + 10 + ((b+c)/100)) + c * (10 + 20 + ((b+c)/100))

#constraints
prob += a + b + c == 1000

prob.solve()

print("Status: ", LpStatus[prob.status])
for v in prob.variables():
    print(v.name,'=',v.varValue)

错误：

TypeError: Non-constant expressions cannot be multiplied

解决方案：
ABCF=201
ABEF=798
ADEF=1

Answer 1

删除非线性项的一个选项是，将非线性成本弧上的整数决策变量替换为该弧上每个可能数量的驱动因素的二进制决策变量（将严重扩展-但对于这个小问题没有问题）

下面给出了示例代码。请注意，此返回的解决方案与您在问题中给出的解决方案不同（我得到ABCF=250，ABEF=750），我得出此解决方案的目标值为29375，而您所引用的解决方案的成本略高于29399-除非我误解了

from pulp import *

prob = LpProblem("Network",LpMinimize)

nodes = ['A', 'B', 'C', 'D', 'E', 'F']

arc_costs = [[('A', 'D'), 10],
             [('B', 'C'), 20],
             [('B', 'E'), 10],
             [('D', 'E'), 20],
             [('C', 'F'), 5]]

ab_cost = LpVariable('ab_cost', lowBound=0, upBound=None, cat=LpContinuous)
ef_cost = LpVariable('ef_cost', lowBound=0, upBound=None, cat=LpContinuous)

# Binary variable == 1 iff number of drivers along arc = index value
ab_flow = LpVariable.dicts('ab_flow', range(1001), cat=LpBinary)
ef_flow = LpVariable.dicts('ef_flow', range(1001), cat=LpBinary)

# Variables to contain the selected Number of drivers
ab_flow_val = LpVariable('ab_flow_val', lowBound=0, upBound=None, cat=LpContinuous)
ef_flow_val = LpVariable('ef_flow_val', lowBound=0, upBound=None, cat=LpContinuous)


arc_flow_val = LpVariable.dicts('arc_flow_val', [i[0] for i in arc_costs],
                             lowBound=0, upBound=None, cat=LpInteger)

# objective function
prob +=  lpSum([arc_flow_val[i]*j for i, j in arc_costs] + ab_cost + ef_cost)

#constraints

# costs for the non-linear costed arcs:
prob += ab_cost == lpSum([ab_flow[x]*((x**2)/100) for x in range(1001)])
prob += ef_cost == lpSum([ef_flow[x]*((x**2)/100) for x in range(1001)])

# only one of binary variables can be true for each of the non-linear arcs
prob += lpSum([ab_flow[i] for i in range(1001)]) == 1
prob += lpSum([ef_flow[i] for i in range(1001)]) == 1

# set flow values from the binary variables:
prob += ab_flow_val == lpSum([ab_flow[i]*i for i in range(1001)])
prob += ef_flow_val == lpSum([ef_flow[i]*i for i in range(1001)])

# 1000 must leave and 1000 must arrive
prob += ab_flow_val + arc_flow_val[('A', 'D')] == 1000
prob += arc_flow_val[('C', 'F')] + ef_flow_val == 1000

# Non terminal nodes must have flow balance
for n in nodes[1:-1]:
    if n == 'B':
        prob += ab_flow_val == arc_flow_val[('B', 'C')] + arc_flow_val[('B', 'E')]
    elif n == 'E':
        prob +=  arc_flow_val[('B', 'E')] + arc_flow_val[('D', 'E')] == ef_flow_val
    else:
        # flow into node == flow out of node
        prob += lpSum([arc_flow_val[i] for i in arc_flow_val.keys() if i[0] == n]) == lpSum([arc_flow_val[j] for j in arc_flow_val.keys() if j[1] == n])

prob.solve()

print("Status: ", LpStatus[prob.status])
for v in prob.variables():
    if ('_val' in v.name) or ('cost' in v.name):
        print(v.name,'=',v.varValue)