跳到主要内容

设施位置问题

有 nn 个可以建造设施的位置，mm 个用户；建造设施的费用是 cjc_j，而服务用户的费用是 dijd_{ij}。求最优的位置以及用户的分配方案。

整数规划​

min⁡∑jcjxj+∑ijdijyij;s.t. ∑jyij=1,yij≤xj,xj,yij∈{0,1}\min\sum_jc_jx_j+\sum_{ij}d_{ij}y_{ij};\quad\mathrm{s.t.}~\sum_jy_{ij}=1,y_{ij}\le x_j,x_j,y_{ij}\in\{0,1\}

其中 yij≤xjy_{ij}\le x_j 也可以写做 ∑iyij≤mxj\sum_iy_{ij}\le mx_j。但是容易证明，线性放松之后有

ZAFL≤ZFL≤IZFL=IZAFLZ_{AFL}\le Z_{FL}\le IZ_{FL}=IZ_{AFL}