壁虎优化
Gekko optimization
我正在解决这个优化问题，我需要弄清楚我需要开设多少个配送中心才能满足公司 12 个设施的需求，而 最小化运输成本。运输成本只是配送中心之间的距离乘以每英里的成本，但是在这个问题中，每英里的成本是一美元。我有 5 个选择，分别是 Boston、Nashua、Providence、Springfield 和 Worcester，这 5 个是 12 个公司设施的一部分。
我解决了这个问题并得到了正确的答案，但后来我尝试向同一代码添加两个约束，但我得到的答案不正确。另外两个限制是，从配送中心 (DC) 到其他设施（客户）的平均距离必须小于 60 英里；第二个约束是 50 英里以内的客户百分比必须大于 80% (0.8)。我知道这个问题的答案，费用必须是 66,781 美元，平均客户距离是 15 英里 并且 50 英里范围内的客户百分比为 90%。 我的代码的输出是成本是66289美元美元，平均客户距离是15.36英里并且 50 英里范围内的客户百分比是 179%，这没有意义。
你能帮我弄清楚为什么我得到一个奇怪的输出吗？提前致谢。
from gekko import GEKKO
import numpy as np
import pandas as pd
import math
m = GEKKO(remote=False) #So that it solves the problem locally
m.options.SOLVER = 1 #MILP
varx = [[0 for col in range(12)] for row in range(5)] #Creates an empty list
for i in range (5):
for j in range (12):
varx[i][j] = m.Var(lb = 0, integer = True)
varx = np.array(varx)
varxt = np.transpose(varx)
vary = np.empty([]) #Creates an empty array
for i in range(5):
vary = np.append(vary, m.Var(lb = 0, ub = 1, integer = True)) #Yes/No variables
vary = vary[1:13]
dists = np.array([[0 , 93, 69, 98, 55, 37, 128, 95, 62, 42, 82, 34], #Boston
[37, 65, 33, 103, 20, 0, 137, 113, 48, 72, 79, 41], #Nashua
[42, 106, 105, 73, 92, 72, 94, 57, 104, 0, 68, 38], #Providence
[82, 59, 101, 27, 93, 79, 63, 57, 127, 68, 0, 47], #Springfield
[34, 68, 72, 66, 60, 41, 98, 71, 85, 38, 47, 0]]) #Worcester
max_dist = 60 #Max average distance (in miles)
min_pct = 0.8 #Min percent of demand within 50 miles
aij = np.zeros((5, 12)) #Creates an empty array
for i in range (5):
for j in range (12):
if dists[i][j] <= 50:
aij[i][j] = 1
else:
aij[i][j] = 0 #Creates a 0s and 1s array. If the distance to a costumer
#is less than 50, then the matrix element is 1, it is zero
#otherwise
dem_consts = np.array([425, 12, 43, 125, 110, 86, 129, 28, 66, 320, 220, 182])
fixd_cost = 10000
sum1 = np.sum(np.multiply(varx, dists))
sum2 = np.sum(vary*fixd_cost)
z = sum1 + sum2
tot_dem = np.sum(dem_consts)
M = tot_dem
m.Minimize(z)
for i in range(12):
m.Equation(np.sum(varxt[i, :]) >= dem_consts[i]) #Demand constraints
for i in range(5):
m.Equation(np.sum(varx[i, :]) <= 2000) #Capacity constraints
m.Equation(np.sum(varx[i, :]) <= M*vary[i]) #Enforces 0 or 1 value
m.Equation(np.sum(vary[:]) >= 1)
di_sum = np.sum(np.multiply(varx, dists))
di_sumw = di_sum/ tot_dem
m.Equation(di_sumw <= max_dist) #Average (demand) weighted distance from DC to customer
a_sum = np.sum(np.multiply(varx, aij))
a_sumw = a_sum/tot_dem
m.Equation(a_sumw >= min_pct) #Percent of demand that is within 50 miles
m.solve(disp = False)
p1 = np.zeros((5, 12))
for i in range (5):
for j in range (12):
p1[i][j] = varx[i][j].value[0]
p1t = np.transpose(p1)
p2 = np.zeros((5, ))
for i in range(5):
p2[i] = vary[i].value[0]
mad1 = np.sum(np.multiply(p1, dists))
mad2 = mad1/tot_dem
mpi1 = np.sum(np.multiply(p1, aij))
mpi2 = mpi1/tot_dem
tot1 = np.sum(np.multiply(p1, dists))
tot2 = np.sum(p2)*fixd_cost
tot = tot1 + tot2
print('The minimum cost is:' +str(tot))
print('Average customer distance:' +str(mad2))
print('Percent of customers <= 50 miles:' +str(mpi2))
dc = np.array(['Boston', 'Nashua', 'Providence', 'Springfield', 'Worcester'])
cities = ['Boston', 'Brattleboro', 'Concord', 'Hartford', 'Manchester', 'Nashua',
'New Haven', 'New London', 'Portsmouth', 'Providence', 'Springfield', 'Worcester']
data = {cities[0]: p1t[0], cities[1]: p1t[1], cities[2]: p1t[2], cities[3]: p1t[3],
cities[4]: p1t[4], cities[5]: p1t[5], cities[6]: p1t[6], cities[7]: p1t[7],
cities[8]: p1t[8], cities[9]: p1t[9], cities[10]: p1t[10], cities[11]: p1t[11]}
df = pd.DataFrame(data, index = dc)
df
当您设置 m.solve(disp=True) 时，解算器发出一条消息，它在 500 次迭代时提前终止。它 returns 一个可行的整数解决方案，但它可能不是最好的解决方案。
Warning: best integer solution returned after maximum MINLP iterations
Adjust minlp_max_iter_with_int_sol 500 in apopt.opt to change limit
Successful solution
---------------------------------------------------
Solver : APOPT (v1.0)
Solution time : 1.3654 sec
Objective : 66829.
Successful solution
---------------------------------------------------
The minimum cost is:66829.0
Average customer distance:15.3659793814433
Percent of customers <= 50 miles:1.7943871706758305
如果添加求解器选项：
m.solver_options = ['minlp_gap_tol 1.0e-2',\
'minlp_maximum_iterations 10000',\
'minlp_max_iter_with_int_sol 5000']
objective函数改进为66285:
Successful solution
---------------------------------------------------
Solver : APOPT (v1.0)
Solution time : 1.7178 sec
Objective : 66285.
Successful solution
---------------------------------------------------
The minimum cost is:66285.0
Average customer distance:20.781786941580755
Percent of customers <= 50 miles:1.9873997709049256
是否应该改为 <= 50 英里的客户百分比？：mpi3 = mpi1/np.sum(p1) 平均距离是？：mad3 = mad1/np.sum(p1)。这给出了 <= 50 英里的客户比例等于 89.94%：
Percent of customers <= 50 miles (mpi3):0.8994297563504406
新的平均距离是：
Average customer distance (mad3):9.405132192846034
这里是一个修改后的脚本，它使用 gekko 数组和 gekko 求和函数，因此更加高效。
from gekko import GEKKO
import numpy as np
import pandas as pd
import math
m = GEKKO(remote=False) #So that it solves the problem locally
m.options.SOLVER = 1 #MILP
varx = m.Array(m.Var,(5,12),lb=0,integer=True)
vary = m.Array(m.Var,5,lb=0,ub=1,integer=True)
dists = np.array([[0 , 93, 69, 98, 55, 37, 128, 95, 62, 42, 82, 34], #Boston
[37, 65, 33, 103, 20, 0, 137, 113, 48, 72, 79, 41], #Nashua
[42, 106, 105, 73, 92, 72, 94, 57, 104, 0, 68, 38], #Providence
[82, 59, 101, 27, 93, 79, 63, 57, 127, 68, 0, 47], #Springfield
[34, 68, 72, 66, 60, 41, 98, 71, 85, 38, 47, 0]]) #Worcester
max_dist = 60 #Max average distance (in miles)
min_pct = 0.8 #Min percent of demand within 50 miles
#Creates a 0s and 1s array. If the distance to a costumer
#is less than 50, then the matrix element is 1, it is zero otherwise
aij = [[1 if dists[i,j]<=50 else 0 for j in range(12)] for i in range(5)]
dem_consts = np.array([425, 12, 43, 125, 110, 86, 129, 28, 66, 320, 220, 182])
fixd_cost = 10000
sum1 = np.sum(np.multiply(varx, dists))
sum2 = np.sum(vary*fixd_cost)
z = sum1 + sum2
tot_dem = np.sum(dem_consts)
M = tot_dem
m.Minimize(z)
for j in range(12):
m.Equation(m.sum(varx[:,j]) >= dem_consts[j]) #Demand constraints
for i in range(5):
m.Equation(m.sum(varx[i,:]) <= 2000) #Capacity constraints
m.Equation(m.sum(varx[i,:]) <= M*vary[i]) #Enforces 0 or 1 value
m.Equation(m.sum(vary) >= 1)
di_sum = np.sum(np.multiply(varx, dists))
di_sumw = di_sum/ tot_dem
m.Equation(di_sumw <= max_dist) #Average (demand) weighted distance from DC to customer
a_sum = np.sum(np.multiply(varx, aij))
a_sumw = m.Intermediate(a_sum/tot_dem)
m.Equation(a_sumw >= min_pct) #Percent of demand that is within 50 miles
m.solver_options = ['minlp_gap_tol 1.0e-2',\
'minlp_maximum_iterations 10000',\
'minlp_max_iter_with_int_sol 5000']
m.solve(disp = True)
p1 = np.zeros((5, 12))
for i in range (5):
for j in range (12):
p1[i][j] = varx[i][j].value[0]
p1t = np.transpose(p1)
p2 = np.zeros(5)
for i in range(5):
p2[i] = vary[i].value[0]
mad1 = np.sum(np.multiply(p1, dists))
mad2 = mad1/tot_dem
mad3 = mad1/np.sum(p1)
mpi1 = np.sum(np.multiply(p1, aij))
mpi2 = mpi1/tot_dem
mpi3 = mpi1/np.sum(p1)
tot1 = np.sum(np.multiply(p1, dists))
tot2 = np.sum(p2)*fixd_cost
tot = tot1 + tot2
print(p1)
print(p2)
print('The minimum cost is:' +str(tot))
print('Average customer distance (mad2):' +str(mad2))
print('Average customer distance (mad3):' +str(mad3))
print('Percent of customers <= 50 miles (mpi2):' +str(mpi2))
print('Percent of customers <= 50 miles (mpi3):' +str(mpi3))
dc = np.array(['Boston', 'Nashua', 'Providence', 'Springfield', 'Worcester'])
cities = ['Boston', 'Brattleboro', 'Concord', 'Hartford', 'Manchester', 'Nashua',
'New Haven', 'New London', 'Portsmouth', 'Providence', 'Springfield', 'Worcester']
data = {cities[0]: p1t[0], cities[1]: p1t[1], cities[2]: p1t[2], cities[3]: p1t[3],
cities[4]: p1t[4], cities[5]: p1t[5], cities[6]: p1t[6], cities[7]: p1t[7],
cities[8]: p1t[8], cities[9]: p1t[9], cities[10]: p1t[10], cities[11]: p1t[11]}
df = pd.DataFrame(data, index = dc)
df
解决方法如下：
[[1102. 0. 43. 0. 110. 86. 0. 0. 66. 0. 0. 182.]
[ 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
[ 0. 0. 0. 0. 0. 0. 0. 28. 0. 495. 0. 0.]
[ 0. 12. 0. 125. 0. 0. 129. 0. 0. 0. 1480. 0.]
[ 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]]
[1. 0. 1. 1. 0.]
The minimum cost is:66285.0
Average customer distance (mad2):20.781786941580755
Average customer distance (mad3):9.405132192846034
Percent of customers <= 50 miles (mpi2):1.9873997709049256
Percent of customers <= 50 miles (mpi3):0.8994297563504406
我正在解决这个优化问题，我需要弄清楚我需要开设多少个配送中心才能满足公司 12 个设施的需求，而 最小化运输成本。运输成本只是配送中心之间的距离乘以每英里的成本，但是在这个问题中，每英里的成本是一美元。我有 5 个选择，分别是 Boston、Nashua、Providence、Springfield 和 Worcester，这 5 个是 12 个公司设施的一部分。
我解决了这个问题并得到了正确的答案，但后来我尝试向同一代码添加两个约束，但我得到的答案不正确。另外两个限制是，从配送中心 (DC) 到其他设施（客户）的平均距离必须小于 60 英里；第二个约束是 50 英里以内的客户百分比必须大于 80% (0.8)。我知道这个问题的答案，费用必须是 66,781 美元，平均客户距离是 15 英里 并且 50 英里范围内的客户百分比为 90%。 我的代码的输出是成本是66289美元美元，平均客户距离是15.36英里并且 50 英里范围内的客户百分比是 179%，这没有意义。
你能帮我弄清楚为什么我得到一个奇怪的输出吗？提前致谢。
from gekko import GEKKO
import numpy as np
import pandas as pd
import math
m = GEKKO(remote=False) #So that it solves the problem locally
m.options.SOLVER = 1 #MILP
varx = [[0 for col in range(12)] for row in range(5)] #Creates an empty list
for i in range (5):
for j in range (12):
varx[i][j] = m.Var(lb = 0, integer = True)
varx = np.array(varx)
varxt = np.transpose(varx)
vary = np.empty([]) #Creates an empty array
for i in range(5):
vary = np.append(vary, m.Var(lb = 0, ub = 1, integer = True)) #Yes/No variables
vary = vary[1:13]
dists = np.array([[0 , 93, 69, 98, 55, 37, 128, 95, 62, 42, 82, 34], #Boston
[37, 65, 33, 103, 20, 0, 137, 113, 48, 72, 79, 41], #Nashua
[42, 106, 105, 73, 92, 72, 94, 57, 104, 0, 68, 38], #Providence
[82, 59, 101, 27, 93, 79, 63, 57, 127, 68, 0, 47], #Springfield
[34, 68, 72, 66, 60, 41, 98, 71, 85, 38, 47, 0]]) #Worcester
max_dist = 60 #Max average distance (in miles)
min_pct = 0.8 #Min percent of demand within 50 miles
aij = np.zeros((5, 12)) #Creates an empty array
for i in range (5):
for j in range (12):
if dists[i][j] <= 50:
aij[i][j] = 1
else:
aij[i][j] = 0 #Creates a 0s and 1s array. If the distance to a costumer
#is less than 50, then the matrix element is 1, it is zero
#otherwise
dem_consts = np.array([425, 12, 43, 125, 110, 86, 129, 28, 66, 320, 220, 182])
fixd_cost = 10000
sum1 = np.sum(np.multiply(varx, dists))
sum2 = np.sum(vary*fixd_cost)
z = sum1 + sum2
tot_dem = np.sum(dem_consts)
M = tot_dem
m.Minimize(z)
for i in range(12):
m.Equation(np.sum(varxt[i, :]) >= dem_consts[i]) #Demand constraints
for i in range(5):
m.Equation(np.sum(varx[i, :]) <= 2000) #Capacity constraints
m.Equation(np.sum(varx[i, :]) <= M*vary[i]) #Enforces 0 or 1 value
m.Equation(np.sum(vary[:]) >= 1)
di_sum = np.sum(np.multiply(varx, dists))
di_sumw = di_sum/ tot_dem
m.Equation(di_sumw <= max_dist) #Average (demand) weighted distance from DC to customer
a_sum = np.sum(np.multiply(varx, aij))
a_sumw = a_sum/tot_dem
m.Equation(a_sumw >= min_pct) #Percent of demand that is within 50 miles
m.solve(disp = False)
p1 = np.zeros((5, 12))
for i in range (5):
for j in range (12):
p1[i][j] = varx[i][j].value[0]
p1t = np.transpose(p1)
p2 = np.zeros((5, ))
for i in range(5):
p2[i] = vary[i].value[0]
mad1 = np.sum(np.multiply(p1, dists))
mad2 = mad1/tot_dem
mpi1 = np.sum(np.multiply(p1, aij))
mpi2 = mpi1/tot_dem
tot1 = np.sum(np.multiply(p1, dists))
tot2 = np.sum(p2)*fixd_cost
tot = tot1 + tot2
print('The minimum cost is:' +str(tot))
print('Average customer distance:' +str(mad2))
print('Percent of customers <= 50 miles:' +str(mpi2))
dc = np.array(['Boston', 'Nashua', 'Providence', 'Springfield', 'Worcester'])
cities = ['Boston', 'Brattleboro', 'Concord', 'Hartford', 'Manchester', 'Nashua',
'New Haven', 'New London', 'Portsmouth', 'Providence', 'Springfield', 'Worcester']
data = {cities[0]: p1t[0], cities[1]: p1t[1], cities[2]: p1t[2], cities[3]: p1t[3],
cities[4]: p1t[4], cities[5]: p1t[5], cities[6]: p1t[6], cities[7]: p1t[7],
cities[8]: p1t[8], cities[9]: p1t[9], cities[10]: p1t[10], cities[11]: p1t[11]}
df = pd.DataFrame(data, index = dc)
df
当您设置 m.solve(disp=True) 时，解算器发出一条消息，它在 500 次迭代时提前终止。它 returns 一个可行的整数解决方案，但它可能不是最好的解决方案。
Warning: best integer solution returned after maximum MINLP iterations
Adjust minlp_max_iter_with_int_sol 500 in apopt.opt to change limit
Successful solution
---------------------------------------------------
Solver : APOPT (v1.0)
Solution time : 1.3654 sec
Objective : 66829.
Successful solution
---------------------------------------------------
The minimum cost is:66829.0
Average customer distance:15.3659793814433
Percent of customers <= 50 miles:1.7943871706758305
如果添加求解器选项：
m.solver_options = ['minlp_gap_tol 1.0e-2',\
'minlp_maximum_iterations 10000',\
'minlp_max_iter_with_int_sol 5000']
objective函数改进为66285:
Successful solution
---------------------------------------------------
Solver : APOPT (v1.0)
Solution time : 1.7178 sec
Objective : 66285.
Successful solution
---------------------------------------------------
The minimum cost is:66285.0
Average customer distance:20.781786941580755
Percent of customers <= 50 miles:1.9873997709049256
是否应该改为 <= 50 英里的客户百分比？：mpi3 = mpi1/np.sum(p1) 平均距离是？：mad3 = mad1/np.sum(p1)。这给出了 <= 50 英里的客户比例等于 89.94%：
Percent of customers <= 50 miles (mpi3):0.8994297563504406
新的平均距离是：
Average customer distance (mad3):9.405132192846034
这里是一个修改后的脚本，它使用 gekko 数组和 gekko 求和函数，因此更加高效。
from gekko import GEKKO
import numpy as np
import pandas as pd
import math
m = GEKKO(remote=False) #So that it solves the problem locally
m.options.SOLVER = 1 #MILP
varx = m.Array(m.Var,(5,12),lb=0,integer=True)
vary = m.Array(m.Var,5,lb=0,ub=1,integer=True)
dists = np.array([[0 , 93, 69, 98, 55, 37, 128, 95, 62, 42, 82, 34], #Boston
[37, 65, 33, 103, 20, 0, 137, 113, 48, 72, 79, 41], #Nashua
[42, 106, 105, 73, 92, 72, 94, 57, 104, 0, 68, 38], #Providence
[82, 59, 101, 27, 93, 79, 63, 57, 127, 68, 0, 47], #Springfield
[34, 68, 72, 66, 60, 41, 98, 71, 85, 38, 47, 0]]) #Worcester
max_dist = 60 #Max average distance (in miles)
min_pct = 0.8 #Min percent of demand within 50 miles
#Creates a 0s and 1s array. If the distance to a costumer
#is less than 50, then the matrix element is 1, it is zero otherwise
aij = [[1 if dists[i,j]<=50 else 0 for j in range(12)] for i in range(5)]
dem_consts = np.array([425, 12, 43, 125, 110, 86, 129, 28, 66, 320, 220, 182])
fixd_cost = 10000
sum1 = np.sum(np.multiply(varx, dists))
sum2 = np.sum(vary*fixd_cost)
z = sum1 + sum2
tot_dem = np.sum(dem_consts)
M = tot_dem
m.Minimize(z)
for j in range(12):
m.Equation(m.sum(varx[:,j]) >= dem_consts[j]) #Demand constraints
for i in range(5):
m.Equation(m.sum(varx[i,:]) <= 2000) #Capacity constraints
m.Equation(m.sum(varx[i,:]) <= M*vary[i]) #Enforces 0 or 1 value
m.Equation(m.sum(vary) >= 1)
di_sum = np.sum(np.multiply(varx, dists))
di_sumw = di_sum/ tot_dem
m.Equation(di_sumw <= max_dist) #Average (demand) weighted distance from DC to customer
a_sum = np.sum(np.multiply(varx, aij))
a_sumw = m.Intermediate(a_sum/tot_dem)
m.Equation(a_sumw >= min_pct) #Percent of demand that is within 50 miles
m.solver_options = ['minlp_gap_tol 1.0e-2',\
'minlp_maximum_iterations 10000',\
'minlp_max_iter_with_int_sol 5000']
m.solve(disp = True)
p1 = np.zeros((5, 12))
for i in range (5):
for j in range (12):
p1[i][j] = varx[i][j].value[0]
p1t = np.transpose(p1)
p2 = np.zeros(5)
for i in range(5):
p2[i] = vary[i].value[0]
mad1 = np.sum(np.multiply(p1, dists))
mad2 = mad1/tot_dem
mad3 = mad1/np.sum(p1)
mpi1 = np.sum(np.multiply(p1, aij))
mpi2 = mpi1/tot_dem
mpi3 = mpi1/np.sum(p1)
tot1 = np.sum(np.multiply(p1, dists))
tot2 = np.sum(p2)*fixd_cost
tot = tot1 + tot2
print(p1)
print(p2)
print('The minimum cost is:' +str(tot))
print('Average customer distance (mad2):' +str(mad2))
print('Average customer distance (mad3):' +str(mad3))
print('Percent of customers <= 50 miles (mpi2):' +str(mpi2))
print('Percent of customers <= 50 miles (mpi3):' +str(mpi3))
dc = np.array(['Boston', 'Nashua', 'Providence', 'Springfield', 'Worcester'])
cities = ['Boston', 'Brattleboro', 'Concord', 'Hartford', 'Manchester', 'Nashua',
'New Haven', 'New London', 'Portsmouth', 'Providence', 'Springfield', 'Worcester']
data = {cities[0]: p1t[0], cities[1]: p1t[1], cities[2]: p1t[2], cities[3]: p1t[3],
cities[4]: p1t[4], cities[5]: p1t[5], cities[6]: p1t[6], cities[7]: p1t[7],
cities[8]: p1t[8], cities[9]: p1t[9], cities[10]: p1t[10], cities[11]: p1t[11]}
df = pd.DataFrame(data, index = dc)
df
解决方法如下：
[[1102. 0. 43. 0. 110. 86. 0. 0. 66. 0. 0. 182.]
[ 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
[ 0. 0. 0. 0. 0. 0. 0. 28. 0. 495. 0. 0.]
[ 0. 12. 0. 125. 0. 0. 129. 0. 0. 0. 1480. 0.]
[ 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]]
[1. 0. 1. 1. 0.]
The minimum cost is:66285.0
Average customer distance (mad2):20.781786941580755
Average customer distance (mad3):9.405132192846034
Percent of customers <= 50 miles (mpi2):1.9873997709049256
Percent of customers <= 50 miles (mpi3):0.8994297563504406