第三节对偶问题与灵敏度分析 对偶问题及其模型 例7:回顾例1 Maxz=x+12x, 这时有另一家厂商 提出要购买其煤、电 9x+4x2≤360煤 油全部资源,并希望花 4x+5x2≤200电 st 费尽量少。试建立购买 3x1+10x2≤300油 者的线性规划模型 x,x2≥0 解:设其购买三种资源的价格 煤某 电 油 Mm=360y+200y2+300y 分别为y,y,y,总花费为hp,则 9y+4y2+3y27甲 例7称为例1的对偶问题,记为 s{4y+5y+10y,≥12乙 (D),例1称为例7的原问题 记为(P) y,y2,y,≥0
第三节 对偶问题与灵敏度分析 一、对偶问题及其模型 例7：回顾例1 + + + , 0 3 10 300 4 5 200 9 4 360 . . 1 2 1 2 1 2 1 2 x x x x x x x x st Maxz = 7x1 +12x 2 甲 乙 油 电 煤 这时有另一家厂商 提出要购买其煤、电、 油全部资源，并希望花 费尽量少。试建立购买 者的线性规划模型。 分别为 总花费为 则 解：设其购买三种资源的价格 , , , , y 1 y 2 y 3 w + + + + , , 0 4 5 9 4 . . 1 2 1 2 1 2 10 12 3 7 y y y y y y y y y s t 3 Minw = 360 y 1 + 200 y 2 + 300 y 煤 电 油 乙 甲 例7称为例1的对偶问题，记为 （D），例1称为例7的原问题, 记为（P）
对偶模型的一般式 以例7为例,原问题为 记Y=(y,y,y.,则对偶问题为 maXz=CX min w=y6 (P) AX<6 (D) YA≥C s t st X20 Y≥0 这是最常见的对偶模型形式,称为对称式对偶模型。二者间 具有十分对称的对应关系: 原问题(P) 对偶问题(D) 目标max型 目标min型 有n个变量(非负) 有n个约束(大于等于) 有m个约束(小于等于) 有m个变量(非负) 价格系数 资源向量 资源向量 价格系数 技术系数矩阵 技术系数矩阵的转置
对偶模型的一般式 以例7为例，原问题为 记Y = ( y 1，y 2 , y 3 ),则对偶问题为 = 0 . . X A X b s t maxz CX （P） = 0 . . min Y YA C st w Yb （D） 这是最常见的对偶模型形式，称为对称式对偶模型。二者间 具有十分对称的对应关系： 原问题（P） 对偶问题 （D） 目标max型 目标min型 有n个变量（非负） 有n个约束（大于等于） 有m个约束 （小于等于） 有m个变量（非负） 价格系数 资源向量 资源向量 价格系数 技术系数矩阵 技术系数矩阵的转置
此外,还有一种情形 原问题(P) 对偶问题(D) 第个变量为自由变量 第/个约束为等式约束 第i个约束为等式约束 第i个变量为自由变量 例8:写出下面线性规划的对偶规划模型: max z= 2x+3x 2 +2x,<3 2x 5 +3x2=1 ≥0
此外，还有一种情形 原问题（P） 对偶问题 （D） 第j个变量为自由变量 第j个约束为等式约束 第i个约束为等式约束 第i个变量为自由变量 例8：写出下面线性规划的对偶规划模型： − + = − + = + 0 3 1 2 5 2 3 . . 2 3 1 1 2 1 2 1 2 1 2 x x x x x x x s t max z x x
例8:写出下面线性规划的对偶规划模型: maxz=2x +3x +2x<3 2x-x.<5 s t x+3x=1 x≥0 解:设对偶变量为,y,y,对偶目标为n,则 minw=3y, +5y,+y y1+2y2-y t12y1-y2+3y,=3 ≥0
例8：写出下面线性规划的对偶规划模型： − + = − + = + 0 3 1 2 5 2 3 . . max 2 3 x x x x x x x s t z x x 解：设对偶变量为y , y , y ,对偶目标为w ,则 − + = + − = + + , 0 3 2 2 . . 3 5 1 2 1 2 3 1 2 3 1 2 3 y y y y y y y y s t w y y y 2 3 min
二、对偶的性质 考虑 maXz=CX m inz=y b (P) AX<6 (D) YA≥C s. t s t X≥0 y≥0 对称性(P)与(D)互为对偶。 2弱对偶性设X,Y分别是(P),(D)的可行解,则CX≤Yb 证:由(P)、(D)的约束可得CX≤YAX≤Yb 几何意义: CX Y6 3解的最优性若X与Y分别是(P)与(D)的可行解,且CX=Yb 则X=X,Y=F 证:对任可行解X,由弱对偶性,CX≤Yb=CX 故X=X‘同理,Y=Y
二、对偶的性质 = 0 . . X A X b s t maxz CX （P） = 0 . . Y Y A C s t minz Y b （D） 考虑 1 .对称性 （P）与（D）互为对偶。 2.弱对偶性 设X，Y分别是（P），（D）的可行解，则CX Yb. 证：由（P）、（D）的约束可得 C X Y AX Y b , . 3 . P D , X X Y Y X Y CX Yb = = = 则 解的最优性 若 与 分别是（ ）与（ ）的可行解，且 证：对任可行解X，由弱对偶性，CX Y b =CX . . . 故X = X 同理，Y =Y 几何意义： CX Yb