第一节 线性规划的对偶问题 用矩阵形式表示，对称形式的线性规划问题 的原问题为： max Z=CX AX≤b (2-5) X≥0 其对偶问题为： min W=b'Y A'Y≥C (2-6) Y≥0 13
13 用矩阵形式表示，对称形式的线性规划问题 的原问题为： = 0 max X AX b Z CX 其对偶问题为： = 0 min Y A Y C W b Y (2-5) (2-6) 第一节 线性规划的对偶问题
第一节 线性规划的对偶问题 在上述对偶问题中，令Z*=-W,则(2-6) 可改写为： max Z*=-b'Y -A'Y≤-C (2-7 Y≥0 如将其作为原问题，则可得对偶问题如下： 14
14 在上述对偶问题中，令Z * = - W，则（2-6） 可改写为: − − = − 0 max * Y A Y C Z b Y (2-7) 如将其作为原问题，则可得对偶问题如下： 第一节 线性规划的对偶问题
第一节 线性规划的对偶问题 min Z**=(-C' (-A)'X≥(-b)Y (2-8) X≥0 再令Z=-Z*,则上式可改写为原问题(2-3) 三、非对称形式下原问题与对偶问题的关系 并非所有的线性规划问题都具有对称形式， 我们可以按照下面的4个规则将一般情况下的线性 规划问题化成等价的对称形式来求出相应的对偶 问题 15
15 再令Z= -Z **，则上式可改写为原问题(2-3)。 三、非对称形式下原问题与对偶问题的关系 并非所有的线性规划问题都具有对称形式， 我们可以按照下面的4个规则将一般情况下的线性 规划问题化成等价的对称形式来求出相应的对偶 问题。 − − = − 0 ( ) ( ) min ** ( ) X A X b Z C X (2-8) 第一节 线性规划的对偶问题
第一节 线性规划的树偶问题 规则1： x自由取值 等价于 X=X1-X2,X1>=0,X2>=0 规则2： x<=0等价于X=-x1,x>=0 规则3： aiX1+a2x2+.+anxn>=b 等价于-a1x1a2X2anxm<=-b 规则4： a1X1+a2x2+.+anXn=b 等价于 -a1x1-a2x2.-anXm<=-b且 aiX1+a2x2+.+anxn <=b 16
16 规则1： x自由取值 等价于 x = x1 - x2 , x1>=0, x2>=0 规则2： x<=0 等价于 x = -x1 , x1>= 0 规则3： a1x1+ a2x2 +.+ anxn >= b 等价于 - a1x1 - a2x2 -.- anxn <= -b 规则4： a1x1+a2x2+.+anxn = b 等价于 -a1x1 - a2x2 - . - anxn <= -b且 a1x1 + a2x2 +.+ anxn <= b 第一节 线性规划的对偶问题
第一节 线性规划的树偶问题 例2试写出下面线性规划问题的对偶问题。 maxZ-1x+4x2+3x3 2x1+3x2-5X3≤2 3x1-1x2+6x3≥1 1x1+1x2+1x3≥4 x1>0,x2<0,3无约束 17
17 例2 试写出下面线性规划问题的对偶问题。 + + − + + − = + + 1 2 3 无约束 1 2 3 1 2 3 1 2 3 1 2 3 0, 0, 1x 1x 1x 4 3x 1x 6 x 1 2 x 3x 5x 2 max 1 4 3 x x x Z x x x 第一节 线性规划的对偶问题