最小化最大距离的k中心选址问题线性规划建模咨询

你描述的是经典的k中心优化问题，核心是选至多k个中心点，让所有点到最近中心点的最大距离最小，完整线性规划建模思路如下：

变量定义 #

• 0-1变量 x_j：x_j=1 表示点j被选入中心集合C，否则为0，j∈N
• 非负连续变量 y：表示所有点到最近中心的最大距离，也就是最终要最小化的目标值

约束条件 #

1. 中心数量约束：所有选中的中心总数不超过k

   sum_{j∈N} x_j ≤ k
   

2. 距离约束：对每个点i，至少存在一个选中的中心j，使得i到j的距离不超过y
   这一步用大M法转化为线性约束，取U为所有d_ij的最大值（只要大于等于所有距离即可），对所有i∈N、j∈N添加约束：

   d_ij ≤ y + U * (1 - x_j)
   

   约束逻辑说明：
   • 如果x_j=1（j是选中的中心），约束简化为d_ij ≤ y
   • 如果x_j=0（j未被选中），约束右侧为y+U，因为U是所有距离的上界，该约束自动成立，不会产生限制
     只要存在任意一个选中的j满足d_ij ≤ y，点i的约束就全部成立；如果所有选中的j到i的距离都大于y，那么对应x_j=1的约束会直接触发不满足，从而保证了约束的正确性。

目标函数 #

最小化最大距离y：

min y

实现说明 #

你可以直接用Python的线性规划求解库（如Pulp、OR-Tools、Gurobi）实现上述模型，小规模输入可以得到精确最优解。k中心本身是NP难问题，大规模输入下如果对精度要求不高，也可以用经典的2倍近似贪心算法求解。

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