数学建模竞赛实战：网络流优化与选址分配问题求解指南

1. 问题引入：当数学建模遇上“未来新城”的交通规划

如果你最近在准备数学建模竞赛，尤其是像五一赛、国赛这类含金量高的比赛，那你对B题这种“未来新城背景下的交通需求规划与可达率问题”一定不会陌生。这类题目听起来高大上，融合了城市规划、交通工程和运筹优化，但内核往往是一个经典的网络流优化或选址-分配问题。它的核心挑战在于，你如何用一个数学模型，去描述并解决一个现实中极其复杂的系统性问题——如何在新城区科学地布局交通服务设施（比如公交站、共享单车点、物流中心），使得居民出行的需求得到最大程度的满足，同时控制建设成本。

这不仅仅是套个模型、跑个代码那么简单。很多新手队伍一看到“未来新城”、“可达率”这些词就发怵，要么觉得无从下手，要么直接套用现成的算法，最后论文空洞，缺乏说服力。我参加过也指导过不少这类比赛，发现胜出的关键往往在于对问题本质的洞察和将现实约束转化为数学语言的精准度。今天，我就以这道B题为例，抛开那些华而不实的理论堆砌，直接切入核心，分享一套从问题拆解、模型构建、算法实现到论文写作的完整实战思路，并提供可直接运行的Matlab和Python代码框架。无论你是第一次参赛的小白，还是想提升建模水平的老手，这篇文章都能让你对这类“规划与可达率”问题有一个透彻的理解。

2. 核心需求解析：题目到底在问什么？

拿到题目，第一步不是找模型，而是做“阅读理解”。我们需要把一段充满背景描述的赛题，翻译成清晰的数学问题。以B题为例，我们可以拆解出以下几个核心需求点：

2.1 核心要素定义

首先，我们必须明确题目中的几个关键“角色”：

• 需求点：通常代表居民区、商业区、办公区等产生交通需求的区域。每个需求点有一个“需求量”，比如每日出行人次、货物吞吐量。
• 候选设施点：规划中可以建设交通服务设施（如公交枢纽、共享单车停放点、物流中心）的备选位置。题目可能给出具体坐标，也可能需要你自己在区域内合理假设。
• “可达”的定义：这是问题的核心。“可达率”不是简单的直线距离。它通常被定义为：从一个需求点出发，在一定的最大忍受时间或距离内（例如15分钟步行、30分钟车程），能否到达至少一个服务设施。如果能，则该需求点被“覆盖”，其需求量计入已满足的部分。

2.2 问题目标的数学化

题目要求“交通需求规划与可达率优化”，其目标通常可以转化为以下两种之一或两者的结合：

1. 覆盖最大化：在建设成本（或设施数量）有限的条件下，选择一组设施点进行建设，使得被“覆盖”的总需求（或需求点数量）最大。这对应着最大覆盖选址问题。
2. 成本最小化：在要求达到一个最低整体可达率（例如90%的需求被覆盖）的前提下，寻找建设总成本最小的设施选址方案。这对应着集合覆盖问题或其变种。

2.3 必须考虑的约束条件

现实中的规划从不自由，模型必须体现这些约束：

• 设施建设能力上限：一个设施点（如一个公交站）的服务能力是有限的，不能无限制满足所有需求。
• 需求分配规则：一个需求点的需求是否只能由一个设施服务？还是可以拆分由多个设施共同服务？这决定了你的模型是“单分配”还是“多分配”模型，复杂度差异很大。
• 距离或时间衰减：更远的设施服务效率可能更低，或满意度下降。有时需要用“覆盖衰减函数”而非简单的0/1覆盖来刻画。
• 预算约束：每个设施点的建设成本可能不同，总预算有限。

注意：竞赛题目为了简化，常常默认“单分配、无容量限制的0/1覆盖模型”。但高水平的论文往往会讨论这些复杂约束，作为模型的扩展和灵敏度分析的一部分，这是拿高分的关键。

3. 模型构建：从概念到数学公式

理解了问题，接下来就是为它量身打造一个数学模型。我们以最常见的最大覆盖选址问题为例，构建一个基础的0/1整数规划模型。

3.1 定义集合与参数

• I: 需求点的集合，索引为i(i = 1, 2, ..., m)。
• J: 候选设施点的集合，索引为j(j = 1, 2, ..., n)。
• d_i: 需求点i的需求量（如人口数、出行量）。
• p: 允许建设的最大设施数量（预算约束的简化形式）。
• a_{ij}: 0/1参数。如果需求点i在设施点j的覆盖范围（如距离 ≤ R）内，则a_{ij} = 1，否则为0。这个矩阵需要你事先根据坐标和覆盖半径计算好。

3.2 定义决策变量

• x_j: 0/1变量。如果在候选点j建设设施，则x_j = 1，否则为0。
• y_i: 0/1变量。如果需求点i的需求被至少一个已建设的设施覆盖，则y_i = 1，否则为0。

3.3 构建目标函数与约束条件

我们的目标是最大化被覆盖的总需求。

目标函数：Maximize Z = Σ_{i ∈ I} (d_i * y_i)

约束条件：

1. 设施数量约束：Σ_{j ∈ J} x_j ≤ p （最多建设p个设施）。
2. 覆盖逻辑约束：对于每一个需求点i，只有当至少一个能覆盖它的设施被建设时，y_i才能等于1。这个逻辑用线性不等式表达为：y_i ≤ Σ_{j ∈ J} (a_{ij} * x_j)， 对于所有i ∈ I。同时，y_i是0/1变量。
3. 变量类型约束：x_j ∈ {0, 1},y_i ∈ {0, 1}。

这个模型清晰地描述了问题：选择至多p个设施点（约束1），使得尽可能多的需求（目标函数）被覆盖，而一个需求点被覆盖的前提是至少有一个能服务它的设施被选中（约束2）。

3.4 模型变体与扩展

• 加权覆盖：如果不同需求点的重要性不同，可以在目标函数中为d_i加上权重w_i。
• 设施建设成本不同：将约束1改为 Σ_{j ∈ J} (c_j * x_j) ≤ Budget，其中c_j是建设成本。
• 设施容量限制：引入新的变量z_{ij}表示从设施j分配给需求点i的需求量，并增加约束 Σ_{i ∈ I} z_{ij} ≤ Capacity_j * x_j， 以及 Σ_{j ∈ J} z_{ij} = d_i * y_i。这会将问题升级为带容量的覆盖选址问题，复杂度激增，通常需要用启发式算法求解。

4. 算法求解：精确解与启发式算法的选择

模型建好了，怎么求解？这里分两种情况。

4.1 小规模问题：整数规划求解器（求精确解）

当问题规模较小（例如需求点和候选点各几十个），我们可以直接使用优化求解器来寻找全局最优解。这在论文中可以作为基准答案。

• MATLAB实现（使用优化工具箱）：

  % 假设已有以下数据： % demand: m x 1 向量，每个需求点的需求量 d_i % coverMatrix: m x n 矩阵，覆盖矩阵 a_{ij} % p: 最大设施数量 m = size(coverMatrix, 1); n = size(coverMatrix, 2); % 创建优化问题 prob = optimproblem('ObjectiveSense', 'maximize'); % 定义变量 x = optimvar('x', n, 'Type', 'integer', 'LowerBound', 0, 'UpperBound', 1); y = optimvar('y', m, 'Type', 'integer', 'LowerBound', 0, 'UpperBound', 1); % 定义目标函数 prob.Objective = sum(demand .* y); % 定义约束 prob.Constraints.numFacilities = sum(x) <= p; % 覆盖约束：对于每个需求点i， y_i <= sum_j(a_ij * x_j) for i = 1:m prob.Constraints.(['cover_' num2str(i)]) = ... y(i) <= sum(coverMatrix(i, :) .* x'); end % 求解 [sol, fval, exitflag, output] = solve(prob); % 输出结果 selectedSites = find(round(sol.x) > 0.5); coveredDemand = fval; disp(['选中的设施点索引: ', num2str(selectedSites')]); disp(['覆盖的总需求: ', num2str(coveredDemand)]);

• Python实现（使用PuLP库）：

  import pulp # 假设已有以下数据： # demand_list: m个元素列表，每个需求点的需求量 d_i # cover_matrix: m x n 的列表的列表，覆盖矩阵 a_{ij} # p: 最大设施数量 m = len(demand_list) n = len(cover_matrix[0]) # 创建问题 prob = pulp.LpProblem('Max_Coverage_Location_Problem', pulp.LpMaximize) # 定义变量 x = pulp.LpVariable.dicts('x', range(n), lowBound=0, upBound=1, cat='Binary') y = pulp.LpVariable.dicts('y', range(m), lowBound=0, upBound=1, cat='Binary') # 定义目标函数 prob += pulp.lpSum([demand_list[i] * y[i] for i in range(m)]) # 定义约束 prob += pulp.lpSum([x[j] for j in range(n)]) <= p, "Max_Facilities" for i in range(m): # 约束: y_i <= sum(a_ij * x_j) for all j prob += y[i] <= pulp.lpSum([cover_matrix[i][j] * x[j] for j in range(n)]), f"Cover_Constraint_{i}" # 求解 (需要安装CBC等求解器，PuLP默认包含) prob.solve(pulp.PULP_CBC_CMD(msg=False)) # 输出结果 selected_sites = [j for j in range(n) if pulp.value(x[j]) > 0.5] covered_demand = pulp.value(prob.objective) print(f"选中的设施点索引: {selected_sites}") print(f"覆盖的总需求: {covered_demand}")

4.2 中大规模问题：贪婪启发式算法（求优质可行解）

实际问题中，需求点和候选点可能成百上千，整数规划模型会变得无法在比赛时间内直接求解。这时必须使用启发式算法。贪婪算法是解决最大覆盖问题最经典、最有效的方法之一，其思想直观且效果通常不错。

算法步骤：

1. 初始化已选设施集合 S = ∅， 未覆盖需求点集合 U = 所有需求点。
2. 循环，直到已选设施数量达到 p： a. 遍历每一个未入选的候选设施 j ∉ S。 b. 计算如果选择设施 j，它能新覆盖的 U 中的需求总量（即增量收益）。 c. 选择增量收益最大的那个设施 j*，将其加入 S (S = S ∪ {j*})。 d. 将 j* 新覆盖的需求点从 U 中移除。
3. 输出最终选中的设施集合 S。

• Python实现（贪婪算法）：

  def greedy_max_coverage(demand, cover_matrix, p): """ 贪婪算法求解最大覆盖问题 demand: list of int, 每个需求点的需求量 cover_matrix: list of list of int, cover_matrix[i][j] = 1 表示需求点i能被设施j覆盖 p: int, 最大设施数量 返回: selected_sites (list), covered_demand (int), coverage_record (list) """ m, n = len(demand), len(cover_matrix[0]) uncovered = [1] * m # 1表示未覆盖，0表示已覆盖 selected = [] total_covered_demand = 0 coverage_record = [] # 记录每一步的选择和覆盖需求 for step in range(p): best_gain = -1 best_site = -1 best_newly_covered = [] # 遍历所有未选中的候选点 for j in range(n): if j in selected: continue # 计算该设施能新覆盖的当前未覆盖的需求量 gain = 0 newly_covered_idx = [] for i in range(m): if uncovered[i] and cover_matrix[i][j]: gain += demand[i] newly_covered_idx.append(i) # 选择增益最大的 if gain > best_gain: best_gain = gain best_site = j best_newly_covered = newly_covered_idx.copy() if best_site == -1: # 没有能增加覆盖的设施了 break # 选中该设施，更新状态 selected.append(best_site) for idx in best_newly_covered: uncovered[idx] = 0 total_covered_demand += demand[idx] coverage_record.append({ 'step': step+1, 'site': best_site, 'gain': best_gain, 'total_covered': total_covered_demand }) print(f"第{step+1}步: 选择设施 {best_site}, 新增覆盖需求 {best_gain}, 累计覆盖 {total_covered_demand}") return selected, total_covered_demand, coverage_record # 使用示例 # selected_sites, covered_demand, record = greedy_max_coverage(demand_list, cover_matrix, p)

实操心得：贪婪算法虽然快，但得到的不一定是最优解。在论文中，你可以将整数规划求解器在小规模算例上的结果作为“精确解基准”，与贪婪算法的结果进行对比，分析其性能差距（通常用Gap表示）。这能体现你对算法性能的评估能力。

5. 数据准备与结果可视化：让论文“活”起来

模型和算法是骨架，数据和可视化才是血肉。这部分直接决定论文的直观性和说服力。

5.1 人工数据生成

竞赛题可能不提供具体数据，需要你自己生成符合场景的模拟数据。

import numpy as np def generate_synthetic_data(num_demand=100, num_candidate=20, region_size=100, seed=42): """ 生成模拟数据：在 region_size x region_size 的正方形区域内随机生成需求点和候选点。 """ np.random.seed(seed) # 生成坐标 demand_points = np.random.rand(num_demand, 2) * region_size candidate_points = np.random.rand(num_candidate, 2) * region_size # 生成需求量，可以服从正态分布或均匀分布 demand_weights = np.random.randint(10, 100, size=num_demand) # 假设需求在10-100之间 # 计算覆盖矩阵 (基于欧氏距离，覆盖半径R) R = 20 # 覆盖半径 cover_matrix = [] for i in range(num_demand): row = [] for j in range(num_candidate): dist = np.linalg.norm(demand_points[i] - candidate_points[j]) row.append(1 if dist <= R else 0) cover_matrix.append(row) return demand_points, candidate_points, demand_weights, np.array(cover_matrix) # 生成数据 d_points, c_points, d_weights, c_matrix = generate_synthetic_data()

5.2 结果可视化（Matlab示例）

可视化能清晰展示选址方案的空间合理性。

% 假设已有数据： % demand_points: m x 2, 需求点坐标 % candidate_points: n x 2, 候选点坐标 % selected_idx: 选中的设施索引 % cover_matrix: 覆盖矩阵 % is_covered: m x 1 逻辑向量，表示需求点是否被覆盖 figure('Position', [100, 100, 1200, 500]); % 子图1：展示所有点和覆盖关系 subplot(1,2,1); hold on; grid on; axis equal; % 绘制未覆盖的需求点 plot(demand_points(~is_covered, 1), demand_points(~is_covered, 2), 'ro', 'MarkerSize', 8, 'DisplayName', '未覆盖需求点'); % 绘制已覆盖的需求点 plot(demand_points(is_covered, 1), demand_points(is_covered, 2), 'go', 'MarkerSize', 8, 'DisplayName', '已覆盖需求点'); % 绘制所有候选点 plot(candidate_points(:,1), candidate_points(:,2), 'k^', 'MarkerSize', 10, 'LineWidth', 1.5, 'DisplayName', '候选设施点'); % 绘制被选中的设施点 plot(candidate_points(selected_idx, 1), candidate_points(selected_idx, 2), 'bd', 'MarkerSize', 12, 'LineWidth', 2, 'DisplayName', '选中设施点'); % 为每个选中的设施点绘制覆盖范围 theta = 0:0.01:2*pi; R = 20; % 覆盖半径 for idx = selected_idx' x_circle = candidate_points(idx,1) + R * cos(theta); y_circle = candidate_points(idx,2) + R * sin(theta); plot(x_circle, y_circle, 'b--', 'LineWidth', 1); end xlabel('X坐标'); ylabel('Y坐标'); title('设施选址与需求覆盖情况'); legend('Location', 'bestoutside'); % 子图2：展示算法每一步的覆盖需求增长（贪婪算法记录） subplot(1,2,2); steps = 1:length(coverage_record); gains = [record.gain for record in coverage_record]; cumulative = [record.total_covered for record in coverage_record]; yyaxis left; bar(steps, gains, 'FaceColor', [0.85 0.33 0.10]); ylabel('每一步新增覆盖需求'); yyaxis right; plot(steps, cumulative, 's-', 'LineWidth', 2, 'MarkerSize', 8, 'Color', [0 0.45 0.74]); ylabel('累计覆盖总需求'); xlabel('选址步骤'); title('贪婪算法迭代过程'); grid on; legend('单步覆盖增益', '累计覆盖需求', 'Location', 'northwest');

6. 论文写作与模型拓展：通往高分的最后一步

有了模型、算法和漂亮的结果图，最后一步是如何把它们组织成一篇优秀的数学建模论文。

6.1 论文核心结构建议

1. 问题重述与分析：不要照抄题目，要用自己的话精炼概括，并完成我们在第2部分做的核心需求解析，明确目标与约束。
2. 模型假设与符号说明：列出清晰合理的假设（如“需求点位置固定”、“覆盖为0-1模式”、“设施建设成本相同”等）。符号表格要规范。
3. 模型建立与求解：这是核心章节。详细阐述你的模型（如第3部分的整数规划模型），并解释每个公式的实际意义。接着说明求解方法（精确求解器用于小规模验证，贪婪算法用于主体求解），并给出算法步骤或伪代码。
4. 算例分析与结果：展示你生成的数据、运行的结果。包括：
   • 不同设施数量上限p下，总覆盖需求的变化曲线（灵敏度分析）。
   • 将贪婪算法结果与精确解（小规模时）对比，计算近似比或Gap。
   • 展示最优（或较优）选址方案的可视化地图（如第5部分）。
5. 模型评价与推广：客观评价模型的优点（如考虑周全、求解高效）和缺点（如简化了实际交通网络、未考虑动态需求）。提出可能的改进方向，例如引入容量约束、考虑时变需求、使用更高级的元启发式算法（如遗传算法、模拟退火）进行优化，或者将单一覆盖模型升级为层次覆盖模型（例如，步行5分钟内覆盖为一级，骑行10分钟内覆盖为二级）。

6.2 关键拿分点

• 清晰的逻辑链条：从问题分析 -> 模型假设 -> 模型构建 -> 算法选择 -> 结果分析，每一步都要环环相扣。
• 深度的分析：不要只给出一个答案。要分析“为什么选这里？”、“增加一个设施带来的边际效益如何？”、“模型的稳健性怎样？”。
• 专业的可视化：一图胜千言。空间分布图、迭代收敛图、灵敏度分析图都能极大提升论文质量。
• 代码的规范性：在附录中提供简洁、有注释的核心代码。评委可能会看。

6.3 模型拓展示例：引入容量约束的C++伪代码思路

如果时间允许，在模型拓展部分讨论带容量约束的版本，能显著提升论文深度。这里给出一个基于贪婪自适应搜索（GRASP）的元启发式框架思路：

算法：GRASP for Capacitated Max Coverage 输入：需求点集合I，候选点集合J，覆盖矩阵A，需求d，容量C，迭代次数MaxIter 输出：最佳选址方案S_best 1. S_best = ∅, Z_best = 0 2. for iter = 1 to MaxIter do 3. S = ∅, U = I (未满足需求集合) 4. // 构造阶段：受限的贪婪随机化 5. while |S| < p and U 非空 do 6. 计算每个候选点j ∉ S的“边际效益密度” = (新覆盖的U中需求) / (建设成本c_j) 7. 构建候选列表RCL，包含效益密度在前α%的候选点 8. 从RCL中随机选择一个点j*加入S 9. 根据容量约束，将j*能服务的需求从U中移除（按需求点距离j*近远或随机分配） 10. end while 11. // 局部搜索阶段：尝试改进解S 12. for 每个在S中的设施点 do 13. for 每个不在S中的候选点 do 14. 尝试交换，计算新解的目标值Z_new 15. 如果Z_new > Z(S)，则接受交换 16. end for 17. end for 18. // 更新全局最优解 19. if Z(S) > Z_best then 20. S_best = S, Z_best = Z(S) 21. end if 22. end for 23. return S_best

在论文中，你不需要给出完整代码，但描述这个框架并讨论其如何克服简单贪婪算法的局限性（如陷入局部最优），就足以展现你的建模深度。

数学建模竞赛的本质是用数学工具讲一个逻辑自洽、解决实际问题的好故事。对于“交通需求规划与可达率”这类问题，抓住“覆盖”这一核心概念，构建严谨的整数规划模型，用高效的启发式算法求解，再辅以扎实的数据分析和可视化，你的论文就有了坚实的骨架和血肉。记住，多思考“为什么这样建模”，比堆砌复杂的模型更重要。希望这份结合了思路、代码与实战经验的指南，能帮助你在下次比赛中，更从容地面对那道看似复杂的B题。