2009-7-26 1
运 筹 学 Operations Research
§ 4.3 割平面法

njx
bAxts
xcz
IP
j
T
,,2,1,,0
..
m a x
:)(
整数给定整数规划对应的松弛线性规划问题为
0
..
m a x
:)(
x
bAxts
xcz
LP
T
2009-7-26 2
运 筹 学 Operations Research
割平面法的基本思想：
.
)(
)(
.)(
)(
)(
)(
.)(
解为止的最优到继续上述步骤，直到得
，，设得最优解为继续求解新的的任一可行解可行解，而不割去的一部分在内的平面，割去含割增加一个约束条件否则，给的最优解；即为为整数解，则若
，设得最优解利用单纯形法求解
IP
xLP
IP
LPx
LP
IPxx
xLP



2009-7-26 3
运 筹 学 Operations Research
割平面的选取：
相应的单纯形表为
，最终得最优基设利用单纯形法求解 ),,,()(...,21 mPPPBLPGOLW




0
1
0
1
,,2,1,
zxrz
mibxbx
n
mj
jj
i
n
mj
jiji?




n
mj
jj
n
mj
jijii
xrzz
mixbbx
1
0
1
0,,2,1,?
2009-7-26 4
运 筹 学 Operations Research
单纯形表为
.)0,,0,0,,,,()( 002010 zbbbxLP Tm,最优值为的最优解为
2009-7-26 5
运 筹 学 Operations Research
.)0,,0,0,,,,()( 020100 Tmi bbbxIPZb 的最优解为，则若的方程为行对应，则单纯形表的第否则，不妨设 kmkZb k )1(0



n
mj
jkjkkk
n
mj
jkjk xbbxbxbx
1
00
1
0
[ ] [ ]
0,[ 0,1 ),
k j k j k j k j k j k j k j
k k j
b b f b b f b
ff


令,其 中 为 的 整 数 部 分,为 的 小 数 部 分,
则
.][][
)]([)][(
1
0
1
0
1
00
1
0






n
mj
jkjk
n
mj
jkjk
n
mj
jkjkjkk
n
mj
jkjkk
xffxbb
xfbfbxbbx
2009-7-26 6
运 筹 学 Operations Research
柯莫利割平面（ Gomory cutting plane）,
01
1
1
1
0
1
0
0
0
kn
n
mj
jkj
n
n
mj
jkjk
n
mj
jkjk
fxxf
xxff
xff






为加快计算的速度，常令
}0{m a x 010 imik ff
2009-7-26 7
运 筹 学 Operations Research
割平面的两个性质：
.)(1h 的非整数最优解割平面割去 LPT
.)0,,0,0,,,,( 02010 不满足割平面即可证：仅需证 Tmbbbx
00
1
0

k
n
mj
jkjk fxff?
.)0,,0,0,,,,( 02010 不满足割平面Tmbbbx ▌
2009-7-26 8
运 筹 学 Operations Research
.)(h2 的任一可行解割平面不割去 IPT
.)( 平面即可的任一可行解都满足割证：仅需证 IP
).(?)()?,,?,?(? 21 LPKxIPKxxxx Tn,则?
满足典式又 x?
.][][
)]([)][(
1
0
1
0
1
00
1
0






n
mj
jkjk
n
mj
jkjk
n
mj
jkjkjkk
n
mj
jkjkk
xffxbb
xfbfbxbbx
,?][][?
1
0 Zxbbx
n
mj
jkjkk

，?,?
1
0 Zxff
n
mj
jkjk

2009-7-26 9
运 筹 学 Operations Research
，又 1? 0
0
0?10

k
f
x
n
mj
jkjk fxff
kj
j
0?
1
0

n
mj
jkjk xff ▌
2009-7-26 10
运 筹 学 Operations Research
增添割平面后得新的线性规划



.1,,,2,1,0
..
m a x
01
1
nnjx
fxxf
bAxts
xcz
j
kn
n
mj
jkj
T
增添割平面后的新单纯形表：
对松弛线性规划问题
0
..
m a x
:)(
x
bAxts
xcz
LP
T
2009-7-26 11
运 筹 学 Operations Research
新单纯形表为新表仅是在原表中增加松弛变量的行、列而已！
显然,可继续利用对偶单纯形法求解,
2009-7-26 12
运 筹 学 Operations Research
根据以上讨论，设计算法如下：
2009-7-26 13
运 筹 学 Operations Research
例 1 利用割平面法求解整数规划



整数,0,
43
1..
m a x
:)(
21
21
21
21
xx
xx
xxts
xxz
IP
的松弛线性规划问题为解,)( IP



0,
43
1..
m a x
:)(
21
21
21
21
xx
xx
xxts
xxz
LP
2009-7-26 14
运 筹 学 Operations Research
243 ),( IPPB取初始可行基




4,3,2,1,0
43
1..
m a x
421
321
21
jx
xxx
xxxts
xxz
j
其标准形为
2009-7-26 15
运 筹 学 Operations Research
).,()( 21 PPBLP 的最优基为
100 4
3}
4
3,
4
3m a x { ff
k
0)( 41431310 xfxff作割平面
0)4143(43 43 xx即 434143 543 xxx
2009-7-26 16
运 筹 学 Operations Research
作新单纯形表，并利用对偶单纯形法继续求解：
2009-7-26 17
运 筹 学 Operations Research
.2)1,1()(
.2)0,0,1,1,1()(
，最优值为的最优解为故
，最优值为的最优解为
T
T
IP
LP? ▌
2009-7-26 18
运 筹 学 Operations Research
注：图解法割平面：
1
3)34(
)1(3
33
4
3
4
1
4
3
2
21
21
43
43





x
xx
xx
xx
xx
2009-7-26 19
运 筹 学 Operations Research
Ex.利用割平面法求解整数规划


，整数0,
52
1023..
m a x
:)(
21
2
21
21
xx
x
xxts
xxz
IP
.4)2,2(,最优值为最优解为 T
2009-7-26 20
运 筹 学 Operations Research
§ 4.3 over