第2章对偶问题- (2)最优性: 若X0原问题可行解,Y0对偶问题可行解,且 CXo= Yo b 则Ⅹ0—原问题最优解,Y0对偶问题最优解 证明:设ⅹ*——原问题最优解,Y*——对偶问题最优解 则CX0≤CX*≤Y*b≤Y0b 但CX0=Y0b, CXU=CX=Yb=Yob XO=X, YO=Y 即ⅹ0—原问题最优解,Y°—对偶问题最优解 证毕 2006/3
2006/3 --第2章 对偶问题-- --12-- （2）最优性： 若 X0——原问题可行解，Y 0——对偶问题可行解，且 CX0 = Y 0 b 则 X0——原问题最优解， Y 0——对偶问题最优解 证明：设 X* ——原问题最优解， Y* ——对偶问题最优解 则 CX0 CX* Y* b Y0 b 但 CX0 = Y0 b， ∴ CX0 = CX* = Y* b = Y0 b ∴ X0 = X* ， Y0 = Y* 即 X0——原问题最优解， Y0——对偶问题最优解 证毕
第2章对偶问题- (3)无界性 若原问题最优解无界,则对偶问题无可行解 证:有性质1,CX0≤Y0b,当CX0→∞时,则不可 能存在Y0,使得CX0≤Y0b。 注:逆定理不成立,即 如果原问题(对偶问题)无可行解,那么 对偶问题(或原问题)“解无界”不成立。 2006/3
2006/3 --第2章 对偶问题-- --13-- （3）无界性 若原问题最优解无界，则对偶问题无可行解 证：有性质1，C X0 Y0 b，当 CX0 → ∞ 时，则不可 能存在Y0，使得 C X0 Y0 b。 注：逆定理不成立，即 如果原问题（对偶问题）无可行解，那么 对偶问题（或原问题）“解无界”不成立