对线性规划模型求出最优解以后，如果新增加了约束条件方程，那么原有模型就变成了一个新的模型。针对新模型求解的一般思路是用单纯形法或对偶单纯形法从头开始求解。但我们知道，单纯形法对原有模型的求解过程就是对它的初始单纯形表做行运算，最终变换到最优单纯形表，而这一过程针对新模型来说，就相当于对新模型中原有的约束条件方程做了行运算，而新增加的约束条件方程一直保持不变。可以这样说，原有模型求最优解的过程就相当于新模型一个行运算的中间步骤，只不过新模型还没有找到最优解而已。

鉴于以上的思路，可以对新模型不必从头求解，将新增加的约束条件方程化为等式以后，直接补加到原有模型的最优单纯形表中，然后用对偶单纯形法继续迭代求解即可，这样求解比把新模型从头求解简便得多。

求解的主要步骤如下：

第一步：检验原来的最优解是否满足新增加的约束条件方程，如果满足，原来的最优解就是新模型的最优解，否则转到第二步。

第二步：将新增加的约束条件方程加上松弛变量或减去多余变量使其化为等式，再把这个等式方程的系数补加到原模型的最优单纯形表中。

第三步：令原来的基变量和新增加的松弛变量或多余变量作为新的基变量。

第四步：对新的单纯形表进行初等变换，使新基变量的系数矩阵变为单位矩阵，此时可以得到一个满足最优检验但不一定满足非负约束的可行解。

第五步：利用对偶单纯形法继续迭代求解即可。

下面通过例题具体说明新增加约束条件方程的求解步骤。

例3.5　下面给出了线性规划模型以及最优单纯形表（见表3.15）。

表3.15

现在增加一个新的约束条件方程x1+x2≥10，请求新的最优解。

解　从给出的最优单纯形表可知，最优解为(x1,x2,x3,x4,x5)=(8,1,0,0,0），但此最优解不满足新的约束条件方程x1+x2≥10。另外，新的约束条件方程使原有的模型变为

(www.daowen.com)

模型（3.18）与模型（3.17）可以说是完全不同的两个模型。对模型（3.18）求解的一般思路是用单纯形法或对偶单纯形法从头开始求解，现在用前面的求解步骤求解。

将x1+x2≥10化为x1+x2－x5=10，其中x5≥0，再变换为-x1-x2+x5＝-10，把x5作为基变量，然后把这个方程的系数补加到表3.15的最后一行中，得表3.16。

表3.16

进行初等变换，使基变量的系数矩阵变为单位矩阵，如表3.17所示。

表3.17

表3.17满足最优检验，但x5=-1，不可行，继续迭代求解，得到表3.18。由表3.18可知，满足最优检验，基变量也可行，得到最优解(x1,x2,x3,x4,x5)=(13/2,7/2,1/2,0,0）。

表3.18

特别提示

（1）若原问题新增加约束条件方程不止一个时，仍然可用上面的方法依次求解。

（2）后面第7章的整数规划求解算法，就是利用原问题新增加约束条件方程的思路进行求解的，这里也为学习第7章的整数规划问题奠定了基础。