bi ≥0
bi < 0
≤ =≥
maxZ
minZ
约 束
xs xa
求 解
图 解 法、 单 纯 形 法
单 纯 形 法
不
令xj = xj′令 x j″ 处 xj’ = -xj
不 处 理
理
xj′ ≥0 xj″ ≥0
xj’ ≥0
约 束 条 件 两 端 同 乘 以-1
加 松 弛 变 量 xs
加 入 人 工 变 量 x a
max Z x1 2 x 2 x 3 2 x1 3 x 2 2 x 3 x 4 15 1 s .t x1 x 2 5 x 3 x 5 20 3 x j 0, j 1,2, ,5
不难看出x4、x5可作为初始基变量，列单纯形表计算。
bm 0 1 am,m1 amn m
0
0
3 1
－2
j
x2
1 0
0
17/3 1/3 1 28/9 -1/9 2/3
-98/9 -1/9 -7/3
单纯形法的计算步骤
Page 12
表1-6中所有的 j 都小于或者等于0，表明已经达到了最 优解，因此，现行的基本可行解X=（25，35 /3，0，0，0） T是最优解，Z=95/3是该线性规划的最优值。
减 去 x s, 加 入 xa
不 处 理
令 z′=- Z minZ =－ max z′
0 -M
找出基变量 列出初始单纯形表
求 : j c j ci a j
i 1
m
循环
基变 有某个 否 否 唯一 量中是否 非基变量的 最优解 含有xa j 0
是 是
所有
是
j 0
否
找出 ( j )max即 k
将2化为1，本列的其他值化为0
（表1-5）Cj
cB 0 0 0 基变量 x1 x4 b 2 8 3 2 x1 1 0 0 0 3 x2 0 0 1 0
Paபைடு நூலகம்e 8
换入列
0 x3 1 -4 0 -2 0 x4 0 1 0 0 0 x5 -1/2 2 1/4 1/4 Z=13 θi
换 出 行
4
j
x2
第二步：将第一行加上第二行乘以1/2
② 确定换出变量。根据下式计算并选择θ ，选最小的θ对应基
单纯形法的计算步骤
③
Page 5
用换入变量xk替换基变量中的换出变量，得到一个新的基。 对应新的基可以找出一个新的基可行解，并相应地可以画出 一个新的单纯形表。
5）重复3）、4）步直到计算结束为止。
单纯形法的计算步骤
将4化为1，本列 的其他值化为0
单纯形法的计算步骤
单纯形表
Page 1
cj
cB
XB
c1 cm
x1 xm
c1 cm cm 1 cn i b x1 xm xm1 xn b1 1 0 a1,m1 a1n 1
bm 0 1 am,m1 amn m
单纯形法的进一步讨论－人工变量法
例1.10 用大M法解下列线性规划 max Z 3 x1 x 2 x 3
Page 15
x1 2 x 2 x3 11 4 x x 2 x 3 1 2 3 2 x1 x 3 1 x1、x2、x3 0 解：首先将数学模型化为标准形式
j
00 j c j ci aij
bi 其中： i a kj 0 a kj
单纯形法的计算步骤
例1.8 用单纯形法求下列线性规划的最优解 max Z 2 x1 3 x 2
Page 2
x1 2 x 2 8 4 x1 16 4 x 2 12 x1 , x 2 0 解：1）将问题化为标准型，加入松驰变量x3、x4、 x5则标准 型为: max Z 3 x1 4 x 2 0 x 3 0 x4 0 x5
单纯形法的计算步骤
cj
cB 0 0 基变量 x4 b 15 20
Page 11
1
x1 2 1/3
2
x2 -3 1
1
x3 2 5
0
x4 1 0
0
x5 0 1
θi
j
x5
－ 20 25 60
2
0
j
1
2
x2
x1
x4
75 3 20 1/3 1/3
25 35/3
1
0 1 0 0 1
0
2
17 5
－9
1
1 0 0
1 4 0 2
表1-4
0 0 1 0
1 0 0 0
0 1 0 0
－1/2 0 1/4 －3/4

x2
j
第二步：将第一行减去第三行乘以2 第一步：将第三行除以4
单纯形法的计算步骤
将4化为0
（表1-4）Cj
cB 0 0 0 基变量 x3 x4 b 2 16 3
Page 7
换入列
2 x1 1 4 0 2 3 x2 0 0 1 0 0 x3 1 0 0 0
2 0 3 x1 x5
4 4 2
1 0 0 0
表1-6
0 0 1 0
0 -2 1/2 -3/2
1/4 1/2 -1/8 -1/8
0 1 0

x2
j
0
第一步：将第二行除以2 第三步：将第三行减去第二行乘以1/4
单纯形法的计算步骤
Page 9
表1-6中所有的 j 都小于或者等于0，表明已经达到了最 优解，因此，现行的基本可行解X=（4，2，0，0，4）T是 最优解，Z=14是该线性规划的最优值。
Page 3
0 1 c1 (0 c3a11 c4a21 c5a31 ) 2 (0 1 0 0 4 0 0) 2 x3 1 x4 0 x5 0
θi
4
0
0
x4
x5
16
12
4
0 2
0
4 3
0
0 0
1
0 0
0
1 0
-3 Z=0
j
检验数
1 c1 (c3a11 c4a21 c5a31 ) 2 (0 1 0 4 0 0) 2
（表1-3）cj
cB 0 0 0 基变量 x3 x4 b 8 16 12
Page 6
换入列
2 x1 1 4 0 2 3 x2 2 0 4 3 0 x3 1 0 0 0
bi /ai2，ai2>0
0 x4 0 1 0 0 0 x5 0 0 1 0 θi
j
x5
4 3
Z=0
换 出 行
0 0 3
x3 x4
2 16 3
x1 2 x 2 x 3 8 4 x1 x4 16 4 x 2 x5 12 x1 , x 2 , x 3 , x4 , x5 0
单纯形法的计算步骤
2）求出线性规划的初始基可行解， 列出初始单纯形表。 cj CB 0 XB x3 b 8 2 x1 1 3 x2 2
1
-M-1 -5/3 -2 -7/3 M+2/3
——
j
单纯形法的总结
解的判别：
Page 18
1）唯一最优解判别：最优表中所有非基变量的检验数非 零,则线 规划具有唯一最优解。 2）多重最优解判别：最优表中存在非基变量的检验数为 零,则线则性规划具有多重最优解（或无穷多最优解）。
j >0且aij≤０（i=1，2,…,m）则线 3）无界解判别：某个 性规 划具有无界解。
max Z 3 x1 x 2 x 3 0 x4 0 x5 x1 2 x 2 x 3 x4 11 4 x x 2 x x 3 1 2 3 5 2 x1 x 3 1 x j 0, j 1,2, ,5
Page 17
θi 11 3/2 1
j
→ →
—— 1 —— 4
j
1-3M -5 -2
→
——
-1
3 -1 -1
j
x1 x2 x3 4 1 9
x3
－2
1↑ 1 0 0 0
0
0 0 1 0 0
1
0 0 0 1 0
0
0 1/3 0 2/3 -1/3
0
-1 -2/3 -1 -4/3 -1/3
0
-M+1 2/3 1 4/3 M+1/3
2 c2 (c3a12 c4a22 c5a32 ) 3 (0 2 0 0 0 4) 3
单纯形法的计算步骤
Page 4
3）进行最优性检验 如果表中所有检验数 0 ，则表中的基可行解就是问题 j 的最优解，计算停止。否则继续下一步。 4）从一个基可行解转换到另一个目标值更大的基可行解， 列出新的单纯形表
单纯形法的计算步骤
例1.9 用单纯形法求解
max Z x1 2 x 2 x 3 2 x1 3 x 2 2 x 3 15 1 s .t x1 x 2 5 x 3 20 3 x1、x 2、x 3 0
Page 10
解：将数学模型化为标准形式：
单纯形法的进一步讨论－人工变量法
cj CB 0 -M -M 0 -M -1 0 -1 XB x4 x6 x7 x4 x6 x3 x4 x2 b 11 3 1 10 1 1 12 1 3 x1 1 -4 -2 3-6M 3 0 -2 1 3 0 -1 x2 -2 1 0 -1+M -2 1 0 -1+M↑ 0 1 -1 x3 1 2 1 -1+3M↑ 0 0 1 0 0 0 0 x4 1 0 0 0 1 0 0 0 1 0 0 x5 0 -1 0 -M 0 -1 0 -M -2 -1 -M x6 0 1 0 0 1 1 0 0 2 1 -M x7 0 0 1 0 -1 -2 1