b0 z0
xB0 a0jxj b0
jS
xBi aijxj bi, i 1, ,m jS
i0,1, ,m
若对所有的 i0,1, ,m, bi均为整数
STOP ! x 0已经是( IP )的最优解
XJTU
第三章 整数线性规划
OR
否则, 至少存在某一个l:0lm,使得bl不是整数 .
OR
Proof: 由上述推导过程, 割平面(△)是原( IP )的整数约束推出来
的, 所以它不会切割掉任何整数可行解 .
可选松弛变量S作为对应所增加新约束条件的基变量, 它
与原来的基变量 xB1, , xB一m 起必可构成新松弛问题的基变量. 当 b l 不是整数时, f l 0 , 新松弛问题的基本解中有
的最优解. 否转 S 2 .
S 2 : 任选 x 0 的一个非整数值分量 bl (0l m), 按上述方式
构造割平面方程 fljxj sfl .
jS
S 3 : 将此割平面方程加到松弛问题( P 0 )得新的松弛问题.
用对偶单纯形法求解这个新的松弛问题. 若其最优解为
整数向量, 则STOP, 它亦为( IP )的最优解.
jS
jS
(△)
对应于生成行l 的 Gomory割平面条件
系数为分数→ 分数割平面
Th. : 将割平面(△)加到松弛问题(P 0 )中并没有割掉原IP问 题的任何整数可行点. 当 b l 不是整数时, 则对应新的
松弛问题有一个原始基本不可行解和对偶可行解 .
用对偶单纯形法求解 !
XJTU
第三章 整数线性规划
否则, 用这个最优解代替 x 0 , 转S 2 .
XJTU
第三章 整数线性规划
OR
特点 :
割平面方程系数为分数
迭代过程中保持对偶可行性 分数对偶割平面算法
且用对偶单纯形法求解
收敛性 :
按一定的规则(如字典序)选取诱导方程 用对偶单纯形算法时避免循环
分数对偶割平面算法可在有限步内收敛(终止)
2P(L)
算法通常需要很多次迭代源自既可行解若算法在中途停止, 也 得不到原始问题的 整数解
结果毫无用处 !
XJTU
第三章 整数线性规划
为克服上述不足 :
对偶 整数割平面算法 原始
OR
整数割平面方程的导出 :
诱导方程
xBl aljxj bl jS
任意非零的h乘以上式两边 hxBl haljxj hbl
设用单纯形法求解( IP )的松弛问题( P 0 )所得的最优基本
可行解为 x 0 :
x0
基 BAB 1, ,ABm
基 变 量 xB1, ,xBm
下标集合记为 S ,
而非基变量下标集为 S
迭代终止时目标函数、各个约束条件对应的典式分别为 :
x0
z jxj z0
jS
xB0 z, a0j j
jS
将各变量的系数分离成整数部分和小数部分 :
h x B l h a l j x j h h x B l h a l j h a l j x j h b l h b l h b l
否则, 对( P 0 )增加一个线性约束(几何上为超平面, 故
称为割平面条件)
费
用 减 小


x2
x1
x0
该割平面条件将(P 0 )的可行域割掉一部分, 且使这个非整数
向量 x 0 恰好在被割掉的区域内
但原( IP )的任一可行解均未被切割掉
新的 松弛问题
改进的松弛问题 ( P 1 )
XJTU
第三章 整数线性规划
OR
按上述增加约束、逐步迭代的过程中, 若某步所得的松弛
LP问题
无可行解 无界
原问题( IP )亦不可行
STOP
原问题( IP )或不可行或无界
割平面法为一种松弛方法 !
关键 : 如何生成割平面, 不同的构造方法将产生不同的算法 .
XJTU
第三章 整数线性规划
OR
Gomory 分数割平面算法
S fl 0
它对应的是新松弛问题的一个原始基本解, 但不可行 .
XJTU
第三章 整数线性规划
OR
Gomory 割平面算法计算步骤 :
S 1 : (用单纯形法)求解整数规划问题( IP )的松弛问题( P 0 ) 若( P 0 )没有最优解, STOP ! ( IP )也没有最优解 .
若( P 0 )有最优解 x 0, 如果 x 0 是整数向量, STOP ! x 0为( IP )
xBl aljxj bl jS
诱导(生成)方程
b l b l f l ,0 f l 1 ,a l j a l j f l j ,0 a l j 1 ,j S
由变量的非负性
aljxj aljxj
jS
jS
生成方程变为 :
A、 b、 c 均为整值
放弃该约束
m in c T x s.t. A x b
x 0 ( P0 )
称为( IP )的松弛问题
XJTU
第三章 整数线性规划
OR
用单纯形法或别的方法求解( IP )的松弛问题( P 0 ), 得其最优解 x 0,
若x 0 为整数向量→STOP, x 0 亦为( IP )的最优解.
xBl aljxj bl jS
左边取值必为整数值
xBl aljxj bl
jS
从诱导方程中减去该不等式
XJTU
第三章 整数线性规划
OR
aljaljxjblbl jS
引进松弛变量S
fljxj fl
fljxj sfl
问题输入长度L 的多项式
XJTU
第三章 整数线性规划
OR
分数割平面算法的缺点 :
① 涉及分数. 计算机仅能以有限精度存贮各个参数的值, 从而对无限((不)循环)小数就产生了误差 .
一次一次迭代 误差积累
很难判定一个给定的元素是否为整数
但判定一个元素是否为整数却是生成割平面所必须的 !
② 对偶性 :导致在达到最优性以前未必可找到原始可行解
§ 3.2 割平面算法
XJTU
第三章 整数线性规划
OR
1958 R.E.Gomory 提出割平面(cutting plane)的概念
理论依据 : IP与LP之间的关系, 即前述的“conv(S)”结论 基本思想 :
考虑纯IP :
m in c T x
s.t. A x b
( IP )
x0
x Zn