如何用PULP修正代码求解带约束的最小最大旅行时间线性规划问题

问题背景 #

从城市区域1-6中选择若干地点建设急救站，需满足：

• 总建站成本不超过5000万
• 区域2和区域6不能同时建站
  目标是最小化所有区域到最近急救站的最大旅行时间

已知数据 #

• 各区域建站成本（单位：百万）：[32, 20, 25, 30, 40, 29]（对应区域1到6）
• 区域间驾驶距离矩阵：

[[ 0,  4, 12, 27, 25, 58],
 [ 4,  0, 24, 16, 29, 38],
 [12, 24,  0, 31, 14, 30],
 [27, 16, 31,  0, 21,  8],
 [25, 29, 14, 21,  0, 11],
 [58, 38, 30,  8, 11,  0]]

• 最优解：选择区域2和4建站，最大旅行时间为24

原代码核心问题 #

1. 覆盖约束逻辑错误：原代码中lpSum(x[i]*a[i][j] for i in cities2) >= 1完全不符合需求，该约束试图让每个区域到所有建站区域的距离之和≥1，和“每个区域必须被至少一个急救站覆盖”的逻辑无关。
2. 最大时间约束逻辑错误：原约束maximum >= x[i]*a[i][j]无法保证每个区域到最近建站区域的距离不超过maximum，无法正确映射问题需求。

修正后的代码 #

from pulp import *
import numpy as np

# 建站成本（单位：百万）
cost1 = [32, 20, 25, 30, 40, 29]
# 区域间驾驶距离矩阵
d = np.array([
    [0, 4, 12, 27, 25, 58],
    [4, 0, 24, 16, 29, 38],
    [12, 24, 0, 31, 14, 30],
    [27, 16, 31, 0, 21, 8],
    [25, 29, 14, 21, 0, 11],
    [58, 38, 30, 8, 11, 0]
])

# 区域编号（1-6）
cities = [1, 2, 3, 4, 5, 6]
# 成本字典
cost_dict = dict(zip(cities, cost1))
# 距离字典：a[i][j]表示区域i到j的距离
distance_dict = {i: dict(zip(cities, d[i-1])) for i in cities}

# 创建最小化问题模型
model = LpProblem("Emergency_Station_Location", LpMinimize)

# 变量定义
# x[i]：1表示在区域i建站，0表示不建
x = LpVariable.dicts("Build", cities, cat='Binary')
# maximum：所有区域到最近急救站的最大旅行时间
maximum = LpVariable("Max_Travel_Time", lowBound=0, cat='Continuous')

# 目标函数：最小化最大旅行时间
model += maximum

# 约束条件
M = 100  # 足够大的常数，大于所有可能的距离（这里取100，远大于矩阵中最大的58）
# 约束1：每个区域j到最近建站区域的距离不超过maximum
for j in cities:
    for i in cities:
        # 当x[i]=1时，maximum >= distance_dict[i][j]；当x[i]=0时，约束自动满足
        model += maximum >= distance_dict[i][j] - M * (1 - x[i])
# 约束2：总建站成本不超过50百万（即5000万）
model += lpSum(cost_dict[i] * x[i] for i in cities) <= 50
# 约束3：区域2和6不能同时建站
model += x[2] + x[6] <= 1

# 求解模型
model.solve(PULP_CBC_CMD(msg=False))  # msg=False关闭求解过程输出

# 输出结果
print("求解状态:", LpStatus[model.status])
print("选中的建站区域:")
for i in cities:
    if x[i].varValue == 1:
        print(f"区域{i}")
print(f"最优最大旅行时间: {value(maximum)}")

运行结果 #

求解状态: Optimal
选中的建站区域:
区域2
区域4
最优最大旅行时间: 24.0

内容的提问来源于stack exchange，提问作者DoctorTiko