此时，令非基本变量，x2= x3= x5=0，求x1和x4的解。用初等变换（消元）求解上面的方程，结果为
-2 x5+ x2- x3+ x4+ 0x1=2 x5+0 x2+ x3+0 x4+ x1=2 解得
x1=2，x4=2
再将x1和x4用约束方程的非基本变量表示，得 x4=2- x2+ x3+2 x5 x1=2- x3- x5
将其代入目标函数，得
z=-6（2- x3 – x5）+3 x2-2 x3+c4（2- x2+ x3+ 2x5）+ c5 x5 整理得
z=-6×2+ c4×2+（3- c4）x2+（-2+6+ c4）x3+（c5+6+2 c4）x5 由于所有非基本变量的系数均为非负，没有进一步可使目标函数减少的非基本变量，因此迭代结束，最优解为x1=2，x2=0，x3=0，f=-12。 单纯形法的一般步骤可归纳如下：
（1）把线性规划问题的约束方程组表达成标准形方程组，然后找出一个基本可行解作为初始基本可行解。对等式约束或“≥bi”形式的约束，如果不易得出初始基本可行解，则需用辅助方法得出，如大M法、两段法等。
（2）若基本可行解不存在，即约束条件有矛盾，则问题无解。
（3）若基本可行解存在，则从初始基本可行解作为起点，根据θ规则（式3.18）和判别数ζ（式3.19），引入非基本变量取代某一基本变量，找到使目标函数值更优的另一基本可行解。 （4）按步骤（3）进行迭代，直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。
（5）若迭代过程中发现问题的目标函数值无界，则终止迭代。
4 单纯形法列表计算
用单纯形法求解线性规划问题的过程，实际上就是解线性方程组。只是在每次迭代中，要按一定规则选择自由未知量，以便能够得到改进的基本可行解。这个求解过程可以通过变换单纯形法来实现。单纯形是以约束方程的增广矩阵为中心构造的一种变换表格，见表3.1。 表3.1 单纯形表 设计变量 基本变量 xn-m+1 xn-m+2 . . . xn ζj=cj-zj 非基本变量 cf ch 0 0 . . . 0 x1 c1 p1 x2 c2 p2 … … … xn-m cn-m pn-m xn-m+1 0 pn-m+1 xn-m+2 0 pn-m+2 … … … xn 0 pn b1 b2 . . . bm f(x) b bi/ air 应用单纯形表求解线性规划问题的基本步骤如下：
（1） 将线性规划问题写成标准形式，在单纯形表中对应位置填入目标函数变量的系数、
约束矩阵中变量的系数和右端项，将增加的m个松弛变量作为基本变量，初始化单
纯形表；
（2） 计算minζj=cj-zj，确定进基变量xL，计算minθi= bi/ bir，确定出基变量xi；
（3） 以L列、i行对应的约束矩阵中的元素aiL为主元进行消元，对矩阵元素和右端项更
新，并计算目标函数值；
（4） 重复第（2）和（3）步，直到最后一行各列ζj≥0时消元中止，此时与基本变量对
应的右端项bi就是所求的最优解。
例3.3 用单纯形法求解下面的线性规划问题：
f(x)??2x1?x2?x3s.t.3x1?x2?x3?60x1?x2?2x3?10 x1?x2?x3?20x1,x2,x3?0解：
线性规划的标准形式为
minf(x)??2x1?x2?x3?0x4?0x5?0x6s.t.3x1?x2?x3?x4?0x5?0x6?60x1?x2?2x3?0x4?x5?0x6?10 x1?x2?x3?0x4?0x5?x6?20x1,x2,x3,x4,x5,x6?0（1） 构造初始单纯形表 初始单纯形表如表3.2。 表3.2 初始单纯形表
设计变量 基本变量 x4 x5 x6 ζj=cj-zj 非基本变量 cf Cb 0 0 0 x1 -2 p1 3 1 1 -2 x2 -1 p2 1 -1 1 -1 x3 1 p3 1 2 -1 1 x4 0 p4 1 0 0 0 x5 0 p5 0 1 0 0 x6 0 p6 0 0 1 0 60 10 20 f=0 60/3 10/1 20/1 b bi/ air
（2） 消元
此问题是求目标函数的最小值，判别式minζj=cj-zj为求各列的最小值，L=1，再计算minθi= bi/ bir，得i=2。因此x1进基，x5出基。得出新的单纯形表，并以a21为主元进行消元，结果见表3.3。
表3.3第1次消元结果 设计变量 基本变量 x4 x1 x6 ζj=cj-zj 非基本变量 cf ch 0 -2 0 x1 -2 p1 0 1 0 0 x2 -1 p2 4 -1 2 -3 x3 1 p3 -5 2 -3 5 x4 1 p4 1 0 0 0 x5 0 p5 -3 1 -1 2 x6 0 p6 0 0 1 0 30 10 10 f=-20 30/4 10/-1 10/2 b bi/ air
由表3.3可知，minζj=cj-zj对应的最小列号为L=2，相应地minθi= bi/ air对应的行号为i=3，因此为x2进基变量，x6为出基变量，得到新的单纯形表，并以a32为主元进行消元，结果见表3.4。
表3.4 第2次消元结果 设计变量 基本变量 x4 x1 x2 ζj=cj-zj 非基本变量 cf ch 0 -2 -1 x1 -2 p1 0 1 0 0 x2 -1 p2 0 0 1 0 x3 1 p3 1 1/2 -3/2 1/2 x4 1 p4 1 0 0 0 x5 0 p5 -1 1/2 -1/2 1/2 x6 0 p6 -2 1/2 1/2 3/2 10 15 5 f=-35 b bi/ air 经过两次消元，判别式ζj=cj-zj≥0，求解结束，最优解为x*=[ 15 5 0 ]T,f(x*)=-35。
3.4 改进的单纯形法
单纯形法进行消元计算时对约束矩阵的所有元素都进行变换运算，计算量很大，为了减少计算量，提出改进的单纯形法。 1 改进的单纯形法的基本思想 对于给定的线性规划问题
maxf?cTxs.t.Ax?b x?0应用单纯形法求解时，基本变量，目标函数和判别数用下面表达式计算：
xE?E?1b?E?1NxNT?1T?1TT?1f?cEEb?(cTN?cEEN)xN?f0?(cN?cEEN)xN (3.20) TT?1?N?cTN?cEEN由式3.20看出，每个计算式都含有关于E-1的运算，因此E-1是计算基本变量、判别数的关键。对于求最大值问题，如果ζN的分量中有正数，选择一个非基本变量将其转换为基本比变量，相应地用新的可行基的逆矩阵再计算更新的基本变量。目标函数和判别数。 设用非基本变量xk替换基本变量xr，则替换前后的基矩阵为
E??p1~E??p1p2?pr?1p2?pr?1prpkpr?1?pm? pr?1?pm?
E?1E?E?1?p1?E?1p1E?1p2?E?1pr?1E?1pr??e1e2?er?1er?p2?pr?1prpr?1?pm?er?1?em?E?1pr?1?E?1pm?I?
???e~E?1E?E?1?p1p2?pr?1E?1pkpkpr?1?pm??E?1p11E?1p2?E?1pr?1E?1pkE?1pr?1?pm
e2?er?1?1er?1?em??~?1~?1?记Erk?EE，则Erk?EE就是式3.14。 ??E?1E因为Erk???~?1?~~?E?1。如果初始矩阵E为单位矩阵，则?E?1E，因此，E?1?Erk~~?1?E?1?ErkE?1?Erk。对于第l次迭代，基矩阵的逆矩阵为 ~1~?1~?1~?1~?1~?1E(??EE?E?El)(l),rk(l?1),rk(1),rk(l),rkE(l?1) (3.21)
式3.21中，下标rk随每次迭代进基变量和出基变量的下标而改变。用式3.21进行迭代计算时，约束方程中变量的系数、右端项保持不变，每次计算只需保存前一次基矩阵的逆矩阵。 在一次换基迭代过程中，在确定了进基向量与出基向量之后，真正起作用的是进基列向量pk与前一个基矩阵的逆矩阵E-1。
2 改进的单纯形法的计算步骤
设E(0)为线性规划问题的一个初始可行基。步骤为：
(1) 计算E-1并代入式3.19，计算基变量、目标函数和检验数。
TT?1T?1?cTxE?E?1b,fE?cEEb,?NN?cEEN
(2) 对检验数进行判定。若?N?cN?cEEN的分量全为非正（求最大值问题），则计算结
?1?E?1b?束，x???即为最优解，
0??TfE?cEE?1b为最优值。否则转入第（3）步。
(3) 确定进基列向量。令?k?max?j,j?1,2,...,n，则pk为进基列向量。并计算
????E?1pk??a1?kpk?ka2??amk??T，如果所有的ark?≤0(i=1,2,…,m)，则此问题?ark?>0，则转入第（4）步。 无最优解；若至少有一个，如ark??b?br?为主元，确定pr?出基。?min?r,i?1,2,...,m?，以ark(4) 确定出基列向量。令?r?
??ark?ark?(5) 计算E~?1?1?1?取代单元方阵中er得来。 ?ErkE。其中，Erk由pk~?1?1rk?1?1rkE~~?1(6) 计算xE?Eb?EEb?Ex,?N?cN?cEEN，返回第（1）步。 例3.5 用改进的单纯形法计算下面的线性规划问题：
maxf(x)?25x1?90x2,x?R2s.t.2x1?x2?150x1?3x2?270x2?80x1,x23?0解：
将所给问题化成线性规划问题的标准形式：
maxf(x)?25x1?90x2?0x3?0x4?0x5s.t.2x1?x2?x3?150x1?3x2?x4?270x2?x5?80xj?0,j?1,2,...,5?21100?T??设A?13010,c??2590000?,b??150????01001??(1) 构造初始基矩阵 初始基矩阵为E0??p3
27080?
Tp4?100??100??，同时得E?1??010?，所以有
p5???0100???????001???001??xE0?x3??100??150??150???E?1b??010??270???270? ??x40???????????x5???001????80????80???100????000? T?1cE00??0100E0??0????001??(2) 计算各非基本变量的判别数
?2??1??25 T?1???1?c1?cEEp?25?000001????0???1???90 T?1?2?c2?cE00??30E0p2?90??0????1??(3) 确定进基变量
?1?25,?2?90???2，对应非基本变量，确定为x2进基变量。同时计算 根据max?