使用 Pulp 解决线性规划 python 问题

Question

基本上我试图让每个目的地只有一个起点所有目的地必须只有一个来源并非所有来源都必须使用我希望有人能帮助我，我知道这不是正确的方法，但我得到的是

from pulp import*
import pandas as pd 
origin = ["a","b","c","d","e","f","g","h"]
destination = ["1","2","3","4","5","6","7","8","9","10"]


offer = {"a":3,"b":3,"c":3,"d":3,"e":3,"f":4,"g":3,"h":3}
demand = {"1":1,"2":1,"3":1,"4":1,"5":1,"6":1,"7":1,"8":1,"9":1,"10":1}
cost_to_send = { 
"a":{"1":1,"2":1,"3":1},
"b":{"2":1,"3":1,"9":1},
"c":{"5":1,"6":1,"7":1},
"d":{"7":1,"9":1,"10":1},
"e":{"3":1,"6":1,"8":1},
"f":{"1":1,"4":1,"7":1,"9":1},
"g":{"4":1,"5":1,"9":1},
"h":{"1":1,"4":1,"8":1}
}
prob = LpProblem("Exercise", LpMinimize)

Routes = [(i,j) for i in origin for j in destination]

quantity = LpVariable.dicts("quantity de envio",(origin,destination),0)

prob += lpSum(quantity[i][j]*cost_to_send[i][j] for (i,j) in Routes)

for j in destination:
    prob += lpSum(quantity[i][j] for i in origin) == demand[j]

for i in origin:
    prob += lpSum(quantity[i][j] for j in destination) == 1

prob.solve()
print("Status: ", LpStatus[prob.status])

for v in prob.variables():
    if v.varValue > 0:
        print(v.name, "=", v.varValue)

print("Answer ", value(prob.objective))

Answer 1

我认为你非常接近你想要的，但你有一些问题。首先，您将 Routes 定义为所有可能的路线，而您只为某些路线定义了 cost_to_send。

假设成本已定义的路线是可行路线，您最好将 Routes 定义为：

Routes = [(i, j) for i in origin for j in destination if j in cost_to_send[i]]

我看到的另一个问题是您的第二组约束：

for i in origin:
    prob += lpSum(quantity[i][j] for j in destination) == 1

这是说对于每个起点，到所有目的地的总流量必须为 1。但是在您的问题陈述中您说：

all destinations must have only one source and not all origins necessarily have to be used

但是有了这个约束，你就强制使用每个原点。删除此约束，您的问题将得到解决：

from pulp import *
import pandas as pd 
origin = ["a","b","c","d","e","f","g","h"]
destination = ["1","2","3","4","5","6","7","8","9","10"]


offer = {"a":3,"b":3,"c":3,"d":3,"e":3,"f":4,"g":3,"h":3}
demand = {"1":1,"2":1,"3":1,"4":1,"5":1,"6":1,"7":1,"8":1,"9":1,"10":1}
cost_to_send = { 
"a":{"1":1,"2":1,"3":1},
"b":{"2":1,"3":1,"9":1},
"c":{"5":1,"6":1,"7":1},
"d":{"7":1,"9":1,"10":1},
"e":{"3":1,"6":1,"8":1},
"f":{"1":1,"4":1,"7":1,"9":1},
"g":{"4":1,"5":1,"9":1},
"h":{"1":1,"4":1,"8":1}
}
prob = LpProblem("Exercise", LpMinimize)

# Routes = [(i,j) for i in origin for j in destination]
Routes = [(i, j) for i in origin for j in destination if j in cost_to_send[i]]

quantity = LpVariable.dicts("quantity de envio",Routes,0)

prob += lpSum(quantity[(i,j)]*cost_to_send[i][j] for (i,j) in Routes)

for j in destination:
    prob += lpSum(quantity[(i,j)] for i in origin if (i,j) in Routes) == demand[j]

#for i in origin:
#    prob += lpSum(quantity[i][j] for j in destination) == 1

prob.solve()
print("Status: ", LpStatus[prob.status])

for v in prob.variables():
    if v.varValue > 0:
        print(v.name, "=", v.varValue)

print("Answer ", value(prob.objective))


Returns:

Status:  Optimal
quantity_de_envio_('a',_'1') = 1.0
quantity_de_envio_('a',_'2') = 1.0
quantity_de_envio_('a',_'3') = 1.0
quantity_de_envio_('b',_'9') = 1.0
quantity_de_envio_('c',_'5') = 1.0
quantity_de_envio_('c',_'6') = 1.0
quantity_de_envio_('d',_'10') = 1.0
quantity_de_envio_('f',_'4') = 1.0
quantity_de_envio_('f',_'7') = 1.0
quantity_de_envio_('h',_'8') = 1.0
Answer  10.0

请注意，如果您希望给定目的地的需求大于 1，但又想强制目的地仅接收来自单个来源的输入 - 那么您需要添加 binary每个个变量'Route'来控制每条路由是否打开。然后，您将设置一个约束条件，如果这些二进制变量为真，则数量变量只能为非零，然后您可以将这些二进制变量的总和限制到每个目的地 == 1.

使用 Pulp 解决线性规划 python 问题

Solve linear programming python problem using Pulp

python

pandas

linear-programming

pulp