P中位问题

p中位问题（p-median problem）从候选地点选出 $p$ 个设施，使需求点到最近设施的加权距离总和最小。它优化的是总体运输或服务代价；名称中的“中位”不表示把候选地点简单求平均。

一条公路上有四个需求点，位置为零、二、五、九千米，每天的服务次数权重为一、三、一、一。设施也只能建在这四处，先不限制每处的服务能力。若只建一个，选二千米处的总单程服务距离为 $$1\times 2+3\times 0+1\times 3+1\times 7=12.$$ 而选零、五、九时分别为二十、十八、三十四。位置二并非公路中点，却靠近频繁发生的需求。

分配变量与选址变量

需求点集为 $I$、候选点集为 $J$，权重 $w_i\ge 0$ 表示单位时期的需求量，$d_{ij}\ge 0$ 为距离。令 $y_j$ 表示建站，$x_{ij}$ 表示把需求点分给某站，则 $$\begin{array}{cc}min& \sum _{i\in I}{w}_i\sum _{j\in J}{d}_{ij}{x}_{ij},\\ \sum _j{x}_{ij}& =1(i\in I),\\ x_{ij}& \le y_j,\sum _j{y}_j=p,\\ x_{ij},y_j& \in \{0,1\}.\end{array}$$ 目标单位为“需求量乘距离”。第一式保证每个点有站服务，第二式禁止分给未开设施，第三式固定数量。对于给定开站集合 $S$，各需求点的分配彼此独立，因此总是可选最近站；最优目标化成 $$F(S)=\sum _i{w}_i\underset{j\in S}{min}{d}_{ij},|S|=p.$$ 这里最近站独立选择依赖于没有容量约束。若每站可服务数量有限，客户分配会互相争用资源，就不能直接取逐行最小距离。

从一个站到两个站

六组双站集合按位置写为 $\{0,2\},\{0,5\},\{0,9\},\{2,5\},\{2,9\},\{5,9\}$，目标依次为十、十、十、六、五、十四。因此最优建在二和九：位置零到二为二，位置五到二为三，其余距离为零，总计五。

点上的数字w为每天服务次数；箭头表示分配而非新增道路。零到二贡献2，五到二贡献3。

一般地，在仍可增加设施且距离非负时，最优目标随 $p$ 增大不会上升：给一个可行站集合增加一站，每个点可选的最近距离只会缩短或不变。这是目标的单调性，不意味着任意贪心添加顺序都给出各个 $p$ 下的最优组合。

公路线上的加权中位数

如果只建一个站，且允许在整条公路上连续选址，目标为 $f(s)=\sum _i{w}_i|s-a_i|$。不在需求点时向右移动一小段，左侧每单位权重增加同样距离，右侧每单位权重减少同样距离，所以斜率是“左权重减右权重”。在某个需求点，斜率向上跳跃两倍该点权重。

于是一个点最优，当且仅当其左、右两侧严格位于该侧的权重都不超过总权重一半。这也由绝对值函数的凸性给出全局证书：左导数不大于零、右导数不小于零。主例总权重六，在位置二的左权重一、右权重二，满足条件。若只有零和九、权重相同，那么零至九之间每一点的距离和都等于九，最优解不是唯一的。

有限候选集的核对程序

以下直接枚举设施子集，输入非负距离矩阵、非负权重及合法设施数，返回最小加权距离和候选点下标。逐集合按最近设施分配，覆盖全部可能开站方案，故可作为小规模精确核对。

Python 3

from itertools import combinations
import math

def p_median(distance, weights, p):
    d, w = tuple(tuple(r) for r in distance), tuple(weights)
    if not d or len(w) != len(d) or not d[0]:
        raise ValueError("nonempty demand and candidate sets required")
    m = len(d[0])
    if any(len(r) != m for r in d) or type(p) is not int or not 1 <= p <= m:
        raise ValueError("rectangular matrix and valid p required")
    if any(not math.isfinite(v) or v < 0 for r in d for v in r):
        raise ValueError("finite nonnegative distances required")
    if any(not math.isfinite(v) or v < 0 for v in w):
        raise ValueError("finite nonnegative weights required")
    return min((sum(w[i] * min(d[i][j] for j in s)
                    for i in range(len(d))), s)
               for s in combinations(range(m), p))

a = [0, 2, 5, 9]
d = [[abs(x-y) for y in a] for x in a]
print(p_median(d, [1, 3, 1, 1], 2))
# (5, (1, 3))

时间为 $O((\genfrac{}{}{0ex}{}{m}{p})np)$，其中 $n$ 为需求点数、$m$ 为候选点数；保存输入需 $O(nm)$ 空间，枚举本身只需当前集合与最佳结果。

变式。 四点权重全改为一、仅建一站。在二和五的费用均为十二；连续位置二至五之间的每一点也是最优。需求权重、距离的定义和候选地点的限制，都可能改变选址结论。若要控制最偏远客户的服务距离，应改用p中心问题，不能把平均目标当成最坏情况保证。