简介一份针对2021年华为杯F题机组排班优化问题的思路与代码包面向参加中国研究生数学建模竞赛的在校研究生尤其适合需要快速上手、参考完整求解流程的备赛者。包内含赛题思路笔记、数据处理脚本与分步求解代码覆盖数据预处理、模型构建及结果分析等环节。压缩包共16个文件以9个Python脚本和4个CSV数据文件为主另有Word赛题文档、txt注释说明及Markdown思路文档整体仅211KB轻量精炼便于对照学习。目前已有135人学习浏览。借助该思路包读者可清晰理解F题的排班建模逻辑并参考各题代码中的详细注释特别是第2问进行复现与扩展节省从零摸索的时间是一份实用价值较高的竞赛参考资料。1. F题不是“排班题”是“拿奖题”每年9月中旬的研究生数模竞赛F题永远以“看起来很像运筹学”的面目出现。2021年的F题是航空公司机组优化排班很多队拿到题目就慌了——机组、航班、休息期数据一堆以为要用专门的调度软件。可你把题目拆开看本质就是三道递进的整数规划先让你把每个航班“盖”上一组机组再让你把“机组连续休息”这类规则写进约束最后让你在成本、均衡、疲劳度里挑一个目标做优化。用Matlab的intlinprog完全能顶住难点在建模而不是算法。下面按“考什么→哪三问→怎么建模→易错哪→怎么答题”给你过一遍。适合目标省一及以上的队伍尤其是不想卷信号题、无人机题的选手。2. 考点分布与赛题拆解F题的三个小问到底在考什么2.1 研赛F题的整体结构数据、问题、代码三位一体拿到题先看文件目录。这份资源里给了Data文件夹里面有A-Crew.csv、A-Flight.csv、B-Crew.csv、B-Flight.csv还有problem文件夹下的“航空公司机组优化排班问题.docx”code文件夹下分第1题、第2题、第3题并且第3题代码的详细注释放在第2问中。这说明题目不是只有一套数据而是分为A、B两组数据对应不同的机队或航线网络。比赛时多数队伍会栽在第一步不建索引直接用Excel打开CSV看到时间格式就懵。正确做法是先把CSV读进Matlab统一时间格式把航班号和机组ID变成分类变量然后才开始建模。文件路径内容使用时机Data/A-Flight.csv航班表航班号、起降时间、起降机场等第一问建模输入Data/A-Crew.csv机组组列表人员组、基地、可用时段第二问约束输入Data/B-Flight.csv另一组航班数据第三问换数据验证Data/B-Crew.csv另一组机组数据第三问换数据验证problem/航空公司机组优化排班问题.docx题目全文与三个小问第一天精读code/第1题、第2题、第3题对应三问的Matlab实现第二天起对照这类“给数据给问题文档”的赛题评分标准一般按三部分走模型是否完整40%、求解与结果是否合理35%、论文表达与图表25%。资源里单独列出的“思路.md”就是对三小问的逐题分析配合data里的CSV能省下很多整理数据的时间。先把这个结构认清楚后面建模才不会乱。2.2 三个小问的考点层次与分值预估第一问通常是基础排班给定一组航班和机组集合要求每个航班分配机长和乘务组满足最基本的覆盖目标是最少使用机组数或最低成本。这一问考的是“0-1变量覆盖约束”的建模基本功属于送分但容易丢分的地方。第二问会加“机组连续休息时间”或“基地出发返回”这类真实规则这就需要把时间轴上的状态变成约束条件考的是约束矩阵的构造。第三问一般会升级为多目标或者多基地、多机型的组合优化考的是降阶、线性化、或者用遗传/粒子群这类启发式算法做近似。从近几年的分水岭看大多数队伍能做出第一问但第二问开始拉开差距约束少了会被判定“规则未满足”约束多了模型规模爆炸。第二问的建模水平直接决定你是有省奖还是国家奖。第三问只要给出“把多目标加权化为单目标”的合理方案就能拿到大半分数不要求你真的跑出全局最优。所以复习重点应该压在第2问的约束表达和矩阵构造上而不是盲目追求高级算法。2.3 这份资源里“思路.md”和“code”的使用顺序不要拿到资源先翻代码也不要先看思路。比赛时间只有4天正确顺序是这样的第一天上午通读“航空公司机组优化排班问题.docx”把三个小问的约束逐条抄成清单下午看“思路.md”把每问的建模变量和约束对号入座晚上再打开code文件夹对照第1题和第2题的注释理解怎么用intlinprog写矩阵。第3题的代码在第2问中带详细注释说明第三问很可能是在第二问基础上加目标函数或松弛约束不是独立模型。这样用的原因在于代码是别人整理好的“黑匣子”思路如果你先读代码很容易照搬而不知道自己改了哪些参数对应什么含义。评委最反感的是“模型很漂亮但结果对不上约束”。先把问题文档梳理成数据表再对着思路文档填变量最后用代码验证这是最稳的拿奖路径。这也解释了为什么资源要分“思路.md”和“code”——思路管建模代码管落地缺一不可。3. 高频考点机组排班建模的三大核心3.1 考点一0-1变量与航班覆盖约束机组排班第一关是把“谁飞哪个航班”表示成决策变量。设x(i,j)1表示第j组机组执行航班i否则为0。每个航班至少要有一组机组覆盖所以对航班i有sum_j x(i,j) 1。这里有个很多队伍会踩的坑题目里的“机组”是机长、副驾驶、乘务员的组合不是一个个体。所以更准确的建模是“机组组”也就是把同一套人员组合当一个整体。A-Crew.csv和B-Crew.csv里每一行应视为一个可用的机组排班单元。覆盖约束是整数规划里最基础的约束但它的坑在“等于”还是“大于等于”。如果允许某个航班由两组机组共同执行比如长航线需要换班就要用如果严格要求每个航班恰好一组则用。2021年F题大概率是“至少一组”或“恰好一组”读题时注意“每架航班必须且只能分配一组”的表达。第二个坑是同一机组在同一时间段不能被重复指派这需要加时间冲突约束不是单看航班覆盖就能解决的。真正的比赛模型里x(i,j)前面还要乘上一个“可执行系数”如果机组组j没有执飞航班i的资质直接就设x(i,j)0或从变量集合里剔除。3.2 考点二机组休息与基地约束的建模机组不能连续飞无限长至少要满足“飞行一定时长后休息N小时”的规则。这种约束通常转换成“如果机组j执行了航班i则它不能在航班i落地后的N小时内执行另一个航班k”。用数学表达就是x(i,j)x(k,j)1当航班k的起飞时刻落在航班i落地时刻加休息期之后时这个约束不触发落在期内就要触发。实际编码时可以先算出任意两个航班i和k之间的“最小间隔”如果间隔小于休息时长就把这两个航班设成冲突对加入约束矩阵。基地约束是指机组从哪个基地出发最终要回到哪个基地。排班表必须闭合不能让机组飞到外地过夜除非题目允许。处理方法是把“机组所属基地”变成数据的一列对每个基地的机组集合统计其执行航班序列的最终落地机场要求最终落地机场等于基地。在Matlab里这一部分一般不做成线性约束而是先生成可行链再在链的级别做组合优化。这也是为什么第三问难度上升的原因一旦引入链式排班0-1变量之间会出现大量组合关系。关键思路是“先过滤后建模”——先把无法形成闭环的航班对从变量里删掉再去跑整数规划。3.3 考点三目标函数与Matlab的intlinprog求解目标函数通常有两种考法最小化机组使用数或最小化总成本/总飞行时长偏差。如果是最小化机组数可以设y(j)1表示机组j被启用目标就是sum_j y(j)。y与x的关系是若x(i,j)有任何一个是1则y(j)必须为1即y(j) x(i,j)同时x(i,j) y(j)。这组不等式是整数规划里的经典“激活变量”逻辑评委看到这一步会直接加分。Matlab里用intlinprog求解这类混合整数线性规划。假设已经构造好目标向量f、不等式约束Axb、等式约束Aeqxbeq以及变量上下界和整数变量下标调用方式如下% 变量数量 n 航班数*机组组数 机组组数 % 目标函数先排x部分再排y部分y的系数为启用成本 f [zeros(flights*groups,1); ones(groups,1)]; % 不等式约束每个航班覆盖至少一个机组 % A(航班i, 对应x) -1; b对应-1用于 转为 % 整数变量全部lb0, ub1 [x_opt, fval, exitflag] intlinprog(f, 1:n, A, b, Aeq, beq, lb, ub);这段代码里intlinprog默认求解线性规划第一个参数f是目标系数第二个参数1:n表示所有变量都是整数变量A和b是不等式约束Aeq和beq是用等式表达严格覆盖或多乘务员配置。注意把“”约束转成“”时要同时把两边取负号否则A矩阵符号错会导致无解。exitflag是求解器返回状态1表示成功-2表示无解0表示迭代次数超限。看到-2时不要慌先检查是不是覆盖约束符号写反了再检查数据里有没有时间冲突导致所有解都被禁掉。4. 真题演练三问的答题思路与Matlab实现4.1 第1问基础排班怎么写出第一版可行解第1问要求的往往是“在保证每个航班都被覆盖的前提下用的机组组数最少”。最直接的答题思路是三步第一读取A-Flight.csv和A-Crew.csv把航班按起飞时间排序第二定义x(i,j)为航班i由机组组j执行第三构造覆盖约束和目标函数。这里要展示给评委的不只是代码而是“为什么覆盖约束用而不是”。如果题目允许一名机组组在同一天执行多个航班只要时间不重叠那么一个机组组可以覆盖多个航班此时每个航班只需要一组所以用。如果不允许同一组多飞那就要换成“机组组当日累计飞行时间上限”来组合。第1问结果通常是一个整数矩阵每一行是航班每一列是机组组1表示匹配。输出表建议包含航班号、起飞时间、落地时间、机组组编号、该组当日飞行累计时长。评委拿到这张表一眼能看出你是否真的理解了覆盖关系。代码里不要把所有变量建成稀疏矩阵然后用for循环填约束那样效率低。用向量化方式先构造航班与机组组的“时间冲突矩阵”再把它展开成约束的稀疏矩阵。时间冲突矩阵是n×m的0-1矩阵1表示该机组可以执行该航班0表示时间冲突或资质不符。这个矩阵同时也是约束矩阵的主干。% 构造时间冲突矩阵 available(i,j)1 表示机组组j可执行航班i available zeros(flights, groups); for i 1:flights for j 1:groups % 判断机组组j的资质与时间是否满足航班i if crew_ability(j, flight_type(i)) ... dep_time(i) crew_available_start(j) ... arr_time(i) crew_available_end(j) available(i,j) 1; end end end % 将available矩阵作为x变量的可行域不可行的x强制为0这段代码的目的不是直接求解而是缩小变量范围。在论文里你要写出“对于available(i,j)0的位置x(i,j)直接置0或从模型中删除”这是把大规模问题降阶的第一个重要操作。很多队伍忽略了这一步导致整数规划变量数多到求解器跑不动。4.2 第2问加约束后的修正建模第2问一般会加入“机组连续休息时间不少于N小时”或“每个机组组每天最多飞M小时”。这类约束属于“成对互斥”约束直接加在x变量上。对任意两个冲突的航班i和k它们由同一机组执行时违反了休息时间或飞行时长限制加入x(i,j)x(k,j)1对所有机组组j成立。如果机组数很多这个约束的数量会爆炸但大多数是冗余的。优化技巧只对“时间间隔小于最小休息时长”的航班对生成约束不要全连。答题时用一段伪代码展示冲突航班对的生成逻辑再给出Matlab里构造稀疏矩阵的方法。这里有个加分点把“休息规则”设计成可配置参数比如定义rest_min 8小时飞行时长上限fly_max 8然后用这两个参数去筛选冲突航班对。这体现灵敏度分析的意识评委很吃这一套。实际代码可以写% 假设flights表有dep_time和arr_time两个列使用datenum格式 % crew_groups是机组组列表 % 冲突矩阵 conflict(i,k) 1 表示航班i与k由同一组执行会违反休息规则 rest_min 8; % 小时 for j 1:groups % 取机组组j可执飞的航班列表 flight_list find(available(:,j)1); for a 1:length(flight_list) for b a1:length(flight_list) i1 flight_list(a); i2 flight_list(b); gap dep_time(i2) - arr_time(i1); % 单位是天 if gap rest_min / 24 % 转成天 % 加入约束 x(i1,j)x(i2,j) 1 end end end end这段代码里最容易被忽略的是时间单位换算。CSV里的时间通常是字符串比如“2021-08-01 08:30”Matlab读进来要用datenum转成数值相减得到“天”。休息8小时就得写8/24不是写8。很多队伍最后结果算不出就是卡在单位换算上。另一方面循环三层虽然直观但数据量大时会很慢。比赛时可以用“先按机组组可飞航班列表排序再用差分时间”加速。如果第2问数据量不大直接三层循环也够用。4.3 第3问多目标或更大规模的降阶处理第3问常见两种升级方向一是目标函数变成“总成本 机组使用不平衡惩罚”的多目标二是把A/B两组数据合起来或要求跨基地闭环。应对多目标的套路是线性加权把两个目标归一化后相加。比如总成本C1最大最小机组工作量差C2目标写为min (w1C1 w2C2)权重w1,w2需要做灵敏度分析列出几组取值下的结果对比。这个表格在论文里非常提分。如果是规模爆炸不要硬跑整数规划。先用“分时段的贪心”或“机组组优先级排序”给出一个可行解作为初值再在初值周围用启发式搜索比如遗传算法的变异算子来改进。第3题代码里“详细注释在第2问中”暗示第3问很可能是直接调用第2问的模型换一组数据或换一个目标函数。所以答题时要写清楚第3问的模型是第2问模型的扩展不是新模型。具体地扩展点要么在等式约束上加了新的覆盖要求要么在目标函数里加了惩罚项。评委希望看到你“复用既有模型并解释改动”而不是推翻重来。第3问的Matlab实现建议用函数封装把“数据读入”“冲突矩阵构造”“目标函数计算”“约束矩阵生成”分别写成function这样第2问函数第3问可以复用。代码组织得好论文里贴核心段就够了不用把几百行的主程序全贴上去。这也是资源里code文件夹分“第1、第2、第3”的原因比赛代码要分层。拿到代码后你只需要改参数和读入文件名就能完成第三问的验证。5. 易错点这5处失分最多5.1 易错一时间格式错乱导致冲突计算失败错在哪直接用字符串去减或者把“8小时”写成8。为什么错Matlab里字符串不能相减datenum得到的是天8小时是8/24天。如果gap直接和8比较相当于把8天和8小时混为一谈所有约束都会失效。怎么答对读CSV后用datenum统一转成数值写一个time_to_hours函数所有休息时长的比较用hours (dep_time - arr_time)*24。在论文里明确写“所有时间统一为天小时数通过乘以24换算”这一句就是考点。5.2 易错二覆盖约束写成“1”没考虑一个机组组飞多班错在哪把“每个航班必须且只能被一个机组组执行”理解为sum_j x(i,j)1忽略了机组组可以跨航班执行。为什么错当机组组j执行航班i又执行航班k时x(i,j)1, x(k,j)1每个航班单独看都是“被一个组执行”但“每个航班恰好一个组”并不等于“一个组只飞一个航班”。所以用“sum_j x(i,j) 1”更合理。怎么答对读题时看有没有“每名机组当日只能执行一个航班”没有就写并在论文里说明为什么可以大于1——因为同一个机组组在不同时间段执行不同航班是被允许的只要时间不冲突。5.3 易错三机组组资质过滤遗漏错在哪直接把所有机组组放给所有航班没有看A/B组数据里的舱位资质、执飞资格。为什么错有些机组组只能飞某种机型或某个舱位配置如果忽略这一点求出的“最优解”在真实规则下不可行评委用题目条件一验证就扣分。怎么答对在构造变量x(i,j)前先做“可执行矩阵”用数据里的字段筛掉不匹配的组合再开始建立约束。这一步放在数据预处理阶段不要混在约束矩阵里。5.4 易错四intlinprog的参数写反或变量数不对错在哪把不等式约束的A和b构造反了或者整数变量下标写成1:groups而不是1:n。为什么错intlinprog要求所有整数变量必须明确列出把转成时如果忘了乘-1约束方向就反了。变量数量不匹配时Matlab会直接报错“Subscript indices must either be real positive integers”。怎么答对先在模型里列出所有变量并编号哪些是x哪些是y再构造f、A、b。建议用变量名注释清楚跑出结果前用size检查矩阵维度比如size(A,2)必须等于n。5.5 易错五只报目标函数值不交付排班表错在哪论文里只给了最优值但没有给出哪个航班由哪组机组执行的明细。为什么错评委没法验证你的解是否满足约束也没法核对数据。很多队伍把目标值算出来就收工结果评委看不到x矩阵的值。怎么答对把x矩阵的1的位置提取出来输出成“航班号、机组组号、起飞时间、落地时间”的表放在附录。这也是第1问最容易拿分的动作还能让评委相信你确实跑出了可行解。6. 答题技巧与押题把建模过程变成加分项6.1 论文里必须出现的三张表和一页图三张表变量定义表、参数取值表、结果对比表。变量定义表让评委不用猜你的符号参数取值表说明休息时长、权重系数这些数值是怎么定的结果对比表列出不同权重或不同约束松紧下的目标值和机组使用数。一页图是指排班甘特图横轴时间纵轴机组组用条形表示每次飞行任务。这张图能直观展示时间冲突是否被避开是评委会看的第一个视觉信息。画图用Matlab的barh或gantt的自定义绘制半小时搞定。6.2 灵敏度分析这样做调一个参数记录三个指标押题方向大概率是“调整休息时长N后所需机组数如何变化”或“成本权重w变化后排班均衡性如何变化”。答题时不要只放一个曲线而是做一张参数-指标表取N6、8、10、12小时记录机组数、总飞行时长方差、求解时间。结论写“随着N增大所需机组数从X增加到Y说明休息规则是约束瓶颈”之类。这种话术是拿奖的快捷键它证明你不仅会跑代码还理解模型行为。权重分析也类似列三组w1/w2取值看目标值变化说明你做了权衡。6.3 我的血泪习惯每一版模型先跑小样例再上全量数据我从那次比赛后每次建模都强制先构造一个5个航班、3组机组的玩具样例把全部约束和代码跑通再换全量数据。因为全量数据一旦报错你根本不知道是数据脏还是约束错。玩具样例可以手工验证10分钟内定位问题。这个习惯救了我好几次特别是第二问加冲突约束时小样例能让你看清约束矩阵是不是漏了某对角块。另一个习惯是每次改完变量数就重新打印一次size(A,2)核对避免低级错误。希望帮到你F题拿奖没有捷径但把上面这些板子搭好省奖起步是稳的。本文还有配套的精品资源点击获取
