第一章 线性规划
max
st
z=
2x1 +3x2 +x3 x1 +3x2 +x3 2x1 +3x2 x1
-x3 -x2 +x3
?15 ?18 ?3
x2, x3 x1, ?0
目标函数转变为极小化，引进松弛变量： min st
z’= -2x1 -3x2 -x3
x1 +3x2 +x3 +x4
2x1 +3x2 x1
x2, x2 3 [3] 3 -1 -x3 x3, x3 1 1 -1 1 -x2 +x3
x4,
+x5
=15
x1, 列出单纯形表 z’ x1 z’ x4 x5 x6 1 0 0 0 2 1 2 1 =18
+x6 = 3 x5, x6 ?0
x5 0 0 1 0 x5 0 0 1 0 x5 -1 -1/3 1 -4/3 x5 -1/3 0 1/3 -1/3 x6 0 0 0 1 x6 0 0 0 1 x6 0 0 0 1 x6 -1/2 -1/4 1/2 1/4 RHS 0 15 18 3 RHS -15 5 3 8 RHS -18 4 3 4 RHS -20 3 5 1 15/3 18/3 - 5/1/3 3/1 8/4/3 4/1 -- 4/4
x4 0 1 0 0 x4 -1 1/3 -1 1/3 x4 0 2/3 -1 5/3 x4 -5/6 1/4 -1/6 5/12 x2进基，x4离基，y12=3为主元 z’ x1 x2 x3 z’ x2 x5 x6 1 0 0 0 1 1/3 [1] 4/3 0 1 0 0 0 1/3 -2 4/3 x1进基，x5离基，y21＝1为主元 z’ x1 x2 x3 z’ x2 x1 x6 1 0 0 0 0 0 1 0 0 1 0 0 2 1 -2 [4] x3进基，x6离基，y33＝4为主元 z’ x1 x2 x3 z’ x2 x1 x3
1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 得到最优解：x1=5，x2=3，x3=1。最优目标函数值min z’=-20 , max z=20。
36
第一章 线性规划
例1.20 用单纯形表求以下线性规划问题的最优解。 max s.t.
z=
x1 x1 2x1 -x1
+2x2 +x2 +3x2 +x2
+x3 +x3 +x3 +x3
?12 ?18 ?24 ≥0 +x3 x4 x4 0 1 0 0 x4 0 1 0 0 x4 -1/2 3/2 -1/2 -1 x1 x2 x3
目标函数转化为极小化，引进松弛变量，使约束条件转变为等式： min s.t.
z’=
-x1 x1 2x1 -x1
-2x2 +x2 +3x2 +x2 x2 x2 2 1 [3] 1 x2 0 0 1 0 x2 0 0 1 0 -x3 +x3 +x3 +x3 x3 x3 1 1 1 1 x3 1/3 [2/3] 1/3 2/3 x3 0 1 0 0
+x5 x6 x5 0 0 1 0 x5 -2/3 -1/3 1/3 -1/3 x5 -1/2 -1/2 1/2 0 =12 =18 =24 ≥0 x6 0 0 0 1 x6 0 0 0 1 x6 0 0 0 1 RHS 0 12 18 24 RHS -12 6 6 18 RHS -15 9 3 12 12/1 18/3 24/1 6/2/3 6/1/3 18/2/3
+x4
x5
x1
列出单纯形表 z x4 x5 x6 z’ x4 x2 x6 z’ x3 x2 x6
z 1 0 0 0 z’ 1 0 0 0 z’ 1 0 0 0 x1 1 1 2 -1 x1 -1/3 1/3 2/3 -5/3 x1 -1/2 1/2 1/2 -2 x2进基，x5离基 x3进基，x4离基
最优解为x1=0，x2=3，x3=9，x4=0，x5=0，x6=12，min z’=-15，max z=15
37
第一章 线性规划
§1.8 初始基础可行解—两阶段法
在以上单纯形算法描述中，没有指明如何取得一个初始基础可行解。对于简单的问题，只要做一些试算就可以确定选定的一个基是否是可行基。但对于规模稍大的问题，用试算的方法就很困难了，必须有一个初始可行基的系统化方法。当用系统的初始可行解方法不能求得任何初始基础可行解时，就可以得出线性规划问题无解的结论。
对于标准形式的问题
min z=CTX s.t. AX=b
X≥0
当b?0时，如果矩阵A中包含一个单位矩阵，则很自然地取该单位矩阵作为初始可行基，这时基变量XB=B-1b≥0，因而必定是初始可行基。
在以上的例子中，问题的约束条件全为“小于等于”约束，并且右边常数全部大于等于0，对于这一类问题，化为标准问题时在每个约束中添加的松弛变量恰构成一个单位矩阵，这个单位矩阵就可以作为初始可行基。
当标准形式问题的A矩阵中不含有单位矩阵或虽含有单位矩阵但b不全为非负时，无法获得一个初始的可行基。 例1.21 设一线性规划问题的约束为
x1 x1, x1 x1,
+x2 x2, +x2 x2,
+x3 ≤6 x3 ≥0 +x3 +x4
=6
-2x1 +3x2 +2x3 ≥3
引进松弛变量x4、x5≥0，得到
-2x1 +3x2 +2x3
-x5 =3
x3, x4, x5 ≥0
基中不包含单位矩阵，因此无法直接获得初始可行基。 例1.22 设一线性规划问题的约束为
x1 -2x1 x1, x1
+x2 -2x3 ≤-3 +x2 +3x3 ≤7 x2,
x3 ≥0
=-3
38
引进松弛变量x4、x5?0，得到
+x2 -2x3 +x4
第一章 线性规划
-2x1 x1,
行基。
+x2 +3x3 x2,
+x5 =7
x3, x4, x5 ≥0
其中虽然含有单位矩阵，但右边常数中出现负值，因此也不能直接获得初始可对于不能直接获得初始可行基的问题，可以用引进人工变量（Artificial Variables）的方法构造一个人工基作为初始可行基。
设问题的约束条件为： 或写为
AX=b X≥0 AX+Xa=b X,Xa≥0
(1.14)
(1.13)
其中X=(x1,x2,?,xn)T。引进人工变量Xa=(xn+1,xn+2,?,xn+m)T，约束(1.13)成为
?A?X?I?????b ?Xa?X,Xa?0 (1.15)
这样，(1.15)的约束中就出现了一个单位矩阵，因而(1.15)有一个基础可行解X=0，Xa=b。但X=0并不是(1.13)的可行解，即(1.13)和(1.15)并不等价。(1.15)的基础可行解(X, Xa)T中的X要满足(1.13)，当且仅当(1.15)的基全部包含在A矩阵中，即Xa=0全部成为非基变量。为了得到(1.13)的一个可行基，可以对(1.15)的初始可行基（人工基）进行基变换，设法迫使人工基中的列向量离基，最终获得全部包含在A矩阵中的一个基，从而也就获得了(1.13)的一个可行基。
根据以上思路，我们构造以下的两阶段法： 设线性规划问题为
min z=CTX s.t. AX=b
X≥0
m (1.16)
第一阶段：引进人工变量Xa=(xn+1，xn+2，?，xn+m)T，构造辅助问题
minz' ??xn?i
i?1s.t.AX?Xa?bX,Xa?0 (1.17)
39
第一章 线性规划
求解辅助问题。若辅助问题的最优基B全部在A中，即Xa全部是非基变量（min z’=0），则B为(1.16)的一个可行基。转第二阶段。若辅助问题的最优目标函数值min z’>0，则至少有一个人工变量留在第一阶段问题最优解的基变量中，这时(1.16)无可行解（证明见§1.10.5）。
第二阶段：以第一阶段(1.17)的最优基B作为(1.16)的初始可行基，求解(1.16)，得到(1.16)的最优基和最优解。 例1.23 求解以下线性规划问题
min z= x1 -2x2 s.t.
x1 +x2 ≥2 -x1 +x2 ≥1
x2 ≤3 x2 ≥0
x1,
引进松弛变量x3，x4，x5?0，得到
min z= x1 -2x2 s.t.
-x1 +x2
x2
x1,
x1 +x2 -x3
=2 =1
-x4
+x5 =3
x2 x3, X4, x5 ≥0
增加人工变量x6，x7≥0，构造辅助问题，并进入第一阶段求解。
min z’= s.t. z’ x6 x7 x5
40
x6 +x7 x1 +x2 -x3 -x1 +x2
x2
+x6
=2 =3
-x4 +x7 =1
+x5
x1, x2， x3, x4, x5 x6, x7 ≥0 z’ 1 0 0 0 x1 0 1 -1 0 x2 0 1 1 1 x3 0 -1 0 0 x4 0 0 -1 0 x5 0 0 0 1 x6 -1 1 0 0 x7 RHS -1 0 1 0 0 2 1 3
写出辅助问题的系数矩阵表：
消去目标函数中基变量x6、x7的系数，得到初始单纯形表并进行单纯形变换：