3.3 割平面法一、基本思想
为整数
：求
21
21
21
21
21
,
0,0
62
1232
.
58m a x
xx
xx
xx
xx
ts
xxz
IP
0,0
62
1232
.
58m a x
21
21
21
21
0
xx
xx
xx
ts
xxz
L,松弛问题的整数解的可行解 0LIP
1232 21 xx
62 21 xx
··
·
·
·
·
·
·
·
·
·
·
·
·
21 58 xxz
·
0,0
3
62
1232
.
58m a x
21
1
21
21
21
xx
x
xx
xx
ts
xxz
：得 110 )3( LxL
的整数解的可行解 1LIP
5.1,75.3 210 xxL 的最优解：
上增加一个约束，思想：在 0L
的所有整数解保留了 0L
2,3 211 xxL 的最优解：
2,3 21 xxIP 的最优解：得的最优解，该约束去掉了 0L
的所有整数解即保留了 IP
割平面割平面法的基本思想：
若整数规划 IP的松弛规划 L0的最优解不是整数解，
对 L0增加一个约束条件，得线性规划 L1，此过程缩小了松弛规划的可行解域，在切去松弛规划的最优解的同时，保留松弛规划的任一整数解，因此整数规划 IP的解均在 L1中，若 L1的最优解为整数解，则得 IP的最优解。若 L1的最优解不是整数解，重复以上步骤，由于可行解域在不断缩小，且保留 IP所有的整数解，总可以在有限次后得到 IP的最优解,
问题,如何寻找割平面？
增加的约束方程须满足什么条件才能使：
1、割掉松弛规划的最优解
2、保留所有的整数解
为整数
：
对整数规划问题
j
x
X
bAX
ts
CXzIP
0.
m a x
0
.
m a x
0
X
bAXts
CXz
L其松弛问题二,割平面法不是整数解的最优解设 00 XL
0,0,,,00100 mi bbbX
不妨设是非基变量是基变量，即 nmmi xxxxx,,,,11
是分数其中 0ib
L0的最优单纯形表：
x1 … xi … xm xm+1 … xm+j … xn 解检 0 … 0 … 0 λ1 … λm+j … λn z-z0
x1 1 … 0 … 0 a1m+1 … a1m+j … a1n b10
︰ ︰ ︰ ︰ ︰ ︰ ︰ ︰
xi 0 … 1 … 0 aim+1 … aim+j … ain bi0
︰ ︰ ︰ ︰ ︰ ︰ ︰ ︰
xm 0 … 0 … 1 amm+1 … amm+j … amn bm0
所在行的方程为,0ib
011 ininjmjimmimi bxaxaxax
源方程
0,0,,,001000 mi bbbXL 的最优解设 是分数0,ib
011 ininjmjimmimi bxaxaxax对源方程：
00 ii fb?
10 0 if
jimjim fa][
10 jimf 01 ijm
mn
j
jimi bxax
00
1
)( iijmjimjim
mn
j
i fbxfax
00
11
iijm
mn
j
jimjm
mn
j
jimi fbxfxax
jmmn
j
imijm
mn
j
jimii xffxabx?
1
10
1
0
0
1
0
jm
mn
j
jimi xff令
------对应于生成行 i的割平面
为整数
：
对整数规划问题
jx
X
bAX
ts
CXzIP
0.
m a x
0.
m a x
0
X
bAXts
CXz
L其松弛问题
0,0,,,001000 mi bbbXL 的最优解 是分数其中 0ib
L0的最优单纯形表：
x1 … xi … xm xm+1 … xm+j … xn 解检 0 … 0 … 0 λ1 … λm+j … λn z-z0
x1 1 … 0 … 0 a1m+1 … a1m+j … a1n b10
︰ ︰ ︰ ︰ ︰ ︰ ︰ ︰
xi 0 … 1 … 0 aim+1 … aim+j … ain bi0
︰ ︰ ︰ ︰ ︰ ︰ ︰ ︰
xm 0 … 0 … 1 amm+1 … amm+j … amn bm0
生成行
0:
1
0
jm
mn
j
jimi xff
对应于生成行 i的割平面
00 ii fb?
10 0 if
jimjim fa][
10 jimf
mnj,2,1
0
.
m a x:1
X
bAX
ts
CXzL线性规划
0
1
ijm
mn
j
jim fxf
0
1
,ijm
mn
j
jim fxf
即非基变量
X 1 X 2 X 3 X 4 X 5 X 6
b?
1
5
4
2
x
x
x
x 0 1 0.5 0 0 -0.5 1
0 0 -1.75 1 0 3.25 5.5
0 0 -1 0 1 1 3
1 0 -0.25 0 0 0.75 1.5
0 0 -0.5 0 0 -1.5 z-9
0,,,,,
42
520
323
632.
34m a x
654321
621
521
421
321
210
xxxxxx
xxx
xxx
xxx
xxxts
xxzL,其松弛问题为整数对
654321
654321
621
521
421
321
21
,,,,,
0,,,,,
42
520
323
632.
34m a x:
xxxxxx
xxxxxx
xxx
xxx
xxx
xxxts
xxzIP
的最优单纯形表,0L
035.5015.10?X最优解对应第 2行的割平面：
0
1
ijm
mn
j
jim fxf
00 ii fb?
10 0 if
jimjim fa][
10 jimf
mnj,2,1
5.025.025.0 63 xx
对应第 4行的割平面,5.025.075.0 63 xx
为整数
：
对整数规划问题
jx
X
bAX
ts
CXzIP
0.
m a x
0.
m a x
0
X
bAXts
CXz
L其松弛问题
0
.
m a x:1
X
bAX
ts
CXzL线性规划
0
1
ijm
mn
j
jim fxf
不是整数最优解 0X
的所有整数解的最优解并保留了割去了定理,001 LLL
代入的最优解证：把 00 XL 0
1
ijm
mn
j
jim fxf
00 if?得 矛盾与 10,0 if
的可行解的最优解不是所以 10 LL
的任一整数解是设 01 **,*,* LbbbX ni
只需证,*
0
1
ijm
mn
j
jim fbf
0*0,1 jmim bf,
0*
1
0
jm
mn
j
jimi bff即整数
10?if因为 1*,
1
0
jm
mn
j
jimi bff所以
0*
1
0
jm
mn
j
jimi bff所以 的可行解是，即 1* LX
非基变量
为整数
：
对整数规划问题
jx
X
bAX
ts
CXzIP
0.
m a x
0.
m a x
0
X
bAXts
CXz
L其松弛问题
0
.
m a x:1
X
bAX
ts
CXzL线性规划
0
1
ijm
mn
j
jim fxf
不是整数最优解 0X
的所有整数解的最优解并保留了割去了定理,001 LLL
的最优解是是整数解，则的最优解定理：若 IPXXL **1
如何求解？
0
1
1 ijm
mn
j
im fsxf
：三、解线性规划 1L
x
1
… xi … xm xm+1 … xm+j … xn 解检 0 … 0 … 0 c1 … cm+j … cn z-z0
x1 1 … 0 … 0 a1m+1 … a1m+j … a1n b10
︰ ︰ ︰ ︰ ︰ ︰ ︰ ︰
xi 0 … 1 … 0 aim+1 … aim+j … ain bi0
︰ ︰ ︰ ︰ ︰ ︰ ︰ ︰
xm 0 … 0 … 1 amm+1 … amm+j … amn bm0s
s
0 … 0 … 0 -fim+1 … -fim+j … -fin 1 –fi0
0
0
︰
0
︰
0
对偶单纯刑法
0
.
m a x
X
bAX
ts
CXz
0
1
ijm
mn
j
jim fxf
的最优单纯形表,0L
四、割平面计算步骤：
第一步,用单纯刑法解整数问题 IP的松弛问题 L0
若 L0没有最优解，则 IP没有最优解。停止若 L0有最优解 X0:
(1)X0是整数解,则 X0也是 IP的最优解，停止
(2)X0不是整数解,转第二步第二步,求割平面方程
，的一个非整数分量任选 00 ibX
所在的行的数据，的最优单纯型表中由 00 ibL
0
1
1 ijm
mn
j
im fxf
得割平面：
0
1
1 ijm
mn
j
im fsxf
即第三步,将割平面加到 L0得 L1
第四步,解 L1
在 L0的最优单纯型表中增加一行一列，
得 L1的单纯型表，
用对偶单纯刑法求解，
若其解是整数解，则该解也是原整数规划的最优解否则将该解记为 X0，返回第二步例 用割平面法求解 IP
为整数21
21
21
21
21
,
0,0
62
1232
.
58m a x:
xx
xx
xx
xx
ts
xxzIP
解,IP问题的松弛规划的标准型：
0,,,
62
1232
.
58m a x:
4321
421
321
210
xxxx
xxx
xxx
ts
xxzL
的最优单纯型表为,0L
X1 X2 X3 X4
0 0 -2.25 -1.75 Z-37.5
X2 0 1 0.25 -0.25 1.5
X1 1 0 0.125 0.375 3.75
X5
0
0
0
的最优解：0L )0,0,5.1,75.3(
找割平面对,75.31?x
75.0375.0125.0 43 xx
75.0375.0125.0 543 xxx即
X5 0 0 -0.125 -0.375 1 -0.75
X1 X2 X3 X4 X5
Z
X2
X1
X4 0 0 0.333 1 -2.667 2
1 0 0 0 1 3
0 1 0.333 0 -0.667 2
0 0 -1.667 0 -4.667 z-34
的最优解：得 1L )0,2,0,2,3(
整数的最优解：所以,IP 2,3 21 xx
最优值,Z=34
10 LL 中加入割平面得在例,用割平面法求解
为整数21
21
21
21
21
,
0,0
357
63
.
97m a x:
xx
xx
xx
xx
ts
xxzIP
解,IP的松弛规划的标准型
0,,,
357
63
.
97m a x:
4321
421
321
210
xxxx
xxx
xxx
ts
xxzL
的最优单纯型表为,0L
X1 X2 X3 X4
0 0 -28/11 -15/11 Z-63
X2 0 1 7/22 1/22 7/2
X1 1 0 -1/22 3/22 9/2
的最优解：0L )0,0,2/7,2/9(
找割平面对,2/72?x
21221227 43 xx
21221227 543 xxx即
X5 0 0 -7/22 -1/22 1 -1/2
X5
0
0
0
X1 X2 X3 X4 X5
X2
X1
X3 0 0 1 1/7 -22/7 11/7
1 0 0 1/7 -1/7 32/7
0 1 0 0 1 3
0 0 0 -1 -8 Z-59
的最优单纯型表：得 1L
的最优解,1L )0,0,711,3,732(
非整数
10 LL 中加入割平面得在
X1 X2 X3 X4 X5
X2
X1
X3 0 0 1 1/7 -22/7 11/7
1 0 0 1/7 -1/7 32/7
0 1 0 0 1 3
0 0 0 -1 -8 Z-59
的最优单纯型表,1L的最优解,1L )0,0,711,3,732(
找割平面对,7321?x
7
4
7
6
7
1
54 xx
7
4
7
6
7
1
654 xxx即
21 LL 中加入割平面得在
X6 0 0 0 -1/7 -6/7 1 -4/7
X6
0
0
0
0
X1 X2 X3 X4 X5 X6
0 0 0 0 -2 -7 Z-55
X2 0 1 0 0 1 1 3
X1 1 0 0 0 -1 1 4
X3 0 0 1 0 -4 1 1
X4 0 0 0 1 6 -7 4
的最优解：得 2L )0,4,1,3,4(
整数的最优解：所以,IP
3,4 21 xx
最优值,Z=55
作业,分别用分枝定界法和割平面法求解以下整数规划：
为整数
21
4321
42
321
21
,
0,,,
52
1023
.
m a x:
xx
xxxx
xx
xxx
ts
xxzIP
1,02,2 4321 xxxx,答案：最优解：
最优值为,Z=4
为整数
：求
21
21
21
21
21
,
0,0
62
1232
.
58m a x
xx
xx
xx
xx
ts
xxz
IP
0,0
62
1232
.
58m a x
21
21
21
21
0
xx
xx
xx
ts
xxz
L,松弛问题的整数解的可行解 0LIP
1232 21 xx
62 21 xx
··
·
·
·
·
·
·
·
·
·
·
·
·
21 58 xxz
·
0,0
3
62
1232
.
58m a x
21
1
21
21
21
xx
x
xx
xx
ts
xxz
：得 110 )3( LxL
的整数解的可行解 1LIP
5.1,75.3 210 xxL 的最优解：
上增加一个约束，思想：在 0L
的所有整数解保留了 0L
2,3 211 xxL 的最优解：
2,3 21 xxIP 的最优解：得的最优解，该约束去掉了 0L
的所有整数解即保留了 IP
割平面割平面法的基本思想：
若整数规划 IP的松弛规划 L0的最优解不是整数解，
对 L0增加一个约束条件，得线性规划 L1，此过程缩小了松弛规划的可行解域，在切去松弛规划的最优解的同时，保留松弛规划的任一整数解，因此整数规划 IP的解均在 L1中，若 L1的最优解为整数解，则得 IP的最优解。若 L1的最优解不是整数解，重复以上步骤，由于可行解域在不断缩小，且保留 IP所有的整数解，总可以在有限次后得到 IP的最优解,
问题,如何寻找割平面？
增加的约束方程须满足什么条件才能使：
1、割掉松弛规划的最优解
2、保留所有的整数解
为整数
：
对整数规划问题
j
x
X
bAX
ts
CXzIP
0.
m a x
0
.
m a x
0
X
bAXts
CXz
L其松弛问题二,割平面法不是整数解的最优解设 00 XL
0,0,,,00100 mi bbbX
不妨设是非基变量是基变量，即 nmmi xxxxx,,,,11
是分数其中 0ib
L0的最优单纯形表：
x1 … xi … xm xm+1 … xm+j … xn 解检 0 … 0 … 0 λ1 … λm+j … λn z-z0
x1 1 … 0 … 0 a1m+1 … a1m+j … a1n b10
︰ ︰ ︰ ︰ ︰ ︰ ︰ ︰
xi 0 … 1 … 0 aim+1 … aim+j … ain bi0
︰ ︰ ︰ ︰ ︰ ︰ ︰ ︰
xm 0 … 0 … 1 amm+1 … amm+j … amn bm0
所在行的方程为,0ib
011 ininjmjimmimi bxaxaxax
源方程
0,0,,,001000 mi bbbXL 的最优解设 是分数0,ib
011 ininjmjimmimi bxaxaxax对源方程：
00 ii fb?
10 0 if
jimjim fa][
10 jimf 01 ijm
mn
j
jimi bxax
00
1
)( iijmjimjim
mn
j
i fbxfax
00
11
iijm
mn
j
jimjm
mn
j
jimi fbxfxax
jmmn
j
imijm
mn
j
jimii xffxabx?
1
10
1
0
0
1
0
jm
mn
j
jimi xff令
------对应于生成行 i的割平面
为整数
：
对整数规划问题
jx
X
bAX
ts
CXzIP
0.
m a x
0.
m a x
0
X
bAXts
CXz
L其松弛问题
0,0,,,001000 mi bbbXL 的最优解 是分数其中 0ib
L0的最优单纯形表：
x1 … xi … xm xm+1 … xm+j … xn 解检 0 … 0 … 0 λ1 … λm+j … λn z-z0
x1 1 … 0 … 0 a1m+1 … a1m+j … a1n b10
︰ ︰ ︰ ︰ ︰ ︰ ︰ ︰
xi 0 … 1 … 0 aim+1 … aim+j … ain bi0
︰ ︰ ︰ ︰ ︰ ︰ ︰ ︰
xm 0 … 0 … 1 amm+1 … amm+j … amn bm0
生成行
0:
1
0
jm
mn
j
jimi xff
对应于生成行 i的割平面
00 ii fb?
10 0 if
jimjim fa][
10 jimf
mnj,2,1
0
.
m a x:1
X
bAX
ts
CXzL线性规划
0
1
ijm
mn
j
jim fxf
0
1
,ijm
mn
j
jim fxf
即非基变量
X 1 X 2 X 3 X 4 X 5 X 6
b?
1
5
4
2
x
x
x
x 0 1 0.5 0 0 -0.5 1
0 0 -1.75 1 0 3.25 5.5
0 0 -1 0 1 1 3
1 0 -0.25 0 0 0.75 1.5
0 0 -0.5 0 0 -1.5 z-9
0,,,,,
42
520
323
632.
34m a x
654321
621
521
421
321
210
xxxxxx
xxx
xxx
xxx
xxxts
xxzL,其松弛问题为整数对
654321
654321
621
521
421
321
21
,,,,,
0,,,,,
42
520
323
632.
34m a x:
xxxxxx
xxxxxx
xxx
xxx
xxx
xxxts
xxzIP
的最优单纯形表,0L
035.5015.10?X最优解对应第 2行的割平面：
0
1
ijm
mn
j
jim fxf
00 ii fb?
10 0 if
jimjim fa][
10 jimf
mnj,2,1
5.025.025.0 63 xx
对应第 4行的割平面,5.025.075.0 63 xx
为整数
：
对整数规划问题
jx
X
bAX
ts
CXzIP
0.
m a x
0.
m a x
0
X
bAXts
CXz
L其松弛问题
0
.
m a x:1
X
bAX
ts
CXzL线性规划
0
1
ijm
mn
j
jim fxf
不是整数最优解 0X
的所有整数解的最优解并保留了割去了定理,001 LLL
代入的最优解证：把 00 XL 0
1
ijm
mn
j
jim fxf
00 if?得 矛盾与 10,0 if
的可行解的最优解不是所以 10 LL
的任一整数解是设 01 **,*,* LbbbX ni
只需证,*
0
1
ijm
mn
j
jim fbf
0*0,1 jmim bf,
0*
1
0
jm
mn
j
jimi bff即整数
10?if因为 1*,
1
0
jm
mn
j
jimi bff所以
0*
1
0
jm
mn
j
jimi bff所以 的可行解是，即 1* LX
非基变量
为整数
：
对整数规划问题
jx
X
bAX
ts
CXzIP
0.
m a x
0.
m a x
0
X
bAXts
CXz
L其松弛问题
0
.
m a x:1
X
bAX
ts
CXzL线性规划
0
1
ijm
mn
j
jim fxf
不是整数最优解 0X
的所有整数解的最优解并保留了割去了定理,001 LLL
的最优解是是整数解，则的最优解定理：若 IPXXL **1
如何求解？
0
1
1 ijm
mn
j
im fsxf
：三、解线性规划 1L
x
1
… xi … xm xm+1 … xm+j … xn 解检 0 … 0 … 0 c1 … cm+j … cn z-z0
x1 1 … 0 … 0 a1m+1 … a1m+j … a1n b10
︰ ︰ ︰ ︰ ︰ ︰ ︰ ︰
xi 0 … 1 … 0 aim+1 … aim+j … ain bi0
︰ ︰ ︰ ︰ ︰ ︰ ︰ ︰
xm 0 … 0 … 1 amm+1 … amm+j … amn bm0s
s
0 … 0 … 0 -fim+1 … -fim+j … -fin 1 –fi0
0
0
︰
0
︰
0
对偶单纯刑法
0
.
m a x
X
bAX
ts
CXz
0
1
ijm
mn
j
jim fxf
的最优单纯形表,0L
四、割平面计算步骤：
第一步,用单纯刑法解整数问题 IP的松弛问题 L0
若 L0没有最优解，则 IP没有最优解。停止若 L0有最优解 X0:
(1)X0是整数解,则 X0也是 IP的最优解，停止
(2)X0不是整数解,转第二步第二步,求割平面方程
，的一个非整数分量任选 00 ibX
所在的行的数据，的最优单纯型表中由 00 ibL
0
1
1 ijm
mn
j
im fxf
得割平面：
0
1
1 ijm
mn
j
im fsxf
即第三步,将割平面加到 L0得 L1
第四步,解 L1
在 L0的最优单纯型表中增加一行一列，
得 L1的单纯型表，
用对偶单纯刑法求解，
若其解是整数解，则该解也是原整数规划的最优解否则将该解记为 X0，返回第二步例 用割平面法求解 IP
为整数21
21
21
21
21
,
0,0
62
1232
.
58m a x:
xx
xx
xx
xx
ts
xxzIP
解,IP问题的松弛规划的标准型：
0,,,
62
1232
.
58m a x:
4321
421
321
210
xxxx
xxx
xxx
ts
xxzL
的最优单纯型表为,0L
X1 X2 X3 X4
0 0 -2.25 -1.75 Z-37.5
X2 0 1 0.25 -0.25 1.5
X1 1 0 0.125 0.375 3.75
X5
0
0
0
的最优解：0L )0,0,5.1,75.3(
找割平面对,75.31?x
75.0375.0125.0 43 xx
75.0375.0125.0 543 xxx即
X5 0 0 -0.125 -0.375 1 -0.75
X1 X2 X3 X4 X5
Z
X2
X1
X4 0 0 0.333 1 -2.667 2
1 0 0 0 1 3
0 1 0.333 0 -0.667 2
0 0 -1.667 0 -4.667 z-34
的最优解：得 1L )0,2,0,2,3(
整数的最优解：所以,IP 2,3 21 xx
最优值,Z=34
10 LL 中加入割平面得在例,用割平面法求解
为整数21
21
21
21
21
,
0,0
357
63
.
97m a x:
xx
xx
xx
xx
ts
xxzIP
解,IP的松弛规划的标准型
0,,,
357
63
.
97m a x:
4321
421
321
210
xxxx
xxx
xxx
ts
xxzL
的最优单纯型表为,0L
X1 X2 X3 X4
0 0 -28/11 -15/11 Z-63
X2 0 1 7/22 1/22 7/2
X1 1 0 -1/22 3/22 9/2
的最优解：0L )0,0,2/7,2/9(
找割平面对,2/72?x
21221227 43 xx
21221227 543 xxx即
X5 0 0 -7/22 -1/22 1 -1/2
X5
0
0
0
X1 X2 X3 X4 X5
X2
X1
X3 0 0 1 1/7 -22/7 11/7
1 0 0 1/7 -1/7 32/7
0 1 0 0 1 3
0 0 0 -1 -8 Z-59
的最优单纯型表：得 1L
的最优解,1L )0,0,711,3,732(
非整数
10 LL 中加入割平面得在
X1 X2 X3 X4 X5
X2
X1
X3 0 0 1 1/7 -22/7 11/7
1 0 0 1/7 -1/7 32/7
0 1 0 0 1 3
0 0 0 -1 -8 Z-59
的最优单纯型表,1L的最优解,1L )0,0,711,3,732(
找割平面对,7321?x
7
4
7
6
7
1
54 xx
7
4
7
6
7
1
654 xxx即
21 LL 中加入割平面得在
X6 0 0 0 -1/7 -6/7 1 -4/7
X6
0
0
0
0
X1 X2 X3 X4 X5 X6
0 0 0 0 -2 -7 Z-55
X2 0 1 0 0 1 1 3
X1 1 0 0 0 -1 1 4
X3 0 0 1 0 -4 1 1
X4 0 0 0 1 6 -7 4
的最优解：得 2L )0,4,1,3,4(
整数的最优解：所以,IP
3,4 21 xx
最优值,Z=55
作业,分别用分枝定界法和割平面法求解以下整数规划：
为整数
21
4321
42
321
21
,
0,,,
52
1023
.
m a x:
xx
xxxx
xx
xxx
ts
xxzIP
1,02,2 4321 xxxx,答案：最优解：
最优值为,Z=4
