在PuLP中利用Big M方法处理线性规划中的最小/最大辅助变量

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
      }
   }
}

# 设置 Big M 值
# M 必须大于所有货物的最大重量。这里最大重量是200，所以300是合适的选择。
M = 300

# 1. 创建问题实例
prob = pulp.LpProblem("Cargo_Allocation_with_Weight_Constraint", pulp.LpMaximize)

# 2. 定义决策变量
# truck_allocation_vars[truck_idx][cargo_idx] 为二元变量，
# 如果卡车 truck_idx 装载货物 cargo_idx，则为1，否则为0。
truck_allocation_vars = {
    truck: pulp.LpVariable.dicts("cargo_allocation", cargo[truck], 0, 1, pulp.LpBinary)
    for truck in cargo
}

# 辅助变量：用于捕捉分配货物中的最大重量和最小重量
max_weight = pulp.LpVariable("max_allocated_weight", cat=pulp.LpContinuous)
min_weight = pulp.LpVariable("min_allocated_weight", cat=pulp.LpContinuous)

# 3. 添加约束

# 约束1: 每辆卡车只能选择一件货物
for truck_idx in truck_allocation_vars:
    prob += pulp.lpSum(list(truck_allocation_vars[truck_idx].values())) == 1, f"One_Cargo_Per_Truck_{truck_idx}"

# 约束2: 定义 max_weight
# max_weight 必须大于等于所有被选中货物的重量
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], \
                f"Max_Weight_Constraint_{truck_idx}_{cargo_idx}"

# 约束3: 定义 min_weight (使用 Big M 方法)
# min_weight 必须小于等于所有被选中货物的重量
for truck_idx in truck_allocation_vars:
    for cargo_idx in cargo[truck_idx].keys():
        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, \
                f"Min_Weight_Constraint_{truck_idx}_{cargo_idx}"

# 约束4: 最大重量与最小重量之差不能超过50公斤
prob += (max_weight - min_weight) <= 50, "Weight_Difference_Constraint"

# 4. 定义目标函数
# 目标是最大化所有卡车分配到的货物总价格
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]]), "Total_Price"

# 5. 求解问题
prob.solve()

# 6. 打印解决方案
print(f"求解状态: {pulp.LpStatus[prob.status]}\n")
print(f"最大总价格: {pulp.value(prob.objective)}\n")

print("卡车分配详情:")
allocated_weights = []
for truck_idx in cargo:
   for cargo_idx in cargo[truck_idx]:
      if truck_allocation_vars[truck_idx][cargo_idx].varValue > 0.1:  # 浮点数比较，使用阈值
         weight = cargo[truck_idx][cargo_idx]['weight']
         price = cargo[truck_idx][cargo_idx]['price']
         print(f'  卡车 {truck_idx} 装载货物 {cargo_idx} (价格: {price}, 重量: {weight}kg)')
         allocated_weights.append(weight)

print(f'\n分配货物中的最大重量: {max_weight.varValue} kg')
print(f'分配货物中的最小重量: {min_weight.varValue} kg')
print(f'重量差异: {max_weight.varValue - min_weight.varValue} kg (要求 <= 50 kg)')

求解状态: Optimal

最大总价格: 700.0

卡车分配详情:
  卡车 truck1 装载货物 c4 (价格: 500, 重量: 80kg)
  卡车 truck2 装载货物 c6 (价格: 100, 重量: 80kg)
  卡车 truck3 装载货物 c9 (价格: 100, 重量: 50kg)

分配货物中的最大重量: 80.0 kg
分配货物中的最小重量: 50.0 kg
重量差异: 30.0 kg (要求 <= 50 kg)