例2根据表2-3写出原问题与对偶 问题的表达式。 表23 y 8
例2 根据表2-3写出原问题与对偶 问题的表达式。 • 表2-3 x y x1 x2 x2 y1 1 1 1 y2 2 2 2 y3 8 8 8 c 4 4 4
标准形式的变换关系为对称形式 原问题(LP)→→对偶问题(DP maxz=2x,+3x2 miOD=8y1+16y2+12y3 x,+2x<8 4x, <16 y+4 y 4x,≤12 y,y2,y3≥0 x1,x≥0
标准形式的变换关系为对称形式 原问题 （LP） 对偶问题(DP) + + + = + = + + 0 2 3 4 2 0 4 12 4 16 2 8 2 3 8 16 12 1 2 3 1 3 1 2 1 2 2 1 1 2 1 2 1 2 3 y , y , y y y y y x ,x x x x x max z x x min y y y
非对称形式的变换关系 原问题的约束条件中含有等式约束条件 时,按以下步骤处理。 设等式约束条件的线性规划问题 ncx2三 ∑ ≥0
非对称形式的变换关系 • 原问题的约束条件中含有等式约束条件 时，按以下步骤处理。 • 设等式约束条件的线性规划问题 = = = = = = x , j , , ,n a x b , i , , m max z c x j n j i j j i n j j j 0 1 2 1 2 1 1
第一步:先将等式约束条件分解 为两个不等式约束条件。 nax 人) ≤bj a.x.≥b J 1.2 x,≥0,j=1,2,…,n ∑ax≤-b1=12,…,m(2-14)
第一步：先将等式约束条件分解 为两个不等式约束条件。 ( ) ( ) − − = − = = − = = = = = = = = = n j i j j n j i j j n j i j j j n j i j j i n j j j a x b i , , ,m a x b j , , ,m a x b j , , ,m x , j , , ,n a x b , i , , m max z c x 1 1 1 1 1 12 2 14 1 2 1 2 2 13 0 1 2 1 2
第二步:按对称形式变换关系 可写出它的对偶问题 设y;′是对应(2-13)式的对偶变量 y;"是对应(2-14)式的对偶变量。 这里=1,2,,m
第二步：按对称形式变换关系 可写出它的对偶问题 • 设yi ′是对应(2-13)式的对偶变量 yi ″是对应(2-14)式的对偶变量。 • 这里i=1,2,…，m