对偶视剡的性质 性质I:若线性规划P中第k个约袁条件是等式,则其对偶规划D 中的第k个变量无非负性限喇。反之若原线性规划P中第 k个变量无非负性限制,则其对偶规划D中的第k个约袁 条件是等式。 性质Ⅱ:若线性规划P中第k个约柬条件是大于等于的形式,则其 对偶规划D中的第k个量小于等于零。反之若原线性规 划P中第k个量小于等于零,则其对偶觌划D中的第k 个约柬条件是小于等于的形式
性质Ⅰ: 若线性规划P中第k个约束条件是等式，则其对偶规划D 中的第k个变量无非负性限制。反之若原线性规划P中第 k个变量无非负性限制，则其对偶规划D中的第k个约束 条件是等式。 性质Ⅱ:若线性规划P中第k个约束条件是大于等于的形式，则其 对偶规划D中的第k个变量小于等于零。反之若原线性规 划P中第k个变量小于等于零，则其对偶规划D中的第k 个约束条件是小于等于的形式
对偶视剡的性质 原问题(对偶问题) 对偶问题(原问题) 目 极大化(Max) 极小化(Min) 价值糸数 资源限值 A AT 标约求方程变量约束类型 n变量 m个变量 m个约袁 n个约求 右边项为资派限值 目标约求方程约束类型支量 右边项为价值糸数 ≥0型 ≥型 ≤0型 ≤型 无约求 型 ≥型 ≤0型 型 0型 =型 无约
原问题(对偶问题) 对偶问题(原问题) 目标 极大化(Max) 目标 极小化(Min) 价值系数 资源限值 约束方程 A 约束方程 AT n个变量 m个变量 m个约束 n个约束 右边项为资源限值 右边项为价值系数 变量 ≥0型 约束类型 ≥型 ≤ 0型 ≤型 无约束 =型 约束类型 ≥型 变量 ≤ 0型 ≤型 ≥0型 =型 无约束
对偶视剡的性质 倒23列出线性规划问题的对偶问题 Minf(r)=2x+3x2-5x3+x 4 Maxg()=10y1-5y2-8y 4x1+x2-3x3+2x425 y1ry2+3y322 +7x4≤4 4y2+2y3≤4 s·t 2x1+3x)+4xx+x4=6 y1-3y2-5y3=3 x1≤0,x2,x3≥0,x4自由 y≥0,y2自由,y3 MaxzE-x+ 2x2+3x3 Min=18y1-4y2+4y 2x+x2-3x=18 21+3y,+y2≤-1 3x1-x2 +2x≥-4 x3 y-y2-y3≥2 x-x2+3x≤4 3y+2y,+3y3=3 x≤0,x2≥0,x3自由 J1自由,y2≥0,y3≤0
Minf(x)=2x1+3x2 -5x3+x4 s · t 4x1+x2-3x3 +2x4 ≥ 5 3x1-2x2 +7x4 ≤ 4 -2x1+3x2+4x3+x4 = 6 x1 ≤ 0 , x2 , x3 ≥0, x4自由 例2.3 列出线性规划问题的对偶问题 y1-y2 +3y3 ≥ 2 -y1 +4 y2 + 2y3 ≤4 y1 -3y2 -5y3 =-3 y1≥ 0 ，y2 自由， y3 ≤0 Max g(y)=10y1-5y2 -8y3 s · t ï î ï í ì £ ³ - + £ - + ³ - + - = = - + + x x x 自由 x x x x x x x x x st MaxZ x x x 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 0, 0, 3 4 3 2 4 2 3 18 2 3 ï î ï í ì ³ £ - + + = - - ³ + + £ - = - + , 0, 0 3 2 3 3 2 2 3 1 18 4 4 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 y y y y y y y y y y y y Minw y y y 自由
线性视剡的对偶理论 定理I:任何对偶问题的对偶是其原问题本身。(对称性定狸) 证明:设原问题是maxz=CX;AX<b;X>0 根据对偶问题的对称变换头糸,可以找到的对偶问题是 min=Yb;YA≥C;Y≥0 若将上式两边取负号,又因mino=max(-0)可得到 max(-0)=-Yb;YA≤C;Y0 根据对称变换关糸,得到上式的对偶问题是 min(-0)=CX;Ax-b;X≥0 又因min(-0)=maxo 可得mxo=maxz=CX;AX<b;x≥0 这就是原问题。证毕
定理Ⅰ:任何对偶问题的对偶是其原问题本身。(对称性定理) 证 明:设原问题是max z=CX; AX≤b； X≥0 根据对偶问题的对称变换关系，可以找到它的对偶问题是 min ω=Yb; YA≥C； Y≥0 若将上式两边取负号，又因min ω=max(-ω)可得到 max(-ω)=-Yb; -YA≤-C； Y≥0 根据对称变换关系，得到上式的对偶问题是 min(-ω′)=-CX； -AX≥-b; X≥0 又因min(-ω′)=maxω′ 可得maxω′=max z=CX； AX≤b; X≥0 这就是原问题。证毕
线性视剡的对偶理论 定狸Ⅱ:设X和】分别是原问题P和对偶问题D的可行解,则必有cX≤Yb (弱对偶定理) 证明:设原问题是maxz=CX;AX≤b;X≥0 因为X是原问题的可行解,所以满足约束条件,即AXb 设Y是对偶问题的可行解,用Y左乘上式,得到YAXY"b 原问题的对偶问题是mino=Yb;YA≥C;Y≥0 因为Y是对偶问题的可行解,所以满足约条件,即YA≥C 将X“右乘上式,得到YAX≥CX 所以有CX*≤YAX≤Yb 证毕。 定狸Ⅲ:若原闷题(对偶问题)为无界解,则其对偶问题(原问题)无可行解。 (无界定狸)
定理Ⅱ:设X和Y分别是原问题P和对偶问题D的可行解，则必有cX≤Yb。 (弱对偶定理) 证 明:设原问题是max z=CX; AX≤b； X≥0 因为X*是原问题的可行解，所以满足约束条件，即AX *≤b 设Y*是对偶问题的可行解，用Y*左乘上式，得到Y*AX*≤ Y*b 原问题的对偶问题是minω=Yb; YA≥C； Y≥0 因为Y*是对偶问题的可行解，所以满足约束条件，即Y*A≥C 将X*右乘上式，得到Y*AX* ≥CX* 所以有 CX* ≤ Y*AX*≤ Y*b 证毕。 定理Ⅲ:若原问题(对偶问题)为无界解，则其对偶问题(原问题)无可行解。 (无界定理)