Как решить эту проблему MILP с модулем Pulp Python?

Question

Я думаю, что столкнулся с проблемой Милпа, но я не уверен.

Проблема в упрощенной форме:Есть 3 поставщика материалов (грузовых автомобилей) для 3 городов.Настоящая проблема - 30 поставщиков и 100 городов ...Емкость поставщиков: а: 1;Би 2;C: 3.Города Спрос: а: 2;б: 3;C: 1Расстояния Поставщик (Города):

• a (a: 2; b: 4; c: 6)
• b (a: 4; b: 2; c: 4)
• с (а: 6; б: 4; с: 2)

вот так с каждым Capacity и Demand

Sa1 - Ca2Sb2 - Cb3Sc3 - 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

Answer 1

Я сделал!Видео Caylie Cincera с youtube мне очень помогают.Иллюстрация проблемы.Каждое местоположение может получить не более одного поставщика.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