考虑下面的 设施选址问题（Faclity Location Problem）。

问题描述

已知一些候选的位置，要从中选择一个或多个，用来建立服务设施。比如建设水库、电站、基站等等。目的是为了给周边的用户提供服务，例如提供水、电、网。此外，设施与用户之间还需要进行连接，比如铺水管、电线等。

注意，一个客户只能跟一个设施建立连接。但反过来不成立。一个设施可以连接多个客户。还要求所有客户必须建立一个连接。

建立设施以及连接客户都有成本，记作开设成本 $f_i$ 和连接成本 $c_{ij}$，其中 $i$ 代表设施， $j$ 代表用户。设施开得越多，总的开设成本越高。但是，总的连接成本可能会降低。反之，开设成本降低，连接成本就增加。

现在的问题是，要选择一些位置开设施，并且决定用户与设施之间的连接。目标是使得开设成本以及连接所有用户的连接成本最低。

问题的关键在于决定在哪里开设设施。因为一旦设施确定了，把用户连接到连接成本最低的设施即可。

数学模型

接下来用整数规划的形式描述这个问题。

下标

  • $i$ - 代表位置或者已开的设施，$i=1,2,..,m$，其中 $m$ 是位置的总数
  • $j$ - 用户，$j=1,2,…, n$，其中 $n$ 用户的总数

参数

  • $f_i$ - 设施在位置 $i$ 的开设成本
  • $c_{ij}$ - 设施 $i$ 与用户 $j$ 的连接成本

变量

  • $x_{ij} \in \set{0, 1} $ - 设施 $i$ 与用户 $j$ 是否连接，$1$ 代表连接；$0$ 代表不连接
  • $y_i \in \set{0, 1}$ - 位置 $i$ 是否建立设施，$1$ 代表建立；$0$ 代表不建立

约束

  • 每个客户有且仅有一个连接 $$ \sum_{i=1}^m x_{ij} = 1, \quad \forall j $$

  • 已经建立连接的设施，必须是已经开设的设施 $$ x_{ij}\leq y_i, \quad \forall i, j $$

目标函数

  • 最小化总成本 $$ \min ~ \sum_{i=1}^m f_iy_i + \sum_{i=1}^m\sum_{j=1}^n c_{ij}x_{ij} $$

综上所述，我们得到如下整数规划问题。

$$ \begin{aligned} \min ~ & \sum_{i=1}^m f_iy_i + \sum_{i=1}^m\sum_{j=1}^n c_{ij}x_{ij}\\[6pt] \text{s.t. } & \sum_{i=1}^m x_{ij} = 1, \quad \forall j\\[6pt] & x_{ij}\leq y_i, \quad \forall i, j\\[6pt] & x_{i,j}, ~y_i \in \set{0,1},\quad \forall i, j \end{aligned} $$

可以证明，如果把条件 $x_{i,j}\in\set{0,1}$ 放松成 $x_{i,j}\geq 0$，那么最优解依然是整数。直观的理解就是，如果一个用户有多个可以选择的设施，为了让连接成本最低，他选最便宜的那一个就行。

这样一来，我们得到下式。

$$ \begin{aligned} \min ~ & \sum_{i=1}^m f_iy_i + \sum_{i=1}^m\sum_{j=1}^n c_{ij}x_{ij}\\[6pt] \text{s.t. } & \sum_{i=1}^m x_{ij} = 1, \quad \forall j\\[6pt] & x_{ij}\leq y_i, \quad \forall i, j\\[6pt] & x_{i,j}\geq 0,~ y_i \in \set{0,1}, \quad \forall i, j \end{aligned} $$

求解思路

这是一个混合整数规划问题，有连续变量也有整数变量。当问题规模不大时，可以考虑直接求解。

分析一下问题的规模。已知 $m$ 是位置的数量，$n$ 是用户的数量。在上面的规划中，变量数量是 $m+m\times n$，约束数量是 $n+m\times n$。在实际问题中，$n$ 一般远远大于 $m$，因此约束的数量远远大于变量的数量，这说明存在较多冗余的约束。

当问题规模较大时，一次考虑所有的约束，可能无法求解。间接的办法就是，把大问题拆成小问题，小问题包含更少的约束，并且它的解是原问题的可行解。然后用迭代的方式，逐步增加约束，去逼近最优解。这就是 行生成 方法，也称为 Benders 分解。

Edit this page

Last updated 27 Apr 2025, 19:40 +0800 . history