最优化理论与方法1(2014-简版) 下载本文

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