第二节线性规划模型的解一、模型标准化标准形式
LP
n
j
jj xcz
1
m in
mibxats i
n
j
jij,,2,1,.
1
njx j,,2,1,0
矩阵表示,CXz?m in
OX
bAXts
.
其中,),,,,( 21 ncccC
),,,,( 21 mbbbb
mnmm
n
n
aaa
aaa
aaa
A
21
22221
11211
1P 2P nP
向量表示,CXz?m in
bPxPxPxts nn2211.
OX?
若 （ 1）,m ax
1
0?
n
j
jj xcx,0xz则令
n
j
jj xcz
1
)(mi n目标函数化为：
两个模型的最优解相同，最优目标值有关系：
zx 0
,)2(
1
i
n
j
jij bxa
－ yi 0?iy 剩余变量
,
1
i
n
j
jij bxa
+yi 0?iy 松弛变量是自由变量，ix)3( 0,, iiiii vuvux则令二、单纯形法
CXz?m in
OX
bAXts
.
OXbAXXS,|
可行域 可行解讨论步骤,1,先将模型变形，缩小搜索范围，变为在有限个可行解（极点）中找最优解。
2,介绍如何找出（迭代）最优解。
S是一个凸集 凸多面体 (有界 )
或为无界的凸区域极点?
单纯形法就是从某一个极点开始，沿 棱 到另一极点的迭代，经有限步求出最优解的方法。
不便用微分法求解
1,mAr?)(设 （即无多余的约束条件）
则 A 中有 m 个列向量线性无关：
mjjj PPP,,,21?（ ）
B = LP 的一个 基矩阵
N =（其余向量） 非基矩阵
TjjjB
mxxxX ),,,( 21
TBBBB
mxxxX ),,,( 21或 基变量
)( 其余变量?NX 非基变量于是 ),,( NBA?,
N
B
X
XX
),( NB CCC?
模型中约束条件,
N
B
X
XNBAX ),(
NB NXBX b?
)(11 可逆BNXBbBX NB
目标函数,
N
B
NB X
XCCCX ),(
NNBB XCXC
NNNB XCNXBbBC )( 11
NNBB XCNBCbBC )( 11
模型改写为,NNBB XCNBCbBCz )(m in 11
OX
NXBbBXts NB
11.
或 kk xyyz 000m i n
kkB xyyxts 1101.
kikiB xyyx i 0
kmkmB xyyx m 0
njx j,,2,1,0
非基变量kx
9 10 11 12
或?
Nj
jj xyyz 000m i n
Nj
jijiB xyyxts i 0.
njx j,,2,1,0
O
bB
X
X
N
B
1
是 AX=b 的一个解,称为 基本解；
,1 ObBX B若
O
bB 1
称 为 基可行解，
相应的 B 称为 可行基；
若 X 既是基可行解，又是最优解，则称为 基最优解相应的 B 称为 最优基,记为 。B
＃
可行解与基可行解的联系
（ 1） LP 有可行解? 有基可行解
（ 2） LP 有最优解? 有基最优解
（ 3） LP 最优解唯一? 基最优解唯一，且相同；
LP 的最优解不唯一（ S有界）
kXX,,1?设 为全部基最优解?
1,0,
11
k
i
ii
k
i
i
i XX是 LP 的全部最优解。
可以证明：
由（ 1）（ 2）知,若有最优解，必可在基可行解中找到,
mnC?
可行域 S?
基本解基可行解基可行解的个数? 基本解个数
S?
可证：基可行解为
S的极点。
2,单纯形法判别定理
),,,( 21 mjjj PPPB设 是 可行基,OO
bB?
1即
（ 1）若 检验数 ),,,2,1(00 njy j 则最优解
,
1
O
bBX 最优目标值
00yz
（ 2）若 Nky k,00
1° 若 ),,,2,1(0 miy ik 则 LP 无下界；
2° 若 ),1(0 msy sk
则 可得 使目标值不增的新的可行基。
按（ 3）（ 4）迭代。
6
（ 3） 1° 让 )( kk xP 入基，即成为基向量（变量）
2° 令
miy
y
y
ik
ik
i,,2,1,0m i n 0 00
lk
l
y
y
)( ll jj xP则 出基,得新基：
),,,,( 1 mjkj PPPB
l 最小比值法则
（ 4） 计算新可行解：
TBkBB
mxxxX ),,,,( 1 ))(,,,(
' 0'20'10 Oyyy m
OX N
新目标值,)( 00'00 yyz
新系数,ijj yy?,'0
返回到（ 1）再判别、迭代。
6
＃
由解线性方程组的 消元法 可得新旧系数之间的关系：
0
0
00
'
00 l
lk
k y
y
yyy
00y?
lj
lk
k
jj yy
yyy 0
0
'
0 nj,,2,1
00
'
0 l
lk
ik
ii yy
yyy,0? )0(?ik
lk
l
ik
i
ik y
y
y
yy 00,0? )0(?
iky
)( li?
)( li? 00' 0
lk
l
l y
yy
lj
lk
ik
ijij yy
yyy'
)( li?
lk
lj
lj y
yy?'
)( li? nj
mi
,,2,1
,,2,1
6
单纯形表
bBCXCNBCOXz BNNBB 11 )(
bBNXBIXOz NB 11
NBIbB
CNBCObBC NBB
11
11
)(BT?
视,
l
i
B
B
x
x
z
nkB xxxx i1
ln
yy
yy
lk
inik
nk yy 0000
0
0
00
l
i
y
y
y
单位向量
)(BT?
6
枢轴元例 423m i n xxz
5,4,3,2,1,0
6
4
22.
531
321
431
jx
xxx
xxx
xxxts
j
,
10101
00111
01102
A,
6
4
2
b
),0,1,0,3,0(?C 3)(?Ar
1P 2P 3P 4P 5P
,Ob?因 A 中含单位阵,且
IPPPB ),,( 5241 是可行基 )( 11 ObbB
),,( 311 PPN? ),0,3,1(),,( 5241 cccC B )0,0(),( 311 ccC N
,),,( 5241 TB xxxX? TN xxX ),( 311?
1.求第一块单纯形表
,11 bbB,1111 NNB
,14
6
4
2
)0,3,1(11
1
bBC B
)2,1()0,0(
11
11
12
)0,3,1(
11 1
1
1
ICNBC NB
得单纯形表：
1x 2x 3x 4x 5x
1
1
2
0
1
0
1
1
1?
0
0
1
1
0
0
00201?
6
4
214
5
2
4
x
x
xz
)( 1BT
2,判别,02
03 y? 。入基 )3()( 33 kxP
3,确定出基向量 4
1
6,
1
4m i n,m i n
33
30
23
20?
y
y
y
y
23
20
y
y?
)2(?l
枢轴元出基，)( 22 xP? 得可行基 ),,( 5342 PPPB?
基变量 TB xxxX ),,( 5342?
4,枢轴
1x 2x 3x 4x 5x
2
1
1
1
1
1
0
1
0
0
0
1
1
0
0
00021?
2
4
66
5
3
4
x
x
xz
)( 2BT
2′,判别,0101y? 。入基 )1()( 11 kxP
3′,确定出基向量 31
30
31
30
11
10 1
2
2,
1
6m i n,m i n
y
y
y
y
y
y
)3(?l出基，)( 55 xP? 得可行基 ),,(
1343 PPPB?
基变量 TB xxxX ),,( 1343?
4′,枢轴
1x 2x 3x 4x 5x
1
0
0
2/1
2/1
2/3
0
1
0
0
0
1
2
100
2
30
1
5
55
1
3
4
x
x
xz
)( 3BT
2/1
2/1
2/1?
5,4,3,2,1,00 jy j?
,)0,5,5,0,1( TX最优解
5z最优目标值
＃
第一块单纯形表可由初等变换得到：
CXz?
bAX?将 改写成,
bNXBXz
XCXCz
NB
NNBB
0
0
系数矩阵
)(BT
NBb
CC NB0
NBIbB
CC NB
11
0
NBIbB
CNBCObBC NBB
11
11
单纯形表避免了计算逆矩阵和矩阵的积。
Ab
C0
例 用单纯形法求以下问题的最优解
4321 32m i n xxxxz
123,31 xxts
0,,,4321?xxxx
2052 321 xxx
102 4321 xxxx
解,
1121
0512
0301
A
),,( 4311 PPPB?取系数阵,?
Ab
C0
112110
051220
030112
13210
1x 2x 3x 4x
不知是否可行
12202
01104
030112
102012
10006
01104
00310
00206
)( 1BT
,0202y? 入基。2P?,0
12
10
y
y又 出基。
1P?
得 ),,( 4322 PPPB?
10006
0103/14
0013/10
0003/26
)(
2
BT
,)6,4,0,0( TX
6z
为枢轴元12y
＃
注,· 第一个可行基的获得 — 人造变量法 ；
· 同时获得第一个可行基和第一章单纯形表
— 二阶段法 。
LP
n
j
jj xcz
1
m in
mibxats i
n
j
jij,,2,1,.
1
njx j,,2,1,0
矩阵表示,CXz?m in
OX
bAXts
.
其中,),,,,( 21 ncccC
),,,,( 21 mbbbb
mnmm
n
n
aaa
aaa
aaa
A
21
22221
11211
1P 2P nP
向量表示,CXz?m in
bPxPxPxts nn2211.
OX?
若 （ 1）,m ax
1
0?
n
j
jj xcx,0xz则令
n
j
jj xcz
1
)(mi n目标函数化为：
两个模型的最优解相同，最优目标值有关系：
zx 0
,)2(
1
i
n
j
jij bxa
－ yi 0?iy 剩余变量
,
1
i
n
j
jij bxa
+yi 0?iy 松弛变量是自由变量，ix)3( 0,, iiiii vuvux则令二、单纯形法
CXz?m in
OX
bAXts
.
OXbAXXS,|
可行域 可行解讨论步骤,1,先将模型变形，缩小搜索范围，变为在有限个可行解（极点）中找最优解。
2,介绍如何找出（迭代）最优解。
S是一个凸集 凸多面体 (有界 )
或为无界的凸区域极点?
单纯形法就是从某一个极点开始，沿 棱 到另一极点的迭代，经有限步求出最优解的方法。
不便用微分法求解
1,mAr?)(设 （即无多余的约束条件）
则 A 中有 m 个列向量线性无关：
mjjj PPP,,,21?（ ）
B = LP 的一个 基矩阵
N =（其余向量） 非基矩阵
TjjjB
mxxxX ),,,( 21
TBBBB
mxxxX ),,,( 21或 基变量
)( 其余变量?NX 非基变量于是 ),,( NBA?,
N
B
X
XX
),( NB CCC?
模型中约束条件,
N
B
X
XNBAX ),(
NB NXBX b?
)(11 可逆BNXBbBX NB
目标函数,
N
B
NB X
XCCCX ),(
NNBB XCXC
NNNB XCNXBbBC )( 11
NNBB XCNBCbBC )( 11
模型改写为,NNBB XCNBCbBCz )(m in 11
OX
NXBbBXts NB
11.
或 kk xyyz 000m i n
kkB xyyxts 1101.
kikiB xyyx i 0
kmkmB xyyx m 0
njx j,,2,1,0
非基变量kx
9 10 11 12
或?
Nj
jj xyyz 000m i n
Nj
jijiB xyyxts i 0.
njx j,,2,1,0
O
bB
X
X
N
B
1
是 AX=b 的一个解,称为 基本解；
,1 ObBX B若
O
bB 1
称 为 基可行解，
相应的 B 称为 可行基；
若 X 既是基可行解，又是最优解，则称为 基最优解相应的 B 称为 最优基,记为 。B
＃
可行解与基可行解的联系
（ 1） LP 有可行解? 有基可行解
（ 2） LP 有最优解? 有基最优解
（ 3） LP 最优解唯一? 基最优解唯一，且相同；
LP 的最优解不唯一（ S有界）
kXX,,1?设 为全部基最优解?
1,0,
11
k
i
ii
k
i
i
i XX是 LP 的全部最优解。
可以证明：
由（ 1）（ 2）知,若有最优解，必可在基可行解中找到,
mnC?
可行域 S?
基本解基可行解基可行解的个数? 基本解个数
S?
可证：基可行解为
S的极点。
2,单纯形法判别定理
),,,( 21 mjjj PPPB设 是 可行基,OO
bB?
1即
（ 1）若 检验数 ),,,2,1(00 njy j 则最优解
,
1
O
bBX 最优目标值
00yz
（ 2）若 Nky k,00
1° 若 ),,,2,1(0 miy ik 则 LP 无下界；
2° 若 ),1(0 msy sk
则 可得 使目标值不增的新的可行基。
按（ 3）（ 4）迭代。
6
（ 3） 1° 让 )( kk xP 入基，即成为基向量（变量）
2° 令
miy
y
y
ik
ik
i,,2,1,0m i n 0 00
lk
l
y
y
)( ll jj xP则 出基,得新基：
),,,,( 1 mjkj PPPB
l 最小比值法则
（ 4） 计算新可行解：
TBkBB
mxxxX ),,,,( 1 ))(,,,(
' 0'20'10 Oyyy m
OX N
新目标值,)( 00'00 yyz
新系数,ijj yy?,'0
返回到（ 1）再判别、迭代。
6
＃
由解线性方程组的 消元法 可得新旧系数之间的关系：
0
0
00
'
00 l
lk
k y
y
yyy
00y?
lj
lk
k
jj yy
yyy 0
0
'
0 nj,,2,1
00
'
0 l
lk
ik
ii yy
yyy,0? )0(?ik
lk
l
ik
i
ik y
y
y
yy 00,0? )0(?
iky
)( li?
)( li? 00' 0
lk
l
l y
yy
lj
lk
ik
ijij yy
yyy'
)( li?
lk
lj
lj y
yy?'
)( li? nj
mi
,,2,1
,,2,1
6
单纯形表
bBCXCNBCOXz BNNBB 11 )(
bBNXBIXOz NB 11
NBIbB
CNBCObBC NBB
11
11
)(BT?
视,
l
i
B
B
x
x
z
nkB xxxx i1
ln
yy
yy
lk
inik
nk yy 0000
0
0
00
l
i
y
y
y
单位向量
)(BT?
6
枢轴元例 423m i n xxz
5,4,3,2,1,0
6
4
22.
531
321
431
jx
xxx
xxx
xxxts
j
,
10101
00111
01102
A,
6
4
2
b
),0,1,0,3,0(?C 3)(?Ar
1P 2P 3P 4P 5P
,Ob?因 A 中含单位阵,且
IPPPB ),,( 5241 是可行基 )( 11 ObbB
),,( 311 PPN? ),0,3,1(),,( 5241 cccC B )0,0(),( 311 ccC N
,),,( 5241 TB xxxX? TN xxX ),( 311?
1.求第一块单纯形表
,11 bbB,1111 NNB
,14
6
4
2
)0,3,1(11
1
bBC B
)2,1()0,0(
11
11
12
)0,3,1(
11 1
1
1
ICNBC NB
得单纯形表：
1x 2x 3x 4x 5x
1
1
2
0
1
0
1
1
1?
0
0
1
1
0
0
00201?
6
4
214
5
2
4
x
x
xz
)( 1BT
2,判别,02
03 y? 。入基 )3()( 33 kxP
3,确定出基向量 4
1
6,
1
4m i n,m i n
33
30
23
20?
y
y
y
y
23
20
y
y?
)2(?l
枢轴元出基，)( 22 xP? 得可行基 ),,( 5342 PPPB?
基变量 TB xxxX ),,( 5342?
4,枢轴
1x 2x 3x 4x 5x
2
1
1
1
1
1
0
1
0
0
0
1
1
0
0
00021?
2
4
66
5
3
4
x
x
xz
)( 2BT
2′,判别,0101y? 。入基 )1()( 11 kxP
3′,确定出基向量 31
30
31
30
11
10 1
2
2,
1
6m i n,m i n
y
y
y
y
y
y
)3(?l出基，)( 55 xP? 得可行基 ),,(
1343 PPPB?
基变量 TB xxxX ),,( 1343?
4′,枢轴
1x 2x 3x 4x 5x
1
0
0
2/1
2/1
2/3
0
1
0
0
0
1
2
100
2
30
1
5
55
1
3
4
x
x
xz
)( 3BT
2/1
2/1
2/1?
5,4,3,2,1,00 jy j?
,)0,5,5,0,1( TX最优解
5z最优目标值
＃
第一块单纯形表可由初等变换得到：
CXz?
bAX?将 改写成,
bNXBXz
XCXCz
NB
NNBB
0
0
系数矩阵
)(BT
NBb
CC NB0
NBIbB
CC NB
11
0
NBIbB
CNBCObBC NBB
11
11
单纯形表避免了计算逆矩阵和矩阵的积。
Ab
C0
例 用单纯形法求以下问题的最优解
4321 32m i n xxxxz
123,31 xxts
0,,,4321?xxxx
2052 321 xxx
102 4321 xxxx
解,
1121
0512
0301
A
),,( 4311 PPPB?取系数阵,?
Ab
C0
112110
051220
030112
13210
1x 2x 3x 4x
不知是否可行
12202
01104
030112
102012
10006
01104
00310
00206
)( 1BT
,0202y? 入基。2P?,0
12
10
y
y又 出基。
1P?
得 ),,( 4322 PPPB?
10006
0103/14
0013/10
0003/26
)(
2
BT
,)6,4,0,0( TX
6z
为枢轴元12y
＃
注,· 第一个可行基的获得 — 人造变量法 ；
· 同时获得第一个可行基和第一章单纯形表
— 二阶段法 。
