分支限界法求解整数规划

"UIUC 数学482线性规划课程讲义，第三十三讲：分支与界法，由Mikhail Lavrov讲解，日期：2020年4月27日，伊利诺伊大学香槟分校" 在解决整数规划问题时，分支与界法（Branch-and-Bound Method）是一种广泛应用的有效算法。整数规划是线性规划的一个扩展，它要求决策变量取整数值，而不仅仅是实数。这个方法主要用于寻找整数解，因为在实际问题中，许多变量必须是整数，如生产数量、人员分配等。 考虑以下整数规划问题： 最大化： 4x + 5y 受以下约束条件限制： x + 4y ≤ 10 3x - 4y ≤ 6 x, y ≥ 0 在没有整数约束的情况下，我们首先解决其线性规划松弛问题，即允许x和y取实数。这是找到整数解的第一步，因为线性规划松弛问题提供了最优解的下界。对于上述问题，通过两次单纯形法迭代，我们可以找到线性规划松弛问题的最优解 (x, y) = (4, 1.5)，目标函数值为23.5。然而，这个解不符合整数规划的要求，因为y不是整数。 分支与界法的核心思想是将问题分解为更小的子问题，并通过不断分支和剪枝来逐步逼近整数解。在每个分支阶段，我们将一个变量设为整数，然后分成两个子问题，一个限制该变量为下界整数，另一个限制为上界整数。同时，我们维护一个边界（bound），记录当前已知的最佳整数解的目标函数值。当一个子问题的最优解不能超过这个边界时，我们就可以剪枝，不再探索该子问题，从而节省计算资源。 在实际应用分支与界法时，通常还会结合其他策略来提高效率，例如使用启发式方法来优先选择分支变量，以及在剪枝过程中利用下界函数来提前排除不可能成为全局最优解的区域。这些策略可以显著减少需要考虑的子问题数量，加速求解过程。 分支与界法是解决整数规划问题的重要工具，通过不断分支、计算和剪枝，逐步逼近并找到问题的全局最优整数解。这种方法在运筹学、优化和计算机科学等领域有着广泛的应用。