标准形式的变换关系称为对称形式 原问题 (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 ω