第一章 线性规划
数z’=-x1-2x2，得到目标函数用当前非基变量表出的形式：
z’=-(2-x3+x4)-2(1-x4)=-4+x3+x4
步骤2、选择进基变量。由于目标函数中非基变量x3，x4的系数都是正数，因此任何一个进基都不能使目标函数减少，而只会使目标函数增大。已经达到最优解。最优解为：
(x1，x2，x3，x4)=(2，1，0，0)，min z’=-4。
原问题的最优解为：(x1，x2)=(2，1)，max z=4。
根据以上讨论，（目标函数极小化问题）单纯形法的步骤可描述如下： 步骤0（初始步骤）：找到一个初始的基和相应基础可行解（极点），确定相应的基变量、非基变量（全部等于0）以及目标函数的值，并将目标函数和基变量分别用非基变量表示。
步骤1、根据目标函数用非基变量表出的表达式中非基变量的系数，选择一个非基变量，使它的值从当前值0开始增加时，目标函数值随之减少。这个选定的非基变量称为“进基变量”。
如果任何一个非基变量的值增加都不能使目标函数值减少，则当前的基础可行解就是最优解。
步骤2、在基变量用非基变量表出的表达式中，观察进基变量增加时各基变量变化情况，确定基变量的值在进基变量增加过程中首先减少到0的变量，这个基变量称为“离基变量”。当进基变量的值增加到使离基变量的值降为0时，可行解移动到相邻的极点。
如果进基变量的值增加时，所有基变量的值都不减少，则表示可行域是不封闭的，且目标函数值随进基变量的增加可以无限减少。
步骤3、将进基变量作为新的基变量，离基变量作为新的非基变量，确定新的基、新的基础可行解和新的目标函数值。返回步骤1。 例1.12 用单纯形法求解以下线性规划问题
max z= x1 +3x2 s.t.
x1 +x2 ≤6 -x1 +2x2 ≤8 x1,
x2 ≥0
26
第一章 线性规划
x2 z=15.3 z=12 z=9 z=6 z=3 z=0 6 5 4 3 2 1 x1 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 图 1.7 标准化，得到
min z’= s.t.
第一次叠代
步骤1：初始非基变量x1=x2=0，基变量x3=6，x4=8，初始基础可行解为
(x1，x2，x3，x4)=(0，0，6，8)，z’=0，
对应于极点O。
基变量和目标函数用非基变量表示
z’= -x1 -3x2 x3
= =
x4
-x1 -3x2 -x1 +2x2 x1,
x2,
=6 =8
x1 +x2 +x3
x3,
+x4
x4 ≥0
x2 x1=0 6 5 x4=0 4 x3=0 3 2 1 x2=0 x1 0 0 1 2 3 4 5 6 -x2
6 -x1
8 +x1 -2x2
步骤2：选择进基变量。x2进基，另一个非基变量x1=0不变。
6步骤3、确定离基变量。min{1，82}=4，当x2=4时，x4=0离基。新的基础可行解为：
(x1，x2，x3，x4)=(0，4，2，0)，z’=-12，对应于极点C。
第二次叠代
27
第一章 线性规划
步骤1：基变量和目标函数用非基变量表示
x2 +x3 = 6 -x1 2x2
x2 = 8 +x1 -x4
将第二个约束两边同除以2，得到
x2 +x3 = 6 -x1
11x2 = 4 +2x1 -2x4
x1=0 6 5 x4=0 4 x3=0 3 2 1 x2=0 x1 0 0 1 2 3 4 5 6 两式相减，消去第一式中的基变量x2，得到
x x3 = 2 -3x1 +1242x -1x x2 = 4 +12124
将基变量x2=4＋1x1－1x4代入目标函数z’=-x1-3x2，消去目标函数中的基变量x2
22z’=-x1-3(4+1x1-1x4)=-12-5x1+3x4
2222x x3 = 2 -3x1 +1242x1 -1x4 x2 = 4 +122步骤2：选择进基变量。x1进基，另一个非基变量x4=0保持不变。
3步骤3：确定离基变量。min{2/2，-}=4，当x1=4时，x3=0离基。这时新的基
33础可行解为：
(x1，x2，x3，x4)=(4，14，0，0)，z’=-64，对应于极点B。
333第三次叠代
步骤1：基变量和目标函数用非基变量表示
x1
+x2 = 6 -x3
-x1 +2x2 = 8 x1 +x2 =
6 -x3
-x4
x2 两式相加，消去第二式中的基变量x1，得到
3x2 = 14 -x3 -x4
将第二个约束两边同除以3，得到
x1 +x2 = 6 -x3
x3 -1x4 x2 = 14 -1333两式相减，消去第一式中的基变量x2，得到 42x x1 = 3 -3x3 +134
x1=0 6 5 x4=0 4 x3=0 3 2 1 x2=0 x1 0 0 1 2 3 4 5 6 28
第一章 线性规划
x3 -1x4 x2 = 14 -1333将以上基变量x1，x2代入目标函数z’=-x1-3x2，消去目标函数中的基变量x1，x2
z’=-(4-2x3+1x4)-3?(14-1x3-1x4)=-46+5x3+2x4
333333333步骤2：选择进基变量。由于目标函数中非基变量x3、x4的系数都是正数，它们中任何一个进基都不能使目标函数减小。已获得最优解。 (x1，x2，x3，x4)=(4，14，0，0)，min z’=-46
333原问题的解为：
(x1，x2，x3，x4)=(4，14，0，0)，max z=46。 333例1. 13 目标函数无界的情况
min z= -x1 -2x2
2 x2 s.t. -x1 +x2 ≤1
x2 ≤2 x2 ≥0
1
x1 -1 0 1 2 =1 +x4 =2 x4 ≥0
x1,
引进松弛变量x3，x4
min z= -x1 -2x2
第一次叠代：
步骤1、取初始可行基，x3，x4为基变量，x1，x2为非基变量。将基变量和目标函数用非基变量表出：
z
=
-x1 -2x2
-x2 -x2
x3
= 1 +x1
x2
s.t. -x1 +x2 +x3
x1, x2, x3,
图 1.8 x4 = 2
当非基变量x1，x2=0时，相应的基变量和目标函数值为x3=1，x4=2，z=0，得到当前的基础可行解：
(x1，x2，x3，x4)=(0，0，1，2)，z=0
这个解对应于极点O。
步骤2、选择进基变量。在目标函数
z=-x1-2x2
29
第一章 线性规划
中，非基变量x1，x2的系数都是负数，因此x1，x2进基都可以使目标函数z减小，但x2的系数为-2，绝对值比x1的系数-1大，因此x2进基可以使目标函数z减少更快。选择x2进基，使x2的值从0开始增加，另一个非基变量x1=0保持不变。
步骤3、确定离基变量。在约束条件 z
=
-x1 -2x2
-x2 -x2
x3
= 1 +x1
x4 = 2
中，由于进基变量x2在两个约束条件中的系数都是负数，当x2的值从0开始增加时，基变量x3，x4的值分别从当前的值1和2开始减少，当x2增加到1时，x3首先下降为0成为非基变量。这时，新的基变量为x2，x4，新的非基变量为x1，x3，当前的基础可行解和目标函数值为：
(x1，x2，x3，x4)=(0，1，0，1)，z=-2
对应于极点C。 第二次叠代：
步骤1、将当前的基变量x2，x4用当前的非基变量x1，x3表示： x2
= 1 +x1 -x3
x2 +x4 = 2 x2
消去第二个约束中的基变量x2，得到
= 1 +x1 -x3 x4 = 1 -x1 +x3
将第一个约束x2=1+x1-x3代入目标函数z’=-x1-2x2，得到目标函数用当前非基变量表示的形式：
z=-x1-2(1+x1-x3)=-2-3x1+2x3
步骤2、选择进基变量。在目标函数z’=-2-3x1+2x3中，只有非基变量x1的值增加可以使目标函数z减少，选择非基变量x1进基，另一个非基变量x3=0保持不变。
步骤3、确定离基变量。从约束条件 x2
= 1 +x1 -x3 x4 = 1 -x1 +x3
可以看出，当进基变量x1从0开始增加时，基变量x4的值从1开始减少，另一个基变量x2的值随x1变化而增加。当x1=1时，基变量x4=0离基，这时新的基变量为x1，x2，新的非基变量为x3，x4。当前的基础可行解为：(x1，x2，x3，x4)=(1，2，0，0)，z=-5
这个解对应于极点B。
30