MATLAB实现分支定界法解决混合整数线性规划

分支定界法是一种用于求解混合整数线性规划（Mixed Integer Linear Programming, MIP）问题的有效算法，它在MATLAB环境中得到了应用。在提供的代码片段中，重点展示了如何通过`linprogdis`函数实现分支定界法来解决此类问题。以下是对关键知识点的详细说明： 1. **函数定义**: `linprogdis`函数是MATLAB中的核心函数，它接受多个参数，包括整数变量指示向量`ifint`，目标函数系数向量`f`，线性不等式系数矩阵`A`，上下界向量`b`，等式约束系数矩阵`Aeq`和等式界限向量`beq`，以及变量下界和上界`lb`和`ub`。初始猜测解`x0`和选项设置`options`也是必要的输入。 2. **数据预处理**: 函数首先检查`b`是否为一列向量，如果不是，将其转置以适应线性规划函数的输入格式。这一步确保了输入数据符合标准形式。 3. **调用基础优化**: 使用MATLAB内置的`linprog`函数求解基础线性规划问题。如果`linprog`返回失败（`exitflag<=0`），则整个分支定界过程也会终止。 4. **识别整数变量**: `find(ifint==1)`找出所有带有整数约束的决策变量的索引。`tmp`变量存储这些变量的当前值。 5. **处理整数约束**: 如果没有整数约束（`isempty(tmp)`），说明这是一个纯线性规划问题，可以直接返回结果。如果存在整数约束，`checkint`函数用于检查每个决策变量是否为整数，`v2`存储非整数变量的索引。 6. **分支过程**: 当发现某个决策变量还未达到整数解时（`isempty(v2)`），分支定界法会进行递归操作。具体步骤可能涉及将问题分解成两个子问题，分别针对整数变量和非整数变量，然后继续在子问题上执行`linprogdis`函数，直到找到满足整数约束的最优解或子问题不可行为止。 7. **函数辅助工具**: 代码中提到的`checkint`和`ifrowinmat`是辅助函数，`checkint`用于判断决策变量是否为整数，`ifrowinmat`用于检查一个向量是否与矩阵中的某一行相等，这两个函数简化了分支定界算法的实现。 8. **时间戳和版本信息**: 提供的代码还包含了函数的创建和更新日期，这有助于跟踪功能的演变和调试。 总结起来，这段MATLAB代码实现了分支定界法来求解混合整数线性规划问题，通过一系列条件判断和递归调用，逐步逼近最优解，对于理解和实践MIP求解策略具有重要意义。