如果初始表中没有单位矩阵,注意到前面的分析只涉及辅助变量y一列,它由单位列向量最后变成 B-的第t列P-,检验数由0变为C,P-1.因此,这时只需在最优表中增加一辅助列 对该列重 复1°和2°的过程即可 当然,对于有限资源利用型的问题(如例2),亦可采用如下处理办法:将要去掉的约束之常数项b 换成M,按§1中有关常数项变化后的情形处理,最后令M,>+∞,不过这样作由于出现参数M,,给 上机运算带来困难,故还是采用前述办法好些。 至于增加或减少变量的情形,处理起来比较简单容易,这里不多叙而留作练习。 §3*基向量变化的灵敏度分析 1方法介绍 m 对于线性规划问题 AX= b St X≥0 设B是最优基,xk是一基变量,P是xk的系数构成的基向量。现在假定P变为P,xk的目标函数系数Ck 变为C,则对于式(9)的最优单纯形表中,用BF替换单位列向量BP4,用入=C2BF-C替换 相应的检验数0,然后实行一次uass消元,使BP重新变换为原来的单位列向量,λ1仍变为0。经上述 变动后的表简称为初始表,记号照旧。这时xk虽然仍为基变量,但因常数项和检验数都发生了变化,故解 的最优性及可行性都需加以检验并作相应的处理。以往的做法是:如果常数项仍非负,即可行性不变,则 用单纯形法迭代求优;若常数项出现负值,同时检验数出现正值,即可行性和最忧性都被破坏,则必须引 入人工变量及参数“大M”,建立新的单纯形表,重新计算,其中对引入参数“大M”,将导致很大的计算 量和严重的甚至使计算失败的误差。因此,人们都竭力避免在实际计算中引入参数“大M”,而只用其理 论成果进行某些分析推理。通常在寻找初始基可行解时,多采用“两阶段法”而不用“大M法”,其道理 也在于此。可见以往引入“大M”的处理方法乃是不得己的,迫切需要改进。通过分析研究,我们发现 对于可行性和最优性均遭破坏的情形,既不必引入人工变量,也不用借助参数“大M”,只需使用把单纯 形法和对偶单纯形法结合起来的联合算法,便可求出问题的最优解或断定无解,具体程序表述如下 (1)于初始表中,以-1乘常数项为负数的行,并去掉该行左边的基变量,这样的行以后简称为无基 行。若无基行有多个,可用下述方法使之只剩一个:取一无基行,比如常数项最小的,分别以该行的适当 倍数加于其他无基行,使后者的常数项变为0,然后相继(可按行从小到大的顺序)在每一常数为0的无基 行中取一非0元(如取列下标最小的)为主元,实行一次 Guass消元,该无基行即变为有基行。如此进行 直到常数项为0的那些无基行全变为有基行为止。这样最后只剩下一个无基行,设它的行号为r,则其常数 项b>0,然后转(2)或(3)。 (2)针对正检验数所在列按照通常的规则或最速下降规则确定主元实行单纯形迭代、求优。迭代中 若主元一直没能选在无基行(即该行元素不构成最小比值),且又遇到以下两情形之一,致使单纯形迭代 无法进行时,则分别处理。 (a)所有检验数均非正,说明已满足最优性条件,故可用对偶法的选主元规则于第r行选一基变量, 即取 max-a>0) (若式(10)中的集合为空集,结束,问题无可行解)然后以an为主元实行 Guass消元,便得一对偶可行 解,继用对偶单纯形法迭代求优 (b)虽有正检验数λ,>0,但该j列系数an≤0,i=1,2,…,m。这时若an=0,结束,问题无最优 解;否则必有an<0,故可采取下述所谓Q处理:令Q=max{-,/an,l},其中E是事先取定的一个适 当小的正数,然后把r行的Q倍加于目标函数行(此举使新检验数’≤0),其余不变,返回(2)。114 如果初始表中没有单位矩阵,注意到前面的分析只涉及辅助变量 t y 一列,它由单位列向量最后变成 −1 B 的第t列 −1 Pt ,检验数由0变为C B −1 Pt .因此,这时只需在最优表中增加一辅助列         − − 1 1 B t t C P P ,对该列重 复1 0和2 0的过程即可. 当然，对于有限资源利用型的问题（如例2），亦可采用如下处理办法：将要去掉的约束之常数项 i b 换成 Mi ，按§1中有关常数项变化后的情形处理，最后令 Mi → + ，不过这样作由于出现参数 Mi ，给 上机运算带来困难，故还是采用前述办法好些。 至于增加或减少变量的情形，处理起来比较简单容易，这里不多叙而留作练习。 §3*基向量变化的灵敏度分析 1方法介绍 对于线性规划问题     = = 0 . . min X AX b st f CX (9) 设B是最优基， k x 是一基变量， Pk 是 k x 的系数构成的基向量。现在假定 Pk 变为 Pk ， k x 的目标函数系数 Ck 变为 Ck ，则对于式（9）的最优单纯形表中，用 B Pk −1 替换单位列向量 B Pk −1 ，用 k = CBB Pk −Ck −1  替换 相应的检验数0，然后实行一次Guass消元，使 B Pk −1 重新变换为原来的单位列向量， k 仍变为0。经上述 变动后的表简称为初始表，记号照旧。这时 k x 虽然仍为基变量，但因常数项和检验数都发生了变化，故解 的最优性及可行性都需加以检验并作相应的处理。以往的做法是：如果常数项仍非负，即可行性不变，则 用单纯形法迭代求优；若常数项出现负值，同时检验数出现正值，即可行性和最忧性都被破坏，则必须引 入人工变量及参数“大M”，建立新的单纯形表，重新计算，其中对引入参数“大M”，将导致很大的计算 量和严重的甚至使计算失败的误差。因此，人们都竭力避免在实际计算中引入参数“大M”，而只用其理 论成果进行某些分析推理。通常在寻找初始基可行解时，多采用“两阶段法”而不用“大M法”，其道理 也在于此。可见以往引入“大M”的处理方法乃是不得己的，迫切需要改进。通过分析研究，我们发现， 对于可行性和最优性均遭破坏的情形，既不必引入人工变量，也不用借助参数“大M”，只需使用把单纯 形法和对偶单纯形法结合起来的联合算法，便可求出问题的最优解或断定无解，具体程序表述如下。 （1）于初始表中，以-1乘常数项为负数的行，并去掉该行左边的基变量，这样的行以后简称为无基 行。若无基行有多个，可用下述方法使之只剩一个：取一无基行，比如常数项最小的，分别以该行的适当 倍数加于其他无基行，使后者的常数项变为0，然后相继（可按行从小到大的顺序）在每一常数为0的无基 行中取一非0元（如取列下标最小的）为主元，实行一次Guass消元，该无基行即变为有基行。如此进行， 直到常数项为0的那些无基行全变为有基行为止。这样最后只剩下一个无基行，设它的行号为r，则其常数 项 br  0 ，然后转（2）或（3）。 （2）针对正检验数所在列按照通常的规则或最速下降规则确定主元实行单纯形迭代、求优。迭代中 若主元一直没能选在无基行（即该行元素不构成最小比值），且又遇到以下两情形之一，致使单纯形迭代 无法进行时，则分别处理。 （a）所有检验数均非正，说明已满足最优性条件，故可用对偶法的选主元规则于第r行选一基变量， 即取 rt t rj rj j a a a   max{ |  0} = (10) （若式（10）中的集合为空集，结束，问题无可行解）然后以 rt a 为主元实行Guass消元，便得一对偶可行 解，继用对偶单纯形法迭代求优。 （b）虽有正检验数  j  0 ，但该j列系数 aij  0,i = 1,2,  ,m 。这时若 arj = 0 ，结束，问题无最优 解；否则必有 arj  0 ，故可采取下述所谓Q-处理：令 max{  / ,} Q = − j arj ，其中  是事先取定的一个适 当小的正数，然后把r行的Q倍加于目标函数行（此举使新检验数  J   0 ），其余不变，返回（2）