第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 无符号约束
原问题 对偶问题 目标函数max 目标函数min 目标函数系数 约束方程常数列 约束方程常数列 目标函数系数 变量个数n 约束方程个数n 约束方程个数m 变量个数m 约束方程≤ 变量≥0 ≥ ≤0 = 无符号约束 变量≥0 约束方程≥ ≤0 ≤ 无符号约束 = 系数矩阵A 系数矩阵A 3、混合型对偶问题
s2.2对偶线性规划 解的再论
原题: 对偶问题: maX z 2x1+x2 5x2≤15 mnw=15y1+24y2+5y3 1+2x2≤24 s t y2+y3≥2 1+x2≤5 5y1+v2+y3≥1 标准形 0 最优值 maX Z*=17/2 标准型: 最优值 s t 15 W*=17/2 maX w 最优解 最优解 (7/2,3/2) 5u(0,1/4,1/2) ≥0 原问题原问题的 对偶问题对偶问题 的变量松弛变量 变量 剩余变量 y1y2y3y4y5常数项 000-14-1/2Z-17/2 x001 5/4-15/715/2 152|00-7232m+17 x100 y2|-5410-141414 1/4-1/27/2 ys15201123212 x2010-1/43/23/2
最优单纯形表：对偶问题 剩余变量 对偶问题 的变量 最优单纯形表： 原问题的 松弛变量 原问题 的变量 , 0 5 6 2 24 5 15 max 2 1 2 1 2 1 2 2 1 2 + + = + x x x x x x s.t. x z x x 原问题： , , , 0 5 6 2 24 5 15 max 2 3 4 5 5 4 3 1 2, 1 2 1 2 2 1 2 + + = + + = + = = + x x x x x x x x x x x s.t. x x z x x 标准型： X1 X2 X3 X4 X5 常数项 2 1 3 x x x 0 1 0 -1/4 3/2 3/2 1 0 0 1/4 -1/2 7/2 0 0 1 5/4 -15/2 15/2 0 0 0 -1/4 -1/2 Z-17/2 y , , 0 5 2 1 . 6 2 1 2 3 1 2 3 2 3 + + + y y y y y st y y min 15 1 24 2 5 3 w = y + y + y 对偶问题： 1 2 3 max w = −15y − 24y − 5y 标准型： y , , , , 0 5 2 1 . 6 2 1 2 3 4 5 1 2 3 5 2 3 4 + + − = + − = y y y y y y y y st y y y 2 17 w + y1 y2 y3 y4 y5 常数项 -15/2 0 0 -7/2 -3/2 y2 -5/4 1 0 -1/4 1/4 1/4 y3 15/2 0 1 1/2 -3/2 1/2 最优值 Z*=17/2 最优值 W*=17/2 最优解 （7/2，3/2） 最优解 （0，1/4，1/2）
设原问题(P)对偶问题(D) max z=CX min w=yb s.t. aXsb St.YA≥C X≥0 Y≥0 、对称定理 定理2.1对偶问题的对偶就是原问题。 (即互为对偶规划)
定理2.1 对偶问题的对偶就是原问题。 （即互为对偶规划） 一、对称定理： 设原问题（P） 对偶问题（D） 0 . . max = X st AX b z CX 0 . . min = Y st YA C w Yb
、弱对偶性定理: 定理22若X是原问题(P)的一个可行解,Y是其 对偶问题(D)的一个可行解,则有CY0≤Yb 证明:设原问题P)为对称型则其对偶问题(D)为 max z=CX min s= yb S!AX≤b, stY4≥C, ≥0 X是(P)的一个可行解,,有AX0≤b,X0≥0 Y是(D)的一个可行解,,有YA≥C,Y≥0 由AX0≤b,Y0≥0Y0AX≤b 由YA≥C,X20Y0AY0≥CX0 →C0≤Y0AX≤Yb,即CX。≤Yb
D CX Y b X P Y 0 0 2 0 0 2. 对偶问题（ ）的一个可行解，则有 定理 若 是原问题（ ）的一个可行解， 是其 证明：设原问题(P)为对称型 0 . , X st AX b S Yb D min = 则其对偶问题（ ）为 0 . , Y st YA C max z = CX ,有AX0 b, X0 0 0 由Y0 A C，X0 , 0 0 0 Y AX Y b Y0 AX0 CX0 , 0 0 0 0 CX Y AX Y b CX Y b 即 0 0 X0 是（P）的一个可行解， Y0 是（D）的一个可行解，, 0 有Y0 A C，Y0 由AX0 b,Y0 0 二、弱对偶性定理：
设原问题(P)为其对偶问题(D)为 maxz=CX min s= yb st AX< b s,tYA≥C X≥0 Y≥0 定理22若X是原问题(P)的一个可行解,Y是其 对偶问题(D)的一个可行解,则有CX≤Yb 推论1:若(P)有可行解,但无上界,则(D)无 可行解。若(D)有可行解,但无下界,则 (P)无可行解 推论2、若原问题(P)和其对偶问题(D)都存在可 行解,则P)和(D)都存在最优解
D CX Y b X P Y 0 0 2 0 0 2. 对偶问题（ ）的一个可行解，则有 定理 若 是原问题（ ）的一个可行解， 是其 推论2、若原问题（P）和其对偶问题 （D）都存在可 行解，则（P） 和（D）都存在最优解 推论1： 若（P）有可行解，但无上界，则（D）无 可行解。若（D）有可行解，但无下界，则 （P）无可行解 0 . max = X st AX b z CX 设原问题（P）为 0 . min ( ) = Y st YA C S Yb 其对偶问题 D 为