哈工大运筹学课件 对偶问题.ppt

*--第2章 对偶问题-- 第 2 章 线性规划的对偶理论 Duality 对偶 Dual Problem 对偶问题 Dual Linear Programming 对偶线性规划 Dual Theory 对偶理论 2.1 问题的提出 例：某企业计划生产甲、乙两种产品，该两种产品均需经 A、B、C、D 四种不同设备上加工，按工艺资料规定，在各种不同设备上的加工时间及设备加工能力、单位产品利润如表中所示。问:如何安排产品的生产计划,才能使企业获利最大?  1.最大生产利润模型 设 企业生产甲产品为X1件， 乙产品为X2件，则 max z= 2 X1 +3 X2 s.t 2 X1 +2 X2 ? 12 X1 +2 X2 ? 8 4 X1 ? 16 4 X2 ? 12 X1 ? 0 , X2 ? 0 2.资源最低售价模型 (原问题) ======== ( 对偶问题) 设第i种资源价格为yi,（ i=1, 2, 3, 4,） 则有 min w= 12y1 + 8y2 + 16y3 +12 y4 s.t 2y1 + y2 + 4y3 +0 y4 ? 2 2y1 +2y2 + 0y3 +4 y4 ? 3 yi ? 0, (i=1, 2, 3, 4 ) y1 y2 y3 y4 2.2 原问题与对偶问题的关系 一般表示式： 原问题： max z = c1 X1 + c2 X2 + ┈ + cn Xn 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 对偶问题： min w = b1 y1 + b2 y2 + ┈ + bm ym 　　 s.t　 a11 y1 + a21 y2 + ┈ + am1 ym ? c1 a12 y1 + a22 y2 + ┈ + am2 ym ? c2 　　　························· a1n y1 + a2n y2 + ┈ + amn ym ? cn yi ? 0，(i=1,2,···,m ) 典式模型对应对偶结构矩阵表示 （1） max z = C X s.t AX ? b X ? 0 min w = Y b s.t YA ? C Y ? 0 对偶问题 原问题 对偶模型其他结构关系 （2）若模型为 max z = C X s.t AX ? b X