第2章线性规划的 对偶理论及其应用 线性规划最重要的理论之 进行经济分析的重要工具
第2章 线性规划的 对偶理论及其应用 • 线性规划最重要的理论之一 • 进行经济分析的重要工具
上堂课的主要内容
上堂课的主要内容：
1、对称型对偶问题: (P): maxz=C,+C2x2+.+Cn (d)mn s=b,,+b,y2+.+bm,y +a1x2+…+a1xn≤b auyI+a21y2+.+amym2Cr a21x1+a2x2+…+a2nxn≤b s t . 12V1+a,y,+.+amm =c anmx1+am2x2+…+am2xn ta 2n2 …+a mn. m xn≥0 max z=cx min s= yb StAX≤b, stY4≥C X≥0 Y≥0 12 若取A b y b
1、对称型对偶问题： n n P z = c x + c x ++ c x max 1 1 2 2 ( ): + + + + + + + + + m m mn n m n n n n a x a x a x b a x a x a x b a x a x a x b st 1 1 2 2 21 1 22 2 2 2 11 1 12 2 1 1 . x1 , x2 , xn 0 m m D S = b y + b y ++ b y min 1 1 2 2 ( ) + + + + + + + + + n n mn m n m m m m a y a y a y c a y a y a y c a y a y a y c st 1 1 2 2 1 2 1 2 2 2 2 2 1 1 1 2 1 2 1 1 . y1 , y2 , ym 0 max z = CX0 . , X st AX b ， = xn x x X 2 1 ( ) n C c c c = 1 2 , 1 2 21 22 2 11 12 1 = m m mn n n a a a a a a a a a A 若取 = m b b b b 2 1 ( ) m Y y y y = 1 2 min S = Yb 0 . , Y st YA C
2、标准型的对偶问题: maxz=C1x1+Cx,+…+Cnx a,x,,, tax. t.,x =b max z=CX an,x,+a1x+…+a1x.=b s.t. st ax=b X≥0 +am2x2+…+anmx ≥0 则对偶问题(D)为: minS=bv+b,,+…+b y1+a21y2+…+amym≥ nin s=yb c12y1+a2.y st →stY4≥C Y无符号限制 a1ny1+a,y,+…+an,y C 无符号限制
n n z = c x + c x ++ c x max 1 1 2 2 + + + = + + + = + + + = m m mn n m n n n n a x a x a x b a x a x a x b a x a x a x b st 1 1 2 2 21 1 22 2 2 2 11 1 12 2 1 1 . x1 , x2 , xn 0 2、标准型的对偶问题： m m S = b y + b y ++ b y min 1 1 2 2 + + + + + + + + + n n mn m n m m m m a y a y a y c a y a y a y c a y a y a y c st 1 1 2 2 1 2 1 2 2 2 2 2 1 1 1 2 1 2 1 1 . y1 , y2 , ym 无符号限制 max z = CX0 . , = X st AX b min S = Yb Y无符号限制 s.t YA C, 则对偶问题（D）为：
3、混合型对偶问题 原问题 对偶问题 目标函数max目标函数mn 目标函数系数约束方程常数列 约束方程常数列目标函数系数 系数矩阵A系数矩阵4 变量个数n约束方程个数n 约束方程个数m变量个数m 约束方程 变量≥0 <0 无符号约束 变量>0 约束方程> <0 无符号约束
原问题 对偶问题 目标函数max 目标函数min 目标函数系数 约束方程常数列 约束方程常数列 目标函数系数 变量个数n 约束方程个数n 约束方程个数m 变量个数m 约束方程≤ 变量≥0 ≥ ≤0 = 无符号约束 变量≥0 约束方程≥ ≤0 ≤ 无符号约束 = 系数矩阵A 系数矩阵A 3、混合型对偶问题