0-1型整数线性规划：数学建模国赛美赛核心考点与MATLAB实战

简介：面向数学建模参赛者与运筹优化学习者的MATLAB 0-1型整数线性规划实践资料，聚焦决策变量仅取0或1的离散优化问题，可用于生产计划、资源分配、网络设计等场景的建模求解训练。资源包共6个文件，以4个m脚本和2个asv自动备份文件为主，m文件承载目标函数、约束矩阵与intlinprog调用等核心求解代码，asv文件保留编辑过程中的历史版本，便于对照修改痕迹；压缩包整体约3KB，体量轻便，适合快速导入本地环境运行调试。该资源已有4347人学习下载，具备一定的参考基础。读者可从中获取0-1规划建模的代码骨架、约束条件组织方式与求解参数设置思路，结合初始化、精度调整与剪枝策略等要点，理解intlinprog在实际赛题中的落地方法，并借助备份文件对比不同实现版本，提升将抽象模型转化为可运行程序的能力。

1. 0-1型整数线性规划：建模赛里最容易被低估的拿分模块

数学建模国赛、美赛以及各类校赛里，只要题目沾上“选或不选”“开或不开”“去或不去”，八成就是 0-1 型整数线性规划的战场。很多队伍一看到“整数规划”四个字就绕道走，转头去写遗传算法、模拟退火，结果代码跑了一晚上，论文里连一个像样的约束条件都没写清楚。阅卷人翻到模型建立部分，看到决策变量没有定义成二进制、约束条件漏了互斥关系，基本就判定这支队伍没抓住考点。真正稳的拿分方式恰恰相反：把 0-1 变量设对、把约束写全、用 MATLAB 的intlinprog跑出可行解，再配一张灵敏度分析表，分数就落袋了。这一块适合所有准备建模赛、又不想在启发式算法上调参调到崩溃的选手，尤其是编程手和建模手分工不明确的三人小队——谁都能上手，谁都能检查。

2. 考点分布：0-1规划的四个必考建模动作

2.1 决策变量为什么必须声明成二进制

0-1 型整数线性规划的第一考点，不是求解，而是变量定义。题目里出现“是否选择第 i 个方案”“是否在第 j 个位置建站”，决策变量就必须是 0 或 1，不能写成连续变量再四舍五入。MATLAB 里用intlinprog求解时，二进制变量通过intcon参数指定下标，同时上下界设为lb=0、ub=1。很多队伍只设了intcon却忘了把上界压到 1，结果解出来是 2 或者 3，再手动截断，约束全乱。面试官或阅卷人看模型部分，第一眼就找intcon和ub有没有配对出现。

% 决策变量 x1..x5 均为 0-1 变量 f = [-3; -4; -5; -6; -7]; % 目标函数系数，求最大值取负 intcon = 1:5; % 指定第1到第5个变量为整数 lb = zeros(5,1); % 下界全为0 ub = ones(5,1); % 上界全为1，这一步不能省 [x, fval] = intlinprog(f, intcon, A, b, Aeq, beq, lb, ub);

这段代码的关键在ub = ones(5,1)。只写intcon只能保证变量取整数，不能保证取 0 或 1；加上上界为 1 才真正锁死二进制。目标函数求最大值时系数取负，最后fval再取反，这是 MATLAB 线性规划接口的固定习惯，写论文时要说明清楚，否则评委会以为你目标函数写反了。

2.2 互斥约束与依赖约束的写法差异

第二考点是约束条件的逻辑表达。0-1 规划最常考两类关系：互斥和依赖。互斥指两个项目不能同时选，写成x1 + x2 <= 1；依赖指选了 A 才能选 B，写成x1 - x2 <= 0，即x1 <= x2。这两条式子看起来简单，但考场上有队伍把依赖写成x1 + x2 >= 1，意思变成“至少选一个”，完全跑偏。还有一种隐蔽考法：资源约束里带固定成本，比如“只要开工就有 500 的固定支出”，这时要引入辅助 0-1 变量 y，写成成本 >= 500*y且产量 <= M*y，M 取足够大的常数。这类题在真题里反复出现，答题时把每条约束的中文含义写在式子右边，阅卷人一眼就能对上。

2.3 用 intlinprog 求解时的参数陷阱

第三考点落在求解器调用。intlinprog的标准调用格式是intlinprog(f,intcon,A,b,Aeq,beq,lb,ub)，没有等式约束时Aeq和beq传空矩阵[]，不能省略位置。常见翻车点有三个：一是A矩阵方向搞反，MATLAB 默认A*x <= b，写成>=要整体乘负号；二是intcon传了列向量而不是行向量，老版本直接报错；三是没设options里的Display，求解失败时看不到退出标志。建议固定加一行options = optimoptions('intlinprog','Display','off')，再在论文附录里说明求解状态，显得专业。

% 带等式约束的调用示例：x1+x2+x3 = 2 Aeq = [1 1 1 0 0]; beq = 2; options = optimoptions('intlinprog','Display','off'); [x, fval, exitflag] = intlinprog(f, intcon, A, b, Aeq, beq, lb, ub, options); % exitflag = 1 表示找到最优解，0 表示达到迭代上限，-2 表示无可行解

exitflag是论文里必须交代的细节。很多队伍只贴一个解，不写求解状态，评委无法判断结果可信度。exitflag为 1 才代表收敛到最优，为 0 时要说明是时间限制还是节点限制，为负值则要检查约束是否矛盾。

2.4 真题演练：选址问题的完整答题链

一道典型的 0-1 规划真题是“从 6 个候选地中选若干建配送中心，满足各需求点覆盖，总成本最小”。答题链分四步：第一步设x_i表示第 i 个候选地是否选中；第二步写目标函数，总成本等于建设成本加运输成本；第三步写覆盖约束，每个需求点至少被一个选中地覆盖，形如x1 + x3 + x5 >= 1；第四步调用intlinprog并做结果解读。面试官最想听的是你对“覆盖约束为什么是大于等于 1”的解释——它保证每个需求点不被漏掉，而不是要求每个点只被覆盖一次。易错点在于把覆盖约束写成等式，导致某些需求点被迫重复覆盖，成本虚高。

3. 高频题型：五类真题的答题模板与代码骨架

3.1 背包类：目标函数与容量约束的对应关系

背包问题是 0-1 规划最基础的变体，真题常以“预算分配”“装载方案”出现。答题模板固定为：x_i表示第 i 件物品是否装入，目标最大化总价值sum(v_i * x_i)，约束为总重量不超过容量sum(w_i * x_i) <= W。MATLAB 里求最大值要把f取负，代码骨架和 2.1 节一致，只换系数。考生常错在把容量约束写成>=，或者忘记ub上界。面试追问“如果每件物品最多装一件怎么体现”，答案就是变量本身是 0-1，天然限制一件；如果允许多件，才需要改成整数变量并加上界。

3.2 指派类：每项任务恰好一人的等式约束

指派问题考的是“n 个人 n 项任务，每人一项、每项一人，总耗时最小”。决策变量x_ij表示第 i 人做第 j 项任务，约束是每行和为 1、每列和为 1，即sum_j x_ij = 1和sum_i x_ij = 1。这两组等式约束必须同时写，漏掉列约束就会出现两个人抢同一项任务。代码上Aeq是 2n 行的矩阵，前 n 行对应人员，后 n 行对应任务。答题时把矩阵结构画成表格附在论文里，评委一看就懂。易错点是变量下标展平成一维时顺序搞乱，建议用x = reshape(X, n*n, 1)并在注释里写明“按行优先展开”。

3.3 下料类：用二进制变量表达“启用与否”

下料问题常考“用若干根标准钢管切割不同长度需求，使废料最少”。这里有两层变量：y_j表示第 j 根钢管是否启用，x_ij表示第 j 根钢管切出第 i 种段的数量。约束包括需求满足sum_j x_ij >= d_i，以及启用联动x_ij <= M * y_j，M 取该钢管最多能切的段数。这类题面试官最爱问“为什么需要 y_j”，答案是固定成本或根数计数必须靠 0-1 变量表达，否则无法统计用了多少根原料。答题时把 M 的取值依据写清楚，不能随手写 9999。

3.4 面试题：解释“松弛后取整”为什么不可靠

面试或答辩环节常被问：“线性规划松弛后四舍五入不行吗？”标准答法是：松弛解可能落在可行域内部，取整后可能违反约束，甚至不可行；而且取整后的目标值无法保证接近最优，差距可能很大。举例说明：两个互斥项目松弛解各为 0.5，四舍五入都变 1，直接违反x1 + x2 <= 1。正确做法是用分支定界或直接调intlinprog，它内部就是分支定界加割平面。回答时补一句“0-1 规划的组合爆炸特性决定了不能靠连续解凑”，基本就满分。

3.5 面试题：多目标怎么转成单目标再求解

建模赛里经常出现“成本最低同时覆盖最全”的双目标。面试官想听的是转化方法：加权求和法、主要目标法、分层序列法。加权求和最常用，把两个目标归一化后乘权重相加，权重通过灵敏度分析给出几组对比。答题模板是：先分别求单目标最优值作为归一化基准，再构造min w1*f1/f1* + w2*f2/f2*，最后讨论权重变化对解的影响。易错点是两个目标量纲不同直接相加，导致某一目标被淹没。论文里附一张权重-目标值表格，比空谈“综合考虑”有说服力得多。

4. 易错点：五个反复失分的坑与纠正答法

4.1 变量上界漏设导致解出非二进制值

错在哪：只写了intcon，没写ub = ones(n,1)，求解结果出现 2、3 甚至更大整数。为什么错：intcon只约束整数性，不约束取值范围，MATLAB 默认上界是无穷大。怎么答对：二进制变量必须同时满足lb=0、ub=1、intcon三件套，论文里用一句话说明“决策变量为 0-1 变量，通过上下界与整数约束共同实现”。

4.2 互斥约束方向写反

错在哪：两个项目不能同时选，写成x1 + x2 >= 1。为什么错：这个式子要求至少选一个，和互斥含义完全相反。怎么答对：互斥记作“和不超过 1”，即x1 + x2 <= 1；依赖记作“选了 A 才选 B”，即x1 - x2 <= 0。答题时在约束后面用括号标注中文含义，避免自己回头检查时看混。

4.3 大 M 取值过小导致约束失效

错在哪：联动约束x <= M*y里 M 取 10，但实际单根钢管最多切 50 段。为什么错：M 太小会让x被错误截断，可行解被排除；M 太大则数值不稳定。怎么答对：M 取该约束下x的理论上界，并在论文里写明取值依据，例如“M 取单根原料最大可切段数”。

4.4 求解失败不检查 exitflag

错在哪：代码跑完直接拿x写结论，不看出标志。为什么错：exitflag为负时解不可行或未收敛，结论完全不可信。怎么答对：每次求解后打印exitflag，为 1 才采用；为 0 时放宽迭代次数或检查约束矛盾；为负时逐条排查约束。论文附录附上求解状态说明。

4.5 目标函数求最大值忘记取负

错在哪：intlinprog默认求最小，直接传正系数导致解出最小值。为什么错：MATLAB 接口固定为最小化，最大值问题必须系数取负、结果取反。怎么答对：代码里f = -c，输出时maxval = -fval，并在论文里写清“目标函数取负转化为标准最小化形式”。

5. 考场答题节奏：从读题到交卷的 0-1 规划检查清单

真正拉开差距的不是会不会调intlinprog，而是交卷前有没有走一遍固定检查。我的习惯是读题时先用铅笔圈出所有“是否”“选择”“启用”字眼，圈完立刻在草稿纸左上角写“0-1”两个大字，提醒自己别往连续优化上跑。设完变量先不写目标函数，而是把每条约束翻译成中文短句列成清单，再逐条转成不等式，这样互斥和依赖不会混。代码写完先跑一个小规模手算案例验证，比如三个变量、两条约束，确认exitflag=1且解和手算一致，再换真实数据。最后十分钟专门检查三件事：ub有没有设、intcon是不是行向量、目标函数符号对不对。这套流程听起来笨，但血泪经验是，建模赛丢的分多半不是算法不会，而是这些一眼能看出来的细节没查。

押题方向上，下一场建模赛如果出现“选址+覆盖+预算”三件套，大概率还是 0-1 规划的主场，把覆盖约束和预算约束的写法练熟，比临时学一个新启发式算法划算得多。从那以后我每次带队伍，读题环节都强制走一遍“圈是否、写 0-1、列约束中文清单”这三步，再也没在变量定义上翻过车。希望帮到你。

本文还有配套的精品资源，点击获取