Page 6
解：首先将数学模型化为标准形式
max Z 3 x 1 2 x 2 x 3 4 x1 3 x2 x3 x4 4 x 1 x 2 2 x 3 x 5 10 2 x1 2 x2 x 3 1 x j 0 , j 1, 2 , ,5
系数矩阵中不存在单位矩 阵，无法建立初始单纯形 表。
单纯形法的进一步讨论－人工变量法
max Z 3 x 1 2 x 2 x 3－ Mx Mx
Page 7
故人为添加两个单位向量，得到人工变量单纯形法数学模型：
6 7
4 x1 3 x2 x3 x4 x6 4 x 1 x 2 2 x 3 x 5 10 2 x1 2 x2 x3 x7 1 x j 0 , j 1, 2 , ,7
L
② 确定换出变量。根据下式计算并选择θ ，选最小的θ对应基
bi min a ik 0 a ik
单纯形法的计算步骤
③
Page 4
用换入变量xk替换基变量中的换出变量，得到一个新的基。 对应新的基可以找出一个新的基可行解，并相应地可以画出 一个新的单纯形表。
5）重复3）、4）步直到计算结束为止。
Page 1
单纯形法的计算步骤
Page 2
2）求出线性规划的初始基可行解，列出初始单纯形表。
cj cB 0 基 x3 b 40 3 x1 2 4 x2 1 0 x3 1 0 x4 0
θi
0
x4
30
1
3
3
4
0
0
1
0

j
检验数
1 c 1 ( c 3 a 11 c 4 a 21 ) 3 ( 0 2 0 1 ) 3
0 x5 0 1 0
-M x6 1 0 0
→ →

0 -M -1 x6 x5 x3
-6 -3 2 5-6M －6/5 3/5 －2/5 5↑
0 1 0 0 0 1 0 0 2 5/3 2/3 -25/3
1 0 0 0
3/5 8/3 —— —— 31/3 ——

2 -M -1 x2 x5 x3
3/5 31/5 11/5
单纯形法的计算步骤
换入列
将3化为1
cj cB 0 基变量 x3 b 40 3 x1 2 4 x2 1 0 x3 1
Page 5
bi /ai2，ai2>0
0 x4 0 θi
0

x4
j
30
1
3
3
4
0
0
1
40 10
换 出 行
乘 以 1/3 后 得 到Biblioteka 0 4x3x2
j
30 10
18 4
3 4
x1

x2
j
3 x1 -4 1 2 3-2M 3 8 1
j
2 x2 3 -1 -2 2+M 5 3 -2 5M↑ 1 0 0 0 1 0 0 0
-1 x3 1 2 1 -1+2M↑ 0 0 1 0 0 0 1 0 0 0 1 0
0 x4 -1 0 0 -M -1 0 0 -M －1/5 3/5 －2/5 0 1 1 0 -5
j
→

2 3 -1
x2 x1 x3
13 31/3 19/3
j
0 1 0 0

单纯形法的进一步讨论－人工变量法
单纯性法小结:
建 立 模 型 两 个 求 解 图 解 法、 三个 以上 单纯 形法 不 处 理 xj′ ≥0 xj″ ≥0 xj≥0 xj无 约束 令xj = xj′ xj″ 令 xj’ = - xj 不 处 理 约束条 件两端 同乘以 -1 加 松 弛 变 量 xs 加 入 人 工 变 量 xa 减 去 xs 加 入 xa 不 处 理 xj ≤ 0 bi ≥0 bi < 0 ≤ 个 数 取 值 右 端 项 等式或 不等式 = ≥ 极大或极小 maxZ
单纯形法的计算步骤
3）进行最优性检验
如果表中所有检验数 止。否则继续下一步。
Page 3
，则表中的基可行解就是问题的最优解，计算停 0 j
4）从一个基可行解转换到另一个目标值更大的基可行解， 列出新的单纯形表
① 确定换入基的变量。选择 j 0 ，对应的变量xj作为换入
变量，当有一个以上检验数大于0时，一般选择最大的一 个检验数，即： max{ j | j 0 } ，其对应的xk作为 k 换入变量。 变量作为换出变量。
其中：M是一个很大的抽象的数，不需要给出具体的数值，可以理解为它能大于 给定的任何一个确定数值；再用前面介绍的单纯形法求解该模型，计算结果见下 表。
单纯形法的进一步讨论－人工变量法
cj CB 0 -M -M XB x6 x5 x7 b 4 10 1
j
Page 8
-M x7 0 0 1 θi 4 5 1
单纯形法的计算步骤
例1.8 用单纯形法求下列线性规划的最优解
max Z 3 x 1 4 x 2 2 x 1 x 2 40 x 1 3 x 2 30 x1 , x 2 0
解：1）将问题化为标准型，加入松驰变量x3、x4则标准型为:
max Z 3 x 1 4 x 2 2 x 1 x 2 x 3 40 x 1 3 x 2 x 4 30 x1 , x 2 , x 3 , x4 0
5/3 1/3 5/3 1 0 0
0 1 0 0 1 0
1 0 0 3/5 －1/5 －1
－1/3 1/3 －4/3 －1/5 －2/5 －1
0
18 30
单纯形法的进一步讨论－人工变量法
例1.10 用大M法解下列线性规划
max Z 3 x 1 2 x 2 x 3 4 x1 3 x2 x1 x 2 2 x3 2 x1 2 x2 x 、x 、x 2 3 1 x3 4 10 x 3 1 0
Page 9
新加变量 系数 xs xa
minZ
令 z′=- Z minZ =－ max z′
0
-M
单 纯 形 法