数学建模竞赛优化题实战：线性规划求解空中加油路径规划

1. 项目概述：从一道赛题到完整的解题复盘

2018年第七届数学建模国际赛（俗称“小美赛”）的A题“空中加油飞行计划”，对于很多初次接触运筹优化或军事后勤建模的同学来说，可能是一道让人望而生畏的题目。它不像一些纯数据分析题那样有现成的数据集，也不像一些物理仿真题有明确的公式可套。它更像一个真实的工程问题：给你一个看似简单的目标——让一架轰炸机在有限加油机的支持下飞得更远，但背后却需要你构建一整套逻辑严密的数学模型，并给出可执行的飞行方案。当年我们团队啃下这道题，最终拿到了不错的奖项，整个过程充满了“烧脑”的推导和“试错”的编程。今天，我就以这道经典赛题为例，彻底拆解数学建模竞赛中“优化类”题目的解题全流程，从审题、建模、求解到论文写作，分享我们当时的思考路径、踩过的坑以及最终验证有效的策略。无论你是正在备战数模的新手，还是对运筹学感兴趣的朋友，相信这篇近万字的复盘都能给你带来实实在在的启发。

这道题的核心场景非常明确：我方有一架执行远程任务的轰炸机（记为B），以及若干架用于为其提供空中加油的加油机（记为T）。轰炸机和加油机具有不同的巡航速度、油耗率和航程。加油机可以从前线基地起飞，也可以从后方基地起飞，在执行任务过程中，加油机可以为轰炸机加油，也可以为其他加油机加油（即“接力加油”）。问题的目标是，在给定加油机数量的限制下，规划所有飞机的飞行路线与加油时序，使得轰炸机在完成单向飞行任务时的航程最大化。简单说，就是如何像玩“物流接力赛”一样，用有限的“移动加油站”（加油机），把“主角”（轰炸机）尽可能送得远。

注意：这类问题属于典型的“军事后勤路径规划”或“车辆路径问题（VRP）”的变体，在学术界和工业界（如无人机物流、卫星燃料补给）都有广泛应用。解题的关键不在于追求复杂的算法，而在于如何将模糊的现实问题转化为清晰、可计算的数学语言。

2. 问题深度解析与核心难点拆解

初次读题，可能会被“空中加油”、“多机协作”、“航程最优”这些词唬住。我们需要像剥洋葱一样，一层层理清它的约束和自由度。

2.1 核心任务与决策变量定义

首先，我们必须明确题目要我们“决定”什么。这直接对应数学模型中的决策变量。经过分析，决策变量主要包括：

1. 加油机的出动方案：每架加油机是否出动？从哪个基地（前线/后方）起飞？
2. 飞行路径与汇合点：每架飞机（包括轰炸机和每架加油机）的飞行路径是怎样的？它们在哪里汇合进行加油？
3. 加油事件序列：在什么时间、什么地点、由哪架加油机向哪架飞机加多少油？
4. 各机状态时序：在任何时刻，每架飞机的剩余油量、位置、速度是多少？

这些变量相互耦合，牵一发而动全身。例如，决定让一架加油机去远方汇合点，它自己消耗的油量就多了，能给轰炸机加的油就少了；安排一次接力加油，可以延长某架加油机的在空时间，但增加了协调的复杂性。

2.2 核心物理约束与模型边界

任何模型都不能脱离物理规律。本题的核心约束源于“油量”的守恒与流动：

• 油量守恒：对于任何一次加油事件，加油机给出的油量等于受油机接收的油量（忽略传输损耗）。加油后，加油机剩余油量必须足以安全返航（或前往下一个汇合点）。
• 油量非负与安全余量：任何飞机在任何时刻的油量不能为负，且通常需要保留安全余量以备不时之需。在模型中，我们常设定一个最小安全油量，用于返航。
• 航程与油量关系：飞机的最大航程由其总油量和油耗率决定。即最大航程 = 总油量 / 油耗率。这是一个线性关系，是后续建立优化模型的基础。
• 时间同步：两架飞机要在空间某点汇合加油，它们必须同时到达该点。这引入了复杂的时空协调约束。

2.3 解题的核心难点与常见误区

在实际解题和与后来者的交流中，我发现以下几个难点最容易让人卡住：

• 难点一：模型的抽象层级。是把每架飞机每时每刻的位置都作为变量（连续时空模型），还是只关注关键的“加油事件点”（离散事件模型）？前者精确但计算爆炸，后者可行但需要合理假设。我们选择了后者，将整个任务过程抽象为一系列按顺序发生的加油事件，每个事件发生在某个特定的“汇合点”。飞机在两个事件点之间匀速直线飞行。
• 难点二：“对称性”和“冗余解”。由于加油机可能同质，方案可能存在多种等价表述。例如，交换两架执行相同任务的加油机编号，得到的是实质相同的解。这会在优化算法中导致搜索效率低下。需要引入额外的约束（如按起飞时间排序）来打破对称性。
• 难点三：返航条件的处理。加油机加完油后需要返航，其返航所需油量必须被严格保证。许多初期模型错误地让加油机“耗尽其所有油量来为轰炸机服务”，忽略了其返航需求，导致得到不可行的“最优解”。
• 难点四：目标函数的表述。目标是最大化轰炸机的单向航程。这意味着我们只关心轰炸机从起点到最终燃油耗尽点的距离，不关心它之后如何返回（题目隐含假设任务为单程突防）。这一点必须非常清晰，否则会在计算最终航程时产生混淆。

3. 数学模型构建：从思路到公式

基于以上分析，我们团队构建了一个以线性规划（Linear Programming, LP）为核心的数学模型。为什么选择线性规划？因为核心关系（油量消耗与距离成正比）是线性的，约束条件（油量守恒、非负、航程限制）大多可以表示为决策变量的线性不等式或等式。线性规划模型成熟、求解器稳定，能保证找到全局最优解。

3.1 模型假设与简化

在建立精确的数学公式前，合理的简化是必要的：

1. 二维平面假设：所有飞行在同一平面内进行，忽略地球曲率和高度变化。使用笛卡尔坐标系，以轰炸机起飞点为原点。
2. 匀速直线飞行：所有飞机以各自的巡航速度匀速直线飞行，加速、减速、转弯过程忽略不计或其时间/油耗计入巡航油耗。
3. 瞬时加油：加油过程所耗时间极短，忽略不计。加油期间飞机位置不变。
4. 油耗率恒定：飞机单位时间的油耗是常数，与载油量、速度无关（简化模型）。
5. 单次任务：所有飞机执行一次任务，不考虑多任务循环。

3.2 决策变量与参数定义

• 集合定义：
  • K: 所有加油机的集合，索引为k。B代表轰炸机。
  • E: 所有加油事件的集合，索引为e。事件按时间顺序编号为1, 2, ..., N。事件0代表起点，事件N+1代表轰炸机终点（油尽）或加油机返航终点。
• 关键决策变量：
  • x_e: 第e个加油事件发生的位置（距离原点的距离）。
  • y_{k,e}: 在事件e发生时，加油机k转移给轰炸机B的油量。如果是加油机之间互相加油，则需要更复杂的下标，但核心思路相同。
  • f_{k,e}: 加油机k在完成事件e后的剩余油量（即在离开事件点e时）。
  • F_{B,e}: 轰炸机B在完成事件e后的剩余油量。
• 已知参数：
  • C_k,C_B: 加油机k和轰炸机B的初始总油量。
  • r_k,r_B: 加油机k和轰炸机B的单位距离油耗率（油量/公里）。
  • V_k,V_B: 巡航速度。
  • N_max: 可用的最大加油机数量。

3.3 核心约束方程推导

模型的核心在于用数学公式刻画“油量如何随着飞行和加油而变化”。

1. 轰炸机油量平衡方程： 对于轰炸机，在连续两个事件点e和e+1之间，它飞过了距离(x_{e+1} - x_e)，消耗了油量r_B * (x_{e+1} - x_e)。在事件点e+1，它可能接受加油sum_{k in K}(y_{k, e+1})。因此，油量平衡关系为：F_{B, e+1} = F_{B, e} - r_B * (x_{e+1} - x_e) + sum_{k in K}(y_{k, e+1})这个等式必须对所有事件e成立。它保证了轰炸机油量的连续性。

2. 加油机油量平衡与返航约束： 这是模型中最精妙也最容易出错的部分。对于加油机k，它可能从后方或前线基地起飞。假设它从原点（与轰炸机同基地）起飞。

   • 任务段油量平衡：在前往汇合点e的路上，它消耗油量。在汇合点e，它给出油量y_{k,e}。因此，其油量变化为：f_{k,e} = f_{k, e-1} - r_k * (x_e - x_{e-1}) - y_{k,e}
   • 返航约束：加油机在最后一次为轰炸机加油后（假设在事件m），必须留有足够油量返回基地。它从x_m处返航，飞回原点距离为x_m，所需油量为r_k * x_m。因此，必须有：f_{k,m} >= r_k * x_m这个不等式是保证方案可行的关键，它确保了加油机不会“有去无回”。

3. 加油事件逻辑约束：

   • 一个加油事件e要发生，至少有一架加油机在此地提供了非零的油量：sum_{k in K}(y_{k,e}) > 0。
   • 加油机不能提供超过其当前剩余油量的油：y_{k,e} <= f_{k, e-1} - r_k * (x_e - x_{e-1})。实际上，这个约束已被油量平衡方程隐含。

4. 非负与边界约束：x_e >= 0,y_{k,e} >= 0,f_{k,e} >= 0,F_{B,e} >= 0。轰炸机的初始油量F_{B,0} = C_B，加油机的初始油量f_{k,0} = C_k。

3.4 目标函数

目标非常直接：最大化轰炸机最终飞行的距离。在离散事件模型中，轰炸机在最后一个加油事件N之后，继续飞行直至油尽。设其从x_N处又飞行了距离d后油尽，则有：F_{B,N} - r_B * d = 0=>d = F_{B,N} / r_B因此，轰炸机总航程为x_N + d = x_N + F_{B,N} / r_B。 我们的目标函数就是：Maximize:Z = x_N + F_{B,N} / r_B

至此，一个完整的（但仍是基础版的）线性规划模型就建立起来了。决策变量是x_e,y_{k,e},f_{k,e},F_{B,e}，目标函数是Z的线性表达式（因为F_{B,N}是变量），约束条件都是线性等式或不等式。

4. 模型求解：算法选择与编程实现

模型建好了，但怎么求解？直接手算显然不可能。我们需要借助数学优化求解器和编程语言。

4.1 求解工具选型：为什么是Python + PuLP

我们当时选择了Python语言和PuLP库。这个组合在今天看来依然是入门和解决中小规模线性规划问题的黄金选择。

• Python：语法简洁，库生态丰富，调试方便。相比MATLAB，它免费且更通用；相比C++，它开发效率更高。
• PuLP：一个优秀的线性规划建模接口。它允许你用非常直观的方式定义变量、目标函数和约束（就像写数学公式一样），然后调用后台的求解器（如CBC, GLPK, Gurobi, CPLEX）进行计算。你不需要手动编写复杂的单纯形法或内点法代码。

实操心得：对于数模竞赛，不要自己从头实现优化算法。你的核心价值在于建模和结果分析，而不是算法底层实现。利用成熟的求解器（如PuLP调用CBC）是最高效、最可靠的做法。CBC是一款开源的混合整数规划求解器，对于纯线性规划问题性能足够好。

4.2 编程实现步骤详解

下面，我结合代码片段，详解如何将上述模型“翻译”成PuLP代码。假设我们有2架同型号加油机。

import pulp # 1. 定义问题 prob = pulp.LpProblem('Aerial_Refueling_Optimization', pulp.LpMaximize) # 2. 定义参数 C_B = 100 # 轰炸机初始油量 C_T = 80 # 加油机初始油量 r_B = 1 # 轰炸机油耗率 r_T = 0.8 # 加油机油耗率 N_max = 2 # 最大加油机数 # 假设我们预设最多发生3次加油事件（这个数可以试探性增加） max_events = 3 # 3. 定义决策变量 # 事件位置， 非负连续变量 x = pulp.LpVariable.dicts('x', range(max_events+1), lowBound=0) # x[0], x[1], ..., x[max_events] # 轰炸机在事件e后的油量 F_B = pulp.LpVariable.dicts('F_B', range(max_events+1), lowBound=0) # 加油机k在事件e后的油量 f_T = {} for k in range(N_max): f_T[k] = pulp.LpVariable.dicts(f'f_T_{k}', range(max_events+1), lowBound=0) # 加油机k在事件e时提供给轰炸机的油量 y = {} for k in range(N_max): y[k] = pulp.LpVariable.dicts(f'y_{k}', range(1, max_events+1), lowBound=0) # 事件0没有加油 # 4. 设置目标函数 # 假设最后一个事件是 max_events， 轰炸机从 x[max_events] 处继续飞行 d = F_B[max_events]/r_B prob += x[max_events] + F_B[max_events] / r_B, 'Total_Range' # 5. 添加约束 # 初始条件 prob += F_B[0] == C_B, 'Bomber_Initial_Fuel' for k in range(N_max): prob += f_T[k][0] == C_T, f'Tanker_{k}_Initial_Fuel' prob += x[0] == 0, 'Start_Point' # 轰炸机油量平衡约束 for e in range(max_events): # F_B[e+1] = F_B[e] - r_B*(x[e+1]-x[e]) + sum(y[k][e+1]) prob += (F_B[e+1] == F_B[e] - r_B*(x[e+1]-x[e]) + pulp.lpSum([y[k][e+1] for k in range(N_max)])), f'Bomber_Fuel_Balance_{e}') # 加油机油量平衡与返航约束 for k in range(N_max): for e in range(max_events): # f_T[k][e+1] = f_T[k][e] - r_T*(x[e+1]-x[e]) - y[k][e+1] prob += (f_T[k][e+1] == f_T[k][e] - r_T*(x[e+1]-x[e]) - y[k][e+1]), f'Tanker_{k}_Fuel_Balance_{e}' # 返航约束：最后一次参与加油后（这里简化，假设都在最后一个事件后返航），油量需足够飞回 # 我们需要一个变量来记录每架加油机最后一次提供加油的事件，这里做简化，假设所有加油机在事件 max_events 后返航 prob += f_T[k][max_events] >= r_T * x[max_events], f'Tanker_{k}_Return_{max_events}' # 事件位置单调递增约束 for e in range(max_events): prob += x[e+1] >= x[e] + 0.01, f'Event_Order_{e}' # 加一个小量避免事件点重合 # 6. 求解问题 solver = pulp.PULP_CBC_CMD(msg=False) # 使用CBC求解器，关闭求解日志 prob.solve(solver) # 7. 打印结果 print(pulp.LpStatus[prob.status]) print("最优总航程：", pulp.value(prob.objective)) for e in range(max_events+1): print(f"事件{e}: 位置 x={pulp.value(x[e]):.2f}, 轰炸机油量 F_B={pulp.value(F_B[e]):.2f}") for k in range(N_max): if e>0: print(f" 加油机{k}在事件{e}提供油量 y={pulp.value(y[k][e]):.2f}, 剩余油量 f_T={pulp.value(f_T[k][e]):.2f}")

这是一个高度简化的框架代码。真实赛题中，你需要考虑更多细节，例如：

• 加油机是否出动：需要引入0-1整数变量z_k，表示加油机k是否被使用。这会将问题变为混合整数线性规划（MILP）。
• 加油机间接力加油：变量y的下标需要扩展为y_{i,j,e}，表示飞机i给飞机j在事件e加油。约束会变得复杂。
• 事件数量不确定：上述代码预设了事件数量。更高级的做法是使用“列生成”或“模式分解”思想，或者逐步增加事件数直到目标函数不再提升。

4.3 求解策略与技巧

1. 从小规模开始：先用1架加油机，1-2个事件点进行调试，确保模型基本逻辑正确，再逐步增加复杂度。
2. 可视化中间结果：用Matplotlib绘制每次迭代的飞机航迹和油量变化图，直观检查方案是否合理（如油量是否为负，返航是否可能）。
3. 处理“零加油”事件：在最优解中，可能有些预设的事件点没有发生加油（即所有y_{k,e}=0）。这意味着这些事件点是冗余的。在最终方案描述时，应剔除这些点。
4. 敏感性分析：改变参数（如加油机数量、油量、油耗率），观察最优航程如何变化。这能为论文中的“模型分析”部分提供丰富素材。

5. 方案解读与论文写作要点

求出一个数字只是第一步，如何将模型和方案清晰、有说服力地呈现出来，是拿高分的关键。

5.1 最优飞行方案描述

你的模型输出应该能转化为一个清晰的“飞行计划表”。例如：

总航程：700 km

在论文中，除了表格，最好配上一张时空轨迹图。Y轴表示时间，X轴表示距离。用不同线型画出轰炸机和每架加油机的航迹，并在汇合点标注加油量。这张图能让你方案的逻辑一目了然。

5.2 模型检验与灵敏度分析

这是体现你思考深度的部分。

• 合理性检验：你的方案是否违背常识？例如，加油机提供的油量是否超过了其当前油量？所有飞机是否都能安全返航？计算返航所需油量并与剩余油量对比验证。
• 灵敏度分析：
  • 加油机数量：绘制“最大航程 vs. 加油机数量”曲线。通常航程随数量增加而增加，但边际效益递减。分析多少架之后增加效果就不明显了，这有助于决策资源分配。
  • 油耗率：如果轰炸机或加油机更省油（油耗率降低10%），航程能增加多少？这能说明提升飞机性能的价值。
  • 初始油量：分析加油机初始油量对总航程的影响。有时多带油不如多派一架飞机。
  • 基地位置：如果加油机从前线基地起飞（不是从原点），模型该如何修改？结果会怎样？这可以作为模型的扩展讨论。

5.3 论文写作核心章节布局

一篇完整的数模论文，围绕这个题目，可以这样组织：

1. 摘要：用300字左右概括问题、你的方法、模型、算法、主要结果和结论。务必包含关键数据（如最大航程、所需加油机数）。
2. 问题重述与分析：用自己的话梳理题目，明确已知条件、未知变量、目标和约束。画出问题示意图。
3. 模型假设与符号说明：清晰列出所有假设，并给出符号表。这是论文的基石。
4. 模型建立：这是核心。分小节阐述：
   • 问题分析（思路流程图）
   • 决策变量与参数定义
   • 目标函数
   • 约束条件推导（油量平衡、返航、逻辑约束等）
   • 完整的数学模型（公式汇总）
5. 模型求解：
   • 算法选择与理由（为什么用线性规划/PuLP）
   • 求解流程描述（可配流程图）
   • 关键代码片段展示（不宜过长，突出逻辑）
   • 计算结果（表格、图形）
6. 结果分析与检验：
   • 最优方案详细描述（表格+时空图）
   • 灵敏度分析（各种参数变化对结果的影响，配图）
   • 模型优缺点与鲁棒性讨论
7. 模型评价与推广：
   • 总结模型的创新点、实用性。
   • 讨论模型局限性（如忽略风速、瞬时加油等）。
   • 提出改进方向（如考虑随机故障、多目标优化等）。
8. 参考文献与附录：附录可放完整代码。

避坑指南：论文写作中最忌讳“模型归模型，文字归文字”。必须在描述模型的章节，将每一个公式、每一个变量与之前文字分析的部分紧密对应。评审老师会顺着你的逻辑，检查你是否真正理解了模型的每一个部件。

6. 常见问题与扩展思考

在实战和后续研究中，我们遇到了不少典型问题。

6.1 典型问题排查清单

6.2 模型扩展与深化

这道题有丰富的扩展空间，可以体现建模的深度：

• 多基地与不同机型：加油机有不同类型（载油量、油耗率不同），且从分布在不同位置的基地起飞。这需要为每架飞机定义不同的起点坐标。
• 考虑风速的影响：顺风或逆风会影响地速，从而影响油耗和时间。模型需要引入速度向量，约束条件从单纯的距离关系变为更复杂的时空关系。
• 随机性建模：考虑加油失败的概率、飞机故障率等随机因素。问题将从确定性优化转变为随机规划或鲁棒优化，目标是最大化期望航程或在最坏情况下的航程。
• 多目标优化：不仅追求最大航程，还希望最小化总油耗、最小化出动飞机数量或最小化任务风险。这需要引入多目标优化方法，如加权和法或帕累托前沿求解。

6.3 对参赛新手的建议

回顾整个解题过程，对于想要在数学建模竞赛中应对此类优化题的队伍，我的建议是：

1. 精读题目，列出清单：把题目中的所有数字、条件、目标、限制用清单形式列出来，确保没有遗漏。
2. 先建简单模型，再复杂化：不要想着一口吃成胖子。先从只有1架加油机、1次加油的“极简模型”做起，确保基础物理关系（油量平衡）正确无误。然后像搭积木一样，逐步加入更多飞机、更多事件、更多特性（如接力加油）。
3. 编程与建模同步进行：不要等把所有模型都想完美了再编程。边建模边用代码实现简单的版本，用求解器测试。计算结果的反馈能帮你快速发现模型中的逻辑错误。
4. 重视可视化：一张好的示意图、轨迹图、结果对比图，胜过千言万语。它不仅能帮助你自己理解问题，更是论文中最抓人眼球的部分。
5. 分工明确，定期同步：队伍中最好有人侧重建模推导，有人侧重编程实现，有人侧重论文写作。但每天必须集中讨论，确保三个人的思路在同一频道上。

解决“空中加油飞行计划”这类问题，其乐趣不在于得到一个冰冷的数字，而在于体验将一团乱麻的现实问题，通过逻辑和数学梳理成清晰优美的模型，并最终用计算的力量找到最优解的过程。这种从混沌到秩序、从定性到定量的能力，正是数学建模竞赛带给参赛者最宝贵的财富。希望这篇超详细的复盘，能为你打开这扇门提供一块坚实的垫脚石。当你下次再看到复杂的优化问题时，能够冷静地对自己说：“别急，先看看它的决策变量、约束和目标函数是什么。”