2.4.4　设施选址问题

设施选址问题中常用If-then约束对企业的选址和运输服务决策之间的逻辑关系进行数学描述。给定客户的集合C和设施集合F，其中建设设施j的固定成本为fj（∀j∈F）。使用设施j服务客户i（i∈C）的运输成本为cij。设施选址问题旨在做出最优的选址决策，使得总成本最小。总成本包括设施建造成本和运输成本。注意，这里我们探讨的是设施选址问题的一个简单版本，即无容量限制的设施选址问题（Uncapacitated Facility Location Problem，UFLP）。首先，定义下面的决策变量：

·xij：连续变量，运输决策，表示客户i被设施j满足的比例（0≤xij≤1）。

·yj：0-1变量，若设施j被建设，则yj=1；否则yj=0。

UFLP中存在一个明显的If-then条件，即只有建成设施j，该设施才能服务客户；若不建成设施j，则设施j就不能为任何一个客户提供服务。该If-then条件可以用数学的语言描述为：若yj=0，则xij=0，∀i∈C；若yj=1，则xij≤1，∀i∈C。上述关系可以用大M建模方法写成以下约束：

式中，M为xij的一个上界。根据变量定义可知，xij的一个上界为1，不妨取M=1。因此，约束式（2.42）可以简化为yj≥xij，∀i∈C，∀j∈F。

基于上述分析，可以建立UFLP的数学模型：

下面以一个具体的数值算例来测试该模型。假设有3个设施候选点，3个客户点，且建成设施的固定成本分别为6万元、7万元、6万元，运输成本矩阵｛cij｝设置如下（单位：万元）。

基于此，设施选址问题的模型将变成以下形式。

下面使用Python分别调用COPT和Gurobi求解上述模型。这里仅展示COPT版本的完整代码，Gurobi版本的代码可见本书配套电子资源2-5。

根据求解结果可知，应该在第1个和第3个候选点建设设施，且用第1个设施服务客户1和2，用第3个设施服务客户3，最优总成本为21万元。

---

[1]也叫作服务网络规划问题。

[2]原始文献通过叙述的方式给出了这个方法，本书将其视为定理。

[3]表中的逻辑约束案例引自Logics and integer-programming representations，本书编者对其进行了补充完善。