江西微网站建设,wordpress改中文,介绍家乡网页html代码,wordpress 所有文章404选址问题是要选择设施位置使目标达到最优#xff0c;是数模竞赛中的常见题型。
小白不一定要掌握所有的选址问题#xff0c;但要能判断是哪一类问题#xff0c;用哪个模型。
进一步学习 PuLP工具包中处理复杂问题的字典格式快捷建模方法。
欢迎关注『Python小白的数学建模…
选址问题是要选择设施位置使目标达到最优是数模竞赛中的常见题型。
小白不一定要掌握所有的选址问题但要能判断是哪一类问题用哪个模型。
进一步学习 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 个使所有需求点到最近的服务站的加权距离 dijd_{ij}dij 的总和最小。需求点 i 的权值通常是指该需求点的需求量。
这是一个 MinSum 问题定义决策变量 xjx_jxj 为选中的服务站yijy_{ij}yij 将各需求点匹配到最近的服务站 xj{1服务站j被选中0服务站j未被选中x_j \begin{cases} 1 服务站\ j\ 被选中\\ 0 服务站\ j\ 未被选中 \end{cases} xj{10服务站 j 被选中服务站 j 未被选中 yij{1需求点i由服务站j服务0需求点i不由服务站j服务y_{ij} \begin{cases} 1 需求点\ i\ 由服务站\ j\ 服务\\ 0 需求点\ i\ 不由服务站\ j\ 服务 \end{cases} yij{10需求点 i 由服务站 j 服务需求点 i 不由服务站 j 服务 可以建立数学模型如下
min∑i∈M∑j∈Nwidijyijs.t.:{∑j∈NxjP∑j∈Nyij1∀iyij−xj≤0∀i,jxj∈{0,1},yij∈{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∈NxjP∑j∈Nyij1∀iyij−xj≤0∀i,jxj∈{0,1},yij∈{0,1}
其中j 为服务站i 为需求点wiw_iwi 为需求点 i 的需求量 dijd_{ij}dij 为需求点 i 到服务站 j 的距离。 2.2 P-中心问题
P-中心问题假设有 N 个候选服务站和 M 个需求点要从 N个候选服务站中选择 P个使任一需求点到最近的服务站的最大距离最小。
这是一个 MinMax 问题需要最小化任何需求点与其邻近设施点的最大距离。P-中位问题追求总和最小可以理解为发展经济总量优先P-中心问题关注最差个体的最好结果可以理解为优先进行扶贫。
定义决策变量 xjx_jxj 为选中的服务站yijy_{ij}yij 将各需求点匹配到最近的服务站 xj{1服务站j被选中0服务站j未被选中x_j \begin{cases} 1 服务站\ j\ 被选中\\ 0 服务站\ j\ 未被选中\end{cases} xj{10服务站 j 被选中服务站 j 未被选中
yij{1需求点i由服务站j服务0需求点i不由服务站j服务y_{ij} \begin{cases} 1 需求点\ i\ 由服务站\ j\ 服务\\ 0 需求点\ i\ 不由服务站\ j\ 服务\end{cases} yij{10需求点 i 由服务站 j 服务需求点 i 不由服务站 j 服务
可以建立数学模型如下
minDs.t.:{∑j∈Nwidijyij≤D,∀i∑j∈NxjP∑j∈Nyij1,∀iyij−xj≤0,∀i,jxj∈{0,1},yij∈{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∈NxjP∑j∈Nyij1,∀iyij−xj≤0,∀i,jxj∈{0,1},yij∈{0,1}
其中j 为服务站i 为需求点 dijd_{ij}dij 为需求点 i 到服务站 j 的距离。如果只求需求点到最近的服务站的最大距离则 wi1w_i 1wi1 如果要求任一需求点到最近的服务站的最大运费则 wiw_iwi 为需求点 i 的需求量即加权最大距离。 2.3 集合覆盖问题
覆盖模型适用于一些特殊场景例如消防中心、救护车、巡逻车等应急设施的区位选址问题。覆盖问题分为集合覆盖问题Set covering problem和最大覆盖问题Maximal covering problem。
集合覆盖问题研究满足覆盖所有需求点顾客的前提下服务站的最少个数或建设费用最小的问题。假设有 N 个候选服务站和 M 个需求点已知每个服务站的服务范围或服务容量要从 N个候选服务站中选择若干个使所有需求点得到服务到所属服务站的距离或时间小于给定的临界值服务站的个数最少或成本最小。
定义参数 aija_{ij}aij 为每个服务站的覆盖范围
aij{1服务站j可以覆盖需求点i0服务站j不能覆盖需求点ia_{ij} \begin{cases} 1 服务站\ j\ 可以覆盖需求点\ i\\ 0 服务站\ j\ 不能覆盖需求点\ i \end{cases} aij{10服务站 j 可以覆盖需求点 i服务站 j 不能覆盖需求点 i
定义决策变量 xjx_jxj 为选中的服务站 xj{1服务站j被选中0服务站j未被选中x_j \begin{cases} 1 服务站\ j\ 被选中\\ 0 服务站\ j\ 未被选中\end{cases} xj{10服务站 j 被选中服务站 j 未被选中
可以建立数学模型如下
min∑j∈Ncjxjs.t.:{∑j∈Nixj≥1,∀i∈Mxj∈{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 为需求点cjc_jcj 为服务站 j 的建设费用最少个数问题中不需要考虑Ni{j:aij1}N_i\{j:a_{ij}1\}Ni{j:aij1} 是覆盖需求点 i 的候选服务站的集合。 2.4 最大覆盖问题
最大覆盖问题研究在已知服务站的数目和服务半径的条件下如何设立 P个服务站使得可接受的服务需求最大的问题。
定义决策变量 xjx_jxj 为选中的服务站 xj{1服务站j被选中0服务站j未被选中x_j \begin{cases} 1 服务站\ j\ 被选中\\ 0 服务站\ j\ 未被选中 \end{cases} xj{10服务站 j 被选中服务站 j 未被选中 KaTeX parse error: Undefined control sequence: \ at position 57: … 需求点\ i\ 未被覆盖\̲ ̲\end{cases}
可以建立数学模型如下
max∑i∈Niwizis.t.:{zi≤∑j∈Nixj,∀i∈M∑j∈Mxjpxj∈{0,1},zi∈{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∈Mxjpxj∈{0,1},zi∈{0,1}
其中j 为服务站i 为需求点wiw_iwi 为需求点 i 的需求量。 
2.5 其它选址问题
其它选址问题在数学建模中应用相对较少限于篇幅不能逐一介绍其数学模型。在此将各模型的特点简要介绍以便判断问题的类型。
带固定费用和容量限制的选址问题
服务站建站的固定费用和服务站的容量能力限制这两个因素具有很强的实际意义经常作为基本选址问题的深化研究课题。 无容量限制的固定费用下的选址问题就是去掉服务站个数的约束并将固定建站费用加到 P-中位问题的目标函数上。
选址分配问题
选址分配问题类似于 P-中位问题有 m 个服务站需要选址n 个已知位置的顾客分配给不同的设施已知每个服务站的能力和每个顾客的需求要求服务站的选址和顾客对服务站的分配使顾客与所分配服务站的距离总和最小。
随机选址问题 服务站的运行时间、建设成本、需求点位置、需求数量等全部或部分参数是不确定的但服从某种随机分布。
动态选址问题 研究未来若干时间段内服务站的最优选址问题在不同时间段内动态选址模型的参数是变化的但在某一时间段内模型参数是确定的。
竞争选址问题 研究考虑市场上存在两个以上同类产品或服务的提供者或服务站提供多个产品或服务。 2.6 选址问题的求解算法与编程实现
设施选址问题通常是是 NP 问题不存在多项式时间算法。常用的近似解法有
线性规划舍入算法相当于整数规划问题的求解算法。首先给出原问题的整数规划模型然后求解相应的线性规划松弛问题得到分数最优解根据可行要求对分数最优解进行改造构造原问题的整数可行解。
原始对偶算法首先找到对偶问题的一个可行解再根据该对偶可行解构造原始问题的整数可行解不断调整对偶问题的可行解直到找到最优解为止。
局部搜索算法给定初始可行解定义适当的邻域通过引入恰当的调整策略在邻域中得到改进的可行解依次迭代直到调整策略不能改进为止
启发式算法或随机优化算法。
本节作为线性规划问题系列的一篇仍然选择 PuLP工具包求解选址问题。很多选址问题适合用图论方法描述和求解这将在后续课程中进行介绍。 3. 案例 1PuLP求解指派问题
说明本案例是指派问题不是选址问题。因指派问题未单独成文因此将该案例放在本文中。
另外本案例给出了 PuLP 工具包使用字典方式快捷编程的使用方法这在选址问题中是非常方便的。
3.1 游泳接力赛的指派问题
游泳队中 A、B、C、D 四名运动员组成 4x100米混合泳接力队运动员各种泳姿的成绩如下表所示 单位秒
队员\项目自由泳蛙泳蝶泳仰泳A56746163B63696571C57776367D55766262
如何安排 A、B、C、D 四名运动员的泳姿才最有可能取得好成绩 3.2 指派问题建模分析
引入 0-1 变量 xijx_{ij}xij
xi,j{0第i人不游第j种姿势1第i人游第j种姿势i,j1,...4x_{i,j} \begin{cases} 0第\;i\;人不游第\;j\;种姿势\\ 1第\;i\;人游第\;j\;种姿势i,j1,...4 \end{cases} xi,j{0第i人不游第j种姿势1第i人游第j种姿势i,j1,...4
指派问题的数学模型就可以描述为 minf(x)∑i1n∑j1n(cijxij)s.t.:{∑j1nxij1i1,...,n∑i1nxij1j1,...,nxij0,1i,j1,...,nmin\;f(x) \sum_{i1} ^n \sum_{j1} ^n (c_{ij} x_{ij})\\ s.t.:\;\begin{cases} \sum_{j1} ^n x_{ij} 1i1,...,n\\ \sum_{i1} ^n x_{ij} 1j1,...,n\\ x_{ij} 0,1i,j1,...,n \end{cases} minf(x)i1∑nj1∑n(cijxij)s.t.:⎩⎪⎨⎪⎧∑j1nxij1i1,...,n∑i1nxij1j1,...,nxij0,1i,j1,...,n
其中
ci,j(56746163636965715777636755766262)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 pulp1定义一个规划问题 AssignLP pulp.LpProblem(Assignment_problem_for_swimming_relay_race, sensepulp.LpMinimize)pulp.LpProblem 用来定义问题的构造函数。参数 sense 指定问题求目标函数的最小值/最大值 。
2定义决策变量 rows cols range(0, 4)x pulp.LpVariable.dicts(x, (rows, cols), catBinary)pulp.LpVariable 用来定义决策变量的函数。参数 cat 设定变量类型’ Binary ’ 表示 0/1 变量。
注意指派问题、选址问题中都涉及 N*M 维矩阵变量变量个数很多如果逐一定义非常冗长而且容易出错、不便修改。本例使用 pulp.LpVariable.dicts 提供的字典格式定义了 4*4 个变量 xijx_{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),j1,4)1, i1,4for col in cols:AssignLP pulp.lpSum([x[row][col] for row in rows]) 1 # sum(x(i,j),i1,4)1, j1,4快捷方法对于约束条件的定义与对目标函数的定义相似使用字典定义参数使用循环定义约束条件使程序简单、结构清楚。
5求解和结果输出 AssignLP.solve() # youcansprint(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
# Crated2021-06-02
# Python小白的数学建模课 Youcansimport pulp # 导入 pulp 库
import numpy as np# 主程序
def main():# 问题建模决策变量x(i,j) 0, 第 i 个人不游第 j 种姿势x(i,j) 1, 第 i 个人游第 j 种姿势i1,4, j1,4目标函数min time sum(sum(c(i,j)*x(i,j))), i1,4, j1,4约束条件sum(x(i,j),j1,4)1, i1,4sum(x(i,j),i1,4)1, j1,4变量取值范围x(i,j) 0,1 # 游泳比赛的指派问题 (assignment problem)# 1.建立优化问题 AssignLP: 求最小值(LpMinimize)AssignLP pulp.LpProblem(Assignment_problem_for_swimming_relay_race, sensepulp.LpMinimize) # 定义问题求最小值# 2. 建立变量rows cols range(0, 4)x pulp.LpVariable.dicts(x, (rows, cols), catBinary)# 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),j1,4)1, i1,4for col in cols:AssignLP pulp.lpSum([x[row][col] for row in rows]) 1 # sum(x(i,j),i1,4)1, j1,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, XUPTmain() # 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. 案例 2PuLP求解选址问题
4.1 消防站的选址问题
例题 2某城市有 8 个区每个区最多建一个消防站拟建设消防站到各区的最长时间如下表所示。现要求任何区域发生火警时消防车能在 10分钟内赶到。在此条件下尽量减少消防站数量应该在哪几个区建设消防站
区域12345678171218202426252821458151618181831994141022161341415151018151418520181220925141261821201620610157221820151615598302215201418864.2 选址问题建模分析
首先判断这是一个集合覆盖问题要求从 8 个候选消防站中选择若干个在所有需求点得到服务的时间都小于临界值 10分钟的条件下选择消防站的数量最少。本问题不考虑各候选站点建设费用的差异即不带权重。
定义参数 RijR_{ij}Rij 为每个消防站的覆盖范围 Rij{1消防站j可以覆盖区域i0消防站j不能覆盖区域iR_{ij} \begin{cases} 1 消防站\ j\ 可以覆盖区域\ i\\ 0 消防站\ j\ 不能覆盖区域\ i \end{cases} Rij{10消防站 j 可以覆盖区域 i消防站 j 不能覆盖区域 i
由拟建消防站到各区的最长时间表可以得到参数 RijR_{ij}Rij 如下表
区域12345678110000000201100000301101000400010000500001000600000110700000011800000011
定义决策变量 xjx_jxj 为选中的服务站
xj{1消防站j被选中0消防站j未被选中x_j \begin{cases} 1 消防站\ j\ 被选中\\ 0 消防站\ j\ 未被选中\end{cases} xj{10消防站 j 被选中消防站 j 未被选中
可以建立数学模型如下
minf(x)∑j18xjs.t.:{∑j18xjRij≥1,i1,..8xj∈{0,1},j1,..8min\; f(x) \sum_{j1}^8 x_{j}\\ s.t.:\;\begin{cases} \sum_{j1}^8 x_j R_{ij} \geq 1, i1,..8\\ x_{j} \in \{0,1\}, j1,..8 \end{cases} minf(x)j1∑8xjs.t.:{∑j18xjRij≥1,xj∈{0,1},i1,..8j1,..8
选址问题的模型求解用标准模型的优化算法对模型求解得到优化结果。
模型求解的编程步骤与指派问题是一致的且在例程中给出了详细的注释就不再进行逐项解释了。
需要注意的是选址问题的决策变量、参数、约束条件的数量较大N*M如果对变量、约束条件逐个进行定义编程过程将是非常冗长和痛苦的因此需要使用列表、字典等快捷方式进行定义。对于更大规模的问题模型中的数据要通过读取数据文件获得就更需要采用这种方式来编程。 4.3 选址问题 Python 例程
# mathmodel09_v1.py
# Demo08 of mathematical modeling algorithm
# Solving set covering problem with PuLP.
# Copyright 2021 Youcans, XUPT
# Crated2021-06-06
# Python小白的数学建模课 Youcansimport pulp # 导入 pulp 库# 主程序
def main():# 问题建模决策变量x(j) 0, 不选择第 j 个消防站x(j) 1, 选择第 j 个消防站, j1,8目标函数min fx sum(x(j)), j1,8约束条件sum(x(j)*R(i,j),j1,8) 1, i1,8变量取值范围x(j) 0,1# 消防站的选址问题 (set covering problem, site selection of fire station)# 1.建立优化问题 SetCoverLP: 求最小值(LpMinimize)SetCoverLP pulp.LpProblem(SetCover_problem_for_fire_station, sensepulp.LpMinimize) # 定义问题求最小值# 2. 建立变量zones list(range(8)) # 定义各区域 youcansx pulp.LpVariable.dicts(zone, zones, catBinary) # 定义 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: i1, # 与问题中区域 1~8 一致status: 建站 if x[i].varValue else --}print(temple % output)print(需要建立 {} 个消防站。.format(pulp.value(SetCoverLP.objective)))returnif __name__ __main__: # Copyright 2021 YouCans, XUPTmain() # 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
Crated2021-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数模笔记-模拟退火算法
