§1 整数规划的基本特点 §2 分枝定界法 §3 割平面法 §4 分配问题及其解法 §5 整数规划的应用举例 第5章 整数规划 §1 整数规划的基本特点 §2 分枝定界法 §3 割平面法 §4 分配问题及其解法 §5 整数规划的应用举例
§3 割平面法 这是求解整数规划问题最早提出的一种方法，1958年由Gomory提出。 他的基本思想是在整数规划问题的松弛问题中依次引进线性约束条件，是可行域逐步缩小。但每次切割只割去问题的部分非整数解，直到使问题的目标函数值达到最优的整数点成为缩小后可行域的一个顶点，这样即可用线性规划问题的方法找出这个最优解。 具体步骤如下：
第一步：把问题中所有约束条件的系数均化为整数，若不考虑变量的整数约束，可写出一般的线性规划问题G0：
用单纯形法求得上述问题的最终单纯形表如下： 迭代次数 基变量 CB x1 x2 x3 x4 b 比值 bi/aij 3 2 0 0 x2 x1 2 3 0 1 1/2 -1/2 1 0 -1/4 3/4 5/2 13/4 Cj-Zj 0 0 -1/4 -5/4
第三步：将Gomory约束加到G0中得到新的线性规划问题G1如下： 第四步：重复第一至第三步直到找出最优的整数解为止。
求解G1可以采用对偶单纯形法： 迭代次数 基变量 CB x1 x2 x3 x4 x5 b 比值 bi/aij 3 2 0 0 0 x2 x1 3 2 0 0 0 x2 x1 x5 2 3 0 1 1/2 -1/2 0 1 0 -1/4 3/4 0 0 0 -1/2 -1/2 1 2（1/2） 3（1/4） -1/2 Cj-Zj 0 0 -1/4 -5/4 0 x2 x1 x3 2 3 0 1 0 -1 1/2 1 0 0 1 -1/2 0 0 1 1 -2 3（1/2） 1 Cj-Zj 0 0 0 -1 -1/2
将松弛变量加到G1中得到LP问题G2: 采用对偶单纯形法求解:
迭代次数 基变量 CB x1 x2 x3 x4 x5 x6 b 3 2 0 0 0 0 x2 x1 x3 x6 2 3 0 1 0 -1 1/2 0 1 0 0 1 -1/4 0 0 0 1 1 -1 0 0 0 0 0 -1/2 1 2（1/2） 3（1/2） 1 -1/2 Cj-Zj 0 0 -1/4 -5/4 0 x2 x1 x3 x5 2 3 0 1 0 -1 0 2 1 0 0 1 0 -1 0 0 1 1 0 -4 0 0 0 0 1 -2 1 4 Cj-Zj 0 0 0 -1 0 -1
由于从表中已经找到变量的整数解x1=4,x2=1。求解过程到此结束。
练习：