python - 使用 Pulp 解决线性规划 python 问题
问题描述
基本上我试图让每个目的地只有一个来源所有目的地必须只有一个来源并且并非所有来源都必须使用我希望有人可以帮助我,我知道这不是正确的方式,但我得到了什么
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))
解决方案
我认为你非常接近你想要的,但你有一些问题。首先,您定义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。但是在您的问题陈述中,您说:
所有目的地都必须只有一个来源,并非必须使用所有来源
但是有了这个约束,你就会强制使用每个来源。消除此约束,您的问题可以解决:
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,但希望强制目的地仅接收来自单个来源的输入 - 那么您需要为每个“路线”添加二进制变量以控制每个路线是开放的。然后,您将设置一个约束,即数量变量只能在这些二进制变量为真时为非零,然后您可以将这些二进制变量的总和限制为每个目标为 == 1。
推荐阅读
- spring-boot - 使用 Drools ui 设计器的 Spring Boot
- r - 查找字符串是否包含给定关键字集中的单词的方法
- android - 您可以在 android 中自定义 google maps 中的 ui 轮流导航活动吗?
- amazon-ec2 - 在 EC2-Fleet 上设置 Jenkins 环境变量的问题
- nfs - 使用 UBoot 从 NFS 服务器启动
- npm - 如何使用 forever.json 运行 npm 脚本?
- sql-server - 要选择的 Sql 条目
- docker - TestCafe docker - 对在主机 localhost 上运行的应用程序运行测试
- markdown - 将 Rmd 中的目录和从属关系列表分离为 PDF 文件
- sql - 如何从日期列中获取上个月的最后日期?