第2章对偶问题- 对偶模型其他结构关系 (2)若模型为 max z=CX 变形 max z=CX st「AX≥b 对偶问题 st(-AX≤-b Ⅹ≥0 对偶变量Y′ Min w=Y (-b 令Y=Y st.∫Y"(-A)≥C min w=yb Y≥0 StYA≥C Y≤0 2006/3
2006/3 --第2章 对偶问题-- --7-- 对偶模型其他结构关系 （2）若模型为 max z = C X s.t AX b X 0 max z = C X s.t - AX -b X 0 变形 min w = Y b s.t YA C Y 0 Min w=Y ´(-b) st. Y ´(-A) C Y ´ 0 令 Y=- Y ´ 对偶问题 对偶变量Y
第2章对偶问题- (3)maxz=CⅩ max=-CX stAX≤b 设X=-X st.「-AX≤b Ⅹ≤0 X≥0 变形 min w=yb 则有 min w=yb st-YA≥-C stYA≤C Y≥0 Y≥0 2006/3
2006/3 --第2章 对偶问题-- --8-- （3）max z = C X s.t AX b X 0 变形 设X= -X´ max = -CX ´ st. -AX´ b X´ 0 min w = Y b s.t YA C Y 0 min w = Y b 则有 s.t -YA - C Y 0
第2章对偶问题- 对偶问题典式: 用矩阵形式表示: (1)maxz=CⅩ w=Yb st axs b >StYA≥C X≥0 Y≥0 (2) max Z=CX min w=yb stAX≥b >S.tYA≥C X≥0 Y≤0 (3) max Z= CX min w=yb st ax s b stYA≤C Ⅹ≤0 Y≥0 2006/3
2006/3 --第2章 对偶问题-- --9-- 对偶问题典式： 用矩阵形式表示： （1） max z = C X min w = Y b s.t AX b <========> s.t YA C X 0 Y 0 （2） max z = C X min w = Y b s.t AX b <========> s.t YA C X 0 Y 0 （3）max z = C X min w = Y b s.t AX b <========> s.t YA C X 0 Y 0
第2章对偶问题- 原问题与对偶问题关系表 原问题(对偶问题) 对偶问题(原问题) 目标函数系数 约束右端项 约束右端项 目标函数系数 约束条件系数列向量A 约束条件系数行向量AT 变量个数 约束条件个数 max mIn 变量x 约束方程i x1≥0 Xj无约束 Xi≤0 约束方程 变量y;: yi≥0 yi无约束 yi≤0 2006/3
2006/3 --第2章 对偶问题-- --10-- 原问题与对偶问题关系表 原问题(对偶问题) 对偶问题(原问题) 目标函数系数 约束右端项 约束右端项 目标函数系数 约束条件系数列向量 A 约束条件系数行向量 AT 变量个数 约束条件个数 max min 变量 x j : 约束方程 i : x j 0 x j 无约束 = x j 0 约束方程: 变量 y i : y i 0 = y i 无约束 y i 0
第2章对偶问题- 2.3对偶问题的基本性质 Max z= cX Min w=yb st.AX≤b st.YA≥C X≥0 Y≥0 (1)弱对偶性 若X0—原问题可行解,Y°对偶问题可行解 则CX0≤Y0b 证明:∵Y0≥0,AX0≤b,∴Y0AX0≤Y0b, 而Y0A≥C,∴CX0≤Y0AX0 ∴CX0<Y0AX0<Y0b 2006/3 11
2006/3 --第2章 对偶问题-- --11-- 2.3 对偶问题的基本性质 Max z = CX Min w = Y b s t . AX b s t . YA C X 0 Y 0 (1) 弱对偶性： 若 X0——原问题可行解，Y0——对偶问题可行解 则 CX0 Y0 b 证明： ∵ Y0 0， AX0 b，∴ Y0 AX0 Y0 b， 而 Y0 A C ， ∴ CX0 Y0AX0 ， ∴ CX0 Y0 AX0 Y0 b