否
含 有xa
是 无可行解
(a对ik
0 任一
j 0)
否
是 无界解
有某个 否 非基变量的
j 0
唯一 最优解
是
无穷多
最优解
循
环
停止
计 算 i
( bi alk
alk
0)
用 非 基 变 量xk 替 换 基 变 量xl
列出下一个 新单纯形表
单纯形法的进一步讨论－人工变量法 Page 17
解的判别： 1）唯一最优解判别：最优表中所有非基变量的检验数非零, 则线 规划具有唯一最优解。 2）多重最优解判别：最优表中存在非基变量的检验数为零, 则线则性规划具有多重最优解（或无穷多最优解）。 3）无界解判别：某个λk>0且aik≤０（i=1，2,…,m）则线性 规划具有无界解。 4）无可行解的判断：当用大M单纯形法计算得到最优解并 且存在Ri>0时，则表明原线性规划无可行解。 5）退化解的判别：存在某个基变量为零的基本可行解。
max Z 3 x1 4 x2
2x1 x2 40

x1

3x2

30

x1
,
x2

0
解：1）将问题化为标准型，加入松驰变量x3、x4则标准型为:
max Z 3 x1 4 x2
2 x1 x2 x3 40
ቤተ መጻሕፍቲ ባይዱ

x
1
3x2

x4

30

x1
,
x2
,
x3
换
x3
x4
出
1
0
40 行
0
1
10
0
1
－10/3
18
0
1/3 30
0
3/5 －1/5
－4/3 －1/5
－2/5
－1 －1
单纯形法的计算步骤
Page 10
例1.9 用单纯形法求解
max Z x1 2 x2 x3
2x1 3x2 2x3 15
s
.t

1 3 x1 x2 x1、x 2、x 3
例1.10 用大M法解下列线性规划
max Z 3 x1 2 x2 x3
4x1 3x2 x3 4

x1 x2 2x1
2
2x3 x2
10 x3
1
x1、x2、x3 0
解：首先将数学模型化为标准形式
max Z 3 x1 2 x2 x3
验数，即：k max{ j | j 0} ，其对应的xk作为换入变 量。
② 确定换出变量。根据下式计算并选择θ ，选最小的θ对应基
变量作为换出变量。
L

mi
n
bi aik
aik
0

单纯形法的计算步骤
Page 8
③ 用换入变量xk替换基变量中的换出变量，得到一个新的基。 对应新的基可以找出一个新的基可行解，并相应地可以画出 一个新的单纯形表。
,
x4

0
单纯形法的计算步骤
Page 6
2）求出线性规划的初始基可行解，列出初始单纯形表。
cj
3
4
0
cB
基
b
x1
x2
x3
0
x3
40
2
1
1
0
x4
30
1
3
0
j
3
4
0
0 θi
x4 0
1 0
检验数 1 c1 (c3a11 c4a21 ) 3 (0 2 01) 3
单纯形法的计算步骤
单纯形法的进一步讨论－人工变量法 Page 18
单纯性法小结:
建
立
个数
模
型 两 三个
xj≥0
个 以上
取值
xj无 约束
xj ≤ 0
求 图 单纯 解 解 形法
法、
单 纯 形 法
不
令xj = xj′ - 令 xj’ =
处
xj″
- xj
理
xj′ ≥0
xj″ ≥0
右端项
bi ≥0
bi < 0
等式或 不等式
≤=≥
5）重复3）、4）步直到计算结束为止。
单纯形法的计算步骤
将3化为1
cj
cB
基变量
0
x3
0
x4
j
乘
0
x3
以
1/3 后
4
x2
j
得
3
x1
到
4
x2
j
换入列
3
4
b
x1
x2
40
2
1
30
1
3
3
4
30 5/3 0
10 1/3 1
5/3 0
18 1
0
40
1
0
0
Page 9
bi /ai2，ai2>0
0
0
θi
i
b1 1 0 a1,m1 a1n 1






bm 0 1 am,m1 amn m
0 0 j c j ciaij
其中：i
bi akj
akj
0
单纯形法的计算步骤
Page 5
例1.8 用单纯形法求下列线性规划的最优解
4x1 3x2 x3 x4 4

x1

x2

2x3

x5

10

2
x1

2x2

x3

1
x j 0, j 1,2, ,5
系数矩阵中不存在 单位矩阵，无法建 立初始单纯形表。
单纯形法的进一步讨论－人工变量法 Page 15
故人为添加两个单位向量，得到人工变量单纯形法数学模型：
0 17/3 1/3 1 1 28/9 -1/9 2/3
0 -98/9 -1/9 -7/3
单纯形法的计算步骤
Page 12
学习要点： 1. 线性规划解的概念以及3个基本定理 2. 熟练掌握单纯形法的解题思路及求解步骤
单纯形法的进一步讨论－人工变量法 Page 13
人工变量法： 前面讨论了在标准型中系数矩阵有单位矩阵，很容易
5x3 0

20
解：将数学模型化为标准形式：
max Z x1 2 x2 x3
2x1 3x2 2x3 x4 15
s.t

1
3 x
j
x1
x2 0, j
5x3 1,2,
x5 ,5

20
不难看出x4、x5可作为初始基变量，列单纯形表计算。
单纯形法基本原理
Page 1
凸集：如果集合C中任意两个点X1、X2，其连线上的所有点 也都是集合C中的点，称C为凸集。
凸集
顶点
凸集
不是凸集
单纯形法基本原理
Page 2
定理1：若线性规划问题存在可行解，则该问题的可行域是 凸集。
定理2：线性规划问题的基可行解X对应可行域(凸集)的顶 点。
定理3：若问题存在最优解，一定存在一个基可行解是最优 解。（或在某个顶点取得）
单纯形法的进一步讨论－人工变量法 Page 16
cj
3
2
-1
0
0
-M
-M
CB
XB
b
x1
x2
x3
x4
x5
x6
x7
θi
-M
x6
4
-4
3
1
-1
0
1
0
4
0
x5
10
1
-1
2
0
1
0
0
5
-M
x7
1
2
-2
1
0
0
0
j
3-2M 2+M
-1+2M↑
-M
0
x6
3
-6
5
0
-1
0
1
-M
x5
8
-3
3
0
0
1
0
1
1→
3/5 →
8/3
极大或极小
maxZ
minZ
新加变量 系数
xs
xa
不
约束条 加 加 减
不
处
件两端 松 入 去
处
理
同乘以 弛 人 xs
理
-1
变工加
量变入
xs
量 xa
xa
令 z′=- Z minZ =－ max z′
0 -M
A
求: j cj zj
循环
所有 是
j 0
否
找 出( j )max即 k
基变 量中是否
max Z 3 x1 2 x2 x3－Mx6 Mx7
4x1 3x2 x3 x4 x6 4

x1

x2

2x3

x5

10
2 x1 2 x2 x3 x7 1
x j 0, j 1,2, ,7
其中：M是一个很大的抽象的数，不需要给出具体的数值， 可以理解为它能大于给定的任何一个确定数值；再用前面介 绍的单纯形法求解该模型，计算结果见下表。
Page 7
3）进行最优性检验