情形二:柔紧紧的 原问题 对偶问题 maxz= cX minw= yb S.AX≥b→{s.YA≥C X≥0 Y<0 视明标准对称型 上页 ma艺=CX →{s,t-Ax≤-b 下页 X≥0 (Y=-y) 回对偶minw=-Y →S t-YA C Y≥0
返回 上页 下页 对 偶 问 题 = = Y 0 . A C min X 0 . AX b max st Y w Yb st z CX 原问题 对偶问题 (Y = −Y) 化为标准对称型 情形二： 证明 − = − − − = Y 0 . A C min X 0 . AX b max st Y w Y b st z CX 对偶
对2、非对称形式的对偶 若原问题的约束条件是等式,则 原问题 对偶问题 上页 max z=CX min w=yb 下页 AX=b→)YA≥C X≥0 Y无约東 回 通观图
返回 上页 下页 对 偶 问 题 ◼ 2、 非对称形式的对偶 若原问题的约束条件是等式，则 = = = 无约束 min 0 max Y YA C w Yb X AX b z CX 原问题 对偶问题
推导: max Z=CX AX≥b 原问题AX≤b X≥0 上页 max z=CX 下页 回 4+s/b →4 b X≥0
返回 上页 下页 对 偶 问 题 推导: = 0 max X AX b AX b z CX − − = 0 max X b b X A A z CX 原问题
根据对称形式的对偶模型可直接 写出上述问题的对偶问题 -min w=(Y, Y) -b 上页 A 下页 (Y,Y224≥C 回 Y1≥0.Y2≥0
返回 上页 下页 对 偶 问 题 根据对称形式的对偶模型,可直接 写出上述问题的对偶问题: = -b b min w (Y1,Y 2 ) 0 , 0 ( 1 2 1 2 − Y Y C A A Y ,Y )
min w=(Y1-Y2)b →{(xY1-Y2)A≥C Y1≥0.Y2≥0 令Y=Y1,得对偶问题为 上页 max w=yb 下页 Y4≤C 回 Y无约東 证毕。 通观图
返回 上页 下页 对 偶 问 题 − = − Y , Y (Y Y ) A C w (Y Y ) b 0 0 min 1 2 1 2 1 2 = Y无约束 YA C max w Yb 令 Y = Y ，得对偶问题为： 1 −Y 2 证毕