线性规划
线性规划模型.1
标准型.2
解的概念和性质.4
单纯形算法.5
图解法.3
线性规划模型一,
生产计划问题例 1
利润最大？生产计划，才能使所获
安排千元。问：该厂应如何、、单位产品的利润为、、
同，如下表。耗费的加工时间各不相产品所需材料的数量和
三种产品，它们的单位、、生产某工厂利用某种原材料
754CBA
CBA
产品
资源
原材料
工时
A B C 资源总量
2
1
5.1
2
3
2
100
150
解：
确定目标函数.2
确定决策变量.1
。、、的产量分别为、、设 321 xxxCBA
，则设总利润为 S
321 754 xxxS ???
确定约束条件.3
1 0 035.12 321 ??? xxx
3,2,1,0
15022 321
??
???
ix
xxx
i
数学模型.4 321 754m in xxxS ???
??
?
?
?
??
???
???
3,2,1,0
15022
10035.12
.,321
321
ix
xxx
xxx
ts
i
线性规划模型：
一组决策变量；)1(
一个线性目标函数；)2(
一组线性的约束条件。)3(
的一般形式：线性规划模型 )( LP
?
?
n
i
ii xc
1
(m ax )m i n
?
?
?
?
??
?
?
?
????
??????
??????
??????
nix
bxaxaxa
bxaxaxa
bxaxaxa
ts
i
mnmnmm
nn
nn
,,2,1,0),(
),(
),(
),(
..
2211
22222121
11212111
?
?
?
?
?
标准型二,
标准型.1
?
?
n
i
ii xc
1
m a x
?
?
?
?
??
?
?
?
??
????
????
????
nix
bxaxaxa
bxaxaxa
bxaxaxa
ts
i
mnmnmm
nn
nn
,,2,1,0
..
2211
22222121
11212111
?
?
?
?
?
记为。则线性规划标准型可
记
nmij
T
n
T
m
T
n
aA
xxxxbbbbcccc
??
???
)(
,),,,(,),,,(,),,,( 212121 ???
xcTm ax
??
?
?
?
0.,x
bAxts
化标准型.2
目标函数：)1(
xc Tm in:目标函数原问题 xc T?? m a x
约束条件：)2(
ininii bxaxaxai ???? ?2211)(,原问题条件
??
?
?
??????
?
?
0
2211
in
iinninii
x
bxxaxaxa ?称为松弛变量。
inx ?
ininii bxaxaxaii ???? ?2211)(,原问题条件
??
?
?
??????
?
?
0
2211
in
iinninii
x
bxxaxaxa ?称为剩余变量。inx ?
。无非负约束，则令：原问题 ??? ??? 0,)(
ii
iiii
vu
vuxxi i i
为标准型。将下述线性规划模型化例 1
4321 332m i n xxxx ???
?
?
?
?
?
?
?
?
?????
???
????
无约束2431
4321
421
4321
,0,,
634
7223
332
..
xxxx
xxxx
xxx
xxxx
ts
解,则令,222 vux ??
43221 3332m a x xxvux ?????
?
?
?
?
?
?
?
?
???????
????
??????
0,,,,,,
6344
72223
332
..
2275431
743221
4221
543221
vuxxxxx
xxxvux
xvux
xxxvux
ts
图解法三,
求解线性规划例 2
?
?
?
?
?
?
??
??
??
0,
52
42
..
34m a x
21
21
21
21
xx
xx
xx
ts
xxz
解,。画出可行解的范围)1(
1x
2x
o
A B
C
求极值点。利用等值线平移的方法)2(
表示一族等值平行线。
为参数，则方程以 zxxz ?? 21 34
42 21 ?? xx
52 21 ?? xx
。顶点极大值点为 B?
。中的目标函数改为将例例 21 223 xxz ??
1x
2x
o
A B
C 42 21 ?? xx
52 21 ?? xx
解,。分析同例 2
。等值线,zxx ?? 21 2
任一点。
上的极大值点为线段 AB?
1x
2x
o
A
B
C
221 ?? xx
221 ?? xx
解,。分析同例 2
。等值线,zxx ?? 21 34
求解线性规划例 4
?
?
?
?
?
?
??
??
??
0,
2
2
..
34m a x
21
21
21
21
xx
xx
xx
ts
xxz
不存在最大值。?
结果：
线性规划问题的解 ?
?
?
?
?
?
无最优解
有最优解
??
??
有无穷多最优解
在顶点取到唯一最优解
??
??
可行域为空集
解无界
优解？，是否在顶点中存在最对一般的线性规划问题
质线性规划解的概念和性四,
线性规划解的概念.1
)(LP xcz T?m a x
??
?
?
?
0.,x
bAxts
)1(
)2(
)3(
的可行解。
称为）式的解）、（满足（可行解：
)(
),,,(32 21
LP
xxxx Tn??
。可行域,}0,|{ ??? xbAxxD
定理 是凸集。线性规划问题的可行域 D
证明,。任取 10,,21 ??? ?Dxx
2121 )1())1(( AxAxxxA ???? ?????
b
bb
?
??? )1( ??
是凸集。。即所以 DDxx ??? 21 )1( ??
的一个顶点。为则称，使
。及，。如果不存在为凸集，设顶点：
Sxxxx
SxxSxS
21
21
)1(
10
??
?
???
?????
x
1x
2x
一个基。问题或的为退化子阵，则称
阶的非中为若。秩为的系数矩阵为设基
))((
,:
LPAB
mmABmnmA ??
非基变量。
的变量称为为基变量，不是基变量对应的变量
为基向量，称称设基
),,1(
),,1(,),,,( 21
mjx
PmjPPPPB
j
ijijimii
?
??
?
??
为基变量。为基，则
取列向量线性无关，则可的前不妨设，已知
mm
nm
xxPPPB
mAmAr
,,),,,(
)(
121 ???
??
bAx?因为
即 bxPxPxPxP nnmmmm ?????? ? ?? 111
所以 nnmmmm xPxPbxPxP ?????? ? ?? 111
解得令非基变量,01 ???? nm xx ?
bBxx Tm 11 ),,( ???
的基本解。为对应于基称解变量的取值
得基，令非基变量取零，求取定线性规划问题的基基本解：
BbBbB
B
T)0,(,11 ??
解。的基本解称为基本可行基本可行解：满足条件 )3(
问题给定例 )( LP
?
?
?
?
?
?
????
????
????
0,,,
2222
842
..
22m a x
4321
4321
4321
4321
xxxx
xxxx
xxxx
ts
xxxxz
和一个基本可行解。求此问题的一个基本解
解,。系数矩阵 ?????? ????? 1222 4121A
得，则令非基变量取,022 21 43 ???????? ?? xxB
??
?
??
??
222
82
21
21
xx
xx
?
?
?
?
?
??
?
?
3
7
3
10
2
1
x
x
可行解。是基本解，但不是基本Tx )0,0,3 7,310(1 ???
得，则令非基变量取,012 41 32 ???????? ?? xxB
??
?
??
??
22
84
41
41
xx
xx
?
?
?
?
?
?
?
?
9
14
9
16
4
1
x
x
是基本可行解。Tx )914,0,0,916(2 ??
可行解 基本解基本可行解
mnC?基本解数量
定存在最优解？是否在基本可行解中一
线性规划解的性质.2
的顶点。可行域是是
要条件是基本可行解的充分必的解线性规划问题定理
Dx
xLP )(
基本可行解。如果有可行解，则必有线性规划问题定理 )( LP
可行解。
最优的基本如果有最优解，则必有线性规划问题定理 )( LP
单纯形算法五,
判断出不存在最优解。直到找到最优解，或者
基本可行解，则转换到另一个更好的是则算法结束。不是，
。，判断其是否为最优解从一个基本可行解开始算法思路：.1
问题：
行解？如何得到第一个基本可)1(
最优解的判定法则？)2(
解？变换到另一个基本可行如何从一个基本可行解)3(
)(1 LP求解线性规划问题例
?
?
?
?
?
?
???
???
??
0,,,
52
42
..
34m a x
4321
421
321
21
xxxx
xxx
xxx
ts
xxZ
解,。系数矩阵 ??????? 1012 0121A
。和非基变量为和则基变量为令基 2143,,10 01 xxxxB ???????
??
?
???
????
214
213
25
24
xxx
xxx
代入目标函数得 21 340 xxz ???
单纯形算法分析.2
??
?
?
???
5
4,0
4
3
21 x
xxx 则令
。目标函数值。基本可行解 0)5,4,0,0( 11 ??? zx T
是否为最优解？ 利用目标函数分析。
21 340 xxz ????
大。则目标函数值就可以增取值可以增大为正数，
的和的系数为正数，因此若和目标函数中非基变量 2121 xxxx
??
?
???
???
214
213
25
24
xxx
xxx?
是否可以增大？不变，考察固定 12 xx
??
?
??
???
14
13
25
4
xx
xx
??
???
?
?
?
??
?
?
?
2
5
4
0
0
1
1
4
3
x
x
x
x?
2
5
1 ?? x
变为非基变量。变为基变量，。即时，且 4141 025 xxxx ??
?
?
?
?
?
???
???
?
421
423
2
1
2
1
2
5
2
1
2
3
2
3
xxx
xxx
??
?
???
???
214
213
25
24
xx
xxx
42 210 xxz ????
?
?
?
?
?
?
?
??
2
3
2
5
,0
3
1
42
x
x
xx 则令
。目标函数值。基本可行解 10)0,23,0,25( 22 ??? zx T
42 210 xxz ????
，则。固定增大的系数为正，考察能否因为 422 xxx
?
?
?
?
?
???
???
421
423
2
1
2
1
2
5
2
1
2
3
2
3
xxx
xxx
?
?
?
?
?
??
??
?
21
23
2
1
2
5
2
3
2
3
xx
xx
12 ?? x
变为非基变量。变为基变量，。即时，且 3232 01 xxxx ??
?
?
?
?
?
???
???
?
431
432
3
2
3
12
3
1
3
21
xxx
xxx
43 3
5
3
211 xxz ????
??
?
?
???
1
2,0
2
1
43 x
xxx 则令
。目标函数值。基本可行解 11)0,0,1,2( 33 ??? zx T
增大，所以最优解为所以目标函数值不能再
的系数皆为负数，和其中因为目标函数 4343,353211 xxxxz ???
。最优的目标函数值为,11*)0,0,1,2(* 33 ???? zzxx T
最优解的判定条件)1(
)(LP ??? ni ii xcz 1m a x
?
?
?
?
??
?
?
?
??
????
????
????
nix
bxaxaxa
bxaxaxa
bxaxaxa
ts
i
mnmnmm
nn
nn
,,2,1,0
..
2211
22222121
11212111
?
?
?
?
?
?
?
?
?
?
?
?
??
??
?
?
??
??
n
mj
jmjmm
n
mj
jj
xabx
xabx
1
1
111
''
''
?
设经过迭代后有
为非基变量。为基变量，则 nmm xxxx,,,,11 ?? ?
)1(
代入目标函数得
?? ? ??? ?? ??? nmi iimi nmj jijii xcxabcz 11 1 )''(m ax
?? ??
??? ???
??? n
mj jj
m
i
n
mj jij
m
i iii
xcxacbc
11 11
)'('
?? ? ?
??? ?? ?
??? n
mj jj
m
i
n
mj jij
m
i iii
xcxacbc
11 1 1
)'('
? ? ?
? ?? ?
??? m
i
n
mj jij
m
i ijii
xaccbc
1 1 1
)'('
。则有令 ?? ?? ??? mi ijijjmi ii accbcz 110 ',' ?
? ???? nmj jj xzz 10 ?
为检验数。称 ),,1( nmjj ????
)2(
是最优解。，则，有且对任意的
的一个基本可行解。是对应于基若定理
*01
)0,,0,*,,*(* 1
xnjm
Bbbx
j
T
m
????
?
?
??
最优解。线性规划问题有无穷多
，则，且存在，有如果对任意的
的一个基本可行解。是对应于基设定理
)0(001
)0,,0,*,,*(* 1
??????
?
? knjm
Bbbx
kmj
T
m
??
??
无界。则原线性规划问题的解，
）式中（，且对任意的，如果存在
的一个基本可行解。是对应于基设定理
0'
1,,1)1(0
)0,,0,*,,*(*
,
1
?
?????
?
?
?
kmi
km
T
m
a
mimnk
Bbbx
?
??
?
）式由（证明,2 ?
????
n
mj jj xzz 10 ?
分析可证。
证明：
?
?
?
?
?
?
?
??
??
?
?
??
??
n
mj
jmjmm
n
mj
jj
xabx
xabx
1
1
111
''
''
1 ?）式由（
，则有固定，且对任意的 01 ?????? jxkmjnjm
?
?
?
??
?
?
??
??
??
??
kmkmmmm
kmkm
xabx
xabx
''
''
,
,111
?
则所以令因为,,),,1(0',Mxmia kmkmi ??? ?? ?
),,1(0'',mixabx kmkmiii ????? ??
仍为可行解。所以 Tm Mxxx )0,,0,,,0,,,( 1 ????
。所以 kmMzxz ??? ?0)(
所以因为,0?? km?
)()( 0 ???????? ? MMzxz km?
即线性规划的解无界。
基变换)2(
对应的变量，即若可选取最大的入基变量,j?
为入基变量。对应的也可任选
为入基变量。则选取
jj
kkjjj
x
x
0
,}0|{m a x
?
??
?
???
）式计算则由（设入基变量为离基变量,1,kx
'
'
}0'|'
'
{m i n
,
,
,kl
l
ki
ki
i
a
ba
a
b ????
为离基变量。选取 lx
单纯形表和单纯形算法.3
)(LP ? ???? nmi ii xzz 10m a x ?
?
?
?
?
??
?
?
?
??
????
????
????
??
??
??
nix
bxaxax
bxaxax
bxaxax
ts
i
mnmnmmmm
nnmm
nnmm
,,2,1,0
..
11,
2211,22
1111,11
?
?
?
?
?
形式：约束条件已改写为如下
为基变量，且其），不妨设给定线性规划问题（ mxxLP,,1 ?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
01
1,
221,2
111,1
000
100
010
001
z
baa
baa
baa
nm
mmnmm
nm
nm
?? ??
??
?????
??
??
1x 2x mx 1?mx nx b
单纯形表：
函数值的相反数。
可行解对应的目标列的元素表示当前基本、行）第（
当前基变量的取值；）最后一列的元素对应（
数为零；行，其中基变量的检验）最后一行称为检验数（
的变量为基变量；作为基矩阵，它所对应）包含一个单位子矩阵（
单纯形表的结构：
114
3
2
1
?? nm
单纯形算法步骤：
建立初始单纯形表。确定初始基本可行解，）（ 1
）。否则转（是最优解，算法结束；则当前的基本可行解就
，数。如果检验各非基变量的检验）（
3
),,1(02 nmjj ?????
）。（界，算法结束；否则转则线性规划问题的解无
，的系数列向量使得其对应的变量）如果存在（
4
003 ?? kkk Px?
为入基变量。计算选取设 kkj x,)0(m a x)4( ?? ??
lk
lik
ik
i
a
ba
a
b ??? }0|{m i n?
）。为离基变量。转（选取 5lx
的列。其它元素为，
个系数列向量变换为变换将第为主元旋转。即利用行）以（
01
5
?lk
lk
a
ka
)(2 LP求解线性规划问题例
?
?
?
?
?
?
???
???
???
0,,
824
63
..
2m a x
321
321
321
321
xxx
xxx
xxx
ts
xxxZ
解,化标准型：
?
?
?
?
?
?
????
????
???
0,,,,
824
63
..
2m a x
54321
5321
4321
321
xxxxx
xxxx
xxxx
ts
xxxZ
第一次迭代：
?
?
?
?
?
?
?
?
?
?
?
?
?
000112
810124
601131
初始单纯形表：
1x 2x 3x 4x 5x b 。基变量 54,xx?
。目标函数值
基本可行解
0
,)8,6,0,0,0(
1
1
?
?
z
x T
031 ???,?
不是最优解。1x?
为入基变量，则取 3x 。818 ???
为离基变量。取 5x?
为主元进行旋转。以 23a
第二次迭代：
单纯形表：
?
?
?
?
?
?
?
?
?
?
???
?
810012
810124
14110151x 2x 3x 4x 5x b 。基变量
43,xx?
。目标函数值
基本可行解
8
,)0,14,8,0,0(
2
2
?
?
z
x T
02 ???
不是最优解。2x?
为入基变量，则取 2x 。14114 ???
为离基变量。取 4x?
为主元进行旋转。以 12a
第三次迭代：
单纯形表：
?
?
?
?
?
?
?
?
?
?
???? 2221007
36321014
14110151x 2x 3x 4x 5x b 。基变量
32,xx?
。目标函数值
基本可行解
22
,)0,0,36,14,0(
3
3
?
?
z
x T
。5,,1,0 ?? ?? ii?
。函数值为即为最优解。最优目标 2233 ?? zx
初始基本可行解的计算.4
法大 M
)(LP ??? ni ii xcz 1m a x
?
?
?
?
??
?
?
?
??
????
????
????
nix
bxaxaxa
bxaxaxa
bxaxaxa
ts
i
mnmnmm
nn
nn
,,2,1,0
..
2211
22222121
11212111
?
?
?
?
?
规划问题个人工变量，得新线性对每个约束条件增加一
)'(LP ?? ?? ???? ni mnnii MxMxxcz 1 1m a x ?
?
?
?
?
??
?
?
?
???
?????
?????
?????
?
?
?
mnix
bxxaxaxa
bxxaxaxa
bxxaxaxa
ts
i
mmnnmnmm
nnn
nnn
,,2,1,0
..
2211
222222121
111212111
?
?
?
?
?
为充分大的正数。其中 M
为初始的基变量。）问题中可以取则在（ mnn xxLP ??,,' 1 ?
的最优解。
）问题原（变量，则此最优解也是基变量中必不包含人工
最优的基本可行解的）问题存在最优解，则结论：如果（
LP
LP '
)(3 LP求解线性规划问题例
?
?
?
?
?
?
??
???
???
0,,
24
422
..
232m a x
321
32
321
321
xxx
xx
xxx
ts
xxxZ
解：
?
?
?
?
?
?
???
???
????
0,,,
24
422
..
232m a x
4321
432
321
4321
xxxx
xxx
xxx
ts
MxxxxZ
）（ 'LP
第一次迭代：
初始单纯形表：
1x 2x 3x 4x b
。基变量 41,xx?
。目标函数值基本可行解 Mzx T 28,)2,0,0,4( 11 ???
?
?
?
?
?
?
?
?
?
?
??
?
0232
21140
40221
M
1x 2x 3x 4x b
?
?
?
?
?
?
?
?
?
?
????
??
8206140
21140
40221
MMM
02 ??? 不是最优解。1x?
为入基变量，则取 2x 。21}42,24{m i n ???
为离基变量。取 4x?
为主元进行旋转。以 22a
第二次迭代：
1x 2x 3x 4x b
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
?
?
?
2
15
4
1
4
25
00
2
1
4
1
4
1
10
3
2
1
2
5
01
M
。基变量 21,xx?
。目标函数值
基本可行解
2
15
,)0,0,
2
1
,3(
2
2
?
?
z
x T
。4,,1,0 ?? ?? ii?
。函数值为即为最优解。最优目标 21522 ?? zx
线性规划模型.1
标准型.2
解的概念和性质.4
单纯形算法.5
图解法.3
线性规划模型一,
生产计划问题例 1
利润最大？生产计划，才能使所获
安排千元。问：该厂应如何、、单位产品的利润为、、
同，如下表。耗费的加工时间各不相产品所需材料的数量和
三种产品，它们的单位、、生产某工厂利用某种原材料
754CBA
CBA
产品
资源
原材料
工时
A B C 资源总量
2
1
5.1
2
3
2
100
150
解：
确定目标函数.2
确定决策变量.1
。、、的产量分别为、、设 321 xxxCBA
，则设总利润为 S
321 754 xxxS ???
确定约束条件.3
1 0 035.12 321 ??? xxx
3,2,1,0
15022 321
??
???
ix
xxx
i
数学模型.4 321 754m in xxxS ???
??
?
?
?
??
???
???
3,2,1,0
15022
10035.12
.,321
321
ix
xxx
xxx
ts
i
线性规划模型：
一组决策变量；)1(
一个线性目标函数；)2(
一组线性的约束条件。)3(
的一般形式：线性规划模型 )( LP
?
?
n
i
ii xc
1
(m ax )m i n
?
?
?
?
??
?
?
?
????
??????
??????
??????
nix
bxaxaxa
bxaxaxa
bxaxaxa
ts
i
mnmnmm
nn
nn
,,2,1,0),(
),(
),(
),(
..
2211
22222121
11212111
?
?
?
?
?
标准型二,
标准型.1
?
?
n
i
ii xc
1
m a x
?
?
?
?
??
?
?
?
??
????
????
????
nix
bxaxaxa
bxaxaxa
bxaxaxa
ts
i
mnmnmm
nn
nn
,,2,1,0
..
2211
22222121
11212111
?
?
?
?
?
记为。则线性规划标准型可
记
nmij
T
n
T
m
T
n
aA
xxxxbbbbcccc
??
???
)(
,),,,(,),,,(,),,,( 212121 ???
xcTm ax
??
?
?
?
0.,x
bAxts
化标准型.2
目标函数：)1(
xc Tm in:目标函数原问题 xc T?? m a x
约束条件：)2(
ininii bxaxaxai ???? ?2211)(,原问题条件
??
?
?
??????
?
?
0
2211
in
iinninii
x
bxxaxaxa ?称为松弛变量。
inx ?
ininii bxaxaxaii ???? ?2211)(,原问题条件
??
?
?
??????
?
?
0
2211
in
iinninii
x
bxxaxaxa ?称为剩余变量。inx ?
。无非负约束，则令：原问题 ??? ??? 0,)(
ii
iiii
vu
vuxxi i i
为标准型。将下述线性规划模型化例 1
4321 332m i n xxxx ???
?
?
?
?
?
?
?
?
?????
???
????
无约束2431
4321
421
4321
,0,,
634
7223
332
..
xxxx
xxxx
xxx
xxxx
ts
解,则令,222 vux ??
43221 3332m a x xxvux ?????
?
?
?
?
?
?
?
?
???????
????
??????
0,,,,,,
6344
72223
332
..
2275431
743221
4221
543221
vuxxxxx
xxxvux
xvux
xxxvux
ts
图解法三,
求解线性规划例 2
?
?
?
?
?
?
??
??
??
0,
52
42
..
34m a x
21
21
21
21
xx
xx
xx
ts
xxz
解,。画出可行解的范围)1(
1x
2x
o
A B
C
求极值点。利用等值线平移的方法)2(
表示一族等值平行线。
为参数，则方程以 zxxz ?? 21 34
42 21 ?? xx
52 21 ?? xx
。顶点极大值点为 B?
。中的目标函数改为将例例 21 223 xxz ??
1x
2x
o
A B
C 42 21 ?? xx
52 21 ?? xx
解,。分析同例 2
。等值线,zxx ?? 21 2
任一点。
上的极大值点为线段 AB?
1x
2x
o
A
B
C
221 ?? xx
221 ?? xx
解,。分析同例 2
。等值线,zxx ?? 21 34
求解线性规划例 4
?
?
?
?
?
?
??
??
??
0,
2
2
..
34m a x
21
21
21
21
xx
xx
xx
ts
xxz
不存在最大值。?
结果：
线性规划问题的解 ?
?
?
?
?
?
无最优解
有最优解
??
??
有无穷多最优解
在顶点取到唯一最优解
??
??
可行域为空集
解无界
优解？，是否在顶点中存在最对一般的线性规划问题
质线性规划解的概念和性四,
线性规划解的概念.1
)(LP xcz T?m a x
??
?
?
?
0.,x
bAxts
)1(
)2(
)3(
的可行解。
称为）式的解）、（满足（可行解：
)(
),,,(32 21
LP
xxxx Tn??
。可行域,}0,|{ ??? xbAxxD
定理 是凸集。线性规划问题的可行域 D
证明,。任取 10,,21 ??? ?Dxx
2121 )1())1(( AxAxxxA ???? ?????
b
bb
?
??? )1( ??
是凸集。。即所以 DDxx ??? 21 )1( ??
的一个顶点。为则称，使
。及，。如果不存在为凸集，设顶点：
Sxxxx
SxxSxS
21
21
)1(
10
??
?
???
?????
x
1x
2x
一个基。问题或的为退化子阵，则称
阶的非中为若。秩为的系数矩阵为设基
))((
,:
LPAB
mmABmnmA ??
非基变量。
的变量称为为基变量，不是基变量对应的变量
为基向量，称称设基
),,1(
),,1(,),,,( 21
mjx
PmjPPPPB
j
ijijimii
?
??
?
??
为基变量。为基，则
取列向量线性无关，则可的前不妨设，已知
mm
nm
xxPPPB
mAmAr
,,),,,(
)(
121 ???
??
bAx?因为
即 bxPxPxPxP nnmmmm ?????? ? ?? 111
所以 nnmmmm xPxPbxPxP ?????? ? ?? 111
解得令非基变量,01 ???? nm xx ?
bBxx Tm 11 ),,( ???
的基本解。为对应于基称解变量的取值
得基，令非基变量取零，求取定线性规划问题的基基本解：
BbBbB
B
T)0,(,11 ??
解。的基本解称为基本可行基本可行解：满足条件 )3(
问题给定例 )( LP
?
?
?
?
?
?
????
????
????
0,,,
2222
842
..
22m a x
4321
4321
4321
4321
xxxx
xxxx
xxxx
ts
xxxxz
和一个基本可行解。求此问题的一个基本解
解,。系数矩阵 ?????? ????? 1222 4121A
得，则令非基变量取,022 21 43 ???????? ?? xxB
??
?
??
??
222
82
21
21
xx
xx
?
?
?
?
?
??
?
?
3
7
3
10
2
1
x
x
可行解。是基本解，但不是基本Tx )0,0,3 7,310(1 ???
得，则令非基变量取,012 41 32 ???????? ?? xxB
??
?
??
??
22
84
41
41
xx
xx
?
?
?
?
?
?
?
?
9
14
9
16
4
1
x
x
是基本可行解。Tx )914,0,0,916(2 ??
可行解 基本解基本可行解
mnC?基本解数量
定存在最优解？是否在基本可行解中一
线性规划解的性质.2
的顶点。可行域是是
要条件是基本可行解的充分必的解线性规划问题定理
Dx
xLP )(
基本可行解。如果有可行解，则必有线性规划问题定理 )( LP
可行解。
最优的基本如果有最优解，则必有线性规划问题定理 )( LP
单纯形算法五,
判断出不存在最优解。直到找到最优解，或者
基本可行解，则转换到另一个更好的是则算法结束。不是，
。，判断其是否为最优解从一个基本可行解开始算法思路：.1
问题：
行解？如何得到第一个基本可)1(
最优解的判定法则？)2(
解？变换到另一个基本可行如何从一个基本可行解)3(
)(1 LP求解线性规划问题例
?
?
?
?
?
?
???
???
??
0,,,
52
42
..
34m a x
4321
421
321
21
xxxx
xxx
xxx
ts
xxZ
解,。系数矩阵 ??????? 1012 0121A
。和非基变量为和则基变量为令基 2143,,10 01 xxxxB ???????
??
?
???
????
214
213
25
24
xxx
xxx
代入目标函数得 21 340 xxz ???
单纯形算法分析.2
??
?
?
???
5
4,0
4
3
21 x
xxx 则令
。目标函数值。基本可行解 0)5,4,0,0( 11 ??? zx T
是否为最优解？ 利用目标函数分析。
21 340 xxz ????
大。则目标函数值就可以增取值可以增大为正数，
的和的系数为正数，因此若和目标函数中非基变量 2121 xxxx
??
?
???
???
214
213
25
24
xxx
xxx?
是否可以增大？不变，考察固定 12 xx
??
?
??
???
14
13
25
4
xx
xx
??
???
?
?
?
??
?
?
?
2
5
4
0
0
1
1
4
3
x
x
x
x?
2
5
1 ?? x
变为非基变量。变为基变量，。即时，且 4141 025 xxxx ??
?
?
?
?
?
???
???
?
421
423
2
1
2
1
2
5
2
1
2
3
2
3
xxx
xxx
??
?
???
???
214
213
25
24
xx
xxx
42 210 xxz ????
?
?
?
?
?
?
?
??
2
3
2
5
,0
3
1
42
x
x
xx 则令
。目标函数值。基本可行解 10)0,23,0,25( 22 ??? zx T
42 210 xxz ????
，则。固定增大的系数为正，考察能否因为 422 xxx
?
?
?
?
?
???
???
421
423
2
1
2
1
2
5
2
1
2
3
2
3
xxx
xxx
?
?
?
?
?
??
??
?
21
23
2
1
2
5
2
3
2
3
xx
xx
12 ?? x
变为非基变量。变为基变量，。即时，且 3232 01 xxxx ??
?
?
?
?
?
???
???
?
431
432
3
2
3
12
3
1
3
21
xxx
xxx
43 3
5
3
211 xxz ????
??
?
?
???
1
2,0
2
1
43 x
xxx 则令
。目标函数值。基本可行解 11)0,0,1,2( 33 ??? zx T
增大，所以最优解为所以目标函数值不能再
的系数皆为负数，和其中因为目标函数 4343,353211 xxxxz ???
。最优的目标函数值为,11*)0,0,1,2(* 33 ???? zzxx T
最优解的判定条件)1(
)(LP ??? ni ii xcz 1m a x
?
?
?
?
??
?
?
?
??
????
????
????
nix
bxaxaxa
bxaxaxa
bxaxaxa
ts
i
mnmnmm
nn
nn
,,2,1,0
..
2211
22222121
11212111
?
?
?
?
?
?
?
?
?
?
?
?
??
??
?
?
??
??
n
mj
jmjmm
n
mj
jj
xabx
xabx
1
1
111
''
''
?
设经过迭代后有
为非基变量。为基变量，则 nmm xxxx,,,,11 ?? ?
)1(
代入目标函数得
?? ? ??? ?? ??? nmi iimi nmj jijii xcxabcz 11 1 )''(m ax
?? ??
??? ???
??? n
mj jj
m
i
n
mj jij
m
i iii
xcxacbc
11 11
)'('
?? ? ?
??? ?? ?
??? n
mj jj
m
i
n
mj jij
m
i iii
xcxacbc
11 1 1
)'('
? ? ?
? ?? ?
??? m
i
n
mj jij
m
i ijii
xaccbc
1 1 1
)'('
。则有令 ?? ?? ??? mi ijijjmi ii accbcz 110 ',' ?
? ???? nmj jj xzz 10 ?
为检验数。称 ),,1( nmjj ????
)2(
是最优解。，则，有且对任意的
的一个基本可行解。是对应于基若定理
*01
)0,,0,*,,*(* 1
xnjm
Bbbx
j
T
m
????
?
?
??
最优解。线性规划问题有无穷多
，则，且存在，有如果对任意的
的一个基本可行解。是对应于基设定理
)0(001
)0,,0,*,,*(* 1
??????
?
? knjm
Bbbx
kmj
T
m
??
??
无界。则原线性规划问题的解，
）式中（，且对任意的，如果存在
的一个基本可行解。是对应于基设定理
0'
1,,1)1(0
)0,,0,*,,*(*
,
1
?
?????
?
?
?
kmi
km
T
m
a
mimnk
Bbbx
?
??
?
）式由（证明,2 ?
????
n
mj jj xzz 10 ?
分析可证。
证明：
?
?
?
?
?
?
?
??
??
?
?
??
??
n
mj
jmjmm
n
mj
jj
xabx
xabx
1
1
111
''
''
1 ?）式由（
，则有固定，且对任意的 01 ?????? jxkmjnjm
?
?
?
??
?
?
??
??
??
??
kmkmmmm
kmkm
xabx
xabx
''
''
,
,111
?
则所以令因为,,),,1(0',Mxmia kmkmi ??? ?? ?
),,1(0'',mixabx kmkmiii ????? ??
仍为可行解。所以 Tm Mxxx )0,,0,,,0,,,( 1 ????
。所以 kmMzxz ??? ?0)(
所以因为,0?? km?
)()( 0 ???????? ? MMzxz km?
即线性规划的解无界。
基变换)2(
对应的变量，即若可选取最大的入基变量,j?
为入基变量。对应的也可任选
为入基变量。则选取
jj
kkjjj
x
x
0
,}0|{m a x
?
??
?
???
）式计算则由（设入基变量为离基变量,1,kx
'
'
}0'|'
'
{m i n
,
,
,kl
l
ki
ki
i
a
ba
a
b ????
为离基变量。选取 lx
单纯形表和单纯形算法.3
)(LP ? ???? nmi ii xzz 10m a x ?
?
?
?
?
??
?
?
?
??
????
????
????
??
??
??
nix
bxaxax
bxaxax
bxaxax
ts
i
mnmnmmmm
nnmm
nnmm
,,2,1,0
..
11,
2211,22
1111,11
?
?
?
?
?
形式：约束条件已改写为如下
为基变量，且其），不妨设给定线性规划问题（ mxxLP,,1 ?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
01
1,
221,2
111,1
000
100
010
001
z
baa
baa
baa
nm
mmnmm
nm
nm
?? ??
??
?????
??
??
1x 2x mx 1?mx nx b
单纯形表：
函数值的相反数。
可行解对应的目标列的元素表示当前基本、行）第（
当前基变量的取值；）最后一列的元素对应（
数为零；行，其中基变量的检验）最后一行称为检验数（
的变量为基变量；作为基矩阵，它所对应）包含一个单位子矩阵（
单纯形表的结构：
114
3
2
1
?? nm
单纯形算法步骤：
建立初始单纯形表。确定初始基本可行解，）（ 1
）。否则转（是最优解，算法结束；则当前的基本可行解就
，数。如果检验各非基变量的检验）（
3
),,1(02 nmjj ?????
）。（界，算法结束；否则转则线性规划问题的解无
，的系数列向量使得其对应的变量）如果存在（
4
003 ?? kkk Px?
为入基变量。计算选取设 kkj x,)0(m a x)4( ?? ??
lk
lik
ik
i
a
ba
a
b ??? }0|{m i n?
）。为离基变量。转（选取 5lx
的列。其它元素为，
个系数列向量变换为变换将第为主元旋转。即利用行）以（
01
5
?lk
lk
a
ka
)(2 LP求解线性规划问题例
?
?
?
?
?
?
???
???
???
0,,
824
63
..
2m a x
321
321
321
321
xxx
xxx
xxx
ts
xxxZ
解,化标准型：
?
?
?
?
?
?
????
????
???
0,,,,
824
63
..
2m a x
54321
5321
4321
321
xxxxx
xxxx
xxxx
ts
xxxZ
第一次迭代：
?
?
?
?
?
?
?
?
?
?
?
?
?
000112
810124
601131
初始单纯形表：
1x 2x 3x 4x 5x b 。基变量 54,xx?
。目标函数值
基本可行解
0
,)8,6,0,0,0(
1
1
?
?
z
x T
031 ???,?
不是最优解。1x?
为入基变量，则取 3x 。818 ???
为离基变量。取 5x?
为主元进行旋转。以 23a
第二次迭代：
单纯形表：
?
?
?
?
?
?
?
?
?
?
???
?
810012
810124
14110151x 2x 3x 4x 5x b 。基变量
43,xx?
。目标函数值
基本可行解
8
,)0,14,8,0,0(
2
2
?
?
z
x T
02 ???
不是最优解。2x?
为入基变量，则取 2x 。14114 ???
为离基变量。取 4x?
为主元进行旋转。以 12a
第三次迭代：
单纯形表：
?
?
?
?
?
?
?
?
?
?
???? 2221007
36321014
14110151x 2x 3x 4x 5x b 。基变量
32,xx?
。目标函数值
基本可行解
22
,)0,0,36,14,0(
3
3
?
?
z
x T
。5,,1,0 ?? ?? ii?
。函数值为即为最优解。最优目标 2233 ?? zx
初始基本可行解的计算.4
法大 M
)(LP ??? ni ii xcz 1m a x
?
?
?
?
??
?
?
?
??
????
????
????
nix
bxaxaxa
bxaxaxa
bxaxaxa
ts
i
mnmnmm
nn
nn
,,2,1,0
..
2211
22222121
11212111
?
?
?
?
?
规划问题个人工变量，得新线性对每个约束条件增加一
)'(LP ?? ?? ???? ni mnnii MxMxxcz 1 1m a x ?
?
?
?
?
??
?
?
?
???
?????
?????
?????
?
?
?
mnix
bxxaxaxa
bxxaxaxa
bxxaxaxa
ts
i
mmnnmnmm
nnn
nnn
,,2,1,0
..
2211
222222121
111212111
?
?
?
?
?
为充分大的正数。其中 M
为初始的基变量。）问题中可以取则在（ mnn xxLP ??,,' 1 ?
的最优解。
）问题原（变量，则此最优解也是基变量中必不包含人工
最优的基本可行解的）问题存在最优解，则结论：如果（
LP
LP '
)(3 LP求解线性规划问题例
?
?
?
?
?
?
??
???
???
0,,
24
422
..
232m a x
321
32
321
321
xxx
xx
xxx
ts
xxxZ
解：
?
?
?
?
?
?
???
???
????
0,,,
24
422
..
232m a x
4321
432
321
4321
xxxx
xxx
xxx
ts
MxxxxZ
）（ 'LP
第一次迭代：
初始单纯形表：
1x 2x 3x 4x b
。基变量 41,xx?
。目标函数值基本可行解 Mzx T 28,)2,0,0,4( 11 ???
?
?
?
?
?
?
?
?
?
?
??
?
0232
21140
40221
M
1x 2x 3x 4x b
?
?
?
?
?
?
?
?
?
?
????
??
8206140
21140
40221
MMM
02 ??? 不是最优解。1x?
为入基变量，则取 2x 。21}42,24{m i n ???
为离基变量。取 4x?
为主元进行旋转。以 22a
第二次迭代：
1x 2x 3x 4x b
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
?
?
?
2
15
4
1
4
25
00
2
1
4
1
4
1
10
3
2
1
2
5
01
M
。基变量 21,xx?
。目标函数值
基本可行解
2
15
,)0,0,
2
1
,3(
2
2
?
?
z
x T
。4,,1,0 ?? ?? ii?
。函数值为即为最优解。最优目标 21522 ?? zx
