运筹学-第一章-单纯形法进一步讨论

退化 即计算出的 θ（用于确定换出变量）存在有两个以上 相同的最小比值，会造成下一次迭代中由一个或几个基 变量等于零，这就是退化（会产生退化解）。 为避免出现计算的循环，勃兰特(Bland)提出一个简 便有效的规则（摄动法原理）： ⑴ 当存在多个 j 0 时，选下标最小的非基变量为换 入变量；
解：首先将数学模型化为标准形式
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 x 2 x x 1 2 3 1 x j 0, j 1,2, ,5
1
0 0 0 1 0 0 2 5/3 2/3 -25/3
0
0 0
8/3
—— —— ——
j
x2 x5 x3 x2 x1 x3
x3
31/3 →
j
j
单纯形法的进一步讨论－人工变量法
例1.11 用大M法解下列线性规划
max Z 3 x1 x2 x3
x1 2 x2 x3 11 4 x x 2 x 3 1 2 3 +x3 1 2 x1 解：首先将数学模型化为标准形式 x1、x2、x3 0
max z=-2x1-3x2+0x3 -M x4-M x5 s .t x1+x2 -x3+ x4 =3 x1+2x2 +x5 =4 xj0, (j=1,2,3,4,5)
这种处理方法称为大M法，以下则可完全按单纯形法 求解。
单纯形法的进一步讨论－人工变量法
例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
运 筹 帷 幄 之 中 云南财经大学 物流学院 窦志武
决 胜
单纯形法进一步讨论
千 里 之 外
单纯形法的进一步讨论－人工变量法
人工变量法： 前面讨论了在标准型中系数矩阵有单位矩阵，很容易 确定一组基可行解。在实际问题中有些模型并不含有单位 矩阵，为了得到一组基向量和初基可行解，在约束条件的 等式左端加一组虚拟变量，得到一组基变量。这种人为加 的变量称为人工变量，构成的可行基称为人工基，用大M 法或两阶段法求解，这种用人工变量作桥梁的求解方法称 为人工变量法。
单纯形法的进一步讨论－人工变量法
故人为添加两个单位向量，得到人工变量单纯形法数学模型：
max Z 3x1 x2 x3 + 0x4 + 0x5－Mx6 Mx7 11 3 x1 x2 x3 x4 -4x x 2 x x5 +x6 3 1 2 3 x3 x7 1 2 x1 x j 0, j 1, 2, L , 7
其中：M是一个很大的抽象的数，不需要给出具体的数值， 可以理解为它能大于给定的任何一个确定数值；再用前面介 绍的单纯形法求解该模型，计算结果见下表。
单纯形法的进一步讨论－人工变量法
Cj CB 0 XB x4 b 11 3 x1 1 -1 x2 -2 -1 x3 1 0 x4 1 0 x5 0 -M x6 0 -M x7 0 11
单纯形法的进一步讨论－两阶段法
第一阶段的线性规划问题可写为：
min x6 x7 x4 =11 x1 2 x2 x3 4 x x 2 x x x6 3 1 2 3 5 x3 x7 1 2 x1 x1 , x2 ,，x7 0
2
1 3 0 0
0
0 0 1 0
-1
0 -1 0 -1
1
0 0 0 1
0
1 0 -1 -2
3/2
1 － 1
→ →
0
ω 0 0 0 ω
x3
x4 x2 x3
1
1 12 1 1 0
-2
0 3 0 -2 0
0
1 0 1 0 0
1
0 0 0 1 0
0
0 1 0 0 0
0
-1 -2 -1 0 0
0
0 2 1 0 -1
-M
-M 0 -M -1
x6
3
1 10 1 1
-4
-2 3-6M 3 0 -2 1
1
0 -1+M -2 1 0 -1+M
2
1 -1+3M 0 0 1 0
0
0 0 1 0 0 0
-1
0 -M 0 -1 0 -M
1
0 0 0 1 0 0
0
1 0 -1 -2 1 -3M+1
3/2
1 － 1 －
j
x7 x4 x6 x3
单纯形法的进一步讨论
C 0 C 0 0 Z XB X3 X4 B 1 2 0 x1 -1 -1/2 2 x2 1 1 2 x3 1 0 0 x4 0 1 0 2 2 0 θ
-1 因1 = 2>0 但 P1 = 1 0 所以原问题无最优解 - 2
单纯形法的进一步讨论
第一阶段单纯形法迭代的过程见下表
单纯形法的进一步讨论－两阶段法
Cj CB 0 XB x4 b 11 0 x1 1 0 x2 -2 0 x3 1 0 x4 1 0 x5 0 -1 x6 0 -1 x7 0 11
-1
-1 ω 0 -1
x6
x7 x4 x6
3
1 4 10 1
-4
-2 6 3 0
1
0 1 -2 1
j
0
-1 2 0 -1 2 3 -1
→ →
x5
8
1 3/5 31/5 11/5 13 31/3 19/3
-3
2 5-6M －6/5 3/5 －2/5 5↑ 0 1 0 0
3
-2 5M↑ 1 0 0 0 1 0 0 0
0
1 0 0 0 1 0 0 0 1 0
0
0 -M －1/5 3/5 －2/5 0 1 1 0 -5
→ →
j
单纯形法的进一步讨论－人工变量法
Cj CB 0 XB x4 b 12 3 x1 3 -1 x2 0 -1 x3 0 0 x4 1 0 x5 -2 -M x6 2 -M x7 -5 4
→
-1
-1 Z 3 -1 -1 Z
x2
x3 x1 x2 x3
1
1 -2 4 1 9 2
0
-2 1 1 0 0 0
1
0 0 0 1 0 0
0
1 0 0 0 1 0
0
0 0 1/3 0 2/3 -1/3

-1
0 -1 -2/3 -1 -4/3 -1/3
1
0 -M+1 2/3 1 4/3 -M+1/3
-2
1 -M-1 -5/3 -2 -7/3 -M+2/3
－
－
单纯形法的进一步讨论－两阶段法
用计算机处理数据时，只能用很大的数代替M,可能造 成计算机上的错误，故多采用两阶段法。 第一阶段： 在原线性规划问题中加入人工变量，构造如下模型：
单纯形法的进一步讨论－两阶段法
第二阶段：
cj
cB 0 -1 -1 Z 3 -1 -1 Z x1 x2 x3 xB x4 x2 x3 b 12 1 1 -2 4 1 9 2
maxZ 3x1 x2 x3 0x4 0 x5
3
x1 3 0 -2 1 1 0 0 0
-1
x2 0 1 0 0 0 1 0 0
单纯形法的进一步讨论－人工变量法
故人为添加两个单位向量，得到人工变量单纯形法数学模型：
max Z 3 x1 2 x2 x3－Mx6 Mx7 x6 4 4 x1 3 x2 x3 x4 x x 2x x5 10 1 2 3 x7 1 2 x1 2 x2 x3 x j 0, j 1, 2, L , 7
max Z 3 x1 x2 x3 x1 2 x2 x3 x4 11 4 x x 2 x x 3 1 2 3 5 x3 1 2 x1 x j 0, j 1, 2, L ,5
系数矩阵中不存在 单位矩阵，无法建 立初始单纯形表。
其中：M是一个很大的抽象的数，不需要给出具体的数值， 可以理解为它能大于给定的任何一个确定数值；再用前面介 绍的单纯形法求解该模型，计算结果见下表。
单纯形法的进一步讨论－人工变量法
cj CB -M 0 -M -M XB x6 x5 x7 x6 b 4 10 1 3 3 x1 -4 1 2 3-2M -6 2 x2 3 -1 -2 2+M 5 -1 x3 1 2 1 -1+2M↑ 0 0 x4 -1 0 0 -M -1 0 1 3/5 0 x5 0 1 0 -M x6 1 0 0 -M x7 0 0 1 θi 4 5 1
-1
x3 0 0 1 0 0 0 1 0
0
x4 1 0 0 0 1/3 0 2/3 -1/3
0
x5 -2 -1 0 -1 -2/3 -1 -4/3 -1/3 4 － －
→
∴最优解为（4 1 9 0 0），目标函数 Z = 2
单纯形法的进一步讨论
无可行解 通过大Ｍ法或两阶段法求初始的基本可行解。但是 如果在大Ｍ法的最优单纯形表的基变量中仍含有人工变 量，或者两阶段法的辅助线性规划的目标函数的极小值 大于零，那么该线性规划就不存在可行解。
1
-3 -5 -2 0 -1
－
单纯形法的进一步讨论－两阶段法