选址问题是运筹学中非常经典的问题。选址问题是指在确定选址对象，选址目标区，成本函数以及存在何种约束条件的前提下，以总物流成本最低或总服务最优或社会效益最大化为总目标，以确定物流系统中物流节点的数量、位置，从而合理规划物流网络结构。设施选址问题（Facility Location Problem）自20世纪60年代初期以来，在运筹学中一直占据着中心位置。它来自于工厂、仓库、超市、学校、医院、图书馆、火车站、代理服务器、传感器等位置的确定问题。
一、设施选址问题
1.1 无容量设施选址方法
线性规划舍入(LP rounding)法。此类技巧整体思路为建立问题的整数线性规划，松弛得到线性规划。通过求解线性规划得到分数解，再将其舍入成整数解。由于算法设计是在松弛线性规划的分数最优解基础上进行的，在分析时有下界门槛，利于得到近似比。但同时， 也由于求解线性规划，丢失了问题自身的组合结构。
原始对偶(primal-dual)法。此类技巧整体思路为建立问题的整数线性规划， 松弛得到线性规划。此时不需要求解松弛规划，而是建立松弛规划的对偶规划。利用对偶上升的过程构造对偶规划可行解。进一步通过对偶变量与整数规划的关系构造原始整数可行解。原始对偶技巧具有较好的可移植性， 在很多选址的拓展问题有较好的应用。一般来说， 这类技巧所得的近似比较高。
局部搜索(local search)法。此类技巧整体思想为以任意可行解为初始解，定义在当前解的基础上进行增加一个设施、减少一个设施和交换一对设施三类运算。如果三类运算可以改进当前解，进行更新，否则算法终止。局部搜索技巧结构简单，易于实现。但同时，分析过程复杂，难移植且近似比较高。
1.2 带容量限制的设施选址
实际问题的选址环境由于资源有限，顾客需求丰富等原因会复杂得多，这样出现了大量选址的拓展问题。
(a)带软容量限制的设施选址问题： 每个设施都有容量限制，但可以通过支付多倍的设施费用得到多倍的容量从而对顾客提供服务。该问题的目标为选择每个设施开设的次数， 连接顾客到开设设施上且不违背设施的容量限制，使得开设费用和服务费用总和最小。
(b)带硬容量设施选址问题：每个设施都有容量限制, 且设施的容量不能通过多次支付费用获得。该问题的目标为选择开设一些设施， 连接顾客到开设的设施上且不违背设施的容量限制，使得开设费用和服务费用总和最小。
(c)带惩罚的设施选址问题：在选址中，可以对于某些距离较远的顾客不进行服务。由于不服务会导致利润的损失，或者说成本的上升。因此，每个顾客有不被服务的惩罚成本。该问题的目标为选择开设哪些设施，惩罚哪些顾客，使得开设费用、服务费用和惩罚费用总和最小。
(d)带异常点的设施选址问题：在选址中，商家可以设置顾客异常点的个数。在选址中允许有至多个顾客不被服务，同时选择选择开设哪些设施，服务哪些顾客使得开设费用和服务费用总和最小。
(e)多层设施选址问题：顾客需求的复杂会导致选址是一个“流水线”过程，需要通过多个步骤完成，这样产生了多层设施选址问题。在每一步中都需要选择一些设施开设，每个顾客的需求由每一阶段开设的设施组成的一组开设设施满足，最终使得开设费用和服务费用总和最小。
设施选址的其他变形 根据实际生产生活中的需求，设施选址问题还衍生了一些重要拓展问题， 如k-中位问题、随机设施问题、在线设施选址问题、容错设施选址问题、整合配送网络设计问题等等。
二、整数规划问题示例
2.1 背包问题
设有一个背包，其最大承重为 \(b\) ，考虑 \(n\) 件物品，其中第 \(j\) 件重量为 \(a_j\) ，其价值为 \(c_j\) 。问 如何选取物品装入背包中，使得背包内物品的总价值最大?
设决策变量 \(x_j=\left\{\begin{array}{l}1, \text { 若选第 } j \text { 件物品 } \\ 0, \text { 若不选 }\end{array}\right.\)
则背包问题可以表示为下列整数规划:
2.2 广义指派问题
设有 \(m\) 台机器， \(n\) 个工件，第 \(i\) 台机器的可用工时数为 \(b_i\) ，第 \(i\) 台机器完成第 \(j\) 件工件需 要的工时数为 \(a_{i j}\) ，费用为 \(c_{i j}\) 。问如何最优指派机器生产。
设决策变量 \(x_{i j}=\left\{\begin{array}{l}1, \text { 若第 } i \text { 机器加工第 } j \text { 件工件 } \\ 0, \text { 其他 }\end{array}\right.\)
则广义指派问题可以表示为下列整数规划:
2.3 集合覆盖问题
设某地区划分为若干个区域，需要建立若干个应急服务中心 (如消防站，急救中心等），每个中心 的建立都需要一笔建站费用，设候选中心的位置已知，每个中心可以服务的区域预先知道，问如何 选取中心使得应急服务能覆盖整个地区且使得建站费用最小。
记 \(M=\{1, \cdots, m\}\) 为该地区中的区域， \(N=\{1, \cdots, n\}\) 是可选的中心，设 \(S_j \subseteq M\) 为中心 \(j \in N\) 可以服务的区域集合， \(c_j\) 是中心建站费用，定义0-1关联矩阵 \(A=\left(a_{i j}\right)\) ，其 中，若 \(i \in S\) ，则 \(a_{i j}=1\) ，否则 \(a_{i j}=0\)
设 \(x_j=\left\{\begin{array}{l}1, \text { 选中心 } j \\ 0, \text { 不选 }\end{array}\right.\)
则问题可以表示为:
二、产能受限型工厂选址模型模型
管理者利用该模型将需求在现有生产设施间进行分配。虽然生产设施的地点和产能变化很少，但随着需求和成本的变化，分配给每个设施的需求可以更频繁地改变。需求分配模型需要以下输入：
\(n\) 是工厂地点的数量
\(m\) 是市场或需求点的数量
\(D_j\) 是市场j的年需
\(K_i\) 是工厂i的产能
\(c_{ij}\) 是工厂i运送单位产量到市场j的成本
\(x_{ij}\) 是工厂i运送单位产量到市场j的数量
需求分配问题可以表述为以下线性规划问题：
\[\min \left(\sum_{i=1}^n \sum_{j=1}^m c_{i j} x_{i j}\right) \]约束条件为:
\[\begin{gathered} \sum_{i=1}^n x_{i j}=D_j, \quad j=1,2, \ldots, m \\ \sum_{j=1}^m x_{i j} \leq K_i, \quad i=1,2, \ldots, n \\ 0 \leq x_{i j} \quad i=1,2, \ldots, n\quad j=1,2, \ldots, m \end{gathered} \]原文链接：https://blog.csdn.net/weixin_56917624/article/details/130064118
\[y_{i}= \begin{cases} 1, & 工厂选址在地点i\\ 0, & 其他\end{cases} \]\[x_{ij}= \begin{cases} 1, & 如果市场j需求由工厂i来供应\\ 0, & 其他\end{cases} \]\[\min \left(\sum_{i=1}^n f_i y_i+\sum_{i=1}^n \sum_{j=1}^m D_j c_{i j} x_{i j}\right) \]约束条件为:
\[\begin{gathered} \sum_{i=1}^n x_{i j}=1, \quad j=1,2, \ldots, m \\ \sum_{j=1}^m D_j x_{i j} \leq K_i y_i, \quad i=1,2, \ldots, n \\ x_{i j}, y_i \in\{0.1\} \end{gathered} \]三、案例分析-Python
某供应链企业欲重构北美洲、南美洲、欧洲、非洲和亚洲这5个区域的全球化供应网络，收集到成本(单位：千美元)和需求(单位：百万)数据如下表所示：
| 产 地 | 北美洲B1 | 南美洲B2 | 欧洲B3 | 亚洲B4 | 非洲B5 | 固定成本 | 最高供应量H |
|---|---|---|---|---|---|---|---|
| 北美洲A1 | 81 | 92 | 101 | 130 | 115 | 9000 | 20 |
| 南美洲A2 | 117 | 77 | 108 | 98 | 100 | 6750 | 20 |
| 欧 洲A3 | 102 | 105 | 95 | 119 | 111 | 9750 | 20 |
| 亚 洲A4 | 115 | 125 | 90 | 59 | 74 | 6150 | 20 |
| 非 洲A5 | 142 | 100 | 103 | 105 | 71 | 6000 | 20 |
每个区域的年需求见表中最后一行，中间区域(第2列到第6列)包含了在一个区域组织生产来满足每一个区域的需求所需的生产、库存和运输可变成本(包括税收和关税)，如北美洲生产100万单位产品然后到南美洲销售的可变成本是92000美元；对于每个可供选择的工厂都需固定成本见表中(第7列)，他们都可生产2000万单位的产品，如在北美洲兴建一个工厂所需的固定成本为9000000美元，最高生产能力为2000万。试问选择哪些工厂生产产品，使得整个供应网络运作的总成本最小？
参考文献
| \begin{aligned}
& \min \sum_i f_i y_i+\sum_{i, j} c_{i j} x_{i j} \quad \min \sum_i f_i y_i+\sum_{i, j} c_{i j} x_{i j} \
& \text { s.t. } \sum_i x_{i j} \geq 1, \quad \forall j \quad \stackrel{\text { 松他 }}{\longrightarrow} \text { s.t. } \sum_i x_{i j} \geq 1, \quad \forall j \
& x_{i j} \leq y_i, \quad \forall i, j \quad x_{i j} \leq y_i, \quad \forall i, j \
& x_{i j}, y_i \in{0,1}, \quad \forall i, j \quad x_{i j}, y_i \geq 0, \quad \forall i, j \
& \text { 个舍入 } \
&
\end{aligned} | |