整数规划模型与求解方法：割平面法与分支定界法

"本文主要介绍了如何使用Matlab的`linprog`函数解决整数规划问题，特别是通过分支定界法来找到最优解。文件xxgh3.m是一个示例，展示了如何构建并解决这类问题的代码实例。" 在优化领域，整数规划是一种重要的数学模型，用于寻找满足一系列线性等式和不等式约束的决策变量的最佳整数值，以最大化或最小化一个目标函数。在工业、经济、工程等多个领域中，整数规划都有着广泛的应用。 在上述的几个整数规划模型中，我们看到了不同的实际问题，例如： 1. **投资问题**：公司需要决定在多个项目上投资，以最大化总收益，每个项目的投资金额和收益都是确定的。 2. **生产调度问题**：工厂要分配有限的机时给多个机床，以最小化加工成本，每个机床的工作时间和加工不同零件的成本是已知的。 3. **工厂选址问题**：考虑在多个地点建厂以最小化总运输和固定成本，每个地点的产能、固定成本和与需求点的距离是给定的。 4. **设备购置和安装问题**：工厂需要购买和安装设备以最大化经济效益，设备的单价、已有设备数量、可安装位置及经济效益是已知的。 解决这些整数规划问题，通常会采用线性规划的松弛问题作为起点，即放松对决策变量的整数约束，转化为标准的线性规划问题，然后使用`linprog`函数来寻找最优解。如果得到的最优解已经是整数，那么这就是整数规划的最优解。但当最优解不是整数时，就需要引入分支定界法。 **分支定界法**是一种迭代的搜索策略，它将非整数解的变量分为两个子集，分别强制它们取下界和上界的整数值，形成两个新的子问题。这两个子问题的解将继续被检查，直到找到一个整数解或所有可能的分支都被穷举。在Matlab中，`linprog`函数并不直接支持分支定界，但可以通过自定义代码实现这个过程。 在实施分支定界法时，需要关注以下关键步骤： 1. **松弛问题**：首先解决原始问题的线性规划松弛版本，找出一个初始解。 2. **分支**：如果初始解包含非整数变量，将其中一个变量分支成两个子问题，即设定其等于下界或上界。 3. **定界**：对于每个子问题，计算其最优解，并比较目标函数值。保留具有更好目标值的分支继续进行。 4. **回溯**：当所有分支的解都成为整数或达到预设的停止条件（如最大迭代次数、精度限制等）时，停止分支并返回最优解。 在Matlab的`linprog`函数中，可以设置变量的下界和上界来模拟整数约束，`vlb`表示变量的下界，`vub`表示变量的上界。在xxgh3.m的代码中，可以看到如何设置这些参数来调用`linprog`。 总结来说，整数规划是寻找整数解的优化问题，分支定界法是解决此类问题的有效算法，通过逐步分支和定界过程，可以找到全局最优的整数解。在实际应用中，结合Matlab的`linprog`函数，可以方便地解决许多实际场景中的优化问题。