《最优性检验与解的判别》由会员分享，可在线阅读，更多相关《最优性检验与解的判别（3页珍藏版）》请在金锄头文库上搜索。
1、最优性检验与解的判别我们前面已经讨论过线性规划问题的解的几种情况，分别是由唯一最优的解，无穷多的最优解，无界解和无可行解。下面我们来讨论怎样判别解属于那一种情况（i=1,2,m） (1-1) 1niiijjmxbax将（1-1）式代入目标函数 目标函数式为（1-2）（1-3） 111mnmi jijji jmizcbcax令 011,.mijiji izcbzcan于是（1-4）01()njjjjmzczx再令（j=m+1,n）jjjcz则（1-5）01njjmzx1. 最优解的判别定理若 为对应基 B 的一个基可行解，且对于一切(0)12,.,0.)TXbJ=m+1,n,有 ，则为 最优解。
2、称 为检验数。j(0Xj2. 无穷多最优解判别定理若 为一个基可行解, 对于一切 j = m+ 1 , , n, 有 j (0)12,.,.)Tmb0 ,又存在某个非基变量的检验数 m + k = 0 ,则线性规划问题有无穷多最优解。证只需将非基变量 换入基变量中, 找到一个新基可行解。因 m + k = 0, 由kx(1 -2 )知, 故 也是最优解。由前面提到的定理，即，若可行域有界，线性规划问0z(0)X题的目标函数一定可以在其可行域的顶点上达到最优，可知, ， 连线上所有点都(0)X(1)是最优解3. 无界解判别定理若 为一基可行解, 有一个 m + k 0 , 并且对 i = 1 ,
3、 2 , , (0)12,.,0.)TmXbm,有 , 那么该线性规划问题具有无界解(或称无最优解 )。,ika证构造一个新的解 ，它的分量为(1)(1) , 0)iiimkxba(1)mk(1)0,jxj = 0 , j = m+ 1 , , n, 且 jm + k因 , 所以对任意的 0 都是可行解, 把 x( 1 ) 代入目标函数内得,ika0mkz因 m + k 0 , 故当 + , 则 z + , 故该问题目标函数无界。以上讨论都是针对标准型, 即求目标函数极大化时的情况。当求目标函数极小化时,一种情况如前所述, 将其化为标准型。如果不化为标准型, 只需在上述 1 , 2 点中把 j 0改为 j 0 , 第 3 点中将 0 改写为 m + k 0 即可。mk
