我想我遇到了一个Milp问题，但我不确定。
简化形式的问题是：
有3个城市的材料(卡车(供应商。真正的问题是30家供应商和100个城市...
供应能力：a：1;乙：2;C：3.
城市需求：a：2;乙：3;c：1
距离供应商(城市(：
- 答(甲：2;乙：4;c：6(
- b(a：4;乙：2;c：4(
- c(a：6;乙：4;c：2(
每个容量和需求
都是这样
Sa1 - Ca2
Sb2 - Cb3 Sc3
- Cc1
目标它优化了，但有一个(魔鬼(条件：
- 每个城市只有一个供应商。
尽管这个问题是用基本的线性规划解决的简单问题。
在这种情况下，我认为这可以通过混合整数线性规划 - MILP 来解决。 但不弄清楚如何使用MILP方法和Pulp(python模块(解决这个问题。
如果有人可以帮助我
谢谢！
我的第一次尝试
from scipy.optimize import linprog
c = [2,4,6,4,2,4,6,4,2]
Ae = [[1,1,1,0,0,0,0,0,0],
[0,0,0,1,1,1,0,0,0],
[0,0,0,0,0,0,1,1,1],
[1,0,0,1,0,0,1,0,0],
[0,1,0,0,1,0,0,1,0],
[0,0,1,0,0,1,0,0,1],
]
be = [1,2,3,2,3,1]
x0_bounds = (0,None)
x1_bounds = (0,None)
x2_bounds = (0,None)
x3_bounds = (0,None)
x4_bounds = (0,None)
x5_bounds = (0,None)
x6_bounds = (0,None)
x7_bounds = (0,None)
x8_bounds = (0,None)
sol = linprog(c, A_eq= Ae, b_eq = be, bounds = ((x0_bounds,x1_bounds,x2_bounds,x3_bounds,x4_bounds,x5_bounds,x6_bounds,x7_bounds,x8_bounds)) )
print(sol)
fun: 18.0
message: 'Optimization terminated successfully.'
nit: 10
slack: array([], dtype=float64)
status: 0
success: True
x: array([1., 0., 0., 0., 2., 0., 1., 1., 1.])
Process finished with exit code 0
我已经完成了！ 来自YouTube的Caylie Cincera的视频对我帮助很大。问题的插图。每个地点最多只能接收一个供应商。 https://imgur.com/O2CNa9M
from pulp import *
#Pulp way to start a LP problem
prob = LpProblem("testpulp",LpMinimize)
#The 9 Arcs Origin and destiny
x1 = LpVariable("x1_11",0,None,LpInteger)
x2 = LpVariable("x2_12",0,None,LpInteger)
x3 = LpVariable("x3_13",0,None,LpInteger)
x4 = LpVariable("x4_21",0,None,LpInteger)
x5 = LpVariable("x5_22",0,None,LpInteger)
x6 = LpVariable("x6_23",0,None,LpInteger)
x7 = LpVariable("x7_31",0,None,LpInteger)
x8 = LpVariable("x8_32",0,None,LpInteger)
x9 = LpVariable("x9_33",0,None,LpInteger)
#Auxiliar Variables z y and k
z1 = LpVariable("z1",0,1,LpBinary)
z2 = LpVariable("z2",0,1,LpBinary)
z3 = LpVariable("z3",0,1,LpBinary)
y1 = LpVariable("y1",0,1,LpBinary)
y2 = LpVariable("y2",0,1,LpBinary)
y3 = LpVariable("y3",0,1,LpBinary)
k1 = LpVariable("k1",0,1,LpBinary)
k2 = LpVariable("k2",0,1,LpBinary)
k3 = LpVariable("k3",0,1,LpBinary)
#Objective Function
prob += 2*x1 + 4*x2+ 6*x3 + 4*x4 + 2*x5 + 4*x6 + 6*x7 + 4*x8 + 2*x9, "fobj"
#Constraints
#Supply constraints
prob += x1 + x2 + x3 == 1, "m1"
prob += x4 + x5 + x6 == 2, "m2"
prob += x7 + x8 + x9 == 3, "m3"
#Demand constraints
prob += x1 + x4 + x7 == 2, "d1"
prob += x2 + x5 + x8 == 3, "r2"
prob += x3 + x6 + x9 == 1, "r4"
#Trick to force unique supplier for each location
prob += x1 <= 2*y1, "yx1"
prob += x4 <= 2*y2, "yx2"
prob += x7 <= 2*y3, "yx3"
prob += x2 <= 3*z1, "zx1"
prob += x5 <= 3*z2, "zx2"
prob += x8 <= 3*z3, "zx3"
prob += x3 <= 1*k1, "kx1"
prob += x6 <= 1*k2, "kx2"
prob += x9 <= 1*k3, "kx3"
prob += y1 + y2 + y3 == 1, "yk"
prob += z1 + z2 + z3 == 1, "zk"
prob += k1 + k2 + k3 == 1, "kk"
prob.solve()
for v in prob.variables():
print(v.name, " = ", v.varValue)
print("Total Profit: ",value(prob.objective))
#The "optimal" solution of this problem is the unique solution
#The hard part is to force unique supplier for each location
输出：
k1 = 1.0
k2 = 0.0
k3 = 0.0
x1_11 = 0.0
x2_12 = 0.0
x3_13 = 1.0
x4_21 = 2.0
x5_22 = 0.0
x6_23 = 0.0
x7_31 = 0.0
x8_32 = 3.0
x9_33 = 0.0
y1 = 0.0
y2 = 1.0
y3 = 0.0
z1 = 0.0
z2 = 0.0
z3 = 1.0
Total Profit: 26.0
Process finished with exit code 0