第二阶段：以第一阶段的最优解(不含人工变量)为初 始解，以原目标函数为目标函数。
例8 试用两阶段法求解线性规划问题
min z =-3x1+x2+x3
x1 2 x2 x3 11
s.t.

4 x1 2 x1

x2

2x3 3 x3 1
x1 , x2 , x3 0
0 0 -1 0 0
x2

3 5 11/5
Z0=0
Z1=15
x1
如果将x1换入基底，得 另一解，由可行域凸性 易知，有两个最优解必 有无穷多组最优解 当非基底变量的检验数 中有取零值，或检验数 中零的个数大于基变量 个数时，有无穷多解。
四、无（有）界解
max z=x1+x2 -2x1+x2 4 x1- x2 2 -3x1+x23 x1 ,x2 0
反之，若加了人工变量的问题解后最优解中仍含人工变量为 基变量，便说明原问题无可行解。例3的单纯形表格为：
Cj
3
-1
-1
0
0
-M
CB XB b
x1
x2
x3
x4
x5
x6
0 x4 1
1
-2
1
1
0
0
-M x6 13 -4
1
2
0
-1
1
-M x7 1 -2
0
[1] 0
0
0
j
3-6M M-1 3M-1 0
-M
x1 2 x2 x3 x4
11

4 2
x1 x1

x2

2
x3 x3
x5 x6 3 x7 1
x1 , , x7 0
这时，初始基和初始基可行解很明显。X(0)=(0，0，0， 11，0，3，1)T不满足原来的约束条件。如何使得可从 X(0)开始，经迭代逐步得到x6=0，x7=0 的基可行解，从 而求得问题的最优解，有两种方法：
0
σj
-1
0
-3 x1 4
1
0
1 x2 1
0
1
0 x3 9
0
0
σj
20
0
1
00

x3
x4
x5
0
1 -2 4
0
0 -1 —
1
0 0—
0
01
0 1/3 -2/3
0
0 -1
1 2/3 -4/3
0 1/3 1/3
5. 2 线性规划问题解的讨论
一、无可行解
max z=2x1+4x2 x1 +x2 10 2x1 +x2 40 x1 ,x2 0
0 x4 16
4
0
0
10
4
3 x2 3
0 1 0 0 1/4 -
-z
-9
2 0 0 0 -3/4
X(1)=(0，3，2，16，0)T， z1 =9
cj
2 30 0 0
CB XB
b
x1
x2
x3
x4
x5
2 x1 2 0 x4 8 3 x2 3
1
0
1
0 -1/2 -
0 0 -4 1 2
4
0 1 0 0 1/4 12
x2

2 x3 x3
3 1
x1 , x2 ,x 3 0
标准型：
max z’ =3x1-x2-x3
x1 2 x2 x3 x4 11
s.t.

4 2
x1 x1

x2 2x3 x3
x5 3 1
x1 , , x5 0
其中第2、3个约束方程中无明显基变量，分别加上人工变x6, x7
4 x2 20 0
1 0 1/3
3 x1 20 1
0 0 1/3
cj- zj
0 0 0 -7/3
x2
x1
此题初始解是退化的。 最优解也是退化解。 退化解迭代中，当换入 变量取零值时目标函数 值没有改进，
三、 有无穷多最优解的情况
最优解中有非基变量的检验数等于零的 情况。以这种非基变量作为换入变量，迭代可 求得另一基最优解。
例8 min z =-3x1+x2+x3
x1 2 x2 x3 11
s.t.

4x1 2 x1
x2

2
x3 x3
3 1
x1 , x2 ,x3 0
例8 s.t.
min z =-3x1+x2+x3
x1 2 x2 x3 11

4 x1 2 x1
3 40
x1 x2 x3 1 11 2 10 [1] -1 0
3+M 4-M 0
0 [2] 1 0 30 1 -1 0
0 70 0 1 1/2 0 0 -3/2 1 0 1/2
0 -M
θ x4 x5
00 1 -1 01
00
0 1 0
0 0 1 0
cj- zj
0 0 -3.5 0
0 x3 0 0
0 1 -1/3
X* = (4，1，9，0，0), z* = 2
0 -1
0 -M
-2 -1
0 -1
-2/3 -1
-4/3 -1/3
0
-1
1
-2
1
0
1
0 -3M+1
4
2.两阶段法
第一阶段：以人工变量之和最小化为目标函数 min = x6+x7
只要原问题有可行解，该最小化问题的最优目标函数值就 是 0，解得的最优解 x6=0，x7=0，对应原问题一个基可行解。 反之若该问题的最优解目标函数值大于零，则说明原问题无可 行解。
检验数 中零的 个数多 于基变 量的个 数
检验数大 于零，但 对应列元 素小于等 于零，无 换出变量
单纯形法小结
根据实际问题给出数学模型,列出初始单纯形表,进行标准化,见表
xj≥0 变 xj≤0 量 xj 无约束
约 b>0
不需要处理
令 xj′=-xj; xj′≥0 令 xj=xj′-xj″;xj′,xj″≥0 不需要处理
CB XB
b
x1
x2
x3
x4
x5
2 x1 4 0 x5 4 3 x2 2
1 0 0 1/4 0 0 0 -2 1/2 1 0 1 1/2 -1/8 0
-z
-14
0
0 -1.5 -1/8 0
X(3)=(4，2，0，4，0)T， z3 =14
§5 单纯形法的进一步讨论
5．1 人工变量法
解决初始基可行解的问题。当某个约束方 程中没有明 显的基变量时，在该方程中加上 人工变量。
0
-M

x7
0
11
0 3/2
1
1
0
0 x4 10 3
-2
0
1
-M x6 1
0
[1]
0
0
-1 x3 1 -2
0
1
0
1 -1+M 0
0
0 x4 12 [3]
0
-1 x2 1 0
1
-1 x3 1 -2
0
1
0
0
1
0
0
1
0
0
0
3 x1 4
1
0
0
1/3
-1 x2 1
0
1
0
0
-1 x3 9
0
0
0
0
1
2/3
0 -1/3
向量Pk 0，则此问题是无界解，停止计算。否则，转入下一步 。
(4).根据max(j > 0) =k，确定xk为换入变量，按 规则计算 =min{bi/aik\aik>0}
可确定第l行的基变量为换出变量。转入下一步。 (5).以 alk 为主元素进行迭代(即用高斯消去法或称为旋转变 换)，把 xk 所对应的列向量变换为(0，0，…，1，…，0)T，将
勃兰特规则(P35)可避免死循环。
例:
max z=3x1+4x2 x1 +x2 40
2x1+x260 x1-x2 =0 x1 ,x2 0
cj →
CB XB b 0 x3 40 0 x4 60 -M x5 0
cj- zj
0 x3 40 0 x4 60 3 x1 0
cj- zj 4 x2 20 0 x4 0 3 x1 20
任一最优解可表示为所有基最优解的凸 组合。
例 max z=3x1+5x2 3x1 +5x2 15 2x1 + x2 5 2x1+2x2 11 x1 ,x2 0
CB XB b
0 x3 15
0 x4 5
0 x5 11
cj-zj
5 x2 3
0 x4 2
0 x5
5
cj-zj
3 50 00 x1 x2 x3 x4 x5 3 [5] 1 0 0 2 1010 2 2001 3 5000 3/5 1 1/5 0 0 7/5 0 -1/5 1 0 4/5 0 -2/5 0 1
-z
-13
0
0 -2
0 1/4
cj
2 30 0 0
CB XB
b
x1
x2
x3
x4
x5
2 x1 2 0 x4 8 3 x2 3
1
0
1
0 -1/2 -
0 0 -4 1 (2 ) 4