单纯形法表的解题步骤
单纯形法表结构如下：
j c →
对应变量的价值系数
i θ
B C
b X
b
1x 2x 3x " j x
基变量的价值系数
基变量 资源列
θ规则
求的值
j σ
检验数
①一般形式
若线性规划问题标准形式如下：
123451231425max 23000284164120,1,2,5
j z x x x x x x x x x x x x x j =++++++=⎧⎪+=⎪⎨
+=⎪⎪≥=⎩"
取松弛变量345,,x x x 为基变量，它对应的单位矩阵为基。
这样就得到初始可
行基解：()()0
0,0,8,16,12T
X =。
将有关数字填入表中，得到初始单纯形表，如表
1-1所示：
表 1-1 ()()00,0,8,16,12T
X =
j c →
2 3 0 0 0
i θ
B C b X b
1x 2x 3x 4x 5x
0 3x 8 1 2 1 0 0 4 0
4x
16 4 0 0 1 0 -
5x
12 0 [4] 0 0 1 3
j σ
2 3 0 0 0
若检验数均未达到小于等于0，则对上表进行调整。
选择上表中检验数最大的列，该列对应的非变量为入基变量；再应用θ规则该列对应的各基变量对应的
θ值，选出其中最小的一行，该行对应的基变量为出基变量。
修改单纯形表，对各行进行初等变换，确保基变量组成的矩阵为单为矩阵。
修改后的单纯形表如表
1-2所示：
表 1-2 ()()10,3,2,16,0T
X =
检验数12,0σσ>，则进行继续调整，调整后的单纯形法表如表1-3所示：
表 1-3 ()()22,3,0,8,0T
X =
表1-3中， 50σ>，则继续进行调整，调整结果如表1-4所示：
表 1-4 ()()34,2,0,0,4T
X =
检验数0j σ≤，这表示目标函数值已不可能再增大，于是得到最优解：
()()3*4,2,0,0,4T
X X ==
*14z =
②带人工变量
现有线性规划问题：
12312312313123min 3211
42321,,0
z x x x x x x x x x x x x x x =−++−+≤⎧⎪−++≥⎪⎨
−+=⎪⎪≥⎩ 将上述线性规划问题用大M 法求解，在约束条件中加入松弛变量4x ，剩余变量5x ，人工变量6x ，7x 得到：
1234567123412356137min 300211423210,1,2,,7j z x x x x x Mx Mx x x x x x x x x x x x x x j =−++++++−++=⎧⎪−++−+=⎪⎨
−++=⎪⎪≥=⎩
"
其中，M 是一个任意大的正数。
用单纯形法表进行计算，由于是求MIN ，所以用所有0j σ≥来判别目标函数是否实现了最小化。
初始单纯行表如表2-1所示：
j c →
-3 1 1 0 0 M M
i θ
B C b X b
1x 2x 3x 4x 5x 6x 7x
0 4x 10 3 -2 0 1 0 0 -1 - M 6x 1 0 [1]
0 0 -1 1 -2 1
1
3x
1 -
2 0 1 0 0 0 1 -
j σ
-1 1-M 0 0 M 0 3M-1
j c →
-3 1 1 0 0 M M
i θ
B C b X b
1x 2x 3x 4x 5x 6x 7x
0 4x 12 [3]
0 0 1 -2 2 -5 4
1 2x 1 0 1 0 0 -1 1 -
2 - 1
3x
1 -
2 0 1 0 0 0 1 -
j σ
-1 0 0 0 1 M-1 M+1
上表中得到最优解，12345674,1,9,0,2x x x x x x x z ========−
③两阶段法（含有人工变量的线性规划问题）
下面介绍求解加入人工变量的线性规划问题的两阶段法。
第一阶段：不考虑原问题是否存在基可行解，给原线性规划问题加入人工变量，并构造仅含人工变量的目标函数和要求实现最小化。
如
1111111
21122211
12min 001,,,0n n m n n n n n n n m mn n n m m
n m x x x x a x a x x b a x a x x b
a x a x x b
x x x ω++++++=++++++++=⎧⎪+++=⎪⎪
⎨
⎪+++=⎪≥⎪⎩
"""""""
然后用单纯形法求解上述模型，若得到0ω=,这说明原问题存在基可行解，可以进行第二阶段计算。
否则原问题无可行解，应停止计算。
第二阶段：将第一阶段计算得到的最终表，除去人工变量。
将目标函数行的系数，换成原问题的目标函数系数，作为第二阶段计算的初始表。
各阶段计算方法及步骤与第3节单纯形法相同。
下面举例说明。
例：线性规划问题
12312312313min 3211423211,2,30
z x x x x x x x x x x x x x x =−++++≤⎧⎪−++≥⎪⎨
−+=⎪⎪≥⎩
解：先在上述线性规划问题的约束方程中加入人工变量，给出第一阶段的数学模型为：
67
1234123561374567min 211423211,2,3,,,,0
x x x x x x x x x x x x x x x x x x x x x ω=++++=⎧⎪−++−+=⎪⎨
−++=⎪⎪≥⎩ 这里6x ，7x 是人工变量。
用单纯形法求解，如表3-1所示：
表 3-1 两阶段法求解含人工变量的线性规划问题 第一阶段
j c →
0 0 0 0 0 1 1
i θ
B C b X b
1x 2x 3x 4x 5x 6x 7x
0 4x 10 3 -2 0 1 0 0 -1 - 1 6x 1 0 [1]
0 0 -1 1 -2 1
3x
1 -
2 0 1 0 0 0 1 -
j σ
0 -1 0 0 1 0 3
j c →
0 0 0 0 0 1 1
i θ
B C
b X
b
1x 2x 3x 4x 5x 6x 7x
0 4x 12 3 0 0 1 -2 2 -5 0 2x 1 0 [1]
0 0 -1 1 -2
3x
1 -
2 0 1 0 0 0 1
j σ
0 0 0 0 0 1 1
第一阶段求得的结果是0ω=，得到最优解是：
12345670, 1.1,12,0x x x x x x x =======
因为人工变量670x x ==，所以()0,1,1,12,0T
是该线性规划问题的基可行解。
于是可以进行第二阶段运算。
将第一阶段的最终表中的人工变量取消并填入原问题的目标函数的系数。
进行第二阶段的计算，如表3-2所示：
表 3-2两阶段法求解含人工变量的线性规划问题 第二阶段
j c →
-3 1 1 0 0
i θ
B C b X b
1x 2x 3x 4x 5x
0 4x 12 [3]
0 0 1 -2 4
1 2x 1 0 1 0 0 -1 - 1
3x
1 -
2 0 1 0 0 -
j σ
-1 0 0 0 1
表3-2中得到最优解为1234,1,9x x x ===，目标函数值2z =−。
④退化情况
单纯形法计算中用θ规则确定换出变量时，有时存在两个以上相同的最小比值，这样在下一次迭代中就有一个或几个基变量等于零，这就出现退化解。
这时换出变量。
尽管计算过程的循环现象极少出现，但还是有可能的。
可利用勃兰特规则解决该问题：
（1）选取0j j c z −>中下标最小的非基变量k x 为换入基变量，即
()min |0j j k j c z =−>
（2）当按θ规则计算存在两个和两个以上最小比值时，选取下标最小的基变量为换出变量。