选址问题是要选择设施位置使目标达到最优，是数模竞赛中的常见题型。
小白不一定要掌握所有的选址问题，但要能判断是哪一类问题，用哪个模型。
进一步学习 PuLP工具包中处理复杂问题的字典格式快捷建模方法。
欢迎关注『Python小白的数学建模课 @ Youcans』系列，每周持续更新
1. 选址问题
选址问题是指在某个区域内选择设施的位置使所需的目标达到最优。选址问题也是一种互斥的计划问题。
例如投资场所的选址：企业要在 m 个候选位置选择若干个建厂，已知建厂费用、运输费及 n 个地区的产品需求量，应如何进行选址。
选址问题是运筹学中经典的问题之一，选址问题在生产生活、物流、甚至军事中都有着非常广泛的应用，如工厂、仓库、急救中心、消防站、垃圾处理中心、物流中心、导弹仓库的选址等。更重要的，选址问题也是数模竞赛的热点问题。
选址是重要的长期决策，选址的好坏直接影响到服务方式、服务质量、服务效率、服务成本等，从而影响到利润和市场竞争力，选址问题的研究有着重大的经济、社会和军事意义。
选址问题有四个基本要素：设施、区域、距离和优化目标。
欢迎关注『Python小白的数学建模课 @ Youcans』系列，每周持续更新
Python小白的数学建模课-01.新手必读
Python小白的数学建模课-02.数据导入
Python小白的数学建模课-03.线性规划
Python小白的数学建模课-04.整数规划
Python小白的数学建模课-05.0-1规划
Python小白的数学建模课-06.固定费用问题
Python小白的数学建模课-07.选址问题
Python小白的数学建模课-09.微分方程模型
Python小白的数学建模课-10.微分方程边值问题
Python小白的数学建模课-12.非线性规划
Python小白的数学建模课-15.图论的基本概念
Python小白的数学建模课-16.最短路径算法
Python小白的数学建模课-17.条件最短路径算法
1.1 设施
选址问题加粗样式中所说的设施，在具体题目中可以是工厂、仓库、服务站等形式。
1.2 区域
选址问题中所说的区域，在具体题目中可以是工厂、车间的内部布局，也可以是给定的某个地区、甚至空间范围。
按照规划区域的特征，可以分为连续选址问题和离散选址问题。连续选址问题，设施可以布局在区域内的任意位置，就要求出最优选址的坐标；离散选址问题，只能从若干候选位置中进行选择，运筹学中的选址问题通常是这类离散选址问题。
1.3 距离
选址问题中所说的距离，是指设施到服务对象之间的距离，在具体题目中也可以是某个选址位置的服务时间、成本、覆盖范围。如果用图论方法求解，通常就是连接顶点的边的权值。
当问题所关注的是设施到服务对象之间的距离时，如果问题给出的不是顶点之间的距离，而是设施的位置坐标，要注意不是只有欧式距离，对于不同问题也可能是球面距离、曼哈顿距离、切比雪夫距离。
1.4 优化目标
选址问题要求选择最好的选址位置，但选址位置只是决策变量，选择的最终目的通常是实现加权距离最短、费用最小、利润最大、时间最短，这才是优化问题的目标函数。
按照目标函数的特点，可以分为：中位问题，要求总成本最小；中心问题，服务于每个客户的最大成本最小；反中心问题：服务于每个客户的最小成本最大。
2. 常见选址问题及建模
2.1 P-中位问题（P-median problem）
P-中位问题，假设有 N 个候选服务站和 M 个需求点，要从 N 个候选服务站中选择 P 个，使所有需求点到最近的服务站的加权距离 d i j d_{ij} dij 的总和最小。需求点 i 的权值，通常是指该需求点的需求量。
这是一个 MinSum 问题，定义决策变量 x j x_j xj 为选中的服务站， y i j y_{ij} yij 将各需求点匹配到最近的服务站：
x j = { 1 ， 服 务 站 j 被 选 中 0 ， 服 务 站 j 未 被 选 中 x_j = \begin{cases} 1，& 服务站\ j\ 被选中\\ 0，& 服务站\ j\ 未被选中 \end{cases} xj={1，0，服务站 j 被选中服务站 j 未被选中
y i j = { 1 ， 需 求 点 i 由 服 务 站 j 服 务 0 ， 需 求 点 i 不 由 服 务 站 j 服 务 y_{ij} = \begin{cases} 1，& 需求点\ i\ 由服务站\ j\ 服务\\ 0，& 需求点\ i\ 不由服务站\ j\ 服务 \end{cases} yij={1，0，需求点 i 由服务站 j 服务需求点 i 不由服务站 j 服务
可以建立数学模型如下：
m i n ∑ i ∈ M ∑ j ∈ N w i d i j y i j s . t . : { ∑ j ∈ N x j = P ∑ j ∈ N y i j = 1 ， ∀ i y i j − x j ≤ 0 ， ∀ i , j x j ∈ { 0 , 1 } , y i j ∈ { 0 , 1 } min\;\sum_{i \in M}\sum_{j \in N} w_i d_{ij}y_{ij}\\ s.t.:\;\begin{cases} \sum_{j \in N} x_{j} = P\\ \sum_{j \in N} y_{ij} = 1，\forall i\\ y_{ij} - x_j \leq 0，\forall i,j\\ x_{j} \in \{0,1\}, \;y_{ij} \in \{0,1\} \end{cases} mini∈M∑j∈N∑widijyijs.t.:⎩⎪⎪⎪⎨⎪⎪⎪⎧∑j∈Nxj=P∑j∈Nyij=1，∀iyij−xj≤0，∀i,jxj∈{0,1},yij∈{0,1}
其中：j 为服务站，i 为需求点， w i w_i wi 为需求点 i 的需求量， d i j d_{ij} dij 为需求点 i 到服务站 j 的距离。
2.2 P-中心问题
P-中心问题，假设有 N 个候选服务站和 M 个需求点，要从 N个候选服务站中选择 P个，使任一需求点到最近的服务站的最大距离最小。
这是一个 MinMax 问题，需要最小化任何需求点与其邻近设施点的最大距离。P-中位问题追求总和最小，可以理解为发展经济总量优先；P-中心问题关注最差个体的最好结果，可以理解为优先进行扶贫。
定义决策变量 x j x_j xj 为选中的服务站， y i j y_{ij} yij 将各需求点匹配到最近的服务站：
x j = { 1 ， 服 务 站 j 被 选 中 0 ， 服 务 站 j 未 被 选 中 x_j = \begin{cases} 1，& 服务站\ j\ 被选中\\ 0，& 服务站\ j\ 未被选中\end{cases} xj={1，0，服务站 j 被选中服务站 j 未被选中
y i j = { 1 ， 需 求 点 i 由 服 务 站 j 服 务 0 ， 需 求 点 i 不 由 服 务 站 j 服 务 y_{ij} = \begin{cases} 1，& 需求点\ i\ 由服务站\ j\ 服务\\ 0，& 需求点\ i\ 不由服务站\ j\ 服务\end{cases} yij={1，0，需求点 i 由服务站 j 服务需求点 i 不由服务站 j 服务
可以建立数学模型如下：
m i n D s . t . : { ∑ j ∈ N w i d i j y i j ≤ D , ∀ i ∑ j ∈ N x j = P ∑ j ∈ N y i j = 1 , ∀ i y i j − x j ≤ 0 , ∀ i , j x j ∈ { 0 , 1 } , y i j ∈ { 0 , 1 } min\; D\\ s.t.:\;\begin{cases} \sum_{j \in N} w_i d_{ij} y_{ij} \leq D, \forall i\\ \sum_{j \in N} x_{j} = P\\ \sum_{j \in N} y_{ij} = 1, \forall i\\ y_{ij} - x_j \leq 0, \forall i,j\\ x_{j} \in \{0,1\}, \;y_{ij} \in \{0,1\} \end{cases} minDs.t.:⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧∑j∈Nwidijyij≤D,∀i∑j∈Nxj=P∑j∈Nyij=1,∀iyij−xj≤0,∀i,jxj∈{0,1},yij∈{0,1}
其中：j 为服务站，i 为需求点， d i j d_{ij} dij 为需求点 i 到服务站 j 的距离。如果只求需求点到最近的服务站的最大距离，则 w i = 1 w_i = 1 wi=1 ；如果要求任一需求点到最近的服务站的最大运费，则 w i w_i wi 为需求点 i 的需求量，即加权最大距离。
2.3 集合覆盖问题
覆盖模型适用于一些特殊场景，例如消防中心、救护车、巡逻车等应急设施的区位选址问题。覆盖问题分为集合覆盖问题（Set covering problem）和最大覆盖问题（Maximal covering problem）。
集合覆盖问题研究满足覆盖所有需求点顾客的前提下，服务站的最少个数或建设费用最小的问题。假设有 N 个候选服务站和 M 个需求点，已知每个服务站的服务范围（或服务容量），要从 N个候选服务站中选择若干个，使所有需求点得到服务（到所属服务站的距离或时间小于给定的临界值），服务站的个数最少或成本最小。
定义参数 a i j a_{ij} aij 为每个服务站的覆盖范围：
a i j = { 1 ， 服 务 站 j 可 以 覆 盖 需 求 点 i 0 ， 服 务 站 j 不 能 覆 盖 需 求 点 i a_{ij} = \begin{cases} 1，& 服务站\ j\ 可以覆盖需求点\ i\\ 0，& 服务站\ j\ 不能覆盖需求点\ i \end{cases} aij={1，0，服务站 j 可以覆盖需求点 i服务站 j 不能覆盖需求点 i
定义决策变量 x j x_j xj 为选中的服务站：
x j = { 1 ， 服 务 站 j 被 选 中 0 ， 服 务 站 j 未 被 选 中 x_j = \begin{cases} 1，& 服务站\ j\ 被选中\\ 0，& 服务站\ j\ 未被选中\end{cases} xj={1，0，服务站 j 被选中服务站 j 未被选中
可以建立数学模型如下：
m i n ∑ j ∈ N c j x j s . t . : { ∑ j ∈ N i x j ≥ 1 , ∀ i ∈ M x j ∈ { 0 , 1 } min\; \sum_{j \in N} c_j x_{j}\\ s.t.:\;\begin{cases} \sum_{j \in N_i} x_j \geq 1, \forall i \in M\\ x_{j} \in \{0,1\} \end{cases} minj∈N∑cjxjs.t.:{∑j∈Nixj≥1,∀i∈Mxj∈{0,1}
其中：j 为服务站，i 为需求点， c j c_j cj 为服务站 j 的建设费用（最少个数问题中不需要考虑）， N i = { j : a i j = 1 } N_i=\{j:a_{ij}=1\} Ni={j:aij=1} 是覆盖需求点 i 的候选服务站的集合。
2.4 最大覆盖问题
最大覆盖问题研究在已知服务站的数目和服务半径的条件下，如何设立 P个服务站使得可接受的服务需求最大的问题。
定义决策变量 x j x_j xj 为选中的服务站：
x j = { 1 ， 服 务 站 j 被 选 中 0 ， 服 务 站 j 未 被 选 中 x_j = \begin{cases} 1，& 服务站\ j\ 被选中\\ 0，& 服务站\ j\ 未被选中 \end{cases} xj={1，0，服务站 j 被选中服务站 j 未被选中
KaTeX parse error: Undefined control sequence: \ at position 57: …，& 需求点\ i\ 未被覆盖\̲ ̲\end{cases}
可以建立数学模型如下：
m a x ∑ i ∈ N i w i z i s . t . : { z i ≤ ∑ j ∈ N i x j , ∀ i ∈ M ∑ j ∈ M x j = p x j ∈ { 0 , 1 } , z i ∈ { 0 , 1 } max\; \sum_{i \in N_i} w_i z_i\\ s.t.:\; \begin{cases} z_i \leq \sum_{j \in N_i} x_j , \forall i \in M\\ \sum_{j \in M} x_j = p\\ x_{j} \in \{0,1\}, z_{i} \in \{0,1\} \end{cases} maxi∈Ni∑wizis.t.:⎩⎪⎨⎪⎧zi≤∑j∈Nixj,∀i∈M∑j∈Mxj=pxj∈{0,1},zi∈{0,1}
其中：j 为服务站，i 为需求点， w i w_i wi 为需求点 i 的需求量。
2.5 其它选址问题
其它选址问题，在数学建模中应用相对较少，限于篇幅不能逐一介绍其数学模型。在此将各模型的特点简要介绍，以便判断问题的类型。
带固定费用和容量限制的选址问题
服务站建站的固定费用和服务站的容量（能力）限制这两个因素具有很强的实际意义，经常作为基本选址问题的深化研究课题。
无容量限制的固定费用下的选址问题，就是去掉服务站个数的约束，并将固定建站费用加到 P-中位问题的目标函数上。
选址分配问题
选址分配问题类似于 P-中位问题，有 m 个服务站需要选址，n 个已知位置的顾客分配给不同的设施，已知每个服务站的能力和每个顾客的需求，要求服务站的选址和顾客对服务站的分配，使顾客与所分配服务站的距离总和最小。
随机选址问题
服务站的运行时间、建设成本、需求点位置、需求数量等全部或部分参数是不确定的，但服从某种随机分布。
动态选址问题
研究未来若干时间段内服务站的最优选址问题，在不同时间段内动态选址模型的参数是变化的，但在某一时间段内模型参数是确定的。
竞争选址问题
研究考虑市场上存在两个以上同类产品或服务的提供者，或服务站提供多个产品或服务。
2.6 选址问题的求解算法与编程实现
设施选址问题通常是是 NP 问题，不存在多项式时间算法。常用的近似解法有：
线性规划舍入算法，相当于整数规划问题的求解算法。首先给出原问题的整数规划模型，然后求解相应的线性规划松弛问题得到分数最优解，根据可行要求对分数最优解进行改造，构造原问题的整数可行解。
原始对偶算法，首先找到对偶问题的一个可行解，再根据该对偶可行解构造原始问题的整数可行解，不断调整对偶问题的可行解，直到找到最优解为止。
局部搜索算法：给定初始可行解，定义适当的邻域，通过引入恰当的调整策略，在邻域中得到改进的可行解，依次迭代，直到调整策略不能改进为止
启发式算法或随机优化算法。
本节作为线性规划问题系列的一篇，仍然选择 PuLP工具包求解选址问题。很多选址问题适合用图论方法描述和求解，这将在后续课程中进行介绍。
3. 案例 1：PuLP求解指派问题
说明：本案例是指派问题，不是选址问题。因指派问题未单独成文，因此将该案例放在本文中。
另外，本案例给出了 PuLP 工具包使用字典方式快捷编程的使用方法，这在选址问题中是非常方便的。
3.1 游泳接力赛的指派问题
游泳队中 A、B、C、D 四名运动员组成 4x100米混合泳接力队，运动员各种泳姿的成绩如下表所示 （单位：秒）：
| 队员\项目 | 自由泳 | 蛙泳 | 蝶泳 | 仰泳 |
|---|---|---|---|---|
| A | 56 | 74 | 61 | 63 |
| B | 63 | 69 | 65 | 71 |
| C | 57 | 77 | 63 | 67 |
| D | 55 | 76 | 62 | 62 |
如何安排 A、B、C、D 四名运动员的泳姿，才最有可能取得好成绩？
3.2 指派问题建模分析
引入 0-1 变量 x i j x_{ij} xij：
x i , j = { 0 ， 第 i 人 不 游 第 j 种 姿 势 1 ， 第 i 人 游 第 j 种 姿 势 ， i , j = 1 , . . . 4 x_{i,j} = \begin{cases} 0，第\;i\;人不游第\;j\;种姿势\\ 1，第\;i\;人游第\;j\;种姿势，i,j=1,...4 \end{cases} xi,j={0，第i人不游第j种姿势1，第i人游第j种姿势，i,j=1,...4
指派问题的数学模型就可以描述为：
m i n f ( x ) = ∑ i = 1 n ∑ j = 1 n ( c i j x i j ) s . t . : { ∑ j = 1 n x i j = 1 ， i = 1 , . . . , n ∑ i = 1 n x i j = 1 ， j = 1 , . . . , n x i j = 0 , 1 ， i , j = 1 , . . . , n min\;f(x) = \sum_{i=1} ^n \sum_{j=1} ^n (c_{ij} x_{ij})\\ s.t.:\;\begin{cases} \sum_{j=1} ^n x_{ij} = 1，i=1,...,n\\ \sum_{i=1} ^n x_{ij} = 1，j=1,...,n\\ x_{ij} = 0,1，i,j=1,...,n \end{cases} minf(x)=i=1∑nj=1∑n(cijxij)s.t.:⎩⎪⎨⎪⎧∑j=1nxij=1，i=1,...,n∑i=1nxij=1，j=1,...,nxij=0,1，i,j=1,...,n
其中：
c i , j = ( 56 74 61 63 63 69 65 71 57 77 63 67 55 76 62 62 ) c_{i,j}=\left( \begin{matrix} 56 & 74 & 61 & 63 \\ 63 & 69 & 65 & 71 \\ 57 & 77 & 63 & 67 \\ 55 & 76 & 62 & 62 \end{matrix} \right) ci,j=⎝⎜⎜⎛56635755746977766165636263716762⎠⎟⎟⎞
3.3 指派问题模型求解的编程
模型求解，用标准模型的优化算法对模型求解，得到优化结果。模型求解的编程步骤如下：
（0）导入 PuLP库函数
import pulp（1）定义一个规划问题
AssignLP = pulp.LpProblem("Assignment_problem_for_swimming_relay_race", sense=pulp.LpMinimize)pulp.LpProblem 用来定义问题的构造函数。参数 sense 指定问题求目标函数的最小值/最大值 。
（2）定义决策变量
rows = cols = range(0, 4) x = pulp.LpVariable.dicts("x", (rows, cols), cat="Binary")pulp.LpVariable 用来定义决策变量的函数。参数 cat 设定变量类型，’ Binary ’ 表示 0/1 变量。
注意，指派问题、选址问题中都涉及 N*M 维矩阵变量，变量个数很多，如果逐一定义非常冗长，而且容易出错、不便修改。本例使用 pulp.LpVariable.dicts 提供的字典格式定义了 4*4 个变量 x i j x_{ij} xij，使程序大为简化。
（3）添加目标函数
scoreM = [[56,74,61,63],[63,69,65,71],[57,77,63,67],[55,76,62,62]] AssignLP += pulp.lpSum([[x[row][col]*scoreM[row][col] for row in rows] for col in cols])本例程在语句内使用两重 for 循环遍历列表实现所有变量的线性组合 ，使程序大为简化。
（4）添加约束条件
for row in rows: AssignLP += pulp.lpSum([x[row][col] for col in cols]) == 1 # sum(x(i,j),j=1,4)=1, i=1,4 for col in cols: AssignLP += pulp.lpSum([x[row][col] for row in rows]) == 1 # sum(x(i,j),i=1,4)=1, j=1,4快捷方法对于约束条件的定义与对目标函数的定义相似，使用字典定义参数，使用循环定义约束条件，使程序简单、结构清楚。
（5）求解和结果输出
AssignLP.solve() # youcans print(AssignLP.name) member = ["队员A","队员B","队员C","队员D"] style = ["自由泳","蛙泳","蝶泳","仰泳"] if pulp.LpStatus[AssignLP.status] == "Optimal": # 获得最优解 xValue = [v.varValue for v in AssignLP.variables()] # [0.0, 0.0, 1.0, 0.0, 0.0, 1.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.0] xOpt = np.array(xValue).reshape((4, 4)) # 将 xValue 格式转换为 4x4 矩阵 print("最佳分配：" ) for row in rows: print("{}\t{} 参加项目：{}".format(xOpt[row],member[row],style[np.argmax(xOpt[row])])) print("预测最好成绩为：{}".format(pulp.value(AssignLP.objective)))xValue 获得的是列表变量，通过 numpy 的 reshape() 函数转换为 4*4 矩阵，便于格式化输出。
3.4 指派问题 Python 例程
# mathmodel08_v1.py# Demo08 of mathematical modeling algorithm# Solving assignment problem with PuLP.# Copyright 2021 Youcans, XUPT# Crated：2021-06-02# Python小白的数学建模课 @ Youcansimport pulp # 导入 pulp 库import numpy as np# 主程序def main(): # 问题建模： """ 决策变量： x(i,j) = 0, 第 i 个人不游第 j 种姿势 x(i,j) = 1, 第 i 个人游第 j 种姿势 i=1,4, j=1,4 目标函数： min time = sum(sum(c(i,j)*x(i,j))), i=1,4, j=1,4 约束条件： sum(x(i,j),j=1,4)=1, i=1,4 sum(x(i,j),i=1,4)=1, j=1,4 变量取值范围： x(i,j) = 0,1 """ # 游泳比赛的指派问题 (assignment problem) # 1.建立优化问题 AssignLP: 求最小值(LpMinimize) AssignLP = pulp.LpProblem("Assignment_problem_for_swimming_relay_race", sense=pulp.LpMinimize) # 定义问题，求最小值 # 2. 建立变量 rows = cols = range(0, 4) x = pulp.LpVariable.dicts("x", (rows, cols), cat="Binary") # 3. 设置目标函数 scoreM = [[56,74,61,63],[63,69,65,71],[57,77,63,67],[55,76,62,62]] AssignLP += pulp.lpSum([[x[row][col]*scoreM[row][col] for row in rows] for col in cols]) # 4. 施加约束 for row in rows: AssignLP += pulp.lpSum([x[row][col] for col in cols]) == 1 # sum(x(i,j),j=1,4)=1, i=1,4 for col in cols: AssignLP += pulp.lpSum([x[row][col] for row in rows]) == 1 # sum(x(i,j),i=1,4)=1, j=1,4 # 5. 求解 AssignLP.solve() # youcans # 6. 打印结果 print(AssignLP.name) member = ["队员A","队员B","队员C","队员D"] style = ["自由泳","蛙泳","蝶泳","仰泳"] if pulp.LpStatus[AssignLP.status] == "Optimal": # 获得最优解 xValue = [v.varValue for v in AssignLP.variables()] # [0.0, 0.0, 1.0, 0.0, 0.0, 1.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.0] xOpt = np.array(xValue).reshape((4, 4)) # 将 xValue 格式转换为 4x4 矩阵 print("最佳分配：" ) for row in rows: print("{}\t{} 参加项目：{}".format(xOpt[row],member[row],style[np.argmax(xOpt[row])])) print("预测最好成绩为：{}".format(pulp.value(AssignLP.objective))) returnif __name__ == '__main__': # Copyright 2021 YouCans, XUPT main() # Python小白的数学建模课 @ Youcans3.5 Python 例程运行结果
Welcome to the CBC MILP Solver Version: 2.9.0 Build Date: Feb 12 2015 Result - Optimal solution foundAssignment_problem_for_swimming_relay_race最佳分配：[0. 0. 1. 0.]队员A 参加项目：蝶泳[0. 1. 0. 0.]队员B 参加项目：蛙泳[1. 0. 0. 0.]队员C 参加项目：自由泳[0. 0. 0. 1.]队员D 参加项目：仰泳预测最好成绩为：249.04. 案例 2：PuLP求解选址问题
4.1 消防站的选址问题
例题 2：某城市有 8 个区，每个区最多建一个消防站，拟建设消防站到各区的最长时间如下表所示。现要求任何区域发生火警时，消防车能在 10分钟内赶到。在此条件下尽量减少消防站数量，应该在哪几个区建设消防站？
| 区域 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| 1 | 7 | 12 | 18 | 20 | 24 | 26 | 25 | 28 |
| 2 | 14 | 5 | 8 | 15 | 16 | 18 | 18 | 18 |
| 3 | 19 | 9 | 4 | 14 | 10 | 22 | 16 | 13 |
| 4 | 14 | 15 | 15 | 10 | 18 | 15 | 14 | 18 |
| 5 | 20 | 18 | 12 | 20 | 9 | 25 | 14 | 12 |
| 6 | 18 | 21 | 20 | 16 | 20 | 6 | 10 | 15 |
| 7 | 22 | 18 | 20 | 15 | 16 | 15 | 5 | 9 |
| 8 | 30 | 22 | 15 | 20 | 14 | 18 | 8 | 6 |
4.2 选址问题建模分析
首先判断这是一个集合覆盖问题，要求从 8 个候选消防站中选择若干个，在所有需求点得到服务的时间都小于临界值 10分钟的条件下，选择消防站的数量最少。本问题不考虑各候选站点建设费用的差异，即不带权重。
定义参数 R i j R_{ij} Rij 为每个消防站的覆盖范围：
R i j = { 1 ， 消 防 站 j 可 以 覆 盖 区 域 i 0 ， 消 防 站 j 不 能 覆 盖 区 域 i R_{ij} = \begin{cases} 1，& 消防站\ j\ 可以覆盖区域\ i\\ 0，& 消防站\ j\ 不能覆盖区域\ i \end{cases} Rij={1，0，消防站 j 可以覆盖区域 i消防站 j 不能覆盖区域 i
由拟建消防站到各区的最长时间表可以得到参数 R i j R_{ij} Rij 如下表：
| 区域 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 2 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
| 3 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 0 |
| 4 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| 5 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| 6 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 |
| 7 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 8 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
定义决策变量 x j x_j xj 为选中的服务站：
x j = { 1 ， 消 防 站 j 被 选 中 0 ， 消 防 站 j 未 被 选 中 x_j = \begin{cases} 1，& 消防站\ j\ 被选中\\ 0，& 消防站\ j\ 未被选中\end{cases} xj={1，0，消防站 j 被选中消防站 j 未被选中
可以建立数学模型如下：
m i n f ( x ) = ∑ j = 1 8 x j s . t . : { ∑ j = 1 8 x j R i j ≥ 1 , i = 1 , . . 8 x j ∈ { 0 , 1 } , j = 1 , . . 8 min\; f(x) = \sum_{j=1}^8 x_{j}\\ s.t.:\;\begin{cases} \sum_{j=1}^8 x_j R_{ij} \geq 1, &i=1,..8\\ x_{j} \in \{0,1\}, &j=1,..8 \end{cases} minf(x)=j=1∑8xjs.t.:{∑j=18xjRij≥1,xj∈{0,1},i=1,..8j=1,..8
选址问题的模型求解，用标准模型的优化算法对模型求解，得到优化结果。
模型求解的编程步骤与指派问题是一致的，且在例程中给出了详细的注释，就不再进行逐项解释了。
需要注意的是，选址问题的决策变量、参数、约束条件的数量较大（N*M），如果对变量、约束条件逐个进行定义，编程过程将是非常冗长和痛苦的，因此需要使用列表、字典等快捷方式进行定义。对于更大规模的问题，模型中的数据要通过读取数据文件获得，就更需要采用这种方式来编程。
4.3 选址问题 Python 例程
# mathmodel09_v1.py# Demo08 of mathematical modeling algorithm# Solving set covering problem with PuLP.# Copyright 2021 Youcans, XUPT# Crated：2021-06-06# Python小白的数学建模课 @ Youcansimport pulp # 导入 pulp 库# 主程序def main(): # 问题建模： """ 决策变量： x(j) = 0, 不选择第 j 个消防站 x(j) = 1, 选择第 j 个消防站, j=1,8 目标函数： min fx = sum(x(j)), j=1,8 约束条件： sum(x(j)*R(i,j),j=1,8) >=1, i=1,8 变量取值范围： x(j) = 0,1 """ # 消防站的选址问题 (set covering problem, site selection of fire station) # 1.建立优化问题 SetCoverLP: 求最小值(LpMinimize) SetCoverLP = pulp.LpProblem("SetCover_problem_for_fire_station", sense=pulp.LpMinimize) # 定义问题，求最小值 # 2. 建立变量 zones = list(range(8)) # 定义各区域 youcans x = pulp.LpVariable.dicts("zone", zones, cat="Binary") # 定义 0/1 变量，是否在该区域设消防站 # 3. 设置目标函数 SetCoverLP += pulp.lpSum([x[j] for j in range(8)]) # 设置消防站的个数 # 4. 施加约束 reachable = [[1, 0, 0, 0, 0, 0, 0, 0], [0, 1, 1, 0, 0, 0, 0, 0], [0, 1, 1, 0, 1, 0, 0, 0], [0, 0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0], [0, 0, 0, 0, 0, 1, 1, 0], [0, 0, 0, 0, 0, 0, 1, 1], [0, 0, 0, 0, 0, 0, 1, 1]] # 参数矩阵，第 i 消防站能否在 10分钟内到达第 j 区域 for i in range(8): SetCoverLP += pulp.lpSum([x[j]*reachable[j][i] for j in range(8)]) >= 1 # 5. 求解 SetCoverLP.solve() # 6. 打印结果 print(SetCoverLP.name) temple = "区域 %(zone)d 的决策是：%(status)s" # 格式化输出 if pulp.LpStatus[SetCoverLP.status] == "Optimal": # 获得最优解 for i in range(8): output = {'zone': i+1, # 与问题中区域 1~8 一致 'status': '建站' if x[i].varValue else '--'} print(temple % output) print("需要建立 {} 个消防站。".format(pulp.value(SetCoverLP.objective))) returnif __name__ == '__main__': # Copyright 2021 YouCans, XUPT main() # Python小白的数学建模课 @ Youcans4.4 Python 例程运行结果
Welcome to the CBC MILP Solver Version: 2.9.0 Build Date: Feb 12 2015 Result - Optimal solution foundSetCover_problem_for_fire_station区域 1 的决策是：建站区域 2 的决策是：--区域 3 的决策是：建站区域 4 的决策是：建站区域 5 的决策是：--区域 6 的决策是：建站区域 7 的决策是：建站区域 8 的决策是：--需要建立 5.0 个消防站5. 小结
关于规划问题，我们从线性规划、整数规划、0-1规划到一些特殊类型问题，用 5节课进行了介绍，到这里就暂告一段落了。后面根据需要，可能还会讲非线性规划，实际上主要是非线性优化问题了。虽然各种规划问题的求解算法差别很大，但我们所用的编程实现方法都是基于 PuLP工具包，编程步骤都是一致的。本系列集中体现了与其它课程的区别，没有展开讲算法的实现步骤，而是重点讲编程方法的选择、建立模型方程的过程和编程实现的步骤，这主要是为了便于小白学习和掌握。【本节完】
版权声明：
欢迎关注『Python小白的数学建模课 @ Youcans』 原创作品
原创作品，转载必须标注原文链接：(https://blog.csdn.net/youcans/article/details/117650843)。
Copyright 2021 Youcans, XUPT
Crated：2021-06-06
欢迎关注 『Python小白的数学建模课 @ Youcans』 系列，持续更新
Python小白的数学建模课-01.新手必读
Python小白的数学建模课-02.数据导入
Python小白的数学建模课-03.线性规划
Python小白的数学建模课-04.整数规划
Python小白的数学建模课-05.0-1规划
Python小白的数学建模课-06.固定费用问题
Python小白的数学建模课-07.选址问题
Python小白的数学建模课-09.微分方程模型
Python小白的数学建模课-10.微分方程边值问题
Python小白的数学建模课-12.非线性规划
Python小白的数学建模课-15.图论的基本概念
Python小白的数学建模课-16.最短路径算法
Python小白的数学建模课-17.条件最短路径算法
Python小白的数学建模课-18.最小生成树问题
Python小白的数学建模课-19.网络流优化问题
Python小白的数学建模课-20.网络流优化案例
Python小白的数学建模课-21.关键路径法
Python小白的数学建模课-22.插值方法
Python小白的数学建模课-23.数据拟合全集
Python小白的数学建模课-A1.国赛赛题类型分析
Python小白的数学建模课-A2.2021年数维杯C题探讨
Python小白的数学建模课-A3.12个新冠疫情数模竞赛赛题及短评
Python小白的数学建模课-B2. 新冠疫情 SI模型
Python小白的数学建模课-B3. 新冠疫情 SIS模型
Python小白的数学建模课-B4. 新冠疫情 SIR模型
Python小白的数学建模课-B5. 新冠疫情 SEIR模型
Python小白的数学建模课-B6. 新冠疫情 SEIR改进模型
Python数模笔记-PuLP库
Python数模笔记-StatsModels统计回归
Python数模笔记-Sklearn
Python数模笔记-NetworkX
Python数模笔记-模拟退火算法
