简介这份资源面向参加数学建模竞赛的学生与需要求解离散优化问题的学习者聚焦0-1型整数线性规划这一线性规划特例帮助读者在MATLAB环境中完成从模型抽象到数值求解的完整流程。包内共6个文件以m脚本与asv自动备份文件为主压缩包约3KB脚本涉及0-1型整数规划的建模与求解示例备份文件则保留了编辑过程中的中间版本便于对照理解代码演进。已有4347人学习下载说明其在赛前准备与课堂练习中具有一定参考价值。读者可从中获得intlinprog函数的调用范式、目标函数系数与不等式/等式约束的矩阵组织方式以及整数变量索引、上下界设定等关键参数的配置思路并借此体会初始点选择、约束校验、精度调整与剪枝策略对求解效率的影响从而在有限时间内搭建可复用的求解框架。1. 0-1型整数线性规划一个开关决定一件事做不做你有没有遇到过这种纠结手头预算就那么多几个项目看着都不错到底选哪几个或者排班时每个人只能上一班怎么安排才最省成本这类“做还是不做”“选还是不选”的决策在数学建模里有个非常贴切的名字——0-1型整数线性规划。名字听着唬人拆开看其实很朴素0和1代表“不做”和“做”整数代表结果不能是半个线性规划代表约束和目标都是一次方的加减关系。它之所以值得搞懂是因为现实里大量资源分配问题本质都是在一堆“要不要”的开关之间找最优组合。而用 MATLAB 来解这类问题恰好能把建模思路和求解工具串成一条线是数学建模里性价比很高的一块内容。2. 为什么偏偏是0和1离散决策的数学表达2.1 从“连续”到“离散”的那道坎普通的线性规划变量可以取任意实数。比如生产多少吨钢材、分配多少小时工时答案是 3.7 吨、2.5 小时都合理。但很多决策天然是离散的一个项目要么上要么不上一台机器要么开要么关一个人要么排早班要么排晚班。你没法“上 0.6 个项目”也没法“开 0.3 台机器”。这时候如果还让变量取小数解出来的结果在现实中根本没法执行。0-1型整数线性规划就是给这类决策量身定做的表达方式。它把每个“要不要”的决策压缩成一个变量取值只能是 0 或 1。0 表示不选、不做、不开1 表示选、做、开。多个这样的变量组合起来就能描述一整套选择方案。打个比方这就像一排电灯开关每个开关只有开和关两个状态你要在满足用电限制的前提下让亮着的灯带来的总收益最大。这种表达的好处是模型和现实之间几乎没有翻译损耗。你写下的每一个变量对应现实里一个明确的动作你写下的每一条约束对应现实里一条明确的规则。建模时不容易跑偏求解后也容易解释。2.2 目标函数和约束长什么样用 MATLAB 的视角看0-1型整数线性规划的标准形式可以写成目标函数是一个线性表达式约束也是一组线性等式或不等式变量被限定在 0 和 1 之间且取整数。用数学符号说就是求一组 x 使得 cx 最小或最大同时满足 A·x ≤ b、Aeq·x beq且每个 x 只能取 0 或 1。这里的关键在于“线性”两个字。目标里不能出现 x 的平方约束里不能出现两个变量相乘。一旦出现非线性项就不属于这个模型的范畴了。很多初学者建模时不小心写出 x1 乘以 x2 这样的约束求解器会直接报错或者给出莫名其妙的结果这是后面要专门说的坑。在 MATLAB 里这类问题通常交给 intlinprog 这个函数处理。它的调用方式大致是给定目标系数向量、整数变量的下标、不等式约束矩阵和向量、等式约束矩阵和向量、变量的上下界。对于 0-1 规划上下界分别设为 0 和 1再把所有变量标记为整数变量模型就完整了。下面是一段示意性的代码帮助理解参数是怎么摆进去的% 目标最小化 c*x这里 c 是各决策的代价系数 c [4; 5; 6; 3]; % 整数变量下标四个变量全部要求取整数 intcon [1, 2, 3, 4]; % 不等式约束 A*x b例如总资源不能超过上限 A [2, 3, 1, 4]; b 10; % 等式约束留空 Aeq []; beq []; % 下界全为0上界全为1即0-1变量 lb zeros(4, 1); ub ones(4, 1); % 调用求解器 [x, fval] intlinprog(c, intcon, A, b, Aeq, beq, lb, ub);这段代码里c 是每个决策的代价A 和 b 描述资源上限lb 和 ub 把变量锁死在 0 和 1 之间intcon 告诉求解器哪些变量必须是整数。求解结果 x 里每个分量非 0 即 1直接对应“选或不选”。参数改动的空间很大约束多一条就多一行 A决策多一个就多一列上下界也可以针对个别变量单独调整。理解了这个骨架后面遇到具体问题只是往里填数。2.3 为什么它比“先算小数再四舍五入”靠谱有人会想既然普通线性规划算得快那我先让它算出小数解再把接近 1 的取 1、接近 0 的取 0不就行了这个想法很自然但经常翻车。原因在于四舍五入之后得到的组合很可能违反原来的约束。比如预算约束刚好卡在边界上你把某个 0.4 舍成 0、某个 0.6 入成 1总花费可能就超了。更麻烦的是你没法保证舍入后的方案是“最优”的甚至没法保证它是“可行”的。0-1型整数线性规划的价值就在于它在整个离散组合空间里系统地搜索保证找到的解既满足所有约束又是在这个模型下目标值最好的。代价是计算量比普通线性规划大因为组合数量会随变量个数指数增长。但对于数学建模里常见的几十个决策变量现代求解器配合分支定界之类的策略通常能在可接受的时间内给出结果。这也是为什么建模时更愿意把问题老老实实写成 0-1 模型而不是事后补救。3. 建模时最容易踩的几类坑易混概念与常见误区3.1 误区一把“整数规划”和“0-1规划”当成一回事易混点在于两者都带“整数”二字很多人以为只要变量取整数就是 0-1 规划。为什么混因为教材里常把它们放在同一章讲名字又挨得近。怎么区分看变量的取值范围。整数规划的变量可以取 0、1、2、3 等任意整数比如“安排几个人”可以是 3 个人而 0-1 规划的变量被严格限制在 0 和 1 两个值只表达“是或否”。在 MATLAB 里两者的区别就体现在上下界整数规划的上界可能是正无穷或某个大数0-1 规划的上界固定为 1。建模时如果某个决策天然可以取多个整数值却硬套 0-1 变量就会把问题写错解出来的方案也不符合现实。3.2 误区二约束里出现变量相乘还以为是线性的易混点在于很多现实规则听起来像“如果选 A 就不能选 B”初学者会直接写成 xA 乘以 xB 等于 0。为什么混因为这句话的逻辑确实是“两者不能同时为 1”而乘法恰好能表达这个意思。但一旦写出乘积项模型就不再是线性的intlinprog 这类求解器无法直接处理。怎么区分看表达式里有没有两个决策变量相乘。正确的做法是用线性约束来表达互斥关系比如 xA xB ≤ 1这一条就等价于“最多选一个”。类似地“选了 A 才能选 B”可以写成 xB ≤ xA。把逻辑关系翻译成加减和不等式是 0-1 建模的一项基本功也是区分新手和老手的地方。3.3 误区三忘了给变量设上界解出大于 1 的数易混点在于有人只记得把变量标记为整数却忘了把上界设成 1。为什么混因为“整数变量”这个说法容易让人以为取整数就够了忽略了 0-1 规划还需要额外的边界限制。怎么区分看求解结果里有没有出现 2、3 这样的值。如果出现了说明上界没锁死。在 MATLAB 里ub 必须显式设为全 1 的向量否则求解器只保证整数不保证不超过 1。这个坑很隐蔽因为模型可能照样跑出结果只是结果不符合 0-1 的语义后面解释方案时就会露馅。3.4 误区四目标函数方向搞反最大最小傻傻分不清易混点在于intlinprog 默认求最小化而很多建模题写的是“收益最大”“利润最高”。为什么混因为题目描述和目标函数的方向不一定一致初学者容易直接把收益系数填进去就跑。怎么区分看求解结果的数值是不是明显不对。如果题目要最大化而你把收益系数原样放进最小化框架解出来的往往是“什么都不选”这种极端方案。正确做法是把目标系数取负求最小化再把结果的目标值取负回来或者用求解器支持的最大化参数。这个细节不影响模型结构但直接影响答案对不对属于典型的“一失足成千古恨”。3.5 误区五把“可行解”当成“最优解”易混点在于求解器返回了一个满足约束的 0-1 组合有人就以为大功告成。为什么混因为可行和最优是两回事尤其在约束较多时可行组合可能有很多个目标值差别很大。怎么区分看求解器输出的状态信息和目标值确认它报告的是最优而不是仅仅可行。建模报告里如果只写“得到一组方案”而不说明这组方案在目标上的表现说服力会大打折扣。养成检查求解状态、对比目标值的习惯能避免把“能跑通”误当成“做对了”。4. 拿到一个问题怎么判断该不该用0-1模型4.1 三个信号帮你快速判断第一个信号是决策的离散性。如果问题里的核心动作是“选哪些”“安排谁”“开哪台”而且每个动作只有做和不做两种状态那 0-1 模型几乎是首选。第二个信号是约束的线性可表达性。如果规则能用加减和不等式说清楚比如总量不超过上限、每项至少选一个、某些项互斥那就能落进线性框架。第三个信号是规模可控。决策变量在几十到几百这个量级现代求解器通常扛得住如果变量上千且约束复杂就要考虑求解时间必要时做简化或分阶段处理。反过来如果决策本身是连续的比如分配多少资金比例、设定多高的温度硬套 0-1 变量反而会把问题写拧。还有一种情况是目标或约束里天然带非线性关系比如收益随投入呈平方增长那也不属于这个模型的适用范围需要换用其他方法。判断的标准不是“哪个高级用哪个”而是“哪个贴合问题的真实结构”。4.2 一个具体例子预算有限时的项目选择设想某团队有一笔固定预算面前有若干候选项目每个项目需要一定投入、预期带来一定收益问怎么选才能使总收益最大。这个场景里每个项目对应一个 0-1 变量投入和收益都是线性相加预算上限是一条不等式约束。模型写出来非常干净目标系数是各项目收益取负后求最小约束矩阵是各项目投入右端是预算总额变量上下界锁在 0 和 1。用 MATLAB 求解后结果为 1 的项目就是建议上马的项目。这个例子的价值在于它把 0-1 建模的几个要素都串起来了离散决策、线性目标、线性约束、边界限制。实际建模题往往在此基础上加料比如项目之间有依赖关系选了 A 才能选 B、有互斥关系A 和 B 不能同时上、有数量限制最多选三个。这些都能用线性约束表达模型骨架不变只是约束矩阵多几行。理解了这个骨架遇到变体就不容易慌。4.3 什么时候别硬上边界与替代思路0-1 模型不是万能的。当决策变量数量很大、约束又错综复杂时求解时间可能长到不实用这时候要考虑问题是否真的需要精确最优还是可以接受启发式方法给出的近似解。另外如果问题里的不确定性很强比如收益本身是个随机变量那单纯的确定性 0-1 模型就不够用需要引入其他建模范式。还有一种常见情况是约束里存在明显的非线性逻辑硬转成线性会引入大量辅助变量模型变得臃肿难维护这时要权衡表达清晰度和求解效率。我的习惯是每次动手写模型前先把决策、目标、约束三样东西用大白话列一遍确认每个决策都能落成 0-1 变量、每条规则都能落成线性式再打开 MATLAB 填参数。有一次我跳过这一步直接把一个带互斥条件的排班问题塞进求解器结果因为约束写成了乘积形式反复报错折腾半天才回头补上线性表达。从那以后我每次建模都强制走一遍“白话清单”确认没有非线性项再动手。希望这些经验能帮你在遇到 0-1 型整数线性规划时少走一点弯路。这份资料把建模思路和 MATLAB 实现放在一起适合边看边对照自己的问题往里套。本文还有配套的精品资源点击获取 
长河君 · 2026/10/31 19:08:44 · 阅读 1.2k 0-1型整数线性规划：MATLAB建模与求解实战指南
简介这份资源面向参加数学建模竞赛的学生与需要求解离散优化问题的学习者聚焦0-1型整数线性规划这一线性规划特例帮助读者在MATLAB环境中完成从模型抽象到数值求解的完整流程。包内共6个文件以m脚本与asv自动备份文件为主压缩包约3KB脚本涉及0-1型整数规划的建模与求解示例备份文件则保留了编辑过程中的中间版本便于对照理解代码演进。已有4347人学习下载说明其在赛前准备与课堂练习中具有一定参考价值。读者可从中获得intlinprog函数的调用范式、目标函数系数与不等式/等式约束的矩阵组织方式以及整数变量索引、上下界设定等关键参数的配置思路并借此体会初始点选择、约束校验、精度调整与剪枝策略对求解效率的影响从而在有限时间内搭建可复用的求解框架。1. 0-1型整数线性规划一个开关决定一件事做不做你有没有遇到过这种纠结手头预算就那么多几个项目看着都不错到底选哪几个或者排班时每个人只能上一班怎么安排才最省成本这类“做还是不做”“选还是不选”的决策在数学建模里有个非常贴切的名字——0-1型整数线性规划。名字听着唬人拆开看其实很朴素0和1代表“不做”和“做”整数代表结果不能是半个线性规划代表约束和目标都是一次方的加减关系。它之所以值得搞懂是因为现实里大量资源分配问题本质都是在一堆“要不要”的开关之间找最优组合。而用 MATLAB 来解这类问题恰好能把建模思路和求解工具串成一条线是数学建模里性价比很高的一块内容。2. 为什么偏偏是0和1离散决策的数学表达2.1 从“连续”到“离散”的那道坎普通的线性规划变量可以取任意实数。比如生产多少吨钢材、分配多少小时工时答案是 3.7 吨、2.5 小时都合理。但很多决策天然是离散的一个项目要么上要么不上一台机器要么开要么关一个人要么排早班要么排晚班。你没法“上 0.6 个项目”也没法“开 0.3 台机器”。这时候如果还让变量取小数解出来的结果在现实中根本没法执行。0-1型整数线性规划就是给这类决策量身定做的表达方式。它把每个“要不要”的决策压缩成一个变量取值只能是 0 或 1。0 表示不选、不做、不开1 表示选、做、开。多个这样的变量组合起来就能描述一整套选择方案。打个比方这就像一排电灯开关每个开关只有开和关两个状态你要在满足用电限制的前提下让亮着的灯带来的总收益最大。这种表达的好处是模型和现实之间几乎没有翻译损耗。你写下的每一个变量对应现实里一个明确的动作你写下的每一条约束对应现实里一条明确的规则。建模时不容易跑偏求解后也容易解释。2.2 目标函数和约束长什么样用 MATLAB 的视角看0-1型整数线性规划的标准形式可以写成目标函数是一个线性表达式约束也是一组线性等式或不等式变量被限定在 0 和 1 之间且取整数。用数学符号说就是求一组 x 使得 cx 最小或最大同时满足 A·x ≤ b、Aeq·x beq且每个 x 只能取 0 或 1。这里的关键在于“线性”两个字。目标里不能出现 x 的平方约束里不能出现两个变量相乘。一旦出现非线性项就不属于这个模型的范畴了。很多初学者建模时不小心写出 x1 乘以 x2 这样的约束求解器会直接报错或者给出莫名其妙的结果这是后面要专门说的坑。在 MATLAB 里这类问题通常交给 intlinprog 这个函数处理。它的调用方式大致是给定目标系数向量、整数变量的下标、不等式约束矩阵和向量、等式约束矩阵和向量、变量的上下界。对于 0-1 规划上下界分别设为 0 和 1再把所有变量标记为整数变量模型就完整了。下面是一段示意性的代码帮助理解参数是怎么摆进去的% 目标最小化 c*x这里 c 是各决策的代价系数 c [4; 5; 6; 3]; % 整数变量下标四个变量全部要求取整数 intcon [1, 2, 3, 4]; % 不等式约束 A*x b例如总资源不能超过上限 A [2, 3, 1, 4]; b 10; % 等式约束留空 Aeq []; beq []; % 下界全为0上界全为1即0-1变量 lb zeros(4, 1); ub ones(4, 1); % 调用求解器 [x, fval] intlinprog(c, intcon, A, b, Aeq, beq, lb, ub);这段代码里c 是每个决策的代价A 和 b 描述资源上限lb 和 ub 把变量锁死在 0 和 1 之间intcon 告诉求解器哪些变量必须是整数。求解结果 x 里每个分量非 0 即 1直接对应“选或不选”。参数改动的空间很大约束多一条就多一行 A决策多一个就多一列上下界也可以针对个别变量单独调整。理解了这个骨架后面遇到具体问题只是往里填数。2.3 为什么它比“先算小数再四舍五入”靠谱有人会想既然普通线性规划算得快那我先让它算出小数解再把接近 1 的取 1、接近 0 的取 0不就行了这个想法很自然但经常翻车。原因在于四舍五入之后得到的组合很可能违反原来的约束。比如预算约束刚好卡在边界上你把某个 0.4 舍成 0、某个 0.6 入成 1总花费可能就超了。更麻烦的是你没法保证舍入后的方案是“最优”的甚至没法保证它是“可行”的。0-1型整数线性规划的价值就在于它在整个离散组合空间里系统地搜索保证找到的解既满足所有约束又是在这个模型下目标值最好的。代价是计算量比普通线性规划大因为组合数量会随变量个数指数增长。但对于数学建模里常见的几十个决策变量现代求解器配合分支定界之类的策略通常能在可接受的时间内给出结果。这也是为什么建模时更愿意把问题老老实实写成 0-1 模型而不是事后补救。3. 建模时最容易踩的几类坑易混概念与常见误区3.1 误区一把“整数规划”和“0-1规划”当成一回事易混点在于两者都带“整数”二字很多人以为只要变量取整数就是 0-1 规划。为什么混因为教材里常把它们放在同一章讲名字又挨得近。怎么区分看变量的取值范围。整数规划的变量可以取 0、1、2、3 等任意整数比如“安排几个人”可以是 3 个人而 0-1 规划的变量被严格限制在 0 和 1 两个值只表达“是或否”。在 MATLAB 里两者的区别就体现在上下界整数规划的上界可能是正无穷或某个大数0-1 规划的上界固定为 1。建模时如果某个决策天然可以取多个整数值却硬套 0-1 变量就会把问题写错解出来的方案也不符合现实。3.2 误区二约束里出现变量相乘还以为是线性的易混点在于很多现实规则听起来像“如果选 A 就不能选 B”初学者会直接写成 xA 乘以 xB 等于 0。为什么混因为这句话的逻辑确实是“两者不能同时为 1”而乘法恰好能表达这个意思。但一旦写出乘积项模型就不再是线性的intlinprog 这类求解器无法直接处理。怎么区分看表达式里有没有两个决策变量相乘。正确的做法是用线性约束来表达互斥关系比如 xA xB ≤ 1这一条就等价于“最多选一个”。类似地“选了 A 才能选 B”可以写成 xB ≤ xA。把逻辑关系翻译成加减和不等式是 0-1 建模的一项基本功也是区分新手和老手的地方。3.3 误区三忘了给变量设上界解出大于 1 的数易混点在于有人只记得把变量标记为整数却忘了把上界设成 1。为什么混因为“整数变量”这个说法容易让人以为取整数就够了忽略了 0-1 规划还需要额外的边界限制。怎么区分看求解结果里有没有出现 2、3 这样的值。如果出现了说明上界没锁死。在 MATLAB 里ub 必须显式设为全 1 的向量否则求解器只保证整数不保证不超过 1。这个坑很隐蔽因为模型可能照样跑出结果只是结果不符合 0-1 的语义后面解释方案时就会露馅。3.4 误区四目标函数方向搞反最大最小傻傻分不清易混点在于intlinprog 默认求最小化而很多建模题写的是“收益最大”“利润最高”。为什么混因为题目描述和目标函数的方向不一定一致初学者容易直接把收益系数填进去就跑。怎么区分看求解结果的数值是不是明显不对。如果题目要最大化而你把收益系数原样放进最小化框架解出来的往往是“什么都不选”这种极端方案。正确做法是把目标系数取负求最小化再把结果的目标值取负回来或者用求解器支持的最大化参数。这个细节不影响模型结构但直接影响答案对不对属于典型的“一失足成千古恨”。3.5 误区五把“可行解”当成“最优解”易混点在于求解器返回了一个满足约束的 0-1 组合有人就以为大功告成。为什么混因为可行和最优是两回事尤其在约束较多时可行组合可能有很多个目标值差别很大。怎么区分看求解器输出的状态信息和目标值确认它报告的是最优而不是仅仅可行。建模报告里如果只写“得到一组方案”而不说明这组方案在目标上的表现说服力会大打折扣。养成检查求解状态、对比目标值的习惯能避免把“能跑通”误当成“做对了”。4. 拿到一个问题怎么判断该不该用0-1模型4.1 三个信号帮你快速判断第一个信号是决策的离散性。如果问题里的核心动作是“选哪些”“安排谁”“开哪台”而且每个动作只有做和不做两种状态那 0-1 模型几乎是首选。第二个信号是约束的线性可表达性。如果规则能用加减和不等式说清楚比如总量不超过上限、每项至少选一个、某些项互斥那就能落进线性框架。第三个信号是规模可控。决策变量在几十到几百这个量级现代求解器通常扛得住如果变量上千且约束复杂就要考虑求解时间必要时做简化或分阶段处理。反过来如果决策本身是连续的比如分配多少资金比例、设定多高的温度硬套 0-1 变量反而会把问题写拧。还有一种情况是目标或约束里天然带非线性关系比如收益随投入呈平方增长那也不属于这个模型的适用范围需要换用其他方法。判断的标准不是“哪个高级用哪个”而是“哪个贴合问题的真实结构”。4.2 一个具体例子预算有限时的项目选择设想某团队有一笔固定预算面前有若干候选项目每个项目需要一定投入、预期带来一定收益问怎么选才能使总收益最大。这个场景里每个项目对应一个 0-1 变量投入和收益都是线性相加预算上限是一条不等式约束。模型写出来非常干净目标系数是各项目收益取负后求最小约束矩阵是各项目投入右端是预算总额变量上下界锁在 0 和 1。用 MATLAB 求解后结果为 1 的项目就是建议上马的项目。这个例子的价值在于它把 0-1 建模的几个要素都串起来了离散决策、线性目标、线性约束、边界限制。实际建模题往往在此基础上加料比如项目之间有依赖关系选了 A 才能选 B、有互斥关系A 和 B 不能同时上、有数量限制最多选三个。这些都能用线性约束表达模型骨架不变只是约束矩阵多几行。理解了这个骨架遇到变体就不容易慌。4.3 什么时候别硬上边界与替代思路0-1 模型不是万能的。当决策变量数量很大、约束又错综复杂时求解时间可能长到不实用这时候要考虑问题是否真的需要精确最优还是可以接受启发式方法给出的近似解。另外如果问题里的不确定性很强比如收益本身是个随机变量那单纯的确定性 0-1 模型就不够用需要引入其他建模范式。还有一种常见情况是约束里存在明显的非线性逻辑硬转成线性会引入大量辅助变量模型变得臃肿难维护这时要权衡表达清晰度和求解效率。我的习惯是每次动手写模型前先把决策、目标、约束三样东西用大白话列一遍确认每个决策都能落成 0-1 变量、每条规则都能落成线性式再打开 MATLAB 填参数。有一次我跳过这一步直接把一个带互斥条件的排班问题塞进求解器结果因为约束写成了乘积形式反复报错折腾半天才回头补上线性表达。从那以后我每次建模都强制走一遍“白话清单”确认没有非线性项再动手。希望这些经验能帮你在遇到 0-1 型整数线性规划时少走一点弯路。这份资料把建模思路和 MATLAB 实现放在一起适合边看边对照自己的问题往里套。本文还有配套的精品资源点击获取