二、解的特点从数学模型上看整数规划似乎是线性规划的一种特殊形式，求解只需在线性规划的基础上，通过舍入取整，寻求满足整数要求的解即可。但实际上两者却有很大的不同，通过舍入得到的解（整数）也不一定就是最优解，有时甚至不能保证所得到的解是整数可行解。■整数规划是数学规划中一个较弱的分支，自前只能解中等规模的线性整数规划问题，而非线性整数规划问题，还没有好的办法
二、解的特点 从数学模型上看整数规划似乎是线性规 划的一种特殊形式，求解只需在线性规划的基 础上，通过舍入取整，寻求满足整数要求的解 即可。但实际上两者却有很大的不同，通过舍 入得到的解（整数）也不一定就是最优解，有 时甚至不能保证所得到的解是整数可行解。 整数规划是数学规划中一个较弱的分支， 整数规划是数学规划中一个较弱的分支， 目前只能解中等规模的线性整数规划问 目前只能解中等规模的线性整数规划问 题，而非线性整数规划问题，还没有好的 题，而非线性整数规划问题，还没有好的 办法
例：设整数规划问题如下max Z = Xi + x214 x +9x2 ≤ 51- 6x, +3x2 ≤1Xi,X2 ≥ 0首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）。max Z = xi + x2[14 x, +9x2 ≤51- 6x +3x2 ≤1Xi,x, ≥ 0
例：设整数规划问题如下 ⎪ ⎩ ⎪ ⎨ ⎧ ≥ − + ≤ + ≤ = + , 0且为整数 6 3 1 14 9 51 max 1 2 1 2 1 2 1 2 x x x x x x Z x x 首先不考虑整数约束，得到线性规划问题（一般称 为松弛问题）。 ⎪ ⎩ ⎪ ⎨ ⎧ ≥ − + ≤ + ≤ = + , 0 6 3 1 14 9 51 max 1 2 1 2 1 2 1 2 x x x x x x Z x x
maxZ=x,+x214x+9x2≤51- 6xj +3x2≤1用图解法求出最优解X（2）X,x, ≥0x, = 3/2, x, = 10/3(3/2,10/3)且有Z=29/63现求整数解（最优解）：如用“舍入取整法”可得到4个点即(1，3)(23)(1, 4)(2, 4)。 显然,它们都不可能是整数规划的最优解。X按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集，如图所示
用图 解法求出最优解 x 1 ＝3/2, x2 = 10/3 且有Z = 29/6 x 1 x2 ⑴ ⑵ 3 3 (3/2,10/3) 现求整数解（最优解）： 如用 “舍入取整法 ”可得到 4个点即(1，3) (2， 3)(1，4)(2，4)。显然， 它们都不可能是整数规划 的最优解。 按整数规划约束条件，其可行解肯定在线性规划问题 的可行域内且为整数点。故整数规划问题的可行解集 是一个有限集，如图所示。 ⎪ ⎩ ⎪ ⎨ ⎧ ≥ − + ≤ + ≤ = + , 0 6 3 1 14 9 51 max 1 2 1 2 1 2 1 2 x x x x x x Z x x
因此，可将集合内的整数点一一找出，其最大目标函数的值为最优解，此法为完全枚举法如上例：其中（2，2）（3，1）点为最大值， Z=4。目前，常用的求解整数规划的方法有：分枝定界法和割平面法：对于特别的0－1规划问题采用隐枚举法和匈牙利法
因此，可将集合内的整数点一一找出，其最 大目标函数的值为最优解，此法为完全枚举法。 如上例：其中（ 2 ， 2）（ 3 ， 1）点为最 大值，Z=4 。 目前，常用的求解整数规划的方法有： 分枝定界法和割平面法； 对于特别的0－1规划问题采用隐枚举法和匈 牙利法
第二节分枝定界法算法思想隐枚举法分枝求解松驰问题舍弃变界最优值比界坏分枝最优解为整数最优值比界好最优解为非整数最优值比界好
算法思想 隐枚举法 分枝 求解松驰问题 舍弃 变界 分枝 最优值比界坏 最优解为整数 最优值比界好 最优解为非整数 最优值比界好 第二节 分枝定界法