8
f ( X k ) 0
m
1
-5
1
0
0
0
1
0
k 目标函数及检验数 ZQ
-10 0
K k ZQ CQ Cik aiQ
i 1
14
武汉理工大学
能源与动力工程学院
0 0 由于Z Q 不全大于０，所以 X 不是最优解
（以检验数较小进行计算）
xi l min 0 k al 2 0 a i2
aij
k 1
aij
k
alQ
k a iQ k
i 1,2,...,l 1, l 1,...,m j 1,2,...,n
1 l min 1 7
L=1
0
1
1 12
8 7 1
用x2去替换第１个基本变量
15
武汉理工大学
能源与动力工程学院
基本变 量序号 i
基 本 变 量
基 本 向 量
Cik
-10
CQ -5
列向量 基本变量值
-10 0
0
0
P1 P2
1 2 17 168 1 2
P3 P4 P5 7
17 84
2 0
2
f ( X k ) 70
-14 0 70 0
k 目标函数及检验数 ZQ
K k ZQ CQ Cik aiQ
i 1
18
m
最优解x*=(2 6 0 3/14 0)T
武汉理工大学
能源与动力工程学院
单纯形方法的计算步骤及框图
(1)将约束条件变换成等式，形成m阶n维的线性规划问题，求得基本可行解． 0 0 0 0 0 0 T
5
换出：x1=0,
X2
x3,x4,x5,x6?
武汉理工大学
能源与动力工程学院
3 1 z 2 x1 3x2 2 x1 3 3 x6 9 2 x1 x6 4 4 x1 x6 0, z 9, x 0,3,6,2,16,0
1 T
三个关键问题：
（1）初始顶点（初始的基本可行解）如何确定？ （2）怎样使最优搜索从一个顶点移到另一个顶点？ （3）如何判断所找到的顶点是不是最优点？
2
武汉理工大学
能源与动力工程学院
例:求解线性规划问题 max z’=2x1+3x2 2x1+2x2≤12 x1+2x2 ≤8
解：化为标准型 2x1+2x2+x3
２）若约束条件均为“≥”，或等式约束的系数矩阵不存在m阶单位阵为子 矩阵的情况．这时需引入“人为变量”．
9
武汉理工大学
能源与动力工程学院
２）作初始单纯形表，确定初始基本可行解
c→
s
cBi xB bi b1 b2 … bm cn+1 xn+1 cn+2 xn+2
c1 c2 … c n
x1 a11 a21 … am1 x2 a12 a22 … am2 … … … … … xn a1n a1n … amn
x 2,3,2,0,8,0
2 4 5
T 3 T
x 0, x 0 x 4,2,0,0,0,4 min z 2 4 3 2 14 max z 14 14
'
6
武汉理工大学
能源与动力工程学院
x2 6 2x1+2x2=12 4x1=16
x 0,3,6,2,16,0 Q4
0 P5 0 1
1 P3 0 0 1 B 1 8
0 P4 1 0
8
武汉理工大学
能源与动力工程学院
§２.2单纯形法的计算步骤
1、化一般的线性规划为标准形式，构造一个初始可行基
K
输出X k 及f X K
Ｙ

a K
lQ
xl k
打印
停
k xik 1 xik l aiQ
i 1,2,...,l 1, l 1,...,m xik 1 l
k 1 k k alj alj / alQ k alj
7 12
1 2 3
x２ P2
7
5 7
1 0 0
0 1
0 0 1
x4 P4 0 x5 P5 0
1
f ( X k ) 70
m
-7 0
目标函数及检验数 Z k Q
0
0
70 0
0
K k ZQ CQ Cik aiQ
i 1
16
武汉理工大学
能源与动力工程学院
由于非基本变量所对应的列，还有检验数等于０的（第 一列），故说明还有一个顶点是最优解．所以还可以第 一列所对应的非基本变量x1去替换基本变量x5．
X
x1 , x2 ,..., xm , xm 1 ,..., xn
m


(2)对系数阵的每一列计算检验数：
Z
(k ) Q
k CQ Cik aiQ , Q 1,2,...,n
i 1
对于初始基本可行解k=0,若每一列的检验数全部大于等于零，则 X k 即 k 为最优解，迭代结束．若某个Ｑ列的 Z ( k ) 0 且全部元素 aiQ ， 0 Q 则此问题无解．
k (k ) (3)若某个Ｑ列的 ZQ 0且某些元素 I 有 aiQ 0 ，则选定Q列所对 应的变量XQ作为替换的非基本变量,求新的基本可行解.
(4)再计算每一列的检验数,再判断,如此迭代直至找到最优解.
19
武汉理工大学
能源与动力工程学院
输入：初始基本可行解x(0)及相应的约束、方程组系数矩阵、目标函数系数阵Ｃ
１）若约束条件均为“≤”情况，则引入非负松弛变量xn+i，以形成一个m 阶单位阵(称为初始可行基)．
n aij x j xn i b(i 1,2,...,m) j 1 x j 0( j 1,2,...,n) x 0(i 1,2,...,m) n i
1/4 (-1/4) 0 0 1 0
4
12
j2 c j z j 2
0 -2
Ⅲ
x3 x1 x6 x2
0 4 4 2
0 -3
j3 c j z j 3
0
0
0
12
3/2
1/8
0
武汉理工大学
能源与动力工程学院
单纯形法例题
目标函数：f(x)=-5x1-10x2
x1 x2 x3 1 14 7 x1 x2 x4 1 约束方程： 7 12 x1 x2 x5 8 x1 , x2 .....x5 0

0,0,12,8,16,12
z=0 ?? 最优解？
T
初始基本可行解 x0代入目标函数 基变换
4
武汉理工大学
能源与动力工程学院
x3 12 2 x1 2 x2 x 8 x 2x 4 1 2 x1 x2 0 z 2 x1 3 x2 0 0 x5 16 4 x1 x6 12 4 x2
2)基变换 换入:将式中系数为负、且为最小的那个非基变量换入，作 为基变量。x2 基变量
x3 12 2 x2 x 8 2x 4 12 8 12 2 x2 min , , /, 3 x2 x6 4 2 2 x5 16 x6 12 4 x2
x1+2x2 s.t. 4x1 4x2
求初始基本可行解 = 12
+x4 +x5 =8 =16 +x6 =12
min z’= - 2x1- 3x2
s.t. 4x1 ≤16 4x2 ≤12
x1,x2≥0
2 1 A 4 0 2 2 0 4 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1
P1x1+P2x2+P3x3+P4x4+P5x5=B
x1 x2 x3 1 14 7 x1 x2 x4 1 7 12 x1 x2 x5 8 x1 , x2 .....x5 0
1 P1 7 1
1 14

1 7 1 P2 12 1
cn+1
xn+1 1 0 0 0 0
cn+2
xn+2 0 1 0 0 0
…
cn+m
xn+m 0 0 0 1 0
… … … … … …
i
bi aik
1 2
…
0
…
…
j0 c j z j 0
cn+m xn+m
0 0 0 1 2 ... n
m
z j cBi aij
j0 c j z j 0
0 6
3

0
Ⅰ 0 -3
x4
x5 x2
2
16 3
[1]
4 0
0
0 1
0
0 0
1
0 0
0
1 0
-1/2
0 1/4
2
4 /
j1 c j z j 1
(-2)
0
0
0
0
3/4
11
武汉理工大学
能源与动力工程学院
c→
-2
bi x1
-3
x2
0
x3
0
17