整数规划之割平面法

Question

如题所述

Answer 1

在探讨了繁琐的分支定界法后，我们转向另一种高效计算整数问题的利器——割平面法。这种方法以其相对简便的特性，成为解决此类问题的常用策略，尤其在实际应用中，它的计算量相较于分支定界法大大减少。

让我们通过实例来深入了解割平面法的实战应用，以图(I)为例。与分支定界法不同，割平面法的第一步是暂时忽略整数限制，将所有约束条件调整至整数边界，并转化为标准型，以便于后续的单纯形法求解。

利用单纯形法，我们得到了如下的求解结果:

尽管当前的解并非整数，这是割平面法的关键转折点。我们需要将x1和x2转换为整数加上最小正分数的形式，例如：x1 = 4 + 1/2，x2 = 3 + 1/2。在选择下一步操作时，我们不仅关注小数部分，还需比较每一行剩余非整数部分之和。在本例中，x1的和值为24/22，而x2的和值为8/22，因此我们选择x2行进行下一步操作。

这一步骤涉及到添加一个新的约束条件，即1/2 <= 7/22 * x3 + 8/22 * x4。引入松弛变量后，我们得到：-7/22 * x3 - 1/22 * x4 + y1 = -1/2。将这个表达式加入单纯形表中，我们继续进行对偶单纯形法的求解。

在迭代过程中，我们不断优化，直到发现x1和x3的值依然非整数。根据上述原则，我们选择x1进行下一步操作，并将其代入单纯形表，最终通过换基迭代得到了整数解。

令人欣喜的是，这个解证实是原问题的最优解。由于题目设定为求最大值问题，实际最优值为55的相反数。通过割平面法，我们不仅找到了解决方案，还深入理解了这种方法的高效和直观性。