第四章对偶理论及灵敏度分析 线性规中的对偶理论 对偶单纯形法 ◆灵敏度分析
第四章 对偶理论及灵敏度分析 ◆ 线性规划中的对偶理论 ◆对偶单纯形法 ◆灵敏度分析
§1线性规划的对偶理论 一、对偶问题的实例 产品 资源 maxz=1500x1+2500x2 资源 甲 乙 限制 A 3 2 65 s.t. 3x1+2x2≤65 B 2 1 40 2x1+x2≤40 (1) C 0 3 75 3x2≤75 单件利润 1500 2500 X1,x2≥0 最优解为：x1*=5,x2* 如果称（1)为LP问题的 设y,y23分别为A,B,C 原问题，则称(2)为（1) min w=65y1+40y2+75y3的对偶问题。 s.t. 3y1+2y2 ≥1500(2) 最优解为：y1*=500 2y1+y2+3y3≥2500 y2*=0,y3*=500, y1,y2,y3≥0 wmin=70000
§1 线性规划的对偶理论 一、对偶问题的实例 产品 资源 资源 甲 乙 限制 A 3 2 65 B 2 1 40 C 0 3 75 单件利润 1500 2500 max z =1500x1+2500x2 s.t. 3x1+2x2 ≤65 2x1 +x2 ≤40 (1) 3x2 ≤75 x1 , x2 ≥ 0 最优解为： x1* =5 ， x2* =25 zmax =70000 设 y1 , y2 , y3 分别为 A, B, C 三种资源出售的价格 3y1 +2y2 ≥ 1500 2y1 + y2 +3y3 ≥ 2500 w= 65y1 +40y2 +75y3 min w = 65y1 +40y2 +75y3 s.t. 3y1 +2y2 ≥ 1500 (2) 2y1 + y2 +3y3 ≥ 2500 y1 , y2 , y3≥ 0 最优解为： y1*= 500 y2*= 0 ， y3* = 500, wmin = 70000 如果称（1）为LP 问题的 原问题，则称（2）为（1） 的对偶问题
第四章对偶理论及灵敏度分析 二、对偶问题 min i=cx max y=w b P s.tAx≥b D) s.twA≤C 1、对称型对 x≥0 定义1设原LP问题为 则称下列XP问题 minz=C心+CX2+..+Crxn max y=biw+b2w2+...+bmwm s.t. 01心1+4122+..+01xn≥b1 s.t. a21+422x2+..+a2mxn≥b2 an"1+a2nW2+.…+amwm≤C1 aw+a2w2+...+am2wmc2 4) amam2X2+…+amn≥bm ≥0G=1,2,.,n)） a1nw1+a2nw2+…+AmnWm≤Cn 为其对偶问题，其中 w,≥0(=1,2，，m)称为对偶变量 并称(3)、（4)为一对对称型对偶问题
第四章 对偶理论及灵敏度分析 二、对偶问题的形式 1、对称型对偶问题 min z = c1 x1 + c2 x2 + … + cn xn s.t. a11x1 + a12x2 + … + a1nxn ≥ b1 a21x1 + a22x2 + … + a2nxn ≥ b2 (3) … … am1x1 + am2x2 + … + amnxn ≥ bm xj ≥ 0 （j = 1,2,…,n） max y = b1 w1 + b2 w2 + … +bm wm s.t. a11w1 + a21 w2 + … + am1wm ≤ c1 a12w1 + a22w2 + … + am2 wm ≤ c2 (4) … … a1nw1 + a2nw2 + … + amnwm ≤ cn wi≥ 0 （i = 1,2,…,m） 定义1 设原 LP 问题为 则称下列 LP 问题 为其对偶问题，其中 wi ≥ 0 （i = 1,2,…,m）称为对偶变量， 并称（3）、（4）为一对对称型对偶问题 min z=cx (P) s.t. Ax ≥ b x ≥ 0 max y= w b (D) s.t. w A ≤ c w ≥ 0
§1线性规的对偶理论 2、非对称型对偶问题 maxy=wb D】cA≤C min =cx max y=wb P s.t.Ax=b D s.twA≤ c x≥0 w无符号限制 引入对偶变量 (u,v),其中u=(u,42,,4m) min =cx S.t.Ax≥b 为对应于第一组不等式约束A化≥b的对偶变 -Ax≥-b 量，y=(y,y,ym)为对应于第二组不等式约 x≥0 束-Ax≥-b的对偶变量，按对称型的结论： max y=(u,v) 6 max y=(u-v)b s.t(u-)A≤c 令w=u-y s.t. (u,) A ≤C (-A 4,v≥0 u,v≥0
§1线性规划的对偶理论 2、非对称型对偶问题 min z = cx (P) s.t. Ax = b x ≥ 0 min z = cx s.t. Ax ≥ b -Ax ≥ -b x ≥ 0 引入对偶变量（u,v），其中 u = (u1 ,u2 ,…,um) 为对应于第一组不等式约束 Ax ≥ b 的对偶变 量，v = (v1 ,v2 ,…,vm) 为对应于第二组不等式约 束 -Ax ≥ -b 的对偶变量，按对称型的结论： max ( , ) . . ( , ) , 0 b y u v b A s t u v c A u v = − − max y = (u-v) b s.t. (u-v) A ≤ c u,v ≥ 0 令 w=u-v max y= wb (D) s.t. wA ≤ c max y = wbw ≥ 0 (D) s.t. wA ≤ c w 无符号限制
第四章对偶理论及灵敏度分析 3、一般情形 min cx max P)s.tAx≥b wb +w2b +wb A Axx=b2 -Im 0 S.t.（w1,w2,w3） 0 0 ≤(c,0,0) A3x≤b3 A 0 20, 化原问题为标准型： max y=bw+b2w2+b3W; min =cx 按非对 s.t.WAj+W2A2+w:A:sc s.t.Apx-xs =b1 Axx =b2 称型 w1≥0 AX+比 =b3 w3≤0 w2无限制 x,x,X≥0
第四章 对偶理论及灵敏度分析 3、一般情形 min z = cx (P) s.t. A1x ≥ b1 A2x = b2 A3x ≤ b3 x≥ 0, 其中 Ai 为mi× n 矩阵；bi 为mi维列向量；c为n维行 向量；x为n 维列向量， i=1,2,3 化原问题为标准型： min z = cx s.t. A1x- xs = b1 A2x = b2 A3x+xt = b3 x , xs , xt ≥ 0 max y = b1 w1+b2w2 +b3w3 s.t. w1 A1+w2 A2+w3 A3 ≤ c w1 ≥ 0 w3 ≤ 0 w2 无限制 按非对 称型 1 3 1 1 2 2 3 3 min 0 0 0 . . 0 0 0 , , 0 s t m s m t s t cx x x A I x b s t A x b A I x b x x x + + − = 1 3 1 1 2 2 3 3 1 1 2 3 2 3 max 0 . . ( , , ) 0 0 ( ,0,0) 0 m m w b w b w b A I s t w w w A c A I + + −