第2章对偶理论和灵敏度分析 第4节线性规划的对偶理论 从理论上讨论线性规划的对 偶问题
第2章 对偶理论和灵敏度分析 第4节 线性规划的对偶理论 •从理论上讨论线性规划的对 偶问题
4.1原问题与对偶理论 原问题和对偶问题的标准形式（对称形式）： ·原问题(LP): max =cx+c2x2++c 11 ≤ mn b X1,X2)…,Xm≥0
4.1 原问题与对偶理论 • 原问题（LP）： 0,,, max 21 1 2 1 1 2 11 12 1 2211 ≥ ⎟⎟⎟⎠⎞ ⎜⎜⎜⎝⎛ ≤ ⎟⎟⎟⎟⎟⎠⎞ ⎜⎜⎜⎜⎜⎝⎛⎟⎟⎟⎠⎞ ⎜⎜⎜⎝⎛ = + + + n m n m m mn n nn xxx b b x x x aa a aa a xcxcxcz " # # " #%## " " 原问题和对偶问题的标准形式（对称形式）：
·对偶问题(DP) min @=y b+y2b2++ymbm 2 n 02,,yn ≥(G,c2,,c) Lm2· 19Jy2,…,Jym≥0
•对偶问题(DP) ( ) () 0,,, ,,, ,,, min 21 21 21 1211 1 21 2211 ≥ ≥ ⎟⎟⎟⎠⎞ ⎜⎜⎜⎝⎛ = + + + m n mm mn n m m yyy ccc aaa aaa yyy bybyby " " " #%## " " ω " m
标准形式的原问题与对偶问题的关系 j X1 原关系 min yi 011 012 01n ≤ b y2 02 02n ≤ b2 : : : ym a m2 a ≤ b n m 对偶关系 ≥ ≥ 。。 ≥ maxz C C2 maxz=
标准形式的原问题与对偶问题的关系 1 2 1 11 12 1 1 2 21 22 2 2 1 2 1 2 min maxz maxz min j n i n n m m m mn m n x xx x y y aa a b y aa a b y aa a b cc c ω ω ≤ ≤ ≤ ≥≥ ≥ = " " " # # #"# # # " " " 原关系 对偶关系
例2 根据表2-3写出原问题与对偶 问题的表达式。 。表2-3 X X1 X2 b y y1 1 2 8 y2 4 0 16 y3 0 4 12 c 2 3
例2 根据表2-3写出原问题与对偶 问题的表达式。 • 表2-3 x y x1 x2 b y1 1 28 y2 4 0 16 y3 0 4 12 c 2 3