任务二　整数规划的分支定界法

严格地说，整数规划是非线性问题。因为整数规划的可行解集是由一些离散的非负整数点组成的，而不是一个连续不断的凸集。目前，求解整数规划尚无统一有效的办法。分支定界法是求解整数规划的常用方法，尤其是求解相对比较复杂的整数规划时，应用分支定界法更为有效。

分支定界法是在20世纪60年代初由Land Doig和Dakin等人提出的，由于该方法灵活，便于计算机求解，所以它是现在求解整数规划的重要方法。它的基本思想是，先不考虑原整数规划问题中的整数性约束，去解其相应的松弛问题。对于最大化问题，松弛问题的最优值就是原问题最优值的上界。如果松弛问题的最优解满足整数性约束，则它就是原问题的最优解。否则，就在不满足整数约束的变量中，任意选择xi＝bi，设［bi］是不超过bi的最大整数，将新的约束条件xi≤［bi］和xi≥［bi］＋1分别加入原问题中，把原问题分支为两个子问题，并分别求解子问题的松弛问题。若子问题的松弛问题的最优解满足整数约束，则不再分支，其相应的目标函数值就是原问题目标函数值的一个下界。对不满足整数约束的子问题，如果需要，继续按上述方法进行新的分支，并分别求解其对应的松弛问题，直至求得原问题的最优解为止。

因此，我们总结分支定界法的求解步骤如下。

（1）先不考虑整数约束，求解整数规划的松弛问题，可能得到以下情况之一：

①若松弛问题没有可行解，则整数规划也没有可行解，停止计算；

②若松弛问题有最优解，并符合整数规划的整数条件，则线性规划的最优解即为整数规划的最优解，停止计算；

③若松弛问题有最优解，但不符合整数规划的整数条件，转入下一步。

（2）分支：从不满足整数条件的基变量中任选一个xi进行分支，它必须满足xi≤［xi］或xi≥［xi］＋1中的一个，把这两个约束条件加进原问题中，形成两个互不相容的子问题。

（3）定界：把满足整数条件各分支的最优目标函数值作为上（下）界，用它来判断分支是保留还是剪支。

（4）剪支：把那些子问题的最优值与界值比较，凡不优或不能更优的分支全剪掉，直到每个分支都查清为止。

例3-2-1　用分支定界法求解。

（1）用单纯形法可解得相应的松弛问题的最优解（1.2，2.1），z＝11.1，很明显，这个最优解不符合整数条件，我们需要继续分支，并把这个最优值定为各分支的上界。

（2）选择x1＝1.2来进行分支，加入条件x1≤1和x1≥2，得到两个子问题。

（3）用单纯形法求得P1的最优解（1，2.25），z＝10.75，P2的最优解（2，0.5），z＝9.5。没有得到整数解，继续分支。对P1进行分支，加入条件x2≤2和x2≥3，生出两个子问题。

（4）用单纯形法可解得相应的P3的最优解（1，2），z＝10，P4的最优解（0，3），z＝9。P3和P4的解都是整数，比较它们对应的目标函数值，显然P3的目标函数值大于P4，剪去P4一支，把P3中z＝10作为目标函数的下界。

（5）我们回头看P2，在这一支中，可以继续分支以求得整数解。但这一支现在的最优值z＝9.5，也就是说，不管再怎么分，在这一支中求得的目标函数值不可能超过9.5，因此，也不可能超过P3中求得的z＝10，因此将此支剪去。至此，我们得到了该整数规划的最优解x1＝1，x2＝2，z＝10。

用树形图（见图3-2-1）表示求解这个问题的全过程。