上海交通大学：《线性规划与非线性规划》教学资源_第2章 对偶理论和灵敏度分析 第4节 线性规划的对偶理论

第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

标准形式的变换关系称为对称形式 原问题 (LP)对偶问题(DP) maxz 2x+3x2 mino=8y,+16y2+12y3 x1+2x2≤8 y,+4y2 ≥2 4X1 ≤16 2y1 +4y3≥3 4x2≤12 y1,y2,y3≥0 X1,七2≥0

标准形式的变换关系称为对称形式 原问题 （LP） 对偶问题(DP) 1 2 1 2 3 1 2 1 2 1 1 3 2 123 1 2 max 2 3 min 8 16 12 2 8 4 2 4 16 2 43 4 12 ,, 0 , 0 z x x y y y x x y y x y y x yyy x x = + ω =+ + ⎧ + ≤ ⎧ + ≥ ⎪⎪ ⎪ ≤ ⎨ ⎨ ⇒ +≥ ≤ ⎪ ⎪⎩ ≥ ⎪ ⎩ ≥

非对称形式的变换关系 ·原问题的约束条件中含有等式约束条件 时，按以下步骤处理 ·设等式约束条件的线性规划问题 max ∑cx i=1 2agx,=,i=1,2,m i= x；≥0，j=1,2,…,n

非对称形式的变换关系 • 原问题的约束条件中含有等式约束条件 时，按以下步骤处理。 • 设等式约束条件的线性规划问题 ⎪ ⎩ ⎪ ⎨ ⎧ =≥ == = ∑ ∑ = = jx n ibxa m z xc j n j ijij n j jj ,,2,1,0 ,2,1, max 1 1 "

第一步：先将等式约束条件分解 为两个不等式约束条件。 max z- i=1 4，x,≤，j=12,,m2-13) j=1 ∑gx=6,i=l1,2…m→ ∑ax2b,j=1,2,,m i= x,≥0，j=1,2,…,n ∑agx,≤-bi=12,,m (2-14) j=

第一步：先将等式约束条件分解 为两个不等式约束条件。 ( ) ⎪ ( ) ⎪ ⎪ ⎪ ⎩ ⎪ ⎪ ⎪ ⎪ ⎨ ⎧ =−≤− − ⇓ =≥ =≤ − ⎪ ⎩ ⎪ ⎨ ⎧ =≥ == ⇒ = ∑ ∑ ∑ ∑ ∑ = = = = = n j ijij n j ijij n j ijij j n j ijij n j jj ibxa m jbxa m jbxa m njx mibxa xcz 1 1 1 1 1 142,,2,1 ,,2,1 132,,2,1 ,,2,1,0 ,2,1, max " " " "

第二步：按对称形式变换关系 可写出它的对偶问题 ·设y:'是对应(2-13)式的对偶变量 是对应(2-14)式的对偶变量。 。这里i=1,2,.,m

第二步：按对称形式变换关系 可写出它的对偶问题 •设y i′是对应(2-13)式的对偶变量 y i″是对应(2-14)式的对偶变量。 • 这里i=1,2,… ， m

mio=2by+∑(py) i=l i=l 2a,片+2(a,y)2cj=12.…n i=1 i=l y,y≥0，i=1,2,…m

( ) ( ) ⎪ ⎩ ⎪ ⎨ ⎧ =≥ =≥−+ −+= ∑ ∑ ∑ ∑ = = = = m,,i,y,y n,,j,cyaya min ybyb '' i ' i m i j m i '' iij ' iij m i m i '' ii ' ii " " 210 21 1 1 1 1 ω