(3) 初始基本可行解X0??b1,?,bm,0,?,0?T； (4) 对应于X0的目标函数值f0。

对于基B=I的线性规划，建立初始单纯形表需要计算非基变量的判别数?m?1,??n，以及相应的目标函数值f0。 2、换基运算后的新单纯形表

在初始单纯形表上对线性规划作换基运算。首先确定主元akl，然后按其规则作换基运算，并对单纯形表的最后一行作相应的变换，即 ?'j??j?f'?f0?akjakl?l （注意，此时?l'??l?akl ?l?0）

aklbk?l akl 于是，初始单纯形表变为新单纯形表如下图所示。

P1 ? Pk ?Pm Pm?1 ? Pl ? Pn b 1 a1'k a1',m?1 ? 0 ? a1'n ? ? ? ? ? '' akk ak',m?1 ? 1 ? akn b1' ? bk' ? ? ? ? ? ? '''' amk 1 am,m?1 ? 0 ? amn bm ''0 ? ?k' ? 0 ?m?1 ? 0 ? ?n f' 上表中：(1) ?'j是新单纯形表中Pj判别数；

(2) f'是新基本可行解X1所对应的目标函数值。其中

'X1?b1'?bk'?10bk'?1?bm0?0bk'0?0

??T在新单纯形表中，

(1) 若?'j?0?j?1,?,n?，则X1就是最优解。

(2) 若有某个?'j?0，而Pj?0，则原规划无最优解。

(3) 若有?'j?0且Pj有正分量，则可定理3选择进基列再次作换基运算。 3、单纯形算法

设A 中有m个列Pj1,Pj2,?,Pjm构成单位矩阵。已知：

I??Pj1,Pj2,?,Pjm?b??b1,b2,?,bm?CT??c1,c2,?,cn?CIT??cj1,cj2,?,cjm?A??P1,P2,?,Pn?

计算步骤：

(1) 构造初始单纯形表

?P1P2?Pnb??????f?

n0??12其中

?j?CITPj?cj?j?1,?,n?

f0?CITb

??j?。 (2) 求?l?max1?j?n00? ,?,xn(3) 若?l?0，则X0??x10,x2T(其中，x0 ,?,m?,x0,?,m?)就是最优解，否则转(4)。ji?bi?i?1jl?0?l?1(4) 若Pj?0，则无最优解，否则转(5)。 (5) 求

?b?bk?min?i/ail?0?。 akl1?i?n?ail?(6) 以akl为主元对初始单纯形表作换基运算得到新单纯形表，转(2)。

举例：求解线性规划

?minf?X??x2-3x3?2x5??2x5?7?s.t.x1?3x2?x3??2x2?4x3?x4?12 ???4x2?3x3?8x5?x6?10??xj?0?j?1,?,6??解：取I??P1,P4,P6?为初始基。则

TX0??7,0,0,12,0,10?为初始基本可行集。

CIT??0,0,0?

由?j?CITPj?cj计算出：?2?-1，?3?3，?5??2

?1、?4、?6为基变量所对应的判别数，必有?1??4??6?0

f0?CITb?0

因此，初始单纯形表如下所示。

P1 P2 P4 P3 P5 P6 b 7 1 3 -1 0 2 0 4 1 0 0 12 0 -2 ○0 -4 3 0 8 1 10 0 -1 3 0 -2 0 0 在非零判别数中，只有?3?3?0，且P3有正分量，故应将P3引入基底。 由

?bi??1210?12bk?min?/ai3?0???,??，可知，应选a23?4为主元作换基ak31?i?6?ail??43?4运算得到如下新单纯形表。

P1 P2 P4 P3 P5 P6 b 1 2/5 0 1/4 2 0 10 0 -1/2 1 1/4 0 0 0 -5/2 0 -3/4 8 1 0 1/2 0 -3/4 -2 0 3 1 -9 上表中只有?2?12?0，且P2有正分量，故应以a12?25为主元作换基运算得到如下新单纯形表。

P1 P2 P4 P3 P5 P6 b 4 5 2/5 1 0 1/10 4/5 0 1/5 0 1 3/10 2/5 0 1 0 0 -1/2 10 1 11 -1/5 0 0 -4/5 -12/5 0 -11 上表中各判别数?j?0，故当前基本可行解为

TX0??0,4,5,0,0,11?

为最优解。此时目标函数值为f?X*???11。

由上可知，利用单纯形方法求解线性规划，首先找出一个基本可行解。将目标函数写成非基变量的线性组合(再加上一个常数)的形式。如果组合的系数全部非负，则已经找到最优解。如果组合的系数中有负数，从中选取一个变量(“进基”)来增加取值，可以使得函数值减少。根据约束条件，可以控制增加的范围。在进基变量取最大值时，有一个变量出，从而得到另一个基可行解。重复上面的过程，可以求得最优解。