Made By Haowei Song
单纯形法表的解题步骤
单纯形法表结构如下：
jc→ 对应变量的价值系数
iθ
BC
bX b 1x
2x
3x "
jx
基变量的
价值系数 基变量 资源列
θ规则
求的值
jσ 检验数 ①一般形式
若线性规划问题标准形式如下：
12345
123
14
25max23000
28
416
412
0,1,2,5
jzxxxxx
xxx
xx
xx
xj=++++
++=⎧
⎪+=⎪
⎨+=⎪
⎪≥=⎩"
取松弛变量
345,,xxx为基变量，它对应的单位矩阵为基。这样就得到初始可
行基解：()()00,0,8,16,12TX=。将有关数字填入表中，得到初始单纯形表，如表
1-1所示：
表 1-1 ()()00,0,8,16,12TX=
jc→ 2 3 0 0 0
iθ
BC
bX b 1x
2x
3x
4x
5x
0 3x 8 1 2 1 0 0 4
0 4x 16 4 0 0 1 0 - Made By Haowei Song
0 5x 12 0 [4] 0 0 1 3
jσ 2 3 0 0 0
若检验数均未达到小于等于0，则对上表进行调整。选择上表中检验数最大
的列，该列对应的非变量为入基变量；再应用θ规则该列对应的各基变量对应的
θ值，选出其中最小的一行，该行对应的基变量为出基变量。修改单纯形表，对
各行进行初等变换，确保基变量组成的矩阵为单为矩阵。修改后的单纯形表如表
1-2所示：
表 1-2 ()()10,3,2,16,0TX=
jc→ 2 3 0 0 0
iθ
BC
bX b 1x
2x
3x
4x
5x
0 3x 2 [1] 0 1 0 1
2− 2
0 4x 16 4 0 0 1 0 4
3 2x 3 0 1 0 0 1
4 -
jσ 2 1 0 0 3
4−
检验数
12,0σσ>，则进行继续调整，调整后的单纯形法表如表1-3所示：
表 1-3 ()()22,3,0,8,0TX=
jc→ 2 3 0 0 0
单纯形法原理及步骤
单纯形法，求解线性规划问题的通用方法。单纯形是美国数学家G.B.丹齐克于1947年首先提出来的。它的理论根据是：线性规划问题的可行域是 n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不是，则再转换,按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。
单纯形法是从某一基可行解出发，连续地寻找相邻的基可行解，直到达到最优的迭代过程，其实质是解线性方程组。
概述：
根据单纯形法的原理，在线性规划问题中，决策变量（控制变量）x1，x2，…x n的值称为一个解,满足所有的约束条件的解称为可行解。使目标函数达到最大值（或最小值）的可行解称为最优解。这样，一个最优解能在整个由约束条件所确定的可行区域内使目标函数达到最大值（或最小值）。求解线性规划问题的目的就是要找出最优解。
最优解可能出现下列情况之一：①存在着一个最优解；②存在着无穷多个最优解；③不存在最优解，这只在两种情况下发生，即没有可行解或各项约束条件不阻止目标函数的值无限增大（或向负的方向无限增大）。
单纯形法的一般解题步骤可归纳如下：①把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。②若基本可行解不存在，即约束条件有矛盾，则问题无解。③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。④按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。
Made By Haowei Song
单纯形法表的解题步骤
单纯形法表结构如下：
jc→ 对应变量的价值系数
iθ
BC
bX b 1x
2x
3x "
jx
基变量的
价值系数 基变量 资源列
θ规则
求的值
jσ 检验数 ①一般形式
若线性规划问题标准形式如下：
12345
123
14
25max23000
28
416
412
0,1,2,5
jzxxxxx
xxx
xx
xx
xj=++++
++=⎧
⎪+=⎪
⎨+=⎪
⎪≥=⎩"
取松弛变量
345,,xxx为基变量，它对应的单位矩阵为基。这样就得到初始可
行基解：()()00,0,8,16,12TX=。将有关数字填入表中，得到初始单纯形表，如表
1-1所示：
表 1-1 ()()00,0,8,16,12TX=
jc→ 2 3 0 0 0
iθ
BC
bX b 1x
2x
3x
4x
5x
0 3x 8 1 2 1 0 0 4
0 4x 16 4 0 0 1 0 - Made By Haowei Song
0 5x 12 0 [4] 0 0 1 3
jσ 2 3 0 0 0
若检验数均未达到小于等于0，则对上表进行调整。选择上表中检验数最大
的列，该列对应的非变量为入基变量；再应用θ规则该列对应的各基变量对应的
θ值，选出其中最小的一行，该行对应的基变量为出基变量。修改单纯形表，对
各行进行初等变换，确保基变量组成的矩阵为单为矩阵。修改后的单纯形表如表
1-2所示：
表 1-2 ()()10,3,2,16,0TX=
jc→ 2 3 0 0 0
iθ
BC
bX b 1x
2x
3x
4x
5x
0 3x 2 [1] 0 1 0 1
2− 2
0 4x 16 4 0 0 1 0 4
3 2x 3 0 1 0 0 1
4 -
jσ 2 1 0 0 3
4−
检验数
12,0σσ>，则进行继续调整，调整后的单纯形法表如表1-3所示：
表 1-3 ()()22,3,0,8,0TX=
jc→ 2 3 0 0 0
Made By Haowei Song
单纯形法表的解题步骤
单纯形法表结构如下：
jc→ 对应变量的价值系数
iθ
BC
bX b 1x
2x
3x "
jx
基变量的
价值系数 基变量 资源列
θ规则
求的值
jσ 检验数 ①一般形式
若线性规划问题标准形式如下：
12345
123
14
25max23000
28
416
412
0,1,2,5
jzxxxxx
xxx
xx
xx
xj=++++
++=⎧
⎪+=⎪
⎨+=⎪
⎪≥=⎩"
取松弛变量
345,,xxx为基变量，它对应的单位矩阵为基。这样就得到初始可
行基解：()()00,0,8,16,12TX=。将有关数字填入表中，得到初始单纯形表，如表
1-1所示：
表 1-1 ()()00,0,8,16,12TX=
jc→ 2 3 0 0 0
iθ
BC
bX b 1x
2x
3x
4x
5x
0 3x 8 1 2 1 0 0 4
0 4x 16 4 0 0 1 0 - Made By Haowei Song
0 5x 12 0 [4] 0 0 1 3
jσ 2 3 0 0 0
若检验数均未达到小于等于0，则对上表进行调整。选择上表中检验数最大
的列，该列对应的非变量为入基变量；再应用θ规则该列对应的各基变量对应的
θ值，选出其中最小的一行，该行对应的基变量为出基变量。修改单纯形表，对
各行进行初等变换，确保基变量组成的矩阵为单为矩阵。修改后的单纯形表如表
1-2所示：
表 1-2 ()()10,3,2,16,0TX=
jc→ 2 3 0 0 0
iθ
BC
bX b 1x
2x
3x
4x
5x
0 3x 2 [1] 0 1 0 1
2− 2
0 4x 16 4 0 0 1 0 4
3 2x 3 0 1 0 0 1
4 -
jσ 2 1 0 0 3
4−
检验数
12,0σσ>，则进行继续调整，调整后的单纯形法表如表1-3所示：
表 1-3 ()()22,3,0,8,0TX=
jc→ 2 3 0 0 0
