《数学建模实战：基于MATLAB的整数规划指派问题建模与求解全解析》

1. 整数规划与指派问题入门

第一次接触整数规划时，我也被那些数学符号搞得头晕。直到老师用了个生动的例子：假设你开了一家快递公司，有5个包裹要派送，手上有8辆快递车，每辆车派到不同地点的运费都不一样。怎么分配车辆才能最省钱？这就是典型的指派问题。

整数规划的特殊之处在于，它的解必须是整数。就像你不能派半辆车去送货，现实中很多决策都要求整数解。常见的整数规划包括：

• 纯整数规划：所有变量都必须是整数
• 混合整数规划：部分变量是整数
• 0-1整数规划：变量只能取0或1（比如指派问题中的"派"或"不派"）

在MATLAB中，我们主要使用intlinprog函数求解这类问题。它就像个智能调度员，能帮我们找到最优的整数解。我刚开始用的时候，经常把约束条件写反，结果要么无解，要么得到离谱的结果。后来发现，理解清楚问题的数学表达才是关键。

2. 问题建模：从现实到数学模型

让我们用开头提到的车辆调度问题来练手。假设有8辆车要指派到5个工地，费用表如下（单位：百元）：

2.1 定义决策变量

这里需要引入0-1变量：

x(i,j) = 1 # 指派第j辆车到第i个工地 x(i,j) = 0 # 不指派

因为有5个工地和8辆车，所以总共需要5×8=40个决策变量。

2.2 建立目标函数

我们的目标是最小化总费用：

Min Z = 30x(1,1) + 25x(1,2) + ... + 18x(5,8)

用矩阵表示就是：

c = [30; 25; 18; ... ; 18] % 40×1的列向量

2.3 设置约束条件

这里有两类约束：

1. 每辆车最多去一个工地（不等式约束）：

   x(1,j) + x(2,j) + ... + x(5,j) ≤ 1 (j=1,...,8)

   对应MATLAB中的A矩阵是8×40的稀疏矩阵

2. 每个工地必须有一辆车（等式约束）：

   x(i,1) + x(i,2) + ... + x(i,8) = 1 (i=1,...,5)

   对应Aeq矩阵是5×40的稀疏矩阵

我第一次建模时就漏掉了第二类约束，结果有些工地没人去，被老师当场指出。记住：约束条件要完整反映实际问题！

3. MATLAB求解实战

3.1 准备输入数据

首先把费用表输入MATLAB：

data = [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 构建约束矩阵

构建不等式约束A（8×40）：

A = zeros(8,40); for j = 1:8 A(j, (j-1)*5+1 : j*5) = 1; % 每辆车对应的5个工地 end b = ones(8,1); % 每辆车最多去1个工地

构建等式约束Aeq（5×40）：

Aeq = 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); % 上限为1

3.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 ← 车6

fval会显示最小总费用。在这个例子中，最优解的总费用是18+18+19+18+14=87（百元）。

4.2 常见错误排查

1. 无可行解：检查约束是否矛盾。比如如果工地数>车辆数，肯定无解。

2. 解不合理：可能是约束矩阵构建错误。我曾经把A和Aeq搞反了，结果每辆车要去多个工地。

3. 求解时间过长：对于大规模问题，可以尝试：

   options = optimoptions('intlinprog','Display','iter'); [x,fval] = intlinprog(c,intcon,A,b,Aeq,Beq,lb,ub,options);

4. 内存不足：变量太多时会遇到。这时可以考虑：

   • 使用稀疏矩阵存储约束
   • 分解问题为多个子问题

4.3 灵敏度分析

想了解解的稳定性，可以检查对偶变量：

[x,fval,exitflag,output] = intlinprog(...);

output结构体包含求解过程的详细信息，比如迭代次数、求解时间等。

5. 扩展应用与优化技巧

5.1 处理更复杂的约束

实际问题中可能有额外限制，比如：

• 某些车不能去某些工地：直接设置对应的x(i,j)=0
• 某些工地需要多辆车：修改对应等式约束的右侧值
• 车辆有载重限制：添加新的不等式约束

5.2 大规模问题优化

当变量超过几千个时：

1. 使用稀疏矩阵：

   A = sparse(8,40);

2. 设置初始解：

   x0 = ...; % 启发式初始解 [x,fval] = intlinprog(...,x0);

3. 调整求解器参数：

   options = optimoptions('intlinprog','Heuristics','advanced',...);

5.3 其他应用场景

这个框架可以解决各类指派问题：

• 课程安排：教师→课程
• 任务分配：员工→项目
• 生产调度：机器→订单

我去年就用类似方法帮学校图书馆优化了自习室分配，节省了30%的管理时间。关键是把实际问题准确转化为数学模型。

6. 对比其他求解方法

虽然MATLAB很方便，但有时也需要考虑其他工具：

对于初学者，我建议先用MATLAB掌握建模思路，等遇到性能瓶颈再考虑其他方案。