当我在 PuLP 中运行这个程序时,它应该最小化不受约束的伽玛变量,但我变得不可行。请注意,约束符号是混合的 ≤ 和 ≥。字典中的 gamma 变量表示对该目标重要性的权重。但是当我否定约束以使它们全部≤时(这应该是同一件事),我得到了一个解决方案。关于 PuLP 的工作原理,我缺少什么?
我的问题基于以下事实:目标 1、2、4 和 5 约束不等式在数学上应该是相同的,但程序解不同。
例如,目标 1 最初写为 x3 + x6 +16/6 gamma ≥ 1。
然后我将其否定为 -x3 - x6 - 16/6 gamma ≤ -1,这是相同的。为什么 Pulp 给出了两种不同的解决方案?
import pulp as lp
# Define the problem
prob = lp.LpProblem("Annual_usage", lp.LpMinimize)
# Decision variables
# x_i is the project type
x = {
'X1': lp.LpVariable('x_1', lowBound=0, cat='Binary'),
'X2': lp.LpVariable('x_2', lowBound=0, cat='Binary'),
'X3': lp.LpVariable('x_3', lowBound=0, cat='Binary'),
'X4': lp.LpVariable('x_4', lowBound=0, cat='Binary'),
'X5': lp.LpVariable('x_5', lowBound=0, cat='Binary'),
'X6': lp.LpVariable('x_6', lowBound=0, cat='Binary'),
'X7': lp.LpVariable('x_7', lowBound=0, cat='Binary'),
'X8': lp.LpVariable('x_8', lowBound=0, cat='Binary'),
'gamma': lp.LpVariable('gamma', lowBound=None, cat='Continuous')
}
# Usage
usage = {
'X1': 4.7, 'X2': 12.5, 'X3': 3.2, 'X4': 7.5, 'X5': 41, 'X6': 47, 'X7': 23, 'X8': 16,
'gamma': 0
}
# Costs
cost = {
'X1': 75, 'X2': 180, 'X3': 350, 'X4': 45, 'X5': 120, 'X6': 80, 'X7': 115, 'X8': 210,
'gamma': 0
}
# Acreage
acreage = {
'X1': 7, 'X2': 12, 'X3': 20, 'X4': 6, 'X5': 3, 'X6': 25, 'X7': 5, 'X8': 8,
'gamma': 0
}
goal1 = { # at least 1 of X3 and X6
'X1': 0, 'X2': 0, 'X3': 1, 'X4': 0, 'X5': 0, 'X6': 1, 'X7': 0, 'X8': 0,
'gamma': 16/6
}
goal2 = { # at least 130
'X1': 4.7, 'X2': 12.5, 'X3': 3.2, 'X4': 7.5, 'X5': 41, 'X6': 47, 'X7': 23, 'X8': 16,
'gamma': 16/3
}
goal3 = { #sum is at most 7
'X1': 3, 'X2': 2, 'X3': 1, 'X4': 3, 'X5': 2, 'X6': 1, 'X7': 2, 'X8': 3,
'gamma': 16/2
}
goal4 = { #at least 495)
'X1': 75, 'X2': 180, 'X3': 350, 'X4': 45, 'X5': 120, 'X6': 80, 'X7': 115, 'X8': 210,
'gamma': 16
}
goal5 = { # sum is at least 5
'X1': 1, 'X2': 1, 'X3': 1, 'X4': 1, 'X5': 1, 'X6': 1, 'X7': 1, 'X8': 1,
'gamma': 4
}
gamma_objective = {
'X1': 0, 'X2': 0, 'X3': 0, 'X4': 0, 'X5': 0, 'X6': 0, 'X7': 0, 'X8': 0,
'gamma': 1
}
# Objective function
prob += lp.lpSum(gamma_objective[i] * x[i] for i in x)
# Constraints
prob += lp.lpSum(x[i] * goal1[i] for i in x) >= 1, "goal 1"
prob += lp.lpSum(x[i] * goal2[i] for i in x) >= 130, "goal 2"
prob += lp.lpSum(x[i] * goal3[i] for i in x) <= 7, "goal 3"
prob += lp.lpSum(x[i] * goal4[i] for i in x) >= 495, "goal 4"
prob += lp.lpSum(x[i] * goal5[i] for i in x) >= 5, "goal 5"
prob += lp.lpSum(x[i] * cost[i] for i in x) <=550, "# cost constraint"
prob += lp.lpSum(x[i] * acreage[i] for i in x) <=50, "# acreage constraint"
# Solve the problem
prob.solve()
# Print the solution
for v in prob.variables():
print(v.name, "=", v.varValue)
print("Total Cost =", lp.value(prob.objective))
status = prob.status
print("Status:", lp.LpStatus[status])
当我否定第一个、第二个、第四个和第五个目标约束时,这段代码为我提供了解决方案。
import pulp as lp
# Define the problem
prob = lp.LpProblem("Annual_usage", lp.LpMinimize)
# Decision variables
# x_i is the project type
x = {
'X1': lp.LpVariable('x_1', lowBound=0, cat='Binary'),
'X2': lp.LpVariable('x_2', lowBound=0, cat='Binary'),
'X3': lp.LpVariable('x_3', lowBound=0, cat='Binary'),
'X4': lp.LpVariable('x_4', lowBound=0, cat='Binary'),
'X5': lp.LpVariable('x_5', lowBound=0, cat='Binary'),
'X6': lp.LpVariable('x_6', lowBound=0, cat='Binary'),
'X7': lp.LpVariable('x_7', lowBound=0, cat='Binary'),
'X8': lp.LpVariable('x_8', lowBound=0, cat='Binary'),
'gamma': lp.LpVariable('gamma', lowBound=None, cat='Continuous')
}
# Usage
usage = {
'X1': 4.7, 'X2': 12.5, 'X3': 3.2, 'X4': 7.5, 'X5': 41, 'X6': 47, 'X7': 23, 'X8': 16,
'gamma': 0
}
# Costs
cost = {
'X1': 75, 'X2': 180, 'X3': 350, 'X4': 45, 'X5': 120, 'X6': 80, 'X7': 115, 'X8': 210,
'gamma': 0
}
# Acreage
acreage = {
'X1': 7, 'X2': 12, 'X3': 20, 'X4': 6, 'X5': 3, 'X6': 25, 'X7': 5, 'X8': 8,
'gamma': 0
}
goal1 = { # at least X3 and X6
'X1': 0, 'X2': 0, 'X3': -1, 'X4': 0, 'X5': 0, 'X6': -1, 'X7': 0, 'X8': 0,
'gamma': -16/6
}
goal2 = { # at least 130
'X1': -4.7, 'X2': -12.5, 'X3': -3.2, 'X4': -7.5, 'X5': -41, 'X6': -47, 'X7': -23, 'X8': -16,
'gamma': -16/3
}
goal3 = { #sum is at most 7
'X1': -3, 'X2': -2, 'X3': -1, 'X4': -3, 'X5': -2, 'X6': -1, 'X7': -2, 'X8':-3,
'gamma': -16/2
}
goal4 = { # At least 495k
'X1': -75, 'X2': -180, 'X3': -350, 'X4': -45, 'X5': -120, 'X6': -80, 'X7': -115, 'X8': -210,
'gamma': -16
}
goal5 = { # sum is at least 5
'X1': -1, 'X2': -1, 'X3': -1, 'X4': -1, 'X5': -1, 'X6': -1, 'X7': -1, 'X8': -1,
'gamma': -4
}
gamma_objective = {
'X1': 0, 'X2': 0, 'X3': 0, 'X4': 0, 'X5': 0, 'X6': 0, 'X7': 0, 'X8': 0,
'gamma': 1
}
# Objective function
prob += lp.lpSum(gamma_objective[i] * x[i] for i in x)
# Constraints
prob += lp.lpSum(x[i] * goal1[i] for i in x) <= -1, "goal 1"
prob += lp.lpSum(x[i] * goal2[i] for i in x) <= -130, "goal 2"
prob += lp.lpSum(x[i] * goal3[i] for i in x) <= 7, "goal 3"
prob += lp.lpSum(x[i] * goal4[i] for i in x) <= -495, "goal 4"
prob += lp.lpSum(x[i] * goal5[i] for i in x) <= -5, "goal 5"
prob += lp.lpSum(x[i] * cost[i] for i in x) <=550, "# cost constraint"
prob += lp.lpSum(x[i] * acreage[i] for i in x) <=50, "# acreage constraint"
# Solve the problem
prob.solve()
# Print the solution
for v in prob.variables():
print(v.name, "=", v.varValue)
print("Total Cost =", lp.value(prob.objective))
status = prob.status
print("Status:", lp.LpStatus[status])
所以你打破了等价性,但没有解决不可行性的根本问题。不要费心去修改不同的表示;从业务角度来看,仅使用最明显且易于调试的公式。通常情况下,当您应该使用矩阵、求和和点积时,您却过度使用了字典。目标3太激进了。你需要放松它(或你的其他约束)以使问题变得可行:
import pulp
x1, x2, x3, x4, x5, x6, x7, x8 = project_types = pulp.LpVariable.matrix(
name='x', cat=pulp.LpBinary, indices=range(1, 9))
gamma = pulp.LpVariable(
name='gamma', cat=pulp.LpContinuous)
prob = pulp.LpProblem(name='Annual_usage', sense=pulp.LpMinimize)
usage = pulp.lpDot(project_types, (4.7, 12.5, 3.2, 7.5, 41, 47, 23, 16))
cost = pulp.lpDot(project_types, (75, 180, 350, 45, 120, 80, 115, 210))
acreage = pulp.lpDot(project_types, (7, 12, 20, 6, 3, 25, 5, 8))
prob.addConstraint(
name='goal1',
constraint=x3 + x6 + 16/6*gamma >= 1,
)
prob.addConstraint(
name='goal2',
constraint=usage + 16/3*gamma >= 130,
)
goal3 = pulp.lpDot(
project_types,
(3, 2, 1, 3, 2, 1, 2, 3),
) + 16/2*gamma
prob.addConstraint(
name='goal3',
constraint=goal3 <= 13, # 7
)
prob.addConstraint(
name='goal4',
constraint=cost + 16*gamma >= 495,
)
prob.addConstraint(
name='goal5',
constraint=pulp.lpSum(project_types) + 4*gamma >= 5,
)
prob.addConstraint(
name='cost',
constraint=cost <= 550,
)
prob.addConstraint(
name='acreage',
constraint=acreage <= 50,
)
prob.setObjective(gamma)
print(prob)
prob.solve()
assert prob.status == pulp.LpStatusOptimal
for v in prob.variables():
print(v.name, '=', v.value())
print('usage =', usage.value())
print('cost =', cost.value())
print('acreage =', acreage.value())
print('goal3 only reduced to', goal3.value())
Annual_usage:
MINIMIZE
1*gamma + 0.0
SUBJECT TO
goal1: 2.66666666667 gamma + x_3 + x_6 >= 1
goal2: 5.33333333333 gamma + 4.7 x_1 + 12.5 x_2 + 3.2 x_3 + 7.5 x_4 + 41 x_5
+ 47 x_6 + 23 x_7 + 16 x_8 >= 130
goal3: 8 gamma + 3 x_1 + 2 x_2 + x_3 + 3 x_4 + 2 x_5 + x_6 + 2 x_7 + 3 x_8
<= 13
goal4: 16 gamma + 75 x_1 + 180 x_2 + 350 x_3 + 45 x_4 + 120 x_5 + 80 x_6
+ 115 x_7 + 210 x_8 >= 495
goal5: 4 gamma + x_1 + x_2 + x_3 + x_4 + x_5 + x_6 + x_7 + x_8 >= 5
cost: 75 x_1 + 180 x_2 + 350 x_3 + 45 x_4 + 120 x_5 + 80 x_6 + 115 x_7
+ 210 x_8 <= 550
acreage: 7 x_1 + 12 x_2 + 20 x_3 + 6 x_4 + 3 x_5 + 25 x_6 + 5 x_7 + 8 x_8
<= 50
VARIABLES
gamma free Continuous
0 <= x_1 <= 1 Integer
0 <= x_2 <= 1 Integer
0 <= x_3 <= 1 Integer
0 <= x_4 <= 1 Integer
0 <= x_5 <= 1 Integer
0 <= x_6 <= 1 Integer
0 <= x_7 <= 1 Integer
0 <= x_8 <= 1 Integer
...
Result - Optimal solution found
Objective value: 0.56250000
Enumerated nodes: 0
Total iterations: 4
Time (CPU seconds): 0.00
Time (Wallclock seconds): 0.00
Option for printingOptions changed from normal to all
Total time (CPU seconds): 0.00 (Wallclock seconds): 0.00
gamma = 0.5625
x_1 = 0.0
x_2 = 0.0
x_3 = 0.0
x_4 = 0.0
x_5 = 1.0
x_6 = 1.0
x_7 = 1.0
x_8 = 1.0
usage = 127.0
cost = 525.0
acreage = 41.0
goal3 only reduced to 12.5