我是 LP 新手，我正在尝试解决一个玩具问题，以在 3 辆卡车中分配货物。每个货物有2个属性，价格和重量，每辆卡车每次可以装载1个货物。我想最大化所有卡车分配的货物的总价格总和，同时设置一个约束，即任何卡车的最大和最小分配重量之间的差异不能超过 50 公斤。
我在 PuLP 中尝试了以下问题定义，使用辅助最大和最小变量作为权重约束。
import pulp
# Example toy data
cargo = {
"truck1":{
"c1":{
"price":100,
"weight":20
},
"c2":{
"price":150,
"weight":10
},
"c3":{
"price":90,
"weight":30
},
"c4":{
"price":500,
"weight":80
}
},
"truck2":{
"c5":{
"price":50,
"weight":10
},
"c6":{
"price":100,
"weight":80
},
"c7":{
"price":200,
"weight":150
},
"c8":{
"price":50,
"weight":30
}
},
"truck3":{
"c9":{
"price":100,
"weight":50
},
"c10":{
"price":200,
"weight":200
}
}
}
# Create a problem variable:
prob = pulp.LpProblem("Cargo", pulp.LpMaximize)
# Decision variables
truck_allocation_vars = {truck: pulp.LpVariable.dicts("cargo", cargo[truck], 0, 1, pulp.LpBinary) for truck in cargo}
# Constraint: Only one cargo can be chosen for each truck
for truck in truck_allocation_vars:
prob += pulp.lpSum(list(truck_allocation_vars[truck].values())) == 1
# Objective function: Maximize price
prob += pulp.lpSum([cargo[truck_idx][cargo_idx]['price'] * truck_allocation_vars[truck_idx][cargo_idx] for truck_idx in truck_allocation_vars for cargo_idx in truck_allocation_vars[truck_idx]])
# This is where things to wrong ...
# I need to figure out what is the maximum and minimum weight of the allocated cargos
# So I can subsequently add the weight constraint
max_weight = pulp.LpVariable("max_weight", cat=pulp.LpContinuous)
min_weight = pulp.LpVariable("min_weight", cat=pulp.LpContinuous)
for truck_idx in truck_allocation_vars:
for cargo_idx in cargo[truck_idx].keys():
prob += (max_weight >= int(cargo[truck_idx][cargo_idx]['weight']) * truck_allocation_vars[truck_idx][cargo_idx])
prob += (min_weight <= int(cargo[truck_idx][cargo_idx]['weight']) * truck_allocation_vars[truck_idx][cargo_idx])
# TODO:
# Add weight constraint once max and min weight are correct
# prob += (max_weight - min_weight) < 50
# Solve the problem
prob.solve()
# Print the solution
for truck_idx in truck_allocation_vars:
for cargo_idx in truck_allocation_vars[truck_idx].keys():
if pulp.value(truck_allocation_vars[truck_idx][cargo_idx]) == 1:
print(f"Cargo {cargo_idx} in truck {truck_idx} with price {cargo[truck_idx][cargo_idx]['price']} and weight {cargo[truck_idx][cargo_idx]['weight']}")
print(pulp.value(max_weight))
print(pulp.value(min_weight))
最大变量在求解结束时正确设置，但最小变量保持为 0（这是一个有效的解决方案，只是不是我想要的）。我已经尝试了一些方法（即添加下限、修改成本函数以添加 min_weight），但我还没有找到有效的方法。大多数时候它告诉我问题是不可行的，但我认为这是由于错误的设置造成的。你会做什么？
LP 难题中缺少的一块是使用最小值的“Big M”约束。 （谷歌搜索或查看任何 LP 教科书）。
当您尝试捕获最小值时，您正在执行此操作（其中
xmy_min <= x[j] * val[j]. for all j
问题在于，当
x[j]my_min <= x[j] * val[j] + (1 - x[j]) * M
制作一个小“真相表”，以验证您是否理解其中发生的情况（如果这令人困惑）。
import pulp
# Example toy data
cargo = {
"truck1":{
"c1":{
"price":100,
"weight":20
},
"c2":{
"price":150,
"weight":10
},
"c3":{
"price":90,
"weight":30
},
"c4":{
"price":500,
"weight":80
}
},
"truck2":{
"c5":{
"price":50,
"weight":10
},
"c6":{
"price":100,
"weight":80
},
"c7":{
"price":200,
"weight":150
},
"c8":{
"price":50,
"weight":30
}
},
"truck3":{
"c9":{
"price":100,
"weight":50
},
"c10":{
"price":200,
"weight":200
}
}
}
M = 300 # suitably large, greater than max of weights.
# Create a problem variable:
prob = pulp.LpProblem("Cargo", pulp.LpMaximize)
# Decision variables
truck_allocation_vars = {truck: pulp.LpVariable.dicts("cargo", cargo[truck], 0, 1, pulp.LpBinary) for truck in cargo}
# Constraint: Only one cargo can be chosen for each truck
for truck in truck_allocation_vars:
prob += pulp.lpSum(list(truck_allocation_vars[truck].values())) == 1
# Objective function: Maximize price
prob += pulp.lpSum([cargo[truck_idx][cargo_idx]['price'] * truck_allocation_vars[truck_idx][cargo_idx] for truck_idx in truck_allocation_vars for cargo_idx in truck_allocation_vars[truck_idx]])
# This is where things to wrong ...
# I need to figure out what is the maximum and minimum weight of the allocated cargos
# So I can subsequently add the weight constraint
max_weight = pulp.LpVariable("max_weight", cat=pulp.LpContinuous)
min_weight = pulp.LpVariable("min_weight", cat=pulp.LpContinuous)
for truck_idx in truck_allocation_vars:
for cargo_idx in cargo[truck_idx].keys():
prob += max_weight >= cargo[truck_idx][cargo_idx]['weight'] * truck_allocation_vars[truck_idx][cargo_idx]
prob += min_weight <= cargo[truck_idx][cargo_idx]['weight'] * truck_allocation_vars[truck_idx][cargo_idx] \
+ (1 - truck_allocation_vars[truck_idx][cargo_idx]) * M
# TODO:
# Add weight constraint once max and min weight are correct
prob += (max_weight - min_weight) <= 50
# Solve the problem
prob.solve()
for truck_idx in cargo:
for cargo_idx in cargo[truck_idx]:
if truck_allocation_vars[truck_idx][cargo_idx].varValue > 0.1: # it is selected
print(f'load {truck_idx} with {cargo_idx}')
print(f'weight delta is: {max_weight.varValue - min_weight.varValue}')
Result - Optimal solution found
Objective value: 700.00000000
Enumerated nodes: 0
Total iterations: 0
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
load truck1 with c4
load truck2 with c6
load truck3 with c9
weight delta is: 30.0
这并不容易做到，但肯定可行。您需要更多选择变量 - 每对卡车-货物都有一个选择变量：
import pulp
cargo = {
'truck1': {
'c1': {'price': 100, 'weight': 20},
'c2': {'price': 150, 'weight': 10},
'c3': {'price': 90, 'weight': 30},
'c4': {'price': 500, 'weight': 80},
},
'truck2': {
'c5': {'price': 50, 'weight': 10},
'c6': {'price': 100, 'weight': 80},
'c7': {'price': 200, 'weight': 150},
'c8': {'price': 50, 'weight': 30},
},
'truck3': {
'c9': {'price': 100, 'weight': 50},
'c10': {'price': 200, 'weight': 200},
},
}
def cartesian(name: str) -> dict[str, list[pulp.LpVariable]]:
return {
truck_name: pulp.LpVariable.matrix(
name=name,
indices=(
(truck_name, cargo_name)
for cargo_name in cargos.keys()
),
cat=pulp.LpBinary,
)
for truck_name, cargos in cargo.items()
}
allocations = cartesian(name='alloc')
min_assigns = cartesian(name='minassign')
max_assigns = cartesian(name='maxassign')
min_weight = pulp.lpSum(
pulp.lpDot(
assigns,
[
props['weight']
for props in cargo[truck_name].values()
],
)
for truck_name, assigns in min_assigns.items()
)
max_weight = pulp.lpSum(
pulp.lpDot(
assigns,
[
props['weight']
for props in cargo[truck_name].values()
],
)
for truck_name, assigns in max_assigns.items()
)
# Maximize price
prob = pulp.LpProblem(name='Cargo', sense=pulp.LpMaximize)
prob.setObjective(
pulp.lpSum(
pulp.lpDot(
cargo_allocs,
[
props['price']
for props in cargo[truck_name].values()
],
)
for truck_name, cargo_allocs in allocations.items()
)
)
'''
n min-assignments, binary
n max-assignments, binary
sum(all min-assignments) = 1
sum(all max-assignments) = 1
each min-assignment <= corresponding cargo-assignment
each max-assignment <= corresponding cargo-assignment
min-weight = min-assignment dot weights
max-weight = max-assignment dot weights
For every minassign, minassign dot weight within each truck >= minassign * weight
'''
# For both min and max, exactly one must be assigned
prob.addConstraint(
pulp.lpSum(assigns for assigns in min_assigns.values()) == 1
)
prob.addConstraint(
pulp.lpSum(assigns for assigns in max_assigns.values()) == 1
)
for truck_name, cargos in allocations.items():
# Only one cargo can be chosen for each truck
prob.addConstraint(pulp.lpSum(cargos) == 1)
# The min and max weights must observe the weights in this group
weight = pulp.lpDot(
cargos,
(
props['weight']
for props in cargo[truck_name].values()
),
)
prob.addConstraint(weight >= min_weight)
prob.addConstraint(weight <= max_weight)
for cargos, mins, maxes in zip(allocations.values(), min_assigns.values(), max_assigns.values()):
for alloc, amin, amax in zip(cargos, mins, maxes):
# Min and max selection must follow cargo assignment
prob.addConstraint(amin <= alloc)
prob.addConstraint(amax <= alloc)
# Upper limit to widest weight range
weight_range = 50
prob.addConstraint(max_weight - min_weight <= weight_range)
prob.solve()
assert prob.status == pulp.LpStatusOptimal
for truck_name, cargo_allocs in allocations.items():
for (cargo_name, props), alloc in zip(
cargo[truck_name].items(),
cargo_allocs,
):
if alloc.value() > 0.5:
print(
f"Truck {truck_name} "
f"with cargo {cargo_name:3} "
f"and price {props['price']} "
f"and weight {props['weight']}",
)
print('Min weight on', next(iter(
a
for assigns in min_assigns.values()
for a in assigns
if a.value() > 0.5
)))
print('Max weight on', next(iter(
a
for assigns in max_assigns.values()
for a in assigns
if a.value() > 0.5
)))
print('Min weight:', min_weight.value())
print('Max weight:', max_weight.value())
print('Weight range:', max_weight.value() - min_weight.value(), '<=', weight_range)
Objective value: 700.00000000
Enumerated nodes: 0
Total iterations: 0
Time (CPU seconds): 0.01
Time (Wallclock seconds): 0.01
Option for printingOptions changed from normal to all
Total time (CPU seconds): 0.01 (Wallclock seconds): 0.01
Truck truck1 with cargo c4 and price 500 and weight 80
Truck truck2 with cargo c6 and price 100 and weight 80
Truck truck3 with cargo c9 and price 100 and weight 50
Min weight on minassign_('truck3',_'c9')
Max weight on maxassign_('truck2',_'c6')
Min weight: 50.0
Max weight: 80.0
Weight range: 30.0 <= 50