第二节 单纯形法单纯形法是求解线性规划的主要算法,1947
年由美国斯坦福大学教授丹捷格（ G.B.Danzig）
提出。
尽管在其后的几十年中，又有一些算法问世，
但单纯形法以其简单实用的特色始终保持着绝对的“市场”占有率。
1.线性规划的标准型用单纯形法求解线性规划的前提是先将模型化为标准型：
0
..
X
bAX
ts
CXM a xz
标准型的特征,Max型、等式约束、非负约束一、单纯形法的预备知识
。）（的秩为其中,0, bnmmA
非标准形式如何化为标准
1) Min型化为 Max型
CXM in z? CXM ax z/
加负号因为，求一个函数的极小点，等价于求该函数的负函数的极大点。
)(xf
)(xf?
*x
注意,Min型化为 Max型求解后，最优解不变，但最优值差负号。
2) 不等式约束化为等式约束分析,以例 1中煤的约束为例
3 6 049 21 xx
之所以“不等”是因为左右两边有一个差额，称为“松弛量”，若在左边加上这个松弛量，则化为等式。而这个松弛量也是变量，记为 X3,则有
3 6 049 321 xxx
X3称为松弛变量。问题,它的实际意义是什么？
—— 煤资源的“剩余”。
练习：请将例 1的约束化为标准型
0,
3 0 0103
2 0 054
3 6 049
..
21
21
21
21
xx
xx
xx
xx
ts
解：增加松弛变量 则约束化为,,,
543 xxx
0,,,,
300 103
20054
360 49
..
543
21
5
21
4
21
3
21
xxxxx
xxx
xxx
xxx
ts
易见，增加的松弛变量的系数恰构成一个单位阵 I。
一般地，记松弛变量的向量为 Xs，则
0.,X
bAXts
0,.,s
s
XX
bIXAXts
0.,X
bAXts
0,.,s
s
XX
bIXAXts
问题：松弛变量在目标中的系数为何？ —— 0。
3) 当模型中有某变量 xk 没有非负要求,称为自由变量,则可令 0,,//////
kkkkk xxxxx
化为标准型。
2.基本概念
（ 1）可行解与最优解；的解，记为可行解：满足全体约束 X
。，有解则对任可行的，记为最优解：可行解中最优
*
,
CXCXX
X
直观上,可行解是可行域中的点，是一个可行的方案；
最优解是可行域的角点，是一个最优的方案。
（ 2）基矩阵与基变量基矩阵 (简称基 ),系数阵 A中的 m阶可逆子阵，记为 B；其余部分称为非基矩阵，记为 N。
基向量,基 B中的列；其余称非基向量。
基变量,与基向量 Pj对应的决策变量 xj,记其组成的向量为 XB；与非基向量对应的变量称非基变量，记其组成的向量为 XN。
1 2 3
1 2 4
14
3
2 1
2 3
,,0
x x x
x x x
xx
例,下 面 为 某 线 性 规 划 的 约 束请 例 举 出 其 基 矩 阵 和 相 应 的 基 向 量,基 变 量 。
1 2 3
1 2 4
14
3
21
23
,,0
x x x
x x x
xx
例,下 面 为 某 线 性 规 划 的 约 束请 例 举 出 其 基 矩 阵 和 相 应 的 基 向 量,基 变 量 。
阶可逆子阵有中的，解：本例中,2
1
0
0
1
1
2
2
1
AA?
—— 6个。
一般地,m× n 阶矩阵 A中基的个数最多有多少个？ 个。—— C;,,,
1
0
0
1
4
3
43431 1
x
x
XxxPPB,基变量为，其相应的基向量为
。基变量为其相应的基向量为?
2
1
21212 2
,,,,,
1
2
2
1
x
x
XxxPPB
问题：本例的 A中一共有几个基？
（ 3）基本解与基本可行解
.
0
,0,
,,
,
1
111
bB
XbBXXNXBbBX
b
X
X
NBbAXXXX
NBAmABBA
时，有当取即可表示为约束中的相应地
）（列，则可记中的前表示取定后，不妨设中的基当解；为线性规划的一个基本的解称?
0
bBXbAX
可见：一个基本解是由一个基决定的。
注意：基本解仅是资源约束的解，并未要求其非负，因此其未必可行。
称非负的基本解为 基本可行解 （简称基可行解）。
例 4：在上例中
0,,
32
12
41
421
321
xx
xxx
xxx
求相应于基 B1和 B2的基本解，它们是否基本可行解？
,31311001,1001,1001 111 bBBB解：
是基本可行解。的基本解为相应于基,)3,1,0,0(XB?
,
5
1-
5
7
3
1
5
1-
5
2
5
2
5
1
,
5
1-
5
2
5
2
5
1
,
1-
2
2
1 11
2
bBBB
不是基本可行解。的基本解为相应于基,,0,0 )51,-57(2 XB?
上二组概念间的联系：
系数阵 A中可找出若干个基 B
每个基 B都对应于一个基本解非负的基本解就是基本可行解几种解之间的关系：
可行解 基本解非可行解基本可行解问题：基本可行解是可行域中的哪些点？
3.基本定理
（ 1）线性规划的可行域是一个 凸 多面体。
（ 2）线性规划的最优解（若存在的话）必能在可行域的 角点 获得。
（ 3）线性规划可行域的 角点 与 基本可行解 一一对应。
二、单纯形法的步骤单纯形法是一种迭代的算法，它的思想是在可行域的角点 —— 基本可行解中寻优。由于角点是有限个（为什么？），因此，算法经有限步可终止。
确定一个初始基可行解检验这个基可行解是否最优寻找一个更好的基可行解否是 停止
1.确定初始基可行解由于基可行解是由一个可行基决定的，因此，
确定初始基可行解 X0相当于确定一个初始可行基 B0。
方法,若 A中含 I，则 B0=I；
若 A中不含 I，则可用人工变量法构造一个 I。
问题：若 B0=I，则 X0=？ 可行。,000 bbBX
2,最优性检验问题：用什么检验？ —— 目标。
XNBCCbBC
XCNXBbBC
X
X
CCCXz
)(
)()( 11而目标优。时，当前基可行解为最，则当记 01 NBCC
非最优。则当前解为最优；否则若的检验数方法：计算每个变量
0,
,1
PBCcx
问题：非最优的特征为何？ 。至少有某个检验数 0
3,寻找更好的基可行解由于基可行解与基对应，即寻找一个新的基可行解，相当于从上一个基 B0变换为下一个新的基 B1，因此，本步骤也称为基变换。
（基变换）
0bB
zz
可行：
改善：基变换的原则 ）变换的方法：（ PPPP,,,,,,
进基出基进基；对应的令保证“改善”进基 P0
可决定出基。由保证“可行”出基 011 NXBbBX
出基。对应的令进基；对应的方法：令
PPB
PB
bB
P
0)(
)(
)(
0
1
1
1
m i n
m a x
称作检验比。
以例 1为例，可按上述单纯形法的步骤求出其最优解，其大致的过程如下。
（ 1）先将模型化为标准型
0,,,,
300103
20054
36049
..
543
21
5
21
4
21
3
21
xxxxx
xxx
xxx
xxx
ts
21 127 xxM a x z
(2) 确定初始基可行解、检验;0 0,3 0 0 )( 0,0,3 6 0,2,00)( 3 6 0,2 0 0,3,
0
1
00
XbBB
1
1
1;,PP 向量为再计算检验比确定出基量为计算检验数确定进基向
（ 3）换基、计算下一个基可行解、再检验，直至最优;5 0,0 )( 0,2 4,2 4 0,,)( 2 4 0,5 0,3 0,
10
51
41
1
1
11
XbBB
;0,0 )( 2 0,2 4,8 4,,( 8 4,2 0,2 4 ),
103
54
491
2
1
22
XbBB
0
0;,41 PP 向量为再计算检验比确定出基量为计算检验数确定进基向前解为最优。计算检验数均非正，当问题：当模型规模较大时，计算量很大。
事实上，单纯形法的实现是在单纯形表上完成的。
练习：对于下面的线性规划
0,
62
2
2m in
xx
xx
xx
xxz
（ 1）用图解法求解；
（ 2）将模型化为标准型；
（ 3）用单纯形法步骤求出其最优解，并指出求解过程中每一个基可行解相当于可行域的哪一个角点。
三、单纯形表单纯形表是基于单纯形法的步骤设计的计算格式，是单纯形法的具体实现。
11
0
1
01
1
0
0 )(
)(
0 00 BPB
bBPBCcbBXB
m i n
回顾单纯形法步骤
bB?需计算 AB?需计算
,AbB 1?内容是因此，单纯形表的主体
1
2
1
1
1
0
AbB
AbB
AbB
即单纯形表。
变换迭代计算的由此设计了基于初等行得。也可通过初等行变换求邻两个只有一列不同，故相而相邻两个
1?B
B
单纯形表的主要结构：
X
C
AB?bB?
问题：第一张表的 B-1=？ —— 单位阵 I。
检验数的公式是什么？ PBCc
在哪里？PB? 列中的第 jAB 1
例 5：用单纯形法求解例 1
0,
3 0 0103
2 0 054
3 6 049
..
21
21
21
21
xx
xx
xx
xx
ts
21 127 xxM a x z
将模型化为标准型：解：增加松弛变量,,,543 xxx
0,,,,
300103
20054
36049
..
543
21
5
21
4
21
3
21
xxxxx
xxx
xxx
xxx
ts
21 127 xxM a x z
问题：标准模型的 A中是否含 I？ —— 松弛变量系数恰好构成 I。
54321 xxxxxbB?XC?
0 0 0 12 7
100103
01054
00149
300
200
360
x
x
x
0
0
0
0 0 0 12 7
[ ] 30
40
90
7;
3
4
9
0) 0 (07
1
1
11
pBCc?其中检验数 90
4
3 6 0
[ ] 中表示进基列与出基行的交叉元，下一张表将实行以它为主元的初等行变换（称高斯消去）。方法是：
先将主元消成 1，再用此 1将其所在列的其余元消成 0。
54321 xxxxxbB?XC?
0 0 0 12 7
100103
01054
00149
300
200
360
x
x
x
0
0
0
0 0 0 12 7
[ ] 30
40
90
0,1 0 0 1 0,3 30
0,4- 0 1 0 7,8 240
0,5- 1 0 0 2,5 50
2
4
3
x
x
x
12
0
0
1,2- 0 0 0 3,4
100
20
30.8
[ ]
0,2- 0,4 0 0 1 20
1,1 6 0,3 2- 1 0 0 84
0,1 6 0,1 2- 0 1 0 242
1
3
x
x
x
12
7
0
0,5 2- 1,3 6- 0 0 0
428.,0,0 )( 2 0,2 4,8 4,*zX （请解释其实际意义）
练习：用单纯形法求解下面的线性规划
0,
62
-2-
..
21
21
21
xx
xx
xx
ts
21 2- xxM in s
将模型化为标准型：解：增加松弛变量,,43 xx
21 2 xxM a x z
0,,,
62
2 -
..
43
4
21
3
21
21
xxxx
xxx
xxx
ts
4321 xxxx
0 0 2- 1
bB?XC
10 2 1
01 1 1-
6
2
4
3
x
x
0
0
6
0 0 2- 1
[ ]
1 0 2 1 6
1 1 3 0 8
1
3
x
x
1
0
1- 0 4- 0
X )0,8,0,6( 6s
注,1,表上每一列的含义,),,,(),( PBPBbBAbB
2,每张表上 B-1的位置在哪？ —— 对应于初表中 I 的位置。
,1110B
,10 1111B
54321 xxxxxbB?XC?
0 0 0 12 7
100103
01054
00149
300
200
360
x
x
x
0
0
0
0 0 0 12 7
[ ] 30
40
90
0,1 0 0 1 0,3 30
0,4- 0 1 0 7,8 240
0,5- 0 1 0 2,5 50
2
4
3
x
x
x
12
0
0
1,2- 0 0 0 3,4
100
20
30.8
[ ]
0,2- 0,4 0 0 1 20
1,1 6 0,3 2- 1 0 0 84
0,1 6 0,1 2- 0 1 0 242
1
3
x
x
x
12
7
0
1,2- 1,3 6- 0 0 0
.4 2 8,)0,0,84,24,20( zX
,
1
1
1
B
,
0,1
0,5-1
0,4-1
1
1
B
.
0,1 60,1 2-
0,2-0,4
1,1 63,1 2-1
1
2
B
54321 xxxxxbB?XC
100103
01054
00149
300
200
360
x
x
x
0
0
0
0 0 0 12 7
[ ]
0,2- 0,4 0 1
1,1 6 0,3 2- 1 0
0,1 6 0,1 2- 0 0 2
1
3
x
x
x
12
7
0
0,5 2- 1,3 6- 0 0 0
例 6：
填表：
,
24
20
84
3 0 0
2 0 0
3 6 0
0,1 60,1 20
0,20,40
1,1 63,1 21
1 bB解：
1
0
0
10
5
4
0,1 60,1 20
0,20,40
1,1 63,1 21
1 PB
24
20
84
1
0
0
练习：用单纯形法求解下面的线性规划
0,
2
5
..
21
21
21
xx
xx
xx
ts 105
153
212,5 xxM a xz
将模型化为标准型：解：增加松弛变量,,43 xx
21 xxM a x z 5.2
0,,,
1025
15 53
..
43
4
21
3
21
21
xxxx
xxx
xxx
ts
10 2 5
01 5 3
10
15
4
3
x
x
0
0
0 0 1 2,5
2
5
[ ]
4321 xxxx
0 0 1 2,5
bB?XC?
5
1 0
5
2 1
5
3- 1
5
19 0
2
9
1
3
x
x
2.5
0
0,5- 0 0 0
X )09,0,2,( 5z
,1110B
,
5
1
0
5
3
-1
1
1
B
问题：本题的单纯形终表检验数有何特点？
—— 非基变量 x2 的检验数等于零。
注：（ 1）解的几种情况在单纯形表上的体现（ Max型）：
- 唯一最优解：终表非基变量检验数均小于零；
- 多重最优解：终表非基变量检验数中有等于零的；
- 无界解：任意表有正检验数相应的系数列均非正。
（ 2） Min型单纯形表与 Max型的区别仅在于：检验数反号，即
- 令负检验数中最小的对应的变量进基；
- 当检验数均大于等于零时为最优。
年由美国斯坦福大学教授丹捷格（ G.B.Danzig）
提出。
尽管在其后的几十年中，又有一些算法问世，
但单纯形法以其简单实用的特色始终保持着绝对的“市场”占有率。
1.线性规划的标准型用单纯形法求解线性规划的前提是先将模型化为标准型：
0
..
X
bAX
ts
CXM a xz
标准型的特征,Max型、等式约束、非负约束一、单纯形法的预备知识
。）（的秩为其中,0, bnmmA
非标准形式如何化为标准
1) Min型化为 Max型
CXM in z? CXM ax z/
加负号因为，求一个函数的极小点，等价于求该函数的负函数的极大点。
)(xf
)(xf?
*x
注意,Min型化为 Max型求解后，最优解不变，但最优值差负号。
2) 不等式约束化为等式约束分析,以例 1中煤的约束为例
3 6 049 21 xx
之所以“不等”是因为左右两边有一个差额，称为“松弛量”，若在左边加上这个松弛量，则化为等式。而这个松弛量也是变量，记为 X3,则有
3 6 049 321 xxx
X3称为松弛变量。问题,它的实际意义是什么？
—— 煤资源的“剩余”。
练习：请将例 1的约束化为标准型
0,
3 0 0103
2 0 054
3 6 049
..
21
21
21
21
xx
xx
xx
xx
ts
解：增加松弛变量 则约束化为,,,
543 xxx
0,,,,
300 103
20054
360 49
..
543
21
5
21
4
21
3
21
xxxxx
xxx
xxx
xxx
ts
易见，增加的松弛变量的系数恰构成一个单位阵 I。
一般地，记松弛变量的向量为 Xs，则
0.,X
bAXts
0,.,s
s
XX
bIXAXts
0.,X
bAXts
0,.,s
s
XX
bIXAXts
问题：松弛变量在目标中的系数为何？ —— 0。
3) 当模型中有某变量 xk 没有非负要求,称为自由变量,则可令 0,,//////
kkkkk xxxxx
化为标准型。
2.基本概念
（ 1）可行解与最优解；的解，记为可行解：满足全体约束 X
。，有解则对任可行的，记为最优解：可行解中最优
*
,
CXCXX
X
直观上,可行解是可行域中的点，是一个可行的方案；
最优解是可行域的角点，是一个最优的方案。
（ 2）基矩阵与基变量基矩阵 (简称基 ),系数阵 A中的 m阶可逆子阵，记为 B；其余部分称为非基矩阵，记为 N。
基向量,基 B中的列；其余称非基向量。
基变量,与基向量 Pj对应的决策变量 xj,记其组成的向量为 XB；与非基向量对应的变量称非基变量，记其组成的向量为 XN。
1 2 3
1 2 4
14
3
2 1
2 3
,,0
x x x
x x x
xx
例,下 面 为 某 线 性 规 划 的 约 束请 例 举 出 其 基 矩 阵 和 相 应 的 基 向 量,基 变 量 。
1 2 3
1 2 4
14
3
21
23
,,0
x x x
x x x
xx
例,下 面 为 某 线 性 规 划 的 约 束请 例 举 出 其 基 矩 阵 和 相 应 的 基 向 量,基 变 量 。
阶可逆子阵有中的，解：本例中,2
1
0
0
1
1
2
2
1
AA?
—— 6个。
一般地,m× n 阶矩阵 A中基的个数最多有多少个？ 个。—— C;,,,
1
0
0
1
4
3
43431 1
x
x
XxxPPB,基变量为，其相应的基向量为
。基变量为其相应的基向量为?
2
1
21212 2
,,,,,
1
2
2
1
x
x
XxxPPB
问题：本例的 A中一共有几个基？
（ 3）基本解与基本可行解
.
0
,0,
,,
,
1
111
bB
XbBXXNXBbBX
b
X
X
NBbAXXXX
NBAmABBA
时，有当取即可表示为约束中的相应地
）（列，则可记中的前表示取定后，不妨设中的基当解；为线性规划的一个基本的解称?
0
bBXbAX
可见：一个基本解是由一个基决定的。
注意：基本解仅是资源约束的解，并未要求其非负，因此其未必可行。
称非负的基本解为 基本可行解 （简称基可行解）。
例 4：在上例中
0,,
32
12
41
421
321
xx
xxx
xxx
求相应于基 B1和 B2的基本解，它们是否基本可行解？
,31311001,1001,1001 111 bBBB解：
是基本可行解。的基本解为相应于基,)3,1,0,0(XB?
,
5
1-
5
7
3
1
5
1-
5
2
5
2
5
1
,
5
1-
5
2
5
2
5
1
,
1-
2
2
1 11
2
bBBB
不是基本可行解。的基本解为相应于基,,0,0 )51,-57(2 XB?
上二组概念间的联系：
系数阵 A中可找出若干个基 B
每个基 B都对应于一个基本解非负的基本解就是基本可行解几种解之间的关系：
可行解 基本解非可行解基本可行解问题：基本可行解是可行域中的哪些点？
3.基本定理
（ 1）线性规划的可行域是一个 凸 多面体。
（ 2）线性规划的最优解（若存在的话）必能在可行域的 角点 获得。
（ 3）线性规划可行域的 角点 与 基本可行解 一一对应。
二、单纯形法的步骤单纯形法是一种迭代的算法，它的思想是在可行域的角点 —— 基本可行解中寻优。由于角点是有限个（为什么？），因此，算法经有限步可终止。
确定一个初始基可行解检验这个基可行解是否最优寻找一个更好的基可行解否是 停止
1.确定初始基可行解由于基可行解是由一个可行基决定的，因此，
确定初始基可行解 X0相当于确定一个初始可行基 B0。
方法,若 A中含 I，则 B0=I；
若 A中不含 I，则可用人工变量法构造一个 I。
问题：若 B0=I，则 X0=？ 可行。,000 bbBX
2,最优性检验问题：用什么检验？ —— 目标。
XNBCCbBC
XCNXBbBC
X
X
CCCXz
)(
)()( 11而目标优。时，当前基可行解为最，则当记 01 NBCC
非最优。则当前解为最优；否则若的检验数方法：计算每个变量
0,
,1
PBCcx
问题：非最优的特征为何？ 。至少有某个检验数 0
3,寻找更好的基可行解由于基可行解与基对应，即寻找一个新的基可行解，相当于从上一个基 B0变换为下一个新的基 B1，因此，本步骤也称为基变换。
（基变换）
0bB
zz
可行：
改善：基变换的原则 ）变换的方法：（ PPPP,,,,,,
进基出基进基；对应的令保证“改善”进基 P0
可决定出基。由保证“可行”出基 011 NXBbBX
出基。对应的令进基；对应的方法：令
PPB
PB
bB
P
0)(
)(
)(
0
1
1
1
m i n
m a x
称作检验比。
以例 1为例，可按上述单纯形法的步骤求出其最优解，其大致的过程如下。
（ 1）先将模型化为标准型
0,,,,
300103
20054
36049
..
543
21
5
21
4
21
3
21
xxxxx
xxx
xxx
xxx
ts
21 127 xxM a x z
(2) 确定初始基可行解、检验;0 0,3 0 0 )( 0,0,3 6 0,2,00)( 3 6 0,2 0 0,3,
0
1
00
XbBB
1
1
1;,PP 向量为再计算检验比确定出基量为计算检验数确定进基向
（ 3）换基、计算下一个基可行解、再检验，直至最优;5 0,0 )( 0,2 4,2 4 0,,)( 2 4 0,5 0,3 0,
10
51
41
1
1
11
XbBB
;0,0 )( 2 0,2 4,8 4,,( 8 4,2 0,2 4 ),
103
54
491
2
1
22
XbBB
0
0;,41 PP 向量为再计算检验比确定出基量为计算检验数确定进基向前解为最优。计算检验数均非正，当问题：当模型规模较大时，计算量很大。
事实上，单纯形法的实现是在单纯形表上完成的。
练习：对于下面的线性规划
0,
62
2
2m in
xx
xx
xx
xxz
（ 1）用图解法求解；
（ 2）将模型化为标准型；
（ 3）用单纯形法步骤求出其最优解，并指出求解过程中每一个基可行解相当于可行域的哪一个角点。
三、单纯形表单纯形表是基于单纯形法的步骤设计的计算格式，是单纯形法的具体实现。
11
0
1
01
1
0
0 )(
)(
0 00 BPB
bBPBCcbBXB
m i n
回顾单纯形法步骤
bB?需计算 AB?需计算
,AbB 1?内容是因此，单纯形表的主体
1
2
1
1
1
0
AbB
AbB
AbB
即单纯形表。
变换迭代计算的由此设计了基于初等行得。也可通过初等行变换求邻两个只有一列不同，故相而相邻两个
1?B
B
单纯形表的主要结构：
X
C
AB?bB?
问题：第一张表的 B-1=？ —— 单位阵 I。
检验数的公式是什么？ PBCc
在哪里？PB? 列中的第 jAB 1
例 5：用单纯形法求解例 1
0,
3 0 0103
2 0 054
3 6 049
..
21
21
21
21
xx
xx
xx
xx
ts
21 127 xxM a x z
将模型化为标准型：解：增加松弛变量,,,543 xxx
0,,,,
300103
20054
36049
..
543
21
5
21
4
21
3
21
xxxxx
xxx
xxx
xxx
ts
21 127 xxM a x z
问题：标准模型的 A中是否含 I？ —— 松弛变量系数恰好构成 I。
54321 xxxxxbB?XC?
0 0 0 12 7
100103
01054
00149
300
200
360
x
x
x
0
0
0
0 0 0 12 7
[ ] 30
40
90
7;
3
4
9
0) 0 (07
1
1
11
pBCc?其中检验数 90
4
3 6 0
[ ] 中表示进基列与出基行的交叉元，下一张表将实行以它为主元的初等行变换（称高斯消去）。方法是：
先将主元消成 1，再用此 1将其所在列的其余元消成 0。
54321 xxxxxbB?XC?
0 0 0 12 7
100103
01054
00149
300
200
360
x
x
x
0
0
0
0 0 0 12 7
[ ] 30
40
90
0,1 0 0 1 0,3 30
0,4- 0 1 0 7,8 240
0,5- 1 0 0 2,5 50
2
4
3
x
x
x
12
0
0
1,2- 0 0 0 3,4
100
20
30.8
[ ]
0,2- 0,4 0 0 1 20
1,1 6 0,3 2- 1 0 0 84
0,1 6 0,1 2- 0 1 0 242
1
3
x
x
x
12
7
0
0,5 2- 1,3 6- 0 0 0
428.,0,0 )( 2 0,2 4,8 4,*zX （请解释其实际意义）
练习：用单纯形法求解下面的线性规划
0,
62
-2-
..
21
21
21
xx
xx
xx
ts
21 2- xxM in s
将模型化为标准型：解：增加松弛变量,,43 xx
21 2 xxM a x z
0,,,
62
2 -
..
43
4
21
3
21
21
xxxx
xxx
xxx
ts
4321 xxxx
0 0 2- 1
bB?XC
10 2 1
01 1 1-
6
2
4
3
x
x
0
0
6
0 0 2- 1
[ ]
1 0 2 1 6
1 1 3 0 8
1
3
x
x
1
0
1- 0 4- 0
X )0,8,0,6( 6s
注,1,表上每一列的含义,),,,(),( PBPBbBAbB
2,每张表上 B-1的位置在哪？ —— 对应于初表中 I 的位置。
,1110B
,10 1111B
54321 xxxxxbB?XC?
0 0 0 12 7
100103
01054
00149
300
200
360
x
x
x
0
0
0
0 0 0 12 7
[ ] 30
40
90
0,1 0 0 1 0,3 30
0,4- 0 1 0 7,8 240
0,5- 0 1 0 2,5 50
2
4
3
x
x
x
12
0
0
1,2- 0 0 0 3,4
100
20
30.8
[ ]
0,2- 0,4 0 0 1 20
1,1 6 0,3 2- 1 0 0 84
0,1 6 0,1 2- 0 1 0 242
1
3
x
x
x
12
7
0
1,2- 1,3 6- 0 0 0
.4 2 8,)0,0,84,24,20( zX
,
1
1
1
B
,
0,1
0,5-1
0,4-1
1
1
B
.
0,1 60,1 2-
0,2-0,4
1,1 63,1 2-1
1
2
B
54321 xxxxxbB?XC
100103
01054
00149
300
200
360
x
x
x
0
0
0
0 0 0 12 7
[ ]
0,2- 0,4 0 1
1,1 6 0,3 2- 1 0
0,1 6 0,1 2- 0 0 2
1
3
x
x
x
12
7
0
0,5 2- 1,3 6- 0 0 0
例 6：
填表：
,
24
20
84
3 0 0
2 0 0
3 6 0
0,1 60,1 20
0,20,40
1,1 63,1 21
1 bB解：
1
0
0
10
5
4
0,1 60,1 20
0,20,40
1,1 63,1 21
1 PB
24
20
84
1
0
0
练习：用单纯形法求解下面的线性规划
0,
2
5
..
21
21
21
xx
xx
xx
ts 105
153
212,5 xxM a xz
将模型化为标准型：解：增加松弛变量,,43 xx
21 xxM a x z 5.2
0,,,
1025
15 53
..
43
4
21
3
21
21
xxxx
xxx
xxx
ts
10 2 5
01 5 3
10
15
4
3
x
x
0
0
0 0 1 2,5
2
5
[ ]
4321 xxxx
0 0 1 2,5
bB?XC?
5
1 0
5
2 1
5
3- 1
5
19 0
2
9
1
3
x
x
2.5
0
0,5- 0 0 0
X )09,0,2,( 5z
,1110B
,
5
1
0
5
3
-1
1
1
B
问题：本题的单纯形终表检验数有何特点？
—— 非基变量 x2 的检验数等于零。
注：（ 1）解的几种情况在单纯形表上的体现（ Max型）：
- 唯一最优解：终表非基变量检验数均小于零；
- 多重最优解：终表非基变量检验数中有等于零的；
- 无界解：任意表有正检验数相应的系数列均非正。
（ 2） Min型单纯形表与 Max型的区别仅在于：检验数反号，即
- 令负检验数中最小的对应的变量进基；
- 当检验数均大于等于零时为最优。
