北京交通大学经济管理学院School of EconicsandManagomentBojingJiaotong University当原问题(对偶问题)为无可行解，其对偶问题(原问题)或具有无界解或无可行解北京交通大学
• 当原问题(对偶问题)为无可行解, 其对偶 问题(原问题)或具有无界解或无可行解
北京交通大学经济管理学院SchngstoountaylofEics andManagoment4.可行解是最优解的性质若Xo、YO为可行解,则当CXO=Ybo时可得X、YO为最优解5.(强)对偶定理若原问题有最优解,则对偶问题也有最优解且目标函数值相等北京交通大学1
4. 可行解是最优解的性质 若X0 、Y0为可行解,则当CX0 =Yb0时可得X0 、Y0为最优解. 5. (强)对偶定理 若原问题有最优解,则对偶问题也有最优解, 且目标函数值相等
证：首先,当两者都有可行解时,对Yb的最小值有一个下界,对CX的最大值有一个上界,所以两者必定有最优解.再证它们有相同的最优值设X是(P)的最优解,它对应的基矩阵是B,这时必有C- C,BAf0 Z=CX=C,B-'b设Y=C,B-1,则YA3C，30,说明Y是(D)的可行解由于Yb=C,B-"b=CX根据性质4,Y是(D)的最优解
证：首先,当两者都有可行解时,对 Yb 的最小值有一个 下界,对 CX 的最大值有一个上界,所以两者必定有最优 解. 再证它们有相同的最优值
6.互补松驰定理设、分别为(P)和(D)的可行解,则它们为(P)和(D)的最优解的充分必要条件是： X,=0 和Y,X =0其中,Xs,Ys为(P)、(D)标准型问题中的松弛变量和剩余变量证将(P) (D)的约束化为等式AX +IX.=b,YA- YI =C,因为X是最优解,所以cX=Yb,即(YA - YI)X =Y(AX +IX,)故有-YX，=x而YX,,x30,故只有x、=x =0.亡（易证)
6. 互补松弛定理
7.(P)的单纯形表的检验数行对应(D)的一个基解其对应关系是XBXNXs0-CβB-1Cn-CpB-1N-Ys2Ys1-Y该性质是对偶单纯形法的一个基础可得出的结论：(P)）、（D）同时原问题与对偶问题达到最优同时可行
7. (P)的单纯形表的检验数行对应(D)的一个基解, 其对应关系是 可得出的结论： XB XN XS YS1 -YS2 -Y 0 CN -CBB-1N -CBB-1 （P）、（D）同时 达到最优 原问题与对偶问题 同时可行 该性质是对偶单纯形法的一个基础