第一章 线性规划
第三次叠代：
步骤1、将基变量x1，x2和目标函数z’分别用非基变量x3，x4表示： -x1 +x2 = 1 -x3 x2 = 2 X1
-x4
第一个约束两边同乘以-1，消去第一个约束条件中的x2，得到
= 1 +x3 -x4
-x4
x2 = 2
出的形式：
z=-(1+x3-x4)-2(2-x4)=-5-x3+3x4
步骤2、选择进基变量。由于目标函数中非基变量x3系数是负数，因此选取x3
为进基变量。但从约束条件可以看出，进基变量x3的值增加时，基变量x1的值增加，x2的值不变，因此进基变量x3的值可以无限增加，目标函数值可以无限减少，可行域不封闭，且目标函数无界。
将以上两个基变量x1，x2代入目标函数z’=-x1-2x2，得到目标函数用当前非基变量表
§1.7 单纯形表
从上一节单纯形算法的描述中可以知道，单纯形算法的实质是将非基变量视为一组参数，并将目标函数和基变量都表示成为由非基变量表示的形式。即(1.2)和(1.3)两式。这样就可以讨论当非基变量变化时，目标函数和基变量随之变化的情况。我们可以用一个矩阵来表示单纯形法迭代中所需要的全部信息，这就是所谓的单纯形表。 例1.16 用单纯形表求解例1.9中的线性规划问题，标准形式为
min z’= -x1 -2x2 s.t. min s.t.
x2
x1 +x2 +x3 x1, x2, x3, z’ +x1 +2x2
x2
=3 x4 ?0 =0 =3 x4 ?0
+x4 =1
将目标函数中的变量移到等号左边
x1 +x2 +x3 x1, x2, x3,
+x4 =1
写出系数矩阵。确定非基变量为x1，x2，基变量为x3，x4。将当前的基变量写在表的左侧。RHS（Right Hand Side）是“右边常数”的缩写。
31
第一章 线性规划
下面的表就是线性规划的初始单纯形表。在以下单纯形表中，基变量x3，x4在目标函数中的系数都等于0，基变量x3，x4在约束条件中的系数矩阵是一个单位矩阵。这是任何一张单纯形表必须满足的性质。具备了这些性质，单纯形表就实现了目标函数用非基变量表示，基变量用非基变量表示。
z x3 x4 z 1 0 0 x1 1 1 0 x2 2 1 [1] x3 0 1 0 x4 RHS 0 0 1 0 3 1 3/1 1/1 非基变量在目标函数行中的系数称为非基变量的检验数。在单纯形表中，如果所有非基变量的检验数都不是正数（即全为负数或0），该单纯形表为最优单纯形表。否则，选取检验数为最大正数的非基变量进基。
在上表中，x2的检验数为2，大于x1的检验数1，选择x2为进基变量，并计算右边常数与进基变量在约束条件中的系数的最小比值min{3/1，1/1}=1（两项比值写在单纯形表的右边），确定基变量x4离基。
以进基列和离基行的交叉元素1为主元，进行旋转运算，将主元变成1（本例中主元已经是1），主元所在列的其他元素为0，得到以下单纯形表：
z x1 x2 x3 x4 RHS z x3 x2 1 0 0 1 [1] 0 0 0 1 0 1 0 -2 -1 1 -2 2 1 2/1 -- 用同样的法则确定x1进基，x3离基，确定主元并进行旋转运算，得到以下单纯形表： z x1 x2 x3 x4 RHS
z x1 x2
1 0 0 0 1 0 0 0 1 -1 1 0 -1 -1 1 -4 2 1
非基变量x3，x4的检验数分别为-1和-1都小于0，以上单纯形表已获得最优解。最优解为： x1=2，x2=1，x3=0，x4=0，min z’=-4，即 max z=4。 例1.17 用单纯形表求解例1.15的线性规划问题，标准形式是
min z= -x1 -2x2 s.t.
x2
-x1 +x2 +x3
=1
+x4 =2
32
第一章 线性规划
x1, x2, x3, x4 ?0
以[a3，a4]为基（即以x3，x4为基变量）的单纯形表为 z X1 x2 x3 x4 RHS z x3 x4 1 0 0 1 -1 0 2 [1] 1 0 1 0 0 0 1 0 1 2 1/1 2/1 -- 1/1 -- --
x2进基，x3离基；以1为主元进行旋转运算 z x1 x2 x3 x4 RHS z x2 x4 1 0 0 3 -1 [1] 0 1 0 -2 1 -1 0 0 1 -2 1 1 x1进基，x4离基；以1为主元进行旋转运算 z x1 x2 x3 x4 RHS z X2 X1
1 0 0 0 0 1 0 1 0 1 0 -1 -3 1 1 -5 2 1 由以上单纯形表可以看出，由于非基变量x3的检验数等于1大于0，故x3可以作为进基变量，但此时进基变量在约束条件中的系数为?因此x3可无限增加，目标函数无界。
在最优单纯形表中，在获得一个最优基以及相应的最优解后，我们还可以从非基变量xj的检验数中是否有等于0，来判断这个最优解是否是唯一的最优解。在最优单纯形表中，如果所有非基变量的检验数全部小于0，则相应的最优解是唯一的；如果对于某个非基变量xj的检验数等于0并且这个非基变量在约束条件中的系数至少有一个为正值，这时仍可以将xj进基，同时可以确定离基变量，但这一次基变换并不改变目标函数的值。这样就得到了目标函数值相同的两个不同的最优解，设这两个最优解分别为X1和X2，容易验证，对任何0???1，X=?X1+(1-?)X2都是最优解，并且有相同的目标函数值：
z=CTX=CT[?X1+(1-?)X2]=?CTX1+(1-?)CTX2=?z0+(1-?)z0=z0
例1.18 多个最优解的问题。求解以下线性规划问题
min z= 2x1 -2x2 s.t.
-x1 +x2 ≤1
33
?0??0 ???1?第一章 线性规划
x2 ≤2 x2 ≥0
x1,
引进松弛变量x3、x4，列出初始单纯形表并按单纯形算法继续运行：
z x1 x2 x3 x4 RHS z x3 x4 1 0 0 -2 -1 0 x1 0 -1 [1] 2 [1] 1 x2 0 1 0 0 1 0 x3 -2 1 -1 0 0 1 0 1 2 1/1 2/1 -- 1/1 x2进基，x3离基 z z x2 x4 1 0 0 x4 RHS 0 0 1 -2 1 1 已获得最优解 X1=(x1，x2，x3，x4)T=(0，1，0，1)T，z=-2
但在最优单纯形表中，非基变量x1的检验数等于0，因此还可以将x1进基，x4
离基，再进行一次基变换，得到以下单纯形表： z x1 x2 x3 x4 RHS
z x2 x1
1 0 0 0 0 1 0 1 0 -2 0 -1 0 1 1 -2 2 1
得到新的基以及新的最优解：
X2=(x1，x2，x3，x4)T=(1，2，0，0)T，z=-2
4维空间中这两个点X1，X2以及它们连线上的点都是最优解。最优解集可以表示为：
?0??1??1?t??1??2??2?t?? (0≤t≤1) X=tX1+(1-t)X2=t????(1?t)??????0??0??0???????10t??????综上所述，单纯形算法（极小化问题）可以用以下框图表示：
34
第一章 线性规划
开始 确定初始可行基B 确定非基变量下标集合R B?1b?bB?1aj?yj计算非基变量的检验数 ?1zj?cj?CTBBaj?cj max{zj?cj}?zk?ck j?R唯一最优解 no 终止 zk-ck>0? yes xk进基 no zk-ck=0? yes 多个最优解 终止 Yk?0? no yes 目标函数无界 终止 ?b?bmin?iyik?0??ryrk?yik?xBr离基，确定主元yrk 以yrk为主元进行旋转运算，更新R，zj-cj，b以及Yj 1.10 为了熟练掌握单纯形表的计算，再举两个例子。 例1.19 用单纯形表求以下线性规划问题的最优解。
35
图