1. 整数规划与指派问题入门第一次接触整数规划时我也被那些数学符号搞得头晕。直到老师用了个生动的例子假设你开了一家快递公司有5个包裹要派送手上有8辆快递车每辆车派到不同地点的运费都不一样。怎么分配车辆才能最省钱这就是典型的指派问题。整数规划的特殊之处在于它的解必须是整数。就像你不能派半辆车去送货现实中很多决策都要求整数解。常见的整数规划包括纯整数规划所有变量都必须是整数混合整数规划部分变量是整数0-1整数规划变量只能取0或1比如指派问题中的派或不派在MATLAB中我们主要使用intlinprog函数求解这类问题。它就像个智能调度员能帮我们找到最优的整数解。我刚开始用的时候经常把约束条件写反结果要么无解要么得到离谱的结果。后来发现理解清楚问题的数学表达才是关键。2. 问题建模从现实到数学模型让我们用开头提到的车辆调度问题来练手。假设有8辆车要指派到5个工地费用表如下单位百元地点\车辆12345678工地13025183227192226工地22931191821203019工地32829301919222326工地42930192425191821工地521201817161416182.1 定义决策变量这里需要引入0-1变量x(i,j) 1 # 指派第j辆车到第i个工地 x(i,j) 0 # 不指派因为有5个工地和8辆车所以总共需要5×840个决策变量。2.2 建立目标函数我们的目标是最小化总费用Min Z 30x(1,1) 25x(1,2) ... 18x(5,8)用矩阵表示就是c [30; 25; 18; ... ; 18] % 40×1的列向量2.3 设置约束条件这里有两类约束每辆车最多去一个工地不等式约束x(1,j) x(2,j) ... x(5,j) ≤ 1 (j1,...,8)对应MATLAB中的A矩阵是8×40的稀疏矩阵每个工地必须有一辆车等式约束x(i,1) x(i,2) ... x(i,8) 1 (i1,...,5)对应Aeq矩阵是5×40的稀疏矩阵我第一次建模时就漏掉了第二类约束结果有些工地没人去被老师当场指出。记住约束条件要完整反映实际问题3. MATLAB求解实战3.1 准备输入数据首先把费用表输入MATLABdata [30 25 18 32 27 19 22 26; 29 31 19 18 21 20 30 19; 28 29 30 19 19 22 23 26; 29 30 19 24 25 19 18 21; 21 20 18 17 16 14 16 18]; c data(:); % 将矩阵转为列向量3.2 构建约束矩阵构建不等式约束A8×40A zeros(8,40); for j 1:8 A(j, (j-1)*51 : j*5) 1; % 每辆车对应的5个工地 end b ones(8,1); % 每辆车最多去1个工地构建等式约束Aeq5×40Aeq zeros(5,40); for i 1:5 Aeq(i, i:5:40) 1; % 每个工地对应的8辆车 end Beq ones(5,1); % 每个工地必须有1辆车3.3 设置求解参数intcon 1:40; % 所有变量都是整数 lb zeros(40,1); % 下限为0 ub ones(40,1); % 上限为13.4 调用intlinprog求解[x, fval] intlinprog(c, intcon, A, b, Aeq, Beq, lb, ub); x reshape(x, [5,8]) % 将结果转回5×8矩阵运行后会得到一个5×8的矩阵其中1表示指派关系。比如第一行第三列为1表示第3辆车被派往第1个工地。4. 结果分析与常见问题4.1 解读输出结果典型的解矩阵如下0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0这表示工地1 ← 车3工地2 ← 车4工地3 ← 车5工地4 ← 车7工地5 ← 车6fval会显示最小总费用。在这个例子中最优解的总费用是181819181487百元。4.2 常见错误排查无可行解检查约束是否矛盾。比如如果工地数车辆数肯定无解。解不合理可能是约束矩阵构建错误。我曾经把A和Aeq搞反了结果每辆车要去多个工地。求解时间过长对于大规模问题可以尝试options optimoptions(intlinprog,Display,iter); [x,fval] intlinprog(c,intcon,A,b,Aeq,Beq,lb,ub,options);内存不足变量太多时会遇到。这时可以考虑使用稀疏矩阵存储约束分解问题为多个子问题4.3 灵敏度分析想了解解的稳定性可以检查对偶变量[x,fval,exitflag,output] intlinprog(...);output结构体包含求解过程的详细信息比如迭代次数、求解时间等。5. 扩展应用与优化技巧5.1 处理更复杂的约束实际问题中可能有额外限制比如某些车不能去某些工地直接设置对应的x(i,j)0某些工地需要多辆车修改对应等式约束的右侧值车辆有载重限制添加新的不等式约束5.2 大规模问题优化当变量超过几千个时使用稀疏矩阵A sparse(8,40);设置初始解x0 ...; % 启发式初始解 [x,fval] intlinprog(...,x0);调整求解器参数options optimoptions(intlinprog,Heuristics,advanced,...);5.3 其他应用场景这个框架可以解决各类指派问题课程安排教师→课程任务分配员工→项目生产调度机器→订单我去年就用类似方法帮学校图书馆优化了自习室分配节省了30%的管理时间。关键是把实际问题准确转化为数学模型。6. 对比其他求解方法虽然MATLAB很方便但有时也需要考虑其他工具方法优点缺点MATLAB集成环境调试方便商业软件大规模问题慢PythonPulp开源社区支持好需要编程基础专用求解器处理超大规模问题能力强学习曲线陡峭对于初学者我建议先用MATLAB掌握建模思路等遇到性能瓶颈再考虑其他方案。