《最优性检验与解的判别.docx》由会员分享，可在线阅读，更多相关《最优性检验与解的判别.docx（4页珍藏版）》请在三一办公上搜索。
1、最优性检验与解的判别最优性检验与解的判别 我们前面已经讨论过线性规划问题的解的几种情况，分别是由唯一最优的解， 无穷多的最优解，无界解和无可行解。下面我们来讨论怎样判别解属于那一种情况 xi=bi-j=m+1naijxj (1-1) 将式代入目标函数 目标函数式为 mz=cibi+cj-ciaijxj i=1j=m+1i=1令 mmmnz0=cibi,zj=ciaij,j=m+1,.,n i=1i=1于是 z=z0+再令 j=m+1(cnj-zj)xj sj=cj-zj 则 z=z0+j=m+1snjxj 1. 最优解的判别定理 若X(0)=(b1,b2,.,bm,0,.,0)T为对应基B的一
2、个基可行解，且对于一切 J=m+1,n,有sj0，则为X2. 无穷多最优解判别定理 (0)TX=(b,b,.,b,0,.,0)12m若为一个基可行解, 对于一切j = m+ 1 , , n, 有j 0 , (0)最优解。称sj为检验数。 又存在某个非基变量的检验数m + k = 0 ,则线性规划问题有无穷多最优解。 证只需将非基变量xm+k换入基变量中, 找到一个新基可行解。因m + k = 0, 由 (1 -2 )知,z=z0故X(0)也是最优解。由前面提到的定理，即，若可行域有界，线性规划问题的目标函数一定可以在其可行域的顶点上达到最优，可知,X优解 3. 无界解判别定理 (0)，X(1)
3、连线上所有点都是最(0)TX=(b,b,.,b,0,.,0)12m若为一基可行解, 有一个m + k 0 , 并且对i= 1 , 2 , , m, 有ai,m+k0, 那么该线性规划问题具有无界解(或称无最优解)。 证构造一个新的解X(1)，它的分量为 xi(1)=bi-lai,m+k(l0) (1)xm+k=l x=0, (1)jj = 0 , j = m+ 1 , , n, 且jm + k 因ai,m+k0 , 所以对任意的 0 都是可行解, 把x( 1 ) 代入目标函数内得 z=z0+lsm+k 因m + k 0 , 故当 + , 则z + , 故该问题目标函数无界。 以上讨论都是针对标准型, 即求目标函数极大化时的情况。当求目标函数极小化时, 一种情况如前所述, 将其化为标准型。如果不化为标准型, 只需在上述1 , 2 点中把j 0 改为j 0 , 第3 点中将sm+k0改写为m + k 0 即可。
