1－ 3 单纯形法
图解法的局限性？
1947年 G.B.Dantzig提出的 单纯
形法 提供了方便, 有效的通用算法求
解线性规划 。
一、单纯形法的基本思想
1,顶点的逐步转移
即 从可行域的 一个顶点 （基本可行
解）开始,转移到另一个顶点 （另一个
基本可行解）的迭代过程,转移的条件
是 使 目标函数值得到改善 （逐步变优），
当目标函数达到最优值时，问题也就得
到了最优解。
根据 线性规划问题的可行域是凸多边形
或凸多面体，一个线性规划问题有最优解，
就一定可以在可行域的顶点上找到。
于是,若某线性规划只有唯一的一个最
优解，这个最优解所对应的点一定是可行域
的一个顶点；若该线性规划有多个最优解，
那么肯定在可行域的顶点中可以找到至少一
个最优解。
顶点转移的依据？
转移条件？ 转移结果？
使 目标函数值得到改善
得到 LP最优解, 目标函数达到最优值
（ 单纯形法的由来？ ）
2,需要解决的问题：
(1)为了使目标函数逐步变优, 怎麽转移？
(2)目标函数何时达到最优 ——
判断标准是什麽？
二、单纯形法原理（用代数方法求解 LP）
例 1-6
?
?
?
?
?
?
???
???
???
0,,
974
)(3
..
332m a x
321
321
321
321
xxx
xxx
xxx
ts
xxxZ
（原材料约束）
劳动力约束
第一步,引入非负的松弛变量 x4,x5,将该
LP化为标准型
?
?
?
?
?
?
????
????
?????
0,,,,
974
)(3
..
00332m a x
54321
5321
4321
54321
xxxxx
xxxx
xxxx
ts
xxxxxZ
（原材料约束）
劳动力约束
第二步,寻求初始可行基, 确定基变量
???
?
???
??
10741
01111
A ? ? ???
?
???
???
10
01
,54 PPB
对应的基变量是 x4,x5；
第三步,写出初始基本可行解和相应
的目标函数值
两个关键的基本表达式：
① 用非基变量表示基变量的表达式
T
X
xxxx
xxxx
)9,3,0,0,0(
749
3
)0(
3215
3214
?
?
?
?
?
????
????
初始基本可行解
② 用非基变量表示目标函数的 11111
表达式
请解释结果的经济含义 ——
不生产任何产品，资源全部节余（ x4=3，
x5=9），三种产品的总利润为 0！
???? 321 332 xxxZ
0)0( ?Z当前的目标函数值
第四步,分析两个基本表达式，看看目
标函数是否可以改善？
① 分析 用非基变量表示目标函数的表达式
非基变量前面的系数均为正数，所以任
何一个非基变量进基都能使 Z值增加
通常把非基变量前面的系数叫,检验数,；
321 332 xxxZ ???
② 选哪一个非基变量进基？
选 x1为 进基变量 （ 换入变量 ）
问题：能否选其他的非基变量进基？
? 任意一个
? 任意一个正检验数对应的非基变量
? 最大正检验数对应的非基变量
? 排在 最前面的正检验数对应的非基变量
×
?
?
?
③ 确定出基变量：
问题讨论
? x1进基意味着其取值从 0变成一个正数 （ 经济
意义 —— 生产 A产品 ）, 能否无限增大？
? 当 x1增加时, x4,x5如何变化？
? 现在的非基变量是哪些？
? 具体如何确定换出变量？
?
?
?
????
????
3215
3214
749
3
xxxx
xxxx
由 用非基变量表示基变量的表达式
当 x1增加时, x4,x5会减小, 但有限度 —— 必
须大于等于 0,以保持解的可行性 ！ 于是
?
?
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
???
3
1
9
,
1
3
m in
1
9
1
3
09
03
1
1
1
15
14
x
x
x
xx
xx
当 x1的值从 0增加到 3时, x4首先变为
0,此时 x5=6>0
因此 选 x4为出基变量 （ 换出变量 ） 。
这种用来确定出基变量的规则称为
,最小比值原则, （ 或 θ原则 ） 。
如果 P1≤0,会出现什麽问题？
最小比值原则会失效 ！
?基变换
新的基变量 —— x1,x5；新的非基变量 x2,x3,x4；
写出 用非基变量表示基变量的表达式：
可得新的基本可行解
X（ 1） =（ 3,0,0,0,6） T
?
?
?
????
????
3215
3214
749
3
xxxx
xxxx
由
?
?
?
????
????
4325
4321
636
3
xxxx
xxxx
→
⑤ 写出 用非基变量表示目标函数的表达式,
432
32432
321
6
33)3(2
332
xxx
xxxxx
xxxZ
????
??????
???
可得相应的目标函数值为 Z（ 1） =6
检验数仍有正的
返回 ① 进行讨论 。
第五步,上述过程何时停止？
当 用非基变量表示目标函数的表达式 中, 非
基变量的系数 （ 检验数 ） 全部非正 时, 当前的
基本可行解 就是 最优解 !
为什麽？
—— 分析 用非基变量表示目标函数的表达式,
如果 让负检验数所对应的变量进基, 目标函数
值将下降 ！
三, 表格单纯形法：
1,初始单纯形表的建立
(1)表格结构：
?jCj 2 3 3 0 0
b xj x1 x2 x3 x4 x5CB XB
0 X4 3 1 1 1 1 0
0 X5 9 1 4 7 0 1
-Z 0 2 3 3 0 0
（ 2） 表格设计依据：
将 -Z看作不参与基变换的基变量, 把目标
函数表达式改写成方程的形式, 和原有的 m
个约束方程组成一个具有 n+m+1个变量,
m+1个方程的方程组：
?
?
?
?
?
?
?
?
?
???????
?????
?????
?????
????
?
?
?
0
112211
2211
222222121
111212111
mnmnnnnn
mmnnmnmm
nnn
nnn
xcxcxcxcxcZ
bxxaxaxa
bxxaxaxa
bxxaxaxa
??
?
???
?
?
取出系数写成增广矩阵的形式：
-Z X1 X2 … Xn Xn+1 Xn+2 … Xn+m b
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
01
1000
0100
0010
2121
21
222221
111211
mnnnn
mmnmm
n
n
cccccc
baaa
baaa
baaa
??
??
????????
??
??
-Z,Xn+1,…, Xn+m所对应的系数
列向量构成一个基
用矩阵的初等行变换将该基变成单位阵,这时
变成 0,相应的增广矩
阵变成如下形式：
mnnn ccc ???,,,21 ?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0
21
21
222221
111211
0001
1000
0100
0010
z
baaa
baaa
baaa
n
mmnmm
n
n
??
??
????????
??
??
???
?
?
???
m
i
ijinjj acc
1
?
?
?
????
m
i
iin bcz
1
0 0
其中，,
j=1,2,…, n ；
（ 3） 检验数的两种计算方法：
① 利用矩阵的行变换, 把目标函数表达式中
基变量前面的系数变为 0；
②使用计算公式 ——
njzcPCcacc jjjBj
m
i
ijinjj,,2,1,
1
??????? ?
?
???
增广矩阵的最后一行就是用非基变量表示
目标函数的表达式, （ j=1,2,…, n） 就是
非基变量的检验数 。
j?
2、例 1-6的表格单纯形法计算过程：
CB XB Cj
b
xj
2 3 3 0 0
x1 x2 x3 x4 x5
?j
0
0
X4
X5
3
9
1 1 1 1 0
1 4 7 0 1
3/1
9/1
-Z 0 2 3 3 0 0
2
0
X1
X5
3
6
1 1 1 1 0
0 3 6 -1 1
3/1
6/3
-Z -6 0 1 1 -2 0
2
3
X1
X2
1
2
1 0 -1 4/3 -1/3
0 1 2 -1/3 1/3
-Z -8 0 0 -1 -5/3 -1/3
从最优表可知,
该 LP的
最优解是 X*=(1,2,0,0,0)T
相应的目标函数最优值是 Zmax=8
第二次作业,P70,1-5（共 5个小题）
下周二（ 9月 24日）交
图解法的局限性？
1947年 G.B.Dantzig提出的 单纯
形法 提供了方便, 有效的通用算法求
解线性规划 。
一、单纯形法的基本思想
1,顶点的逐步转移
即 从可行域的 一个顶点 （基本可行
解）开始,转移到另一个顶点 （另一个
基本可行解）的迭代过程,转移的条件
是 使 目标函数值得到改善 （逐步变优），
当目标函数达到最优值时，问题也就得
到了最优解。
根据 线性规划问题的可行域是凸多边形
或凸多面体，一个线性规划问题有最优解，
就一定可以在可行域的顶点上找到。
于是,若某线性规划只有唯一的一个最
优解，这个最优解所对应的点一定是可行域
的一个顶点；若该线性规划有多个最优解，
那么肯定在可行域的顶点中可以找到至少一
个最优解。
顶点转移的依据？
转移条件？ 转移结果？
使 目标函数值得到改善
得到 LP最优解, 目标函数达到最优值
（ 单纯形法的由来？ ）
2,需要解决的问题：
(1)为了使目标函数逐步变优, 怎麽转移？
(2)目标函数何时达到最优 ——
判断标准是什麽？
二、单纯形法原理（用代数方法求解 LP）
例 1-6
?
?
?
?
?
?
???
???
???
0,,
974
)(3
..
332m a x
321
321
321
321
xxx
xxx
xxx
ts
xxxZ
（原材料约束）
劳动力约束
第一步,引入非负的松弛变量 x4,x5,将该
LP化为标准型
?
?
?
?
?
?
????
????
?????
0,,,,
974
)(3
..
00332m a x
54321
5321
4321
54321
xxxxx
xxxx
xxxx
ts
xxxxxZ
（原材料约束）
劳动力约束
第二步,寻求初始可行基, 确定基变量
???
?
???
??
10741
01111
A ? ? ???
?
???
???
10
01
,54 PPB
对应的基变量是 x4,x5；
第三步,写出初始基本可行解和相应
的目标函数值
两个关键的基本表达式：
① 用非基变量表示基变量的表达式
T
X
xxxx
xxxx
)9,3,0,0,0(
749
3
)0(
3215
3214
?
?
?
?
?
????
????
初始基本可行解
② 用非基变量表示目标函数的 11111
表达式
请解释结果的经济含义 ——
不生产任何产品，资源全部节余（ x4=3，
x5=9），三种产品的总利润为 0！
???? 321 332 xxxZ
0)0( ?Z当前的目标函数值
第四步,分析两个基本表达式，看看目
标函数是否可以改善？
① 分析 用非基变量表示目标函数的表达式
非基变量前面的系数均为正数，所以任
何一个非基变量进基都能使 Z值增加
通常把非基变量前面的系数叫,检验数,；
321 332 xxxZ ???
② 选哪一个非基变量进基？
选 x1为 进基变量 （ 换入变量 ）
问题：能否选其他的非基变量进基？
? 任意一个
? 任意一个正检验数对应的非基变量
? 最大正检验数对应的非基变量
? 排在 最前面的正检验数对应的非基变量
×
?
?
?
③ 确定出基变量：
问题讨论
? x1进基意味着其取值从 0变成一个正数 （ 经济
意义 —— 生产 A产品 ）, 能否无限增大？
? 当 x1增加时, x4,x5如何变化？
? 现在的非基变量是哪些？
? 具体如何确定换出变量？
?
?
?
????
????
3215
3214
749
3
xxxx
xxxx
由 用非基变量表示基变量的表达式
当 x1增加时, x4,x5会减小, 但有限度 —— 必
须大于等于 0,以保持解的可行性 ！ 于是
?
?
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
???
3
1
9
,
1
3
m in
1
9
1
3
09
03
1
1
1
15
14
x
x
x
xx
xx
当 x1的值从 0增加到 3时, x4首先变为
0,此时 x5=6>0
因此 选 x4为出基变量 （ 换出变量 ） 。
这种用来确定出基变量的规则称为
,最小比值原则, （ 或 θ原则 ） 。
如果 P1≤0,会出现什麽问题？
最小比值原则会失效 ！
?基变换
新的基变量 —— x1,x5；新的非基变量 x2,x3,x4；
写出 用非基变量表示基变量的表达式：
可得新的基本可行解
X（ 1） =（ 3,0,0,0,6） T
?
?
?
????
????
3215
3214
749
3
xxxx
xxxx
由
?
?
?
????
????
4325
4321
636
3
xxxx
xxxx
→
⑤ 写出 用非基变量表示目标函数的表达式,
432
32432
321
6
33)3(2
332
xxx
xxxxx
xxxZ
????
??????
???
可得相应的目标函数值为 Z（ 1） =6
检验数仍有正的
返回 ① 进行讨论 。
第五步,上述过程何时停止？
当 用非基变量表示目标函数的表达式 中, 非
基变量的系数 （ 检验数 ） 全部非正 时, 当前的
基本可行解 就是 最优解 !
为什麽？
—— 分析 用非基变量表示目标函数的表达式,
如果 让负检验数所对应的变量进基, 目标函数
值将下降 ！
三, 表格单纯形法：
1,初始单纯形表的建立
(1)表格结构：
?jCj 2 3 3 0 0
b xj x1 x2 x3 x4 x5CB XB
0 X4 3 1 1 1 1 0
0 X5 9 1 4 7 0 1
-Z 0 2 3 3 0 0
（ 2） 表格设计依据：
将 -Z看作不参与基变换的基变量, 把目标
函数表达式改写成方程的形式, 和原有的 m
个约束方程组成一个具有 n+m+1个变量,
m+1个方程的方程组：
?
?
?
?
?
?
?
?
?
???????
?????
?????
?????
????
?
?
?
0
112211
2211
222222121
111212111
mnmnnnnn
mmnnmnmm
nnn
nnn
xcxcxcxcxcZ
bxxaxaxa
bxxaxaxa
bxxaxaxa
??
?
???
?
?
取出系数写成增广矩阵的形式：
-Z X1 X2 … Xn Xn+1 Xn+2 … Xn+m b
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
01
1000
0100
0010
2121
21
222221
111211
mnnnn
mmnmm
n
n
cccccc
baaa
baaa
baaa
??
??
????????
??
??
-Z,Xn+1,…, Xn+m所对应的系数
列向量构成一个基
用矩阵的初等行变换将该基变成单位阵,这时
变成 0,相应的增广矩
阵变成如下形式：
mnnn ccc ???,,,21 ?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0
21
21
222221
111211
0001
1000
0100
0010
z
baaa
baaa
baaa
n
mmnmm
n
n
??
??
????????
??
??
???
?
?
???
m
i
ijinjj acc
1
?
?
?
????
m
i
iin bcz
1
0 0
其中，,
j=1,2,…, n ；
（ 3） 检验数的两种计算方法：
① 利用矩阵的行变换, 把目标函数表达式中
基变量前面的系数变为 0；
②使用计算公式 ——
njzcPCcacc jjjBj
m
i
ijinjj,,2,1,
1
??????? ?
?
???
增广矩阵的最后一行就是用非基变量表示
目标函数的表达式, （ j=1,2,…, n） 就是
非基变量的检验数 。
j?
2、例 1-6的表格单纯形法计算过程：
CB XB Cj
b
xj
2 3 3 0 0
x1 x2 x3 x4 x5
?j
0
0
X4
X5
3
9
1 1 1 1 0
1 4 7 0 1
3/1
9/1
-Z 0 2 3 3 0 0
2
0
X1
X5
3
6
1 1 1 1 0
0 3 6 -1 1
3/1
6/3
-Z -6 0 1 1 -2 0
2
3
X1
X2
1
2
1 0 -1 4/3 -1/3
0 1 2 -1/3 1/3
-Z -8 0 0 -1 -5/3 -1/3
从最优表可知,
该 LP的
最优解是 X*=(1,2,0,0,0)T
相应的目标函数最优值是 Zmax=8
第二次作业,P70,1-5（共 5个小题）
下周二（ 9月 24日）交
