对偶规剡 (4)从这里可以得到另一个线性规划问题 Min o=yb YA>C 称它为原线性规划问题{ Max z=CX|AX≤b X0}的对偶规划问题
(4) 从这里可以得到另一个线性规划问题 Min ω=Yb YA≥C Y≥0 称它为原线性规划问题{Max z=CX｜AX≤b， X≥0}的对偶规划问题
对偶规剡 Max f()=c1x+C2x2+.+Cnx Min f()=b1y1+b2y2..+ bmy a1x1+a12x2+…+a1nxnb y1+a21y2 aml) 21~1 + 22 +a2nxn≤b2D an2y1+a22]2+.. +am2ym2C2 amx计+am2x2+,,+amxn≤bm any1+ a2my2+.. amnvn2cn x≥0(i=1,2 Max f(x)=CX Min g(x)=bTY AXb ATY X>0
s · t AX≤b X ≥0 Max f(x)=CX P s · t ATY≥c T Y ≥0 Min g(x)=b TY D s · t a11 x1+ a12 x2+… + a1n xn≤ b1 a21 x1+ a22 x2+… + a2n xn ≤ b2 ……… ……… ……… …… am1 x1+ am2 x2+…+ amn xn ≤ bm xj≥0 (j=1，2，…，n) Max f(x)=c1 x1+ c2 x2+… + cn xn P s · t a11 y1+ a21 y2+… + am1 ym≥c1 a12 y1+a22 y2+… + am2 ym ≥c2 ……… ……… ……… …… a1n y1+ a2m y2+… + amnyn≥ cn xi≥0 (i=1，2，…，m) Min f(x)=b1 y1+ b2 y2+… + bm ym D
对称的对偶舰划 对称形式的对偶规划之间具有下面的对应关糸 原问题(对偶问题) 对偶问题(原问题) 极火化(Max)日 极小化(Min) 价值糸数 标 资源限值 目标约束方程变量 AT n个变量 约 m个变量 m个约束 求 分 n个约束 ≤型 程 ≥型 右边项为资憑限值 右边项为价值糸数 变 >0 量 >0
对称形式的对偶规划之间具有下面的对应关系 原问题(对偶问题) 对偶问题(原问题) 目 标 极大化(Max) 目 标 极小化(Min) 价值系数 资源限值 约 束 方 程 A 约 束 方 程 AT n个变量 m个变量 m个约束 n个约束 ≤型 ≥型 右边项为资源限值 右边项为价值系数 变 量 ≥0 变 量 ≥0
对称的对偶舰划 对称形式的对偶规划之间的对应关糸 原关min n 11 12 In b1 ●● 21 2 2n < < n n n 2 对偶关無≥≥ > arz in a narz 2
对称形式的对偶规划之间的对应关系 w w min c c c y a a a b y a a a b y a a a b x x x y x mn m m m mn m n n n i j = ³ ³ ³ £ £ £ maxz maxz min 1 2 1 2 2 21 22 2 2 1 11 12 1 1 1 2 L L L M M M L M M M L L L 对偶关系 原关系
对称的对偶舰划 例22写出线性规划问题的对偶规划 Max f(x)=2x1-3x2+4 2x1+3x2-5x3≥2 3x1+x,+7x2≤3 1+4x,+6r2≥5 x1,x2,x3≥0 Max f(er=2x1-3x2+4 x3 Ming(y)=-2y1+3y2-5y3 -2xr-3x2+5x3<2 2y1+3y2+y322 3x1+x2+7x3≤3 -31+y2-4y323 x1-4x2-6x3≤5 51+7y2-6y x2,x3≥0
s · t 2x1+ 3x2 – 5x3 ≥ 2 3x1 + x2 +7x3≤ 3 -x1 + 4x2 +6x3 ≥ 5 x1，x2 ， x3 ≥ 0 Max f(x)=2 x1 - 3x2 +4 x3 例2.2 写出线性规划问题的对偶规划 s · t -2x1- 3x2 + 5x3 ≤- 2 3x1 + x2 +7x3 ≤ 3 x1 - 4x2 - 6x3 ≤- 5 x1，x2 ， x3 ≥ 0 Max f(x)=2 x1 -3x2 +4 x3 -2y1+3y2 +y3 ≥2 -3y1 + y2 - 4y3 ≥-3 5y1 + 7y2 - 6y3 ≥ 4 y1，y2 ， y3 ≥ 0 Min g(y)=-2y1+3y2 -5y3 s · t