12??1001?1?333???152??? 101?0?333??2?15???01?4?0?333???252?新的基本可行解为 X??0,,,0,0,??

3??332T应当注意：并不是A的任何一列都可以引入基中。如上例中P5就不能入基，因为P5?0导致bk'?bk即无论在P5中取哪一个为主元，?0，

ak5均不能保证X1?0，故在确定进基列的时候，应保证该列至少有一个正分量。

3、进基列的选择

以上换基运算分析可知，对进基列的要求是至少有一个正分量。然而满足这个条件的列向量可能很多。那么，挑选哪一个作为进基列更好呢？这需要与目标函数联系起来。

如果在上例的约束条件上加上一个目标函数：

f?X??x1?2x2?3x3?4x4?x6

于是 CT??1,?2,3,?4,0,1? 则在X0、X1和X2处相应的目标函数值为

fX0?CTX0?1?2???2??1?3?3?9

?? f?X1??CTX1?1??3?4???4??? f?X2?121 22152?CTX2???2???3??1??5

33312同X0相比，X1处目标函数值上升，X2处目标函数值下降，则此时应该选取P6作进基列。然而，对于一般的线性规划来说，选择什么样的

列作进基列可以使目标函数值下降呢？ 定理3：设线性规划

TT?minf?X??CBXB?CNXN?BXB?NXN?b ?s.t.?XB?0，XN?0?满足以下条件：

?B?1b? (1) 基本可行解X???非退化；

0??0(2) Pl的判断数?l?0；

(3) Pl的分量中至少有一个为正。

则用Pl作进基列将得到使目标函数值下降的基本可行解。

定理3的证明详见傅英定等主编《最优化理论与方法》P60-P61）。 但一般的线性规划符合进基列条件的列通常不止一个，那么，选取哪一列作进基列最好呢？

由于 ?f?X??f?X0??f?X?????l

所以，当??l最大时，目标函数值下降最快。可见?与进基列的选择有关。如果对每一个可供选择的进基列Pj都计算一次?j，再比较各个?j?l的大小，则当可供选择的进基列数目较大时，相应的计算量也较大。所以，通常情况下，若有多个列满足进基列的条件，则选取判别数最大的那一列作进基列，这时目标函数值获得较大的下降。 举例：对于线性规划

?minf?X???2x1?x2??5?s.t.x1?x2?x3??x4?1 ??x1?x2?6x1?2x2?x5?21?xj?0?j?1,?,5????111005????P,P,P,P,P,b? ?Ab????11010112345????6200121??取I??P3,P4,P5?为基，则

?1?CITP1?c1?0?c1?2?0 ?2?CITP2?c2?0?c2?1?0

由于P1、P2均有正分量，故P1、P2都可作进基列但?1??2，故选取P1为将使目标函数值得到较大下降。 2.4.3 单纯形算法 1、初始单纯形表的建立

对于线性规划

TT?minf?X??CBXB?CNXN?BXB?NXN?b ?s.t.?XB?0，XN?0?其中B是可逆矩阵，可作为这个线性规划的基，并建立以下矩阵：

?B?1A?T?1?CBBA?C?B?1b? (★) T?1?CBBb??由上述讨论可知：

?B?1b?? X???是线性规划的一个基本可行解。

0??0T?1? CBBA?C的各分量就是判别数。

T?1? CBBb?f?X0?是对应于基本可行解X0的目标函数值。

因此，矩阵式(★)记录着我们所关心的关于线性规划的全部信息。我们将这个矩阵称为线性规划的初始单纯形表。

特别地，若基B?I是单位矩阵，则初始单纯形表变为

A??T?CIA?Cb?? (★★) CITb?如果将A用?IN?来表示，则基向量的判断数为零，且将目标函数值CITb用f0来表示，则式(★★)又可记为

N?I?TT?0?Nb?? f0?其中

OT??0,?,0?T?N???m?1,?,?n?f0?fX???Cb0TI

TX0??b1,?,bm,0,?,0?此时，线性规划对应的初始单纯形表的一般形式即为下表所示。

P1 ? Pk ?Pm Pm?1 ? Pl ? Pn b 1 a1,m?1 ? a1l ? a1n ? ? ? ? b1 ? 1 ak,m?1 ? akl ? akn bk ? ? ? ? ? 1 am,m?1 ? ak,m?1? ak,n bm 0 ? 0 ? 0 ?m?1 ? ?l ? ?n 初始单纯形表记录着以下信息： (1) 等式约束AX?b的有关数据； (2) 各列向量的判别数?j?j?1,?,n?；

f0