简介面向数学建模参赛者与初学优化算法的读者这份资源聚焦0-1型整数线性规划在MATLAB中的建模与求解围绕目标函数、线性不等式与等式约束、变量上下界及整数变量索引的设定展开帮助读者把生产计划、资源分配、网络设计等离散决策问题抽象为可计算的模型并借助intlinprog完成求解。压缩包共6个文件以4个m脚本为主体承担模型构建与求解演示另含2个asv自动备份文件整体约3KB体量轻便便于直接阅读与改写。已有4347人学习下载说明其在赛前准备与课堂练习中具有一定参考价值。读者可从中获得0-1规划的建模思路、约束条件的组织方式以及初始点选择、精度设置、剪枝策略等实践要点用于对照理解算法行为并迁移到自己的赛题场景。1. 从一道“选不选”的题说起0-1 型整数线性规划到底考什么数学建模国赛里有一类题题干读完你会发现所有决策都是“选或不选”“开或不开”“投或不投”——这就是 0-1 型整数线性规划。它不像连续优化那样能靠求导找极值决策变量只能取 0 或 1解空间是离散的所以建模思路和求解手段都得换一套。matlab 在这类题里的角色很明确用intlinprog把模型喂进去拿到最优方案再回头解释每个 0/1 变量的现实含义。阅卷人看的不是你调了多少参数而是三件事目标函数写对没有、约束条件有没有漏、结果能不能自圆其说。这篇笔记按“考点分布—高频模型—真题演练—易错点—答题套路”的顺序拆适合已经会基本 matlab 语法、但一遇到 0-1 规划就不知道从哪下手的备赛者。2. 考点分布0-1 规划的四个必考模块与分值权重2.1 决策变量定义为什么必须“先翻译再建模”0-1 规划的第一道坎不是求解是把自然语言翻译成变量。阅卷时最常见的扣分不是算错而是变量定义含糊——写了x1, x2却没说明x11代表什么。规范做法是每个 0-1 变量对应一个明确的“动作”并在论文里用表格列出变量名、取值含义、对应题目中的哪句话。以经典的“选址—分配”类问题为例设y_j表示是否在第 j 个候选点建站x_ij表示第 i 个需求点是否由第 j 个站服务。这两个变量的含义必须在建模前写死后面所有约束都围绕它们展开。变量定义错了后面全盘皆输这是血泪经验。变量数量的估算也要提前做。若候选点 10 个、需求点 20 个则y有 10 个、x有 200 个共 210 个 0-1 变量。matlab 的intlinprog处理几百个 0-1 变量毫无压力但如果你把连续变量和 0-1 变量混在一个向量里索引就容易翻车。建议在代码开头用注释标清“第 1–10 位是 y第 11–210 位是 x”后面写约束时按这个偏移量取。2.2 目标函数与约束的标准写法从自然语言到矩阵intlinprog的标准形式是最小化f*x约束为A*x b、Aeq*x beq、lb x ub其中 0-1 变量通过lb0, ub1加intcon指定。很多考生卡在“最大化怎么转最小化”——把f取负即可最后结果再取负回来。约束的翻译是重头戏。以“每个需求点必须被服务且只被一个站服务”为例对应等式约束sum_j x_ij 1对每个 i 写一行Aeq。以“只有建了站才能提供服务”为例对应x_ij y_j即x_ij - y_j 0写进A。这两类约束几乎覆盖了 0-1 规划 80% 的场景剩下的多是容量约束sum_i demand_i * x_ij capacity_j * y_j。写矩阵时最容易错的是符号方向和行列对应。建议先在纸上把每个约束写成代数式再逐行填矩阵填完用一个小规模算例手算验证。下面这段代码演示了上述选址模型的核心矩阵构造% 候选站数 m3需求点数 n4 m 3; n 4; % 变量排列[y1..y3, x11..x14, x21..x24, x31..x34] nvars m m*n; % 目标最小化建站固定成本 服务运输成本 f zeros(nvars,1); f(1:m) [8; 6; 10]; % 各站固定成本 cost [2 3 1 4; 3 2 4 1; 1 4 2 3]; % 运输成本矩阵 for j 1:m f(m(j-1)*n1 : mj*n) cost(j,:); end % 等式约束每个需求点恰好被一个站服务 Aeq zeros(n, nvars); for i 1:n for j 1:m Aeq(i, m(j-1)*ni) 1; end end beq ones(n,1); % 不等式约束x_ij y_j即 x_ij - y_j 0 A zeros(m*n, nvars); b zeros(m*n,1); row 0; for j 1:m for i 1:n row row 1; A(row, m(j-1)*ni) 1; A(row, j) -1; end end % 0-1 变量设置 lb zeros(nvars,1); ub ones(nvars,1); intcon 1:nvars; [x, fval] intlinprog(f, intcon, A, b, Aeq, beq, lb, ub);这段代码的关键在变量排列顺序前 m 位是建站决策后面按“站优先、需求点其次”展开。Aeq每行只在一个位置放 1保证每个需求点被服务一次A每行放一个 1 和一个 -1实现“未建站则不能服务”的逻辑。参数intcon指定所有变量为整数配合lb/ub限定为 0-1。跑完后x(1:m)就是建站方案x后面的部分还原成m×n矩阵就是分配方案。若结果出现小数检查intcon是否漏写或ub是否设成了大于 1。2.3 求解器参数与结果解读别把“无解”当“算错”intlinprog返回的exitflag必须看1 表示找到最优解0 表示达到迭代上限但可行-2 表示无可行解-3 表示无界。很多考生看到exitflag-2就以为代码写错了其实往往是约束互相矛盾——比如同时要求“每个需求点被服务”和“总预算不够建任何站”。这时该做的是放松约束做敏感性分析而不是死磕代码。结果解读还要注意fval的量纲。如果目标里混了固定成本和运输成本fval是两者之和论文里要拆开汇报否则阅卷人看不出你的方案到底省在哪。另外intlinprog默认相对间隙RelativeGapTolerance是 1e-4对建模题足够若题目要求严格最优可设options optimoptions(intlinprog,RelativeGapTolerance,0)但小规模问题没必要。3. 高频模型三类必练的 0-1 规划题型与真题拆解3.1 选址—分配型真题“某物流中转站选址”怎么答这类题的典型问法是给定若干候选点和需求点建站有固定成本、服务有运输成本、每站有容量上限求总成本最小的方案。答题分四步定义变量、写目标、列约束、求解并解释。面试或答辩时面试官最想听的是你对“耦合约束”的处理。x_ij y_j这条约束是选址题的核心它把“建不建”和“服不服务”绑在一起。如果漏了它求解器会给出“不建站却提供服务”的荒谬解fval反而更小这是最隐蔽的失分点。另一条常考约束是容量sum_i demand_i * x_ij cap_j * y_j注意右边乘y_j否则未建站也有容量逻辑就错了。真题演练某模拟项目要求从 5 个候选点选不超过 3 个建站服务 8 个需求点预算上限 25。答题时先加约束sum_j y_j 3和sum_j fixed_j * y_j 25再跑intlinprog。若exitflag-2先检查预算是否连一个最便宜的站都建不起再检查容量总和是否小于总需求。这类题的得分点不在代码长度而在约束是否完整、解释是否对应现实。3.2 背包—投资型0-1 背包的 matlab 写法与变体0-1 背包是 0-1 规划的最小原型n 件物品每件有重量和价值背包容量有限每件要么拿要么不拿。标准模型是最大化sum v_i * x_i约束sum w_i * x_i W。转成intlinprog时目标取负约束一行搞定。变体才是考点。常见变体有三类一是“物品之间有依赖”选 A 必须先选 B写成x_A x_B二是“分组背包”每组最多选一件写成sum_{i in group} x_i 1三是“恰好选 k 件”写成sum x_i k。这三类变体在建模题里反复出现答题时先识别属于哪类再套对应约束模板。% 0-1 背包5 件物品容量 15 w [2 3 4 5 9]; % 重量 v [3 4 5 8 10]; % 价值 W 15; f -v; % 最大化转最小化 A w; b W; lb zeros(5,1); ub ones(5,1); intcon 1:5; [x, fval] intlinprog(f, intcon, A, b, [], [], lb, ub); fprintf(最大价值 %d选择方案 %s\n, -fval, mat2str(x));代码里f-v是最大化转最小化的标准操作Aw只有一行因为背包只有一个容量约束。mat2str(x)把列向量转成行向量方便阅读。若题目要求“恰好选 3 件”加Aeqones(1,5); beq3即可。注意intlinprog的等式约束参数位置是第五、六个别和不等式参数搞混这是新手常翻车的地方。3.3 指派—匹配型匈牙利算法的替代方案与适用边界指派问题是 0-1 规划的特例n 个人 n 项任务每人一项、每项一人成本矩阵已知求最小总成本。经典解法是匈牙利算法但在 matlab 里用intlinprog更通用因为指派题常带额外约束某人不能做某任务、某任务必须由特定人做匈牙利算法改起来麻烦intlinprog加一行约束就行。模型写法变量x_ij共 n² 个目标sum c_ij * x_ij约束sum_j x_ij 1每人一项和sum_i x_ij 1每项一人。这两组等式约束构成Aeq共 2n 行。若某人 k 不能做任务 t令ub中对应位置为 0 即可比改矩阵更干净。适用边界要说清n 小于 50 时intlinprog秒解n 上千时变量数爆炸这时才考虑匈牙利算法或拍卖算法。建模题规模通常不大intlinprog足够答题时提一句“规模增大可换专用算法”能体现你懂取舍但别展开成算法课。4. 易错点五类最常见的失分题与纠正答法4.1 目标函数漏乘系数或符号反了错在哪把“最大化利润”直接写成f profit忘了intlinprog是最小化结果解出来全是 0。为什么错没养成“先转最小化再填 f”的习惯。怎么答对目标函数第一行永远写f -profit或f cost并在注释里标明原始方向最后fval按原始方向解释。4.2 耦合约束写成x_ij 1而非x_ij y_j错在哪约束写成了恒真式求解器给出“不建站也服务”的解。为什么错没理解 0-1 变量之间的逻辑依赖。怎么答对凡是“只有…才…”的句子一律翻译成“前者 后者”并在论文里用一句话解释这条约束的现实含义。4.3 等式约束与不等式约束放错参数位错在哪把Aeq传给了A的位置或beq传成b导致约束全乱。为什么错intlinprog参数顺序是f, intcon, A, b, Aeq, beq, lb, ub记混了。怎么答对调用前用help intlinprog对一遍签名或把参数写成带名字的注释小规模算例先手算验证一组可行解。4.4 忘记设intcon导致解出小数错在哪只设了lb/ub没设intcon求解器返回 0.37 这类小数。为什么错lb/ub只限边界不限整数性。怎么答对0-1 规划必须同时设lb0, ub1, intcon1:nvars三者缺一不可跑完检查x是否只含 0 和 1。4.5 无可行解时直接改代码而不查约束矛盾错在哪exitflag-2后反复调参数越调越乱。为什么错无解通常是约束冲突不是算法问题。怎么答对先放松预算或容量约束跑一遍确认模型本身有解再逐条加回约束定位冲突源论文里把冲突分析写出来反而是加分项。5. 答题套路从读题到交卷的固定流程与押题方向拿到一道 0-1 规划题我习惯强制走一遍五步流程这套流程是从多次翻车里磨出来的。第一步圈出题干里所有“选/不选”“建/不建”“做/不做”的动作每个动作对应一个 0-1 变量列成三列表格变量名、取值含义、题中依据。第二步判断目标方向最大化就取负把目标写成f向量固定成本和变动成本分开算再相加。第三步逐句翻译约束每翻译一句就在纸上写代数式标好是等式还是不等式最后统一填矩阵。第四步设lb/ub/intcon跑intlinprog先看exitflag再看fval。第五步把解还原成现实方案用一段话解释“为什么这个方案最优”并做一次敏感性分析——比如预算加 10% 总成本降多少。押题方向上选址—分配和背包变体是绝对高频指派问题次之。答辩时最容易被追问的是“你的模型和贪心/枚举有什么区别”标准答法是枚举在变量数超过 20 时组合爆炸贪心不保证全局最优0-1 规划用分支定界保证最优且能加复杂约束。另一个高频追问是“结果对参数敏感吗”提前准备一张预算或容量变动 5%–20% 的成本曲线能直接堵住这个问题。题型核心约束常见变体答题优先级选址—分配x_ij y_j、容量约束建站数量上限、预算上限最高背包—投资sum w_i x_i W依赖、分组、恰好 k 件高指派—匹配双重等式约束禁选、必选、多人多任务中最后说个习惯每次交卷前我都会拿一组小规模数据手算一遍最优解和intlinprog的结果对一遍。对不上就说明矩阵填错了对得上才敢往下写论文。这个动作花不了五分钟但能拦住大部分低级错误。希望帮到你。本文还有配套的精品资源点击获取