第三章 整数规划
nxr??yj?m?1nrjxj?br （3.1）
将yrj和br写成整数部分和小数部分 或 由于
xr??(Ij?m?1nrj?Frj)xj?Ir?Fr
nxr??Ij?m?1rjxj?Ir?Fr?n?Fj?m?1rjxj （3.2）
Fr?1，以及
?Fj?m?1rjxj?0
因此对于（3.2）中的任何（整数或非整数的）可行解，有
nnrjxjxr??Ij?m?1?Ir?Fr??Fj?m?1rjxj?1
n （3.3）
rjxj对于任何可行的整数解，xr和xj都是整数，因此xr?n?Ij?m?1?Ir是整数，即
xr??Ij?m?1nrjxj?Ir=…，-2，-1，0
因此对于整数可行解，约束（3.2.2）可以写成更严格的不等式
nrjxjxr??Ij?m?1?Ir?Fr??Fj?m?1rjxj?0 （3.4）
将线性规划（非整数）的最优解
（x1…xr…xm，xm+1…xj…xn）=（b1…br，…bm，0…0…0）
代入（3.4）的左边，得到
nFr??Fj?m?1rjxj?Fr?0
线性规划（非整数）的最优解不满足（3.4）。因此，约束（3.4）具有以下性质：
1、 线性规划可行域中的任何整数解都满足这个约束； 2、 线性规划的（非整数）最优解不满足这个约束。
这样，在原线性规划的约束条件基础上增加约束（3.4），新的可行域将切除原线性规划非整数的最优解而保留所有整数可行解。 例3.4 用割平面法求解以下整数规划
min
z=
3x1 +4x2
11
第三章 整数规划
s.t.
3x1 x1
+x2 ≥4 x2 ≥0
x1 +2x2 ≥4
x1，x2为整数
先求相应的线性规划问题，得到最优单纯形表
z x1 x2
z 1 0 0 x1 0 1 0 x2 0 0 1 x3 -2/5 -2/5 1/5 x4 -9/5 1/5 -3/5 RHS 44/5 4/5 8/5 选择一个非整数的基变量，例如x2=8/5，构造约束条件（3.4），其中
b2=8/5=1+3/5，I2=1，F2=3/5 y23=1/5=0+1/5，I23=0，F23=1/5 y24=-3/5=-1+2/5，I24=-1，F24=2/5
n附加的约束条件Fr??Fj?m?1rjxj?0为
3/5-（1/3x3+2/5x4）≤0
即
1/5x3+2/5x4≥3/5
将这个约束加到线性规划的最优单纯形表中，并增加一个松弛变量x5，得到
z x1 x2 x5
z 1 0 0 0 x1 0 1 0 0 x2 0 0 1 0 x3 -2/5 -2/5 1/5 [-1/5] x4 -9/5 1/5 -3/5 -2/5 x5 0 0 0 1 RHS 44/5 4/5 8/5 -3/5 用对偶单纯形法，x5离基，x3进基
z x1 x2 x3
z 1 0 0 0 x1 0 1 0 0 x2 0 0 1 0 x3 0 0 0 1 x4 -1 1 -1 2 x5 -2 -2 1 -5 RHS 10 2 1 3
12 第三章 整数规划
已获得整数的最优解。
4 3 2 1 0 1 2 3 4 5 切割约束 整数规划 最优解 线性规划 最优解 为了得到切割约束1/5x3+2/5x4≥3/5在（x1, x2）平面中的表达式，将其中的松弛变量x3x4用 x1x2表示
x3=3x1+x2-4，x4=x1+x2-4
代入切割约束，得到
x1+x2≥3
这个切割的图解如图3.2。
图 3.1
13 第三章 整数规划
§3.3 分支定界法
分枝定界法（Branch and Bound，简称B&B）的基本思想如下：
首先不考虑变量的整数约束，求解相应的线性规划问题，得到线性规划的最优解。设线性规划问题
min s.t.
z= CTX
x2
E D C B Sub2 AX = b
X ≥0
的可行域如图3.3中OABCDE（示意图），并 设最优解位于C。如果这个最优解中所有的变 量都是整数，则已经得到整数规划的最优解。 如果其中某一个变量xr不是整数，则在可行 域中除去一块包含这个最优解但不包含任何整数解的区域Ir Sub1 O x1 Ir xr Ir+1 A 图 3.2 的整数部分），线性规划的可行域被划分成不相交的两部分，分别以这两部分区域作为可行域，用原来的目标函数，构造两个子问题Sub1和Sub2： Sub1 s.t. AX xr X =b ≤Ir ≥0 Sub2 min s.t. z= CTX AX xr X =b ≥Ir ≥0 min z= CTX 由于这两个子问题的可行域都是原线性规划问题可行域的子集，这两个子问题的最优解的目标函数值都不会比原线性规划问题的最优解的目标函数值更小。如果这两个问题的最优解仍不是整数解，则继续选择一个非整数的变量，继续将这个子问题分解为两个更下一级的子问题。这个过程称为“分枝（Branch）”。在分枝过程中，每一次分枝得到的子问题最优解的目标函数值，都大于或等于分枝前问题的最优解的目标函数值。 如果某一个子问题的最优解是整数解，就获得了一个整数可行解，这个子问题的目标函数值要记录下来，作为整数规划最优目标函数值的上界。如果某一个子问 14 第三章 整数规划 题的解还不是整数解，但这个非整数解的目标函数值已经超过和这个上界，那么这个子问题就不必再进行分枝，因为继续分枝即使得到整数解，这个整数解的目标函数值必定要大于（或等于）分枝以前问题的目标函数值，因而也大于（或等于）已经获得的整数规划的目标函数值，因此不可能是最优的整数解。如果在分枝过程中得到新的整数解且该整数解的目标函数值小于已记录的上界，则用较小的整数解的目标函数值代替原来的上界。上界的值越小，就可以避免更多不必要的分枝。这个确定整数解目标函数值上界并不断更新上界，并且不断“剪除”目标函数值超过上界的分枝的过程，称为定界（Bound）。 当最低一层子问题出现以下三种情况之一时，分枝定界算法终止： 1、 子问题无可行解； 2、 子问题已获得整数解； 3、 子问题的目标函数值超过上界。 例3.5 用分枝定界法求解以下整数规划 min z= -2x1 s.t. 1217-3x2 +7x2 +9x2 x2 ≤35 ≤36 ≥0 取 x2 4 Sub2 3 2 1 Sub1 x1 0 1 2 3 4 5 6 7 5x1 4x1 x1 x1，x2为整数 617817先求得相应的线性规划的最优解，为 x1?3x2?2617,x2?2,z??14分割可行域，得到以下两个子问题： -3x2 +7x2 +9x2 x2 x2 ≤35 ≤36 ≤2 ≥0 Sub-2 min s.t. z= -2x1 5x1 4x1 x1 -3x2 +7x2 +9x2 x2 x2 ≤35 ≤36 ≥3 ≥0 Sub-1 min s.t. z= -2x1 5x1 4x1 x1 Sub1的最优解为 Sub2的最优解为 15