2009-7-26 1
运 筹 学 Operations Research
§ 4.2 具有整数解的线性规划问题对纯整数规划

njx
bAxts
xcz
IP
j
T
,,2,1,,0
..
m a x
:)(
整数其松弛线性规划问题（ linear programming relaxation）
0
..
m a x
:)(
x
bAxts
xcz
LP
T
2009-7-26 2
运 筹 学 Operations Research
.)(
)()3(
)2(
)()()1(1
的最优解则必为为整数解，，若得最优解设利用单纯形法求解命题
IP
xxLP
zz
LPKIPK
LPIP

.)()( 也不可行不可行，则若推论 IPLP
证,…… ▌
一个,朴素的（ naive）,的设想：
的最优解？的最优解取整得将 )()( IPLP
2009-7-26 3
运 筹 学 Operations Research
上述想法不可行！ 如



整数,0,
13108
122..
m a x
:)(
21
21
21
21
xx
xx
xxts
xxz
IP



0,
13108
122..
m a x
:)(
21
21
21
21
xx
xx
xxts
xxz
LP
2009-7-26 4
运 筹 学 Operations Research
图解法：
2009-7-26 5
运 筹 学 Operations Research
.32,1()(
.9)5,4()(
.
2
17
)
2
9
,4()(
，最优值为）的最优解为实际上，
，最优值为的最优解为取整得
，最优值为的最优解为
T
T
T
IP
IP
LP
显然,二者差别甚大 ！
于是,求解整数规划的新算法的引入成为必要,
2009-7-26 6
运 筹 学 Operations Research
单 （ 幺 ） 模阵 （ unimodular matrix）,行列式的值为 0,-
1,1的整数方阵,
全单 （ 幺 ） 模阵 （ total unimodular matrix）,任一子方阵均为单模阵的矩阵,


31
52


101
011
但是，也确有一些线性规划问题，其本身的结构就决定了它必然存在整数解,
2009-7-26 7
运 筹 学 Operations Research
.
)2(
)1(
.1,1,0,)(2
21
21
21
必为全单模阵则
，和行指标同属零元素所在的非零元素时，这两个非的某列含有两个异号的当；和行指标分属零元素所在的非零元素时，这两个非的某列含有两个同号的当
，使得和的行指标划分为若可将元素的每列至多有两个非零，设矩阵命题
A
II
A
II
A
IIA
AaaA
ijnmij

▌
2009-7-26 8
运 筹 学 Operations Research
例 1 判断矩阵 是否为全单模阵？

00010
10001
10110
00101
A
}43{}2,1{ 21,，解, II ▌
Th1（ 具有整数解的线性规划问题）对线性规划问题
0
..
m a x
:)(
x
bAxts
xcz
LP
T
2009-7-26 9
运 筹 学 Operations Research
.
)(
均为整数解的任一基本解是整数向量，则是全单模阵，若 LPbA
，的基本解为关于任一基证：设





0)(
1 bB
x
xxBLP
N
B
.||1 是整数向量则 bBbBBbBx B?

▌
2009-7-26 10
运 筹 学 Operations Research
例 2 求证：运输问题必有整数解,., Zba
ji其中





njmix
njbx
miaxts
xcz
TP
ij
m
i
jij
i
n
j
ij
m
i
n
j
ijij
,,2,1;,,2,1,0
,,2,1,
,,2,1,..
m i n
:)(
1
1
1 1

.),,,,,,,( 2121 是整数向量证,Tnm bbbaaab
2009-7-26 11
运 筹 学 Operations Research
100100100
010010010
001001001
111000000
000111000
000000111
2
1
2
1
212222111211









nm
m
m
m
xxxxxxxxx
A
mnmmnn
},,2,1{},,,2,1{ 21 nmmmImI
.是全单模阵A ▌
2009-7-26 12
运 筹 学 Operations Research
§ 4.2 over