MATLAB优化工具箱解整数规划：分支定界法详解

"本文主要介绍了如何使用MATLAB优化工具箱解决线性规划问题，并特别讨论了整数规划的分支定界法。通过实例展示了整数规划在投资决策、生产计划、工厂选址和设备购置安装等问题中的应用。" 线性规划是一种优化技术，用于寻找线性目标函数（最大化或最小化）在一组线性不等式约束下的最优解。MATLAB的`linprog`函数是解决这类问题的工具，它可以处理包含不等式和等式约束的线性规划问题。基本调用格式为`x = linprog(c, A, b)`，其中`c`是目标函数的系数向量，`A`和`b`分别对应不等式约束的系数矩阵和右侧常数向量。如果存在等式约束，可以使用`Aeq`和`beq`参数。 整数规划是线性规划的扩展，它在变量上施加了整数值的限制，使得问题更具有实际意义。例如，投资决策中，资金分配通常需要整数单位；生产计划中，机器工时和产出数量也是整数；工厂选址和设备购置安装涉及的建厂数量和设备配置都是整数决策变量。 分支定界法是解决整数规划问题的一种常用算法。该方法通过逐步将非整数解的可行域分割（分支）并逐步逼近整数最优解来求解。首先，求解问题的松弛版本（即允许非整数解的线性规划），如果得到的是整数解，那么就是整数规划的最优解；如果不是，就通过添加割平面（新的约束）来排除非整数解的部分，直到找到满足整数约束的最优解或证明不存在满足条件的解。 割平面法的核心在于构建能排除非整数解的约束，这通常涉及将非整数变量的范围划分为两个子区间，然后为每个子区间创建一个约束，迫使原问题的解落入其中一个子区间。这样，每次分支都会减少非整数解的存在空间，直到所有剩余解都变为整数。 在实际应用中，如工厂选址问题，需要考虑工厂产能、固定成本、运输费用等，通过整数规划模型找到最小化总费用的建厂和运输策略。设备购置和安装问题则涉及设备成本、现有设备数量、经济效益以及安装位置限制，同样可以通过整数规划寻找最大经济效益的解决方案。 总结来说，MATLAB优化工具箱的`linprog`函数和分支定界法是解决包括整数约束在内的线性规划问题的强大工具，广泛应用于各种实际工程和管理决策问题中。通过理解这些概念和方法，可以有效地解决资源分配、生产计划、设施布局等优化问题。