(2.6.2)--02_6_2最优性检验与解的判别.pdf

最优性检验与解的判别 一般情况下,（2-23）经过迭代后（2-24）将（2-24）代入目标函数得：z0jzj令再令于是则（2-2）（2-2）证明:因对一切非基变量的角下标j，均有0，显然，对于任一可行解均有zz0,但是基本可行解能使等式成立，故为最优解（1）最优解的判别定理:若为对应于基B的一个基可行解,且对于一切 j=m+1,n有j0,则为最优解.称j为检验数.（2）无穷多最优解的判别定理:若为一个基可行解,且对于一切j=m+1,n有j0,又存在某个非基变量的检验数m+k=0,则线性规划问题有无穷多最优解.证:只需将非基变量xm+k换入基变量中，找到一个新基可行解X(1).因m+k=0，由(2-27)知z=z0，故X(1)也是最优解.由定理3可知，X(0)和X(1)连线上所有点都是最优解.为一基可行解，有一个m+k，并且对i=1,2,m有ai,m+k0,那么该线性规划问题具有无界解（无最优解）（）无界解（无有限最优解）判别定理若因，所以对任意的0都是可行解，把x(1)代入目标函数内，得到z=z0+m+k因m+k0，故当+，则z+，故该问题目标函数无界.证:构造一个新的解 X(1)，它的分量为约束条件相互矛盾，可行域为空集最终计算表中人工变量仍然为基变量.（）（）无可行解