线性规划几种多余约束条件的判别法

1个回答

  • 分享到:

    收藏推荐 符秀华在求解线性规划问题的过程中,常常遇到下面这种情况:原规划不是标准形式,通过引入松驰变量,先把它化成标准形式,再用单纯形法求出这个标准形式的最优解,然后,在最优解中去掉松驰变量,剩下的即为原规划的最优解.在上述过程中,如果被去掉的松驰变量在最优单纯形表中是基变量,显然它所对应的约束条件对原规划是多余的.设一般线性规划的约束条件为:其中b(i=1,2,...,m)全部为正数.定理一若(1)中前k个约束不等式中,某个约束不等式的系数全部非正,则这个约束不等式为多余约束条件.要证明(1)中一个约束条件为多余的,只须证明由(1)构成的可行域和从(1)中去掉这个约束条件后,剩余的约束条件构成的可行域相同.证明不妨设第一个约束不等式的系数a1j≤0(j=1.2,...,n).设(1)构成的可行域为R,从(1)中去掉第一个约束不等式后,剩余的约束条件构成的可行域为R'.任取XER,则X满足(l)中全部约束不等式,因而XER'.任取