简介一套围绕2021年‘华为杯’中国研究生数学建模竞赛F题整理的思路与代码包面向参赛研究生和各高校备赛团队针对航空公司机组优化排班等赛题建模、求解与验证需求。包内共16个文件以9个Python脚本为主配合4个CSV数据文件、1个Markdown思路说明、1个题目描述文档及1个带注释的文本文件压缩包仅211KB目录按题目序号和数据区分层组织便于快速定位。内容包含第1题至第3题的解题步骤、可运行代码、航班与乘务组排班数据以及详细的注释文本帮助读者理解建模逻辑后直接复现或改进。资源适合有一定Matlab/Python基础、希望借助现成框架冲刺获奖名单的参赛者对于缺乏经验的同学代码中的注释也能降低入门门槛。目前已有135人学习过。1. 2021华为杯F题机组排班一份能直接跑出MATLAB结果的完整方案2021年中国研究生数学建模竞赛F题是航空公司机组优化排班题目给出A、B两个基地的航班计划与机组花名册要求设计最小化机组投入的排班方案。很多人初看觉得是运筹学指派问题上手才发现真正的难点在于把资质匹配、连续执勤上限、轮休间隔这些业务规则转换成约束矩阵再让MATLAB的求解器在可接受时间内给出可行解。这份资源包把三问的思路文档和代码都备齐了适合正在备战研赛、想拿省级及以上奖项的队伍。它不只是参考答案更像一个能照着改的排班问题通用模板。2. 赛题拆解与数据摸底机组排班的约束体系与数据关联2.1 题目文档里那些决定模型形态的硬约束打开problem文件夹里的《航空公司机组优化排班问题.docx》第一问的文字描述很简短——给定航班计划求最少机组数但真正决定模型成败的是散落在题目各处的业务规则。把近几年的排班类赛题放在一起看约束基本逃不出四类资质匹配约束即机长、副驾驶必须拥有对应机型的签注航班覆盖约束即每个航班必须有足够人手执行连续执勤约束即单次执勤不能超过规定小时数休息期约束即两次执勤之间必须有最低休息时长。这四类约束里资质匹配和航班覆盖是静态约束直接写进0-1矩阵就行连续执勤和休息期是动态约束它们依赖排班结果的时间先后关系处理不好会让模型复杂度爆炸。我读题时的习惯是把每条约束抄成一张表左列是业务规则原文右列是数学表达和对应的代码变量名。比如每个航班至少需要2名机组对应 sum(x(:,j)) 2机长只能飞某种机型对应资质矩阵 qualification(i,j)1。等表格填完约束矩阵的轮廓已经出来了。约束类型业务含义数学表达代码变量资质匹配机组必须持有对应机型签注qualification(i,j)10-1资质矩阵航班覆盖每个航班至少有k名机组sum(x(:,j)) kflightCover连续执勤单次连续执勤不超过H小时滑动窗口求和约束dutySlots休息期两次执勤之间休息不少于R小时时隙间隔约束restSlots2.2 四份CSV的数据结构A/B基地与航班-机组关联data目录下四份CSV的命名非常有规律A-Flight是A基地的航班计划A-Crew是A基地的机组花名册B-Flight、B-Crew同理。航班表通常包含航班号、起飞机场、到达机场、起飞时刻、到达时刻、执飞机型六个字段机组表通常包含人员编号、姓名、资质等级、可飞机型、本月累计飞行时长等字段。两份表的关联键是机型机组可飞哪些航班完全取决于他的资质列表是否覆盖该航班机型。这里有一个数据清洗的关键点航班时刻是否跨越午夜。假设有个航班23:50起飞、次日01:30到达如果按自然日直接比较时间会误认为它与次日早上6点的航班不冲突但实际中间只隔了4.5小时休息期约束会被静默破坏。我处理这类数据时会先把所有时刻统一转换成以当天0点为基准的分钟数再判断是否跨零点拆分而不是直接拿字符串比较。这是第二问能否解出合理排班表的隐藏前提。2.3 优化目标与变量规模的预估第一问的目标函数常规写法是最小化启用机组总数作为主目标最小化总执勤时长或最大化机组利用率作为次目标。直接写双目标在MATLAB里不太方便常见做法是加权合成min f w1 * sum(x) w2 * sum(duty_i)其中w1取100量级、w2取0.1量级保证优先减少机组数、在机组数相同时再优化利用率。约束矩阵的规模需要提前心里有数。以A基地200条航班、80名机组为例第一问的指派变量就是200×8016000个0-1变量intlinprog完全能处理但第二问一旦把时间维度展开成15分钟时隙变量数会涨到80×96×200≈150万个量级即便用稀疏约束也需要很强的预求解能力。所以第三问代码选择换启发式算法是面对规模问题时的合理妥协而不是作者偷懒。理解了这一点再看code目录里三问代码的文件布局思路就顺了。3. 核心模块拆解三问代码的建模与实现链路3.1 第一问代码0-1整数规划的MATLAB实现第一问的代码核心是构造航班-机组二部图的0-1指派矩阵。设决策变量 x(i,j)若机组i执行航班j则取1否则取0。每个航班需要至少一名机组覆盖每个机组在同一时刻不能执行两个时间重叠的航班。MATLAB的优化工具箱里intlinprog是这类问题最顺手的求解器配合optimvar写法直观、报错信息可读性好。下面这段是第一问最核心的约束构造nCrew height(crewA); nFlight height(flightA); % 决策变量x(i,j) 表示机组i是否执行航班j x optimvar(x, nCrew, nFlight, ... Type, integer, LowerBound, 0, UpperBound, 1); % 目标min sum(x) 加权执勤时长 dutyMatrix repmat(flightA.duration, nCrew, 1); % 每个机组飞某航班的执勤时长 prob.Objective sum(sum(x)) 0.1 * sum(sum(x .* dutyMatrix)); % 约束1每个航班至少1名机组 prob.Constraints.flightCover sum(x, 1) 1; % 约束2时间重叠的航班不能被同一机组同时执行 overlap buildOverlapMatrix(flightA.startMin, flightA.endMin); for i 1:nCrew for j 1:nFlight for k j1:nFlight if overlap(j, k) prob.Constraints.([conflict_ num2str(i) _ num2str(j) _ num2str(k)]) ... x(i, j) x(i, k) 1; end end end end % 求解 sol solve(prob);逻辑说明overlap矩阵由buildOverlapMatrix函数生成输入是每个航班的开始与结束分钟数输出是nFlight×nFlight的0-1对称矩阵如果航班j和k在时间上有交集则overlap(j,k)1。三重循环虽然写起来粗糙但在16000个变量规模下实际生成的冲突约束条数是航班冲突对乘以机组数MATLAB在循环内动态添加约束的效率可以接受如果航班数再翻倍就要改成向量化构造约束矩阵。最后一行solve返回的sol.x就是0-1指派矩阵的最终结果。参数说明目标函数里0.1这个加权系数是关键调大调小直接影响解的结构——系数太大求解器会牺牲机组数去优化执勤总时长可能多启用1名机组来缩短整体时长系数太小次目标形同虚设。我一般先固定w1100w2从0.01到1做几个档位的对比选机组数稳定且时长最短的那组。3.2 第二问代码时隙化与滑动窗口约束第二问新增连续执勤时长上限和休息期下限。这两条约束用上一问的两两冲突思路去写会非常痛苦因为冲突关系变成了复杂的链条——比如执勤8小时后必须休息12小时不是一个二元关系而是一个区间约束。常规做法是把一天切成96个时隙每15分钟一个引入变量 y(i,t)1 表示机组i在时隙t执勤再把原始航班指派 x(i,j) 映射到时隙序列上。滑动窗口约束的写法是第二问代码里最值得抄的部分slotPerDay 96; % 一天96个15分钟时隙 maxDutySlots 8 * 4; % 8小时32个时隙 minRestSlots 12 * 4; % 12小时48个时隙 % y(i,t) 由 x(i,j) 推导航班j覆盖的时隙集合 y sum(x(:, j) .* flightSlotMask(j, :), 2); % 伪代码实际需展开维度 % 连续执勤约束任意连续32个时隙执勤时隙数不超过32 for i 1:nCrew for s 1:(slotPerDay - maxDutySlots 1) prob.Constraints.([duty_ num2str(i) _ num2str(s)]) ... sum(y(i, s:smaxDutySlots-1)) maxDutySlots; end end逻辑说明滑动窗口约束的核心观察是——任何一段长度超过maxDutySlots的连续执勤区间必然包含某个长度恰为maxDutySlots的完整窗口因此只要所有定长窗口内的执勤时隙数不超过窗口长度就不存在超时连续执勤。这是把无限多种区间压缩成有限个窗口的典型技巧比枚举所有可能的执勤起止点效率高一个量级。参数说明slotPerDay是精度和求解效率的博弈点。96个时隙精度高但会让第二个约束矩阵膨胀到 nCrew×(96-321) ≈ 80×65 5200行乘上其他约束后预求解时间明显上升。如果跑全量数据卡住先把slotPerDay降到4830分钟粒度问题规模直接减半。休息期约束在MATLAB里还有一种更省变量的写法把休息约束转换成执勤状态变化次数限制但那需要引入额外的0-1变量模型复杂度未必更低。3.3 第三问代码启发式搜索的切入与注释复用code目录里的文件命名透露了一个信息——第3题的详细注释写在第二问的代码里。这说明第三问大概率复用了第二问的约束构建函数只改了目标函数和求解策略。当整数规划变量规模达到几十万、约束数上万后intlinprog的收敛速度会变得不可控竞赛时间有限换成遗传算法ga或模拟退火去逼近可行解是合理的选择。第三问代码的示意实现如下% 第三问改用ga求解大规模排班 nvars nCrew * nFlight; LB zeros(1, nvars); UB ones(1, nvars); IntCon 1:nvars; fitness (xVec) fitnessFun(xVec, crewA, flightA, overlap); constraint (xVec) constraintFun(xVec, crewA, flightA, overlap); options optimoptions(ga, ... PopulationSize, 120, ... MaxGenerations, 300, ... FunctionTolerance, 1e-3, ... Display, iter, ... UseParallel, true); [xBest, fval] ga(fitness, nvars, [], [], [], [], ... LB, UB, constraint, IntCon, options);逻辑说明ga求解的核心是fitnessFun和constraintFun两个自定义函数。fitnessFun把长度为nvars的0-1向量还原成指派矩阵计算目标函数值constraintFun返回违反约束的度量比如未覆盖航班数、超时执勤时长ga内部用它做罚函数。调用时注意第三个参数nvars必须与xVec长度一致否则运行后立刻报维度错误。参数说明UseParallel设为true可以让ga并行计算种群适应度在四核以上的机器上提速明显但并行池启动有开销——小规模数据反而不如单线程快。实际调参时先跑一个20航班×15机组的小样本验证约束函数没有返回负数或NaN再放开PopulationSize和MaxGenerations跑全量。ga的随机性意味着每次结果可能不同我一般跑三五次取最优这个多次采样取最优的操作在竞赛里性价比很高。4. 环境准备与运行目录结构、数据预处理与三问复现4.1 资源包目录结构与分工解压后顶层目录非常清晰符合MATLAB竞赛项目的常规组织方式根目录 ├── 思路.md # 文字版解题思路论文写作参考 ├── data │ ├── 机组排班Data A-Crew.csv │ ├── 机组排班Data A-Flight.csv │ ├── 机组排班Data B-Crew.csv │ └── 机组排班Data B-Flight.csv ├── problem │ └── 航空公司机组优化排班问题.docx └── code ├── 第1题 ├── 第2题 └── 第3题 详细注释在第2问中.txtdata与problem分离、思路与代码分离这个结构对竞赛复现非常友好。拿到包后我先读思路.md它对三问的建模逻辑做了文字版串联之后再打开第2题代码因为第3题的注释也写在那里相当于读一份文件同时理解两个问的实现。4.2 数据读取的路径与编码MATLAB运行前把当前目录切换到code文件夹data和problem放在上级目录。代码里涉及相对路径时一定要先确认用csvread还是readtable。建议统一用readtable因为csvread不支持中文列名和字符串列航班号这种字符型数据会直接读成NaN% 推荐的数据读取方式支持中文表头与字符串列 opts detectImportOptions(../data/机组排班Data A-Flight.csv); opts.VariableNamingRule preserve; flightA readtable(../data/机组排班Data A-Flight.csv, opts); % 打印列名确认没有变成Var1 disp(flightA.Properties.VariableNames);逻辑说明第一行detectImportOptions自动检测CSV的每一列类型VariableNamingRule设为preserve后中文表头不会被替换成Var1、Var2后续代码里可以直接用 flightA.航班号 这种方式取列。打印VariableNames是成本最低的自检手段跑数据前花一秒钟看列名能避免后面所有踩坑。参数说明如果读出来中文字段乱码在readtable里追加一个Encoding参数指定字符集。常见CSV编码是UTF-8或GBK一次性判断编码的方法是先用fopen以字节模式打开文件读前三个字节——如果是EF BB BF则是UTF-8带BOM否则大概率是GBK。这个判断在Windows下导出Excel CSV时尤其重要。4.3 三问代码的运行顺序与结果自检第1题脚本运行后输出最小机组数和指派矩阵第2题输出排班表每条记录包含机组编号、航班编号、执勤时段第3题输出优化后的目标值和排班方案。建议按编号顺序运行因为第3题复用了第2题的约束函数必须先让第2题的脚本成功跑完工作区里才有可被第3题调用的函数句柄。如果直接跑第3题报了未定义函数错误多半是第2题没有先执行。运行完一定要做自检。最简单的自检是把排班结果映射回航班数据逐一检查是否所有航班都被覆盖、是否有机组超时执勤。代码如下% 排班结果自检航班覆盖完整性 assignedCrewCount sum(round(x), 1); % 每个航班分配的机组数 uncovered find(assignedCrewCount 1); if ~isempty(uncovered) warning(有 %d 个航班未覆盖编号 %s, ... length(uncovered), num2str(uncovered)); else disp(所有航班均已覆盖); end逻辑说明round(x)把求解器输出的小数解归整到0/1再按列求和得到每个航班的机组数。uncovered列表一旦非空几乎可以确定是模型约束漏写或求解器数值精度问题不是程序崩溃。这时候回到3.1节的约束清单优先检查flightCover那行 sum(x,1) 是否写成了sum(x,2)这是最常见的行列方向翻车点。参数说明intlinprog在默认精度下有时会返回0.9999这样的值round()之后才适合做统计。若发现覆盖数波动很大可以给求解器加一个intlinprog选项optimoptions(intlinprog,IntegerTolerance,1e-4)把整数判定阈值收紧结果会更稳定。5. 避坑指南从数据读取到求解器调参的4条实战踩坑5.1 中文表头读取后变成Var1列引用全部失效现象readtable读取CSV后用 flightA.航班号 取列直接报错变量列表里全是Var1、Var2、Var3。原因MATLAB的readtable默认遵循变量命名规则中文和特殊字符被替换成VarN。这在数据列较多、代码写满列名引用时是致命的所有后续计算都会因为找不到列而失败。解决读取之前先执行 opts detectImportOptions(xxx.csv); opts.VariableNamingRulepreserve; 再 readtable 时中文表头原样保留。如果是老脚本用csvread读的趁早换成readtablecsvread对字符串列的读取是灾难。5.2 航班覆盖约束的方向写反求解结果出现幽灵航班现象目标函数算出来的机组数异常小导出的排班表里有些航班没人飞。原因sum(x,1)和sum(x,2)弄反。按列求和是每个航班覆盖到的机组数按行求和是每个机组执行的航班数。覆盖约束需要前者写反后约束变成了每个机组至少飞一个航班航班无人覆盖却完全不违反约束。解决构造约束后先打印约束矩阵的尺寸flightCover约束的矩阵行数应该等于航班数对应每个航班一条约束。再用一个全零解的语义检查所有机组都不执行任何航班时应有约束被违反而不是通过。5.3 第二问的时隙约束运行半小时不收敛现象第一问秒出结果第二问加了时隙约束后求解器持续输出迭代日志进度停在某个gap值不动。原因时隙化展开后决策变量从1.6万涨到上百万连续执勤约束又把原本稀疏的矩阵变成稠密块。整数规划的分支定界在这种规模下会陷入维度灾难尤其当约束矩阵里存在大量软约束式的宽松不等式时。解决不要干等。第一招把时隙粒度从15分钟放宽到30分钟变量数直接减半第二招把连续执勤约束从窗口枚举改成累计执勤上限前提是题目没有明确要求连续、只在总时长上设限第三招直接切ga用遗传算法在10分钟内找可行解然后人工微调。竞赛现场时间就是分数放弃最优求可行是常态。5.4 输出排班表与评分模板格式不匹配现象排班结果正确但提交后被告知格式错误得分骤降。原因题目或评分规则里通常规定了输出文件的字段顺序和分隔符比如机组编号,航班编号,执勤起始时间,执勤结束时间每行一条记录逗号分隔、无表头。自己导出时习惯性加了表头、或者字段顺序按代码里的变量定义排列导致解析错位。解决拿到题目先找提交模板或输出格式说明没有模板就严格按题目描述字段顺序写。导出后用MATLAB自己读回来验证列数一致、行数与航班数一致再用文本编辑器打开看前几行是否符合字段顺序。这道工序花不了两分钟但能避免整个赛题白做。6. 二次开发把F题代码改造成通用的排班问题模板6.1 参数化改造把硬编码数据抽成配置从这份资源里学到最有用的习惯是把 nCrew、nFlight、slotPerDay、maxDutySlots 这些散落在脚本各处的常量统一抽到一个参数结构体里。改造后换一套数据、调整一个限制条件只需改一处不用在整个代码里搜索替换。% params.m —— 集中管理所有关键参数 params.slotPerDay 96; % 时隙数 params.maxDutyHours 8; % 单次执勤上限 params.minRestHours 12; % 最小休息时长 params.w1 100; % 机组数主目标权重 params.w2 0.1; % 执勤时长次目标权重 params.roundTol 1e-4; % 整数判定容差逻辑说明参数集中管理的好处是明显的——最典型的是赛题里某条约束从8小时改成6小时时不需要搜索所有出现8的地方逐个判断要不要改只需改params里的一行。这对竞赛现场的时间压力非常关键。6.2 换题迁移把航班排班框架搬到其他指派问题F题的框架本质是静态指派 时间冲突检测 连续状态约束这个三段式结构几乎可以平移到任何排班类赛题护理人员排班、生产线任务调度、物流车辆路径与时间窗分配。迁移时只需要重写两个函数buildOverlapMatrix把两个任务的起止时间换成你自己的冲突判定逻辑和objectiveFun换成你自己的目标。约束构造、求解器调用、结果自检这三段逻辑完全不动省下的时间足够用来多调两轮参数。6.3 小样本验证法先跑通流程再上全量验证时将航班表截取前20条、机组表截取前15人跑通主流程后检查目标函数值是否落在合理区间比如机组数在5到10之间。确认无误后再恢复全量数据把ga的MaxGenerations从50逐步升到200观察目标值的收敛曲线。从那以后我每次拿到新排班题都强制走一遍这套流程读数据 → 小样验证 → 全量求解 → 结果自检再没在赛场上翻过车。希望帮到你。本文还有配套的精品资源点击获取