行后，可能会破坏原最优基（原最优基中单位列向量出现了非零元素），需要初等行变换将原单位阵恢复。

检查最优性条件，若原问题可行（对偶问题可行性不变），得到最优解；若原问题不可行，按对偶单纯形法继续迭代。

? 若增加约束条件为“?”形式，引入剩余变量后将不等式化为等式，再用（－1）乘以方程的两边，并以剩余变量为基变量，在最优表中增加一行一列，该剩余变量（基变量）所在列应是一个单位向量，最下面的一个元素为1，其余元素为零；增加一行后，可能会破坏原最优基（原最优基中单位列向量出现了非零元素），需要初等行变换将原单位阵恢复。

由于原问题不可行，再按对偶单纯形法继续迭代。

? 若增加约束条件为“＝”形式，引入人工变量，并以人工变量为新增基变量，在最优表中增加一行一列，该人工变量（基变量）所在列应是一个单位向量，最下面的一个元素为1，其余元素为零；增加一行后，可能会破坏原最优基（原最优基中单位列向量出现了非零元素），需要初等行变换将原单位阵恢复。

检查最优性条件，若原问题可行（对偶问题可行性不变），得到最优解；若原问题不可行，按对偶单纯形法继续迭代。 例11．已知线性规划问题

maxz??x1?x2?4x3?x1?x2?2x3?9??x1?x2?x3?2 s.t.??x?x2?x3?4?1?xj?0,j?1,2,3?其最优表为，

cj CB XB x1 b -1 0 4 1/3 x5 6 x3 13/3 ?j -17 -1 x1 1 0 0 0 -1 x2 -1/3 2 2/3 -4 4 x3 0 0 1 0 0 x4 1/3 0 1/3 -1 0 x5 0 1 0 0 0 x6 -2/3 1 1/3 -2 现增加一个约束条件：?3x1?x2?6x3?17，求新问题的最优解。

80

解：原问题的最优解为，X??(1/3,0,13/3,0,6,0)T

将最优解代入新增的约束条件，可见，

?3?13?0?6?133?25≠17

不满足约束条件。所以，引入松弛变量x7后，新增的约束条件变为，

?3x1?x2?6x3?x7?17

加入原问题的最优表中，有

cj -1 -1 x1 CB XB b x2 -1 1 -1/3 x1 1/3 x5 0 6 0 2 x3 13/3 4 0 2/3 0 x7 17 -3 1 ?j -17 0 -4 4 x3 0 0 1 6 0 0 x4 1/3 0 1/3 0 -1 0 x5 0 1 0 0 0 0 x6 -2/3 1 1/3 0 -2 0 x7 0 0 0 1 0 将第3行乘以（-6）加到第4行，第1行乘以（3）加到第4行，使

x1,x5,x3,x7的系数列向量构成单位阵，如下表，

cj CB XB b -1 0 4 0 -1 0 4 0

1/3 x5 6 x3 13/3 x7 -8 ?j -17 5/3 x5 4 x3 11/3 x6 2 ?j -13 x1 x1 -1 x1 1 0 0 0 0 1 0 0 0 0 -1 x2 -1/3 2 2/3 -4 -4 1/3 1 1/3 1 -2 4 x3 0 0 1 0 0 0 0 1 0 0 0 x4 1/3 0 1/3 -1 -1 1/2 -1/4 1/4 1/4 -1/2 0 x5 0 1 0 0 0 0 1 0 0 0 0 x6 -2/3 1 1/3 [-4] -2 0 0 0 1 0 0 x7 0 0 0 1 0 -1/6 1/4 1/12 -1/4 -1/2 81

所以，新问题的最优解为，X?(,0,3?5113,0,4,2,0)。

T

82