单纯形法的计算步骤
换入列
将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
j j j
x4
x3 x2 x1 x2
30
1
3
3
4
0
0
1
40 10
换 出 行
乘 以 1/3 后 得 到
0 4
30 10
18 4
Page 7
故人为添加两个单位向量，得到人工变量单纯形法数学模型：
其中：M是一个很大的抽象的数，不需要给出具体的数值，可以理解为它能大于 给定的任何一个确定数值；再用前面介绍的单纯形法求解该模型，计算结果见下 表。
单纯形法的进一步讨论－人工变量法
cj CB 0 -M -M 0 -M -1 2 -M -1 2 3 -1 XB x6 x5 x7 x6 x5 x3 x2 x5 x3 x2 x1 x3 b 4 10 1 3 8 1 3/5 31/5 11/5 13 31/3 19/3 3 x1 -4 1 2 3-2M -6 -3 2 5-6M －6/5 3/5 －2/5 5↑ 0 1 0 0 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 0 1 0 0 0 1 0 0 2 5/3 2/3 -25/3 1 0 0 0 0 x5 0 1 0 -M x6 1 0 0 -M x7 0 0 1
单纯形法的计算步骤
3）进行最优性检验
如果表中所有检验数 止。否则继续下一步。
Page 3
，则表中的基可行解就是问题的最优解，计算停 0 j
4）从一个基可行解转换到另一个目标值更大的基可行解， 列出新的单纯形表
① 确定换入基的变量。选择 j 0 ，对应的变量xj作为换入
变量，当有一个以上检验数大于0时，一般选择最大的一 个检验数，即： ，其对应的xk作为 k max{ j | j 0} 换入变量。 变量作为换出变量。
单纯形法的计算步骤
Page 2
2）求出线性规划的初始基可行解，列出初始单纯形表。
cj cB 0 基 x3 b 40 3 x1 2 4 x2 1 0 x3 1 0 x4 0
θi
0
j
检验数
x4
30
1
3
3
4
0
0
1
0
1 c1 (c3a11 c4a21 ) 3 (0 2 0 1) 3
Page 9
新加变量 系数 xs xa
minZ
令 z′=- Z minZ =－ max z′
0
-M
单 纯 形 法
单纯形法的计算步骤
例1.8 用单纯形法求下列线性规划的最优解
max Z 3 x1 4 x 2 2 x1 x 2 40 x1 3 x 2 30 x , x 0 1 2
解：1）将问题化为标准型，加入松驰变量x3、x4则标准型为:
Page 1
max Z 3 x1 4 x 2 2 x1 x 2 x 3 40 x1 3 x 2 x 4 30 x , x , x , x 0 1 2 3 4
解：首先将数学模型化为标准形式
Page 6
max Z 3 x1 2 x 2 x 3 4 x1 3 x 2 x 3 x 4 4 x1 x 2 2 x 3 x 5 10 2 x1 2 x 2 x 3 1 x j 0, j 1,2, ,5
3 4
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 －30
单纯形法的进一步讨论－人工变量法
例1.10 用大M法解下列线性规划
max Z 3 x1 2 x 2 x 3 4 x1 3 x 2 x 3 4 x1 x 2 2 x 3 10 2 x 1 2 x 2 x 3 1 x1、x 2、x 3 0
bi L min a ik 0 a ik
② 确定换出变量。根据下式计算并选择θ ，选最小的θ对应基
单纯形法的计算步骤
③
Page 4
用换入变量xk替换基变量中的换出变量，得到一个新的基。 对应新的基可以找出一个新的基可行解，并相应地可以画出 一个新的单纯形表。
5）重复3）、4）步直到计算结束为止。
系数矩阵中不存在单位矩 阵，无法建立初始单纯形 表。
单纯形法的进一步讨论－人工变量法
max Z 3 x1 2 x 2 x 3－Mx6 Mx7 4 x1 3 x 2 x 3 x 4 x 6 4 x1 x 2 2 x 3 x 5 10 2 x1 2 x 2 x 3 x 7 1 x j 0, j 1,2,,7
Page 8
θi 4 5 1 3/5 8/3 —— —— 31/3 ——
j
→ →
j
→
j
j
单纯形法的进一步讨论－人工变量法
单纯性法小结:
建 立 模 型 两 个 求 解 图 解 法、 三个 以上 单纯 形法 不 处 理 xj′ ≥0 xj″ ≥0 xj≥0 xj 无 约束 令xj = xj′ xj″ 令 xj’ = - xj 不 处 理 约束条 件两端 同乘以 -1 加 松 弛 变 量 xs 加 入 人 工 变 量 xa 减 去 xs 加 入 xa 不 处 理 xj ≤ 0 bi ≥0 bi < 0 ≤ 个 数 取 值 右 端 项 等式或 不等式 = ≥ 极大或极小 maxZ