第三节对偶问题与灵敏度分析 对偶问题及其模型 例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
例9:设线性规划问题1为Mx=1=CX,Y是其对偶问题的最优解; aX<6 st X≥0 又设线性规划问题2为Max2=CY,其中k是已知常向量。 AX<6+k s. t X≥0 求证:Max,≤Max=1+Yk 证:问题1与问题2的对偶问题分别是 Minw=yb (ii Minw=yb+yk YA≥C YA≥C Y≥0 (Ⅰ)与(I)的约束相同,故(I)的最优解Y是(Ⅱ)的可行解。 由弱对偶性,Mαxx≤Yb+Y‘k,而由解的最优性,Yb=Maxz, 得证
1 2 2 1 9 1 , . . 0 2 , 0 Maxz CX Y AX b s t X Maxz CX k AX b k s.t. X Maxz Maxz Y = = + + 例 ：设线性规划问题 为 是其对偶问题的最优解； 又设线性规划问题 为 其中 是已知常向量。 求证： k 。 = = + 0 . . 0 . . 1 2 Y Y A C s t Y Y A C s t （ ）M inw Y b （ ）M inw Y b Y k 证：问题 与问题 的对偶问题分别是 （）与（）的约束相同，故（）的最优解Y 是（）的可行解。 由弱对偶性，M axz Y b +Y k，而由解的最优性，Y b = M axz， 得证
4对偶定理若(P)有最优解,则(D)也有最优解, 且最优值相同。 Maxz=cx 证:对(P)增加松弛变量Xs,化为 AX+ⅠX=b X.X≥0 O 设其最优基为B,终表为 X B-b B-4 B- C-CBA0-CB-I 其检验数为ja=C-CBAs0 取Y=CB-,则Y满足 O=0-CB-Ⅰ≤0 YA≥C Y≥0 即Y是(D)的可行解,且Yb=CBb 由性质3,Y=Y
4.对偶定理 若（P）有最优解，则（D）也有最优解， 且最优值相同。 证：对（P）增加松弛变量Xs，化为 + = = , 0 . . X X A X I X b s t M axz CX 设其最优基为B，终表为 X X C 0 B A B I 1 1 − − C B b − C C B A 0 C B I − − − − = − = − − − 0 0 0 C B I C C B A 其检验数为 取Y =C B −1 ,则Y 满足 Y 0 Y A C − Y Y b =C B b = z 1 即 是（D）的可行解，且 3 . 由性质 ，Y =Y
可题:(1)由性质4可知,对偶问题最优解的表达式Y*=? B (2)求Y*是否有必要重新求解(D)? 不必。可以从原问题(P)的单纯形终表获得。 例如,在前面的练习中已知Manz=2.5x+x2的终表为 3x1+5x2≤15 st5x1+2x2≤10 x1.x2≥0 X=(2,0,9,0 2.5x12 5 000-0.5 Y=(0,0.5) 请指出其对偶问题的最优解和最优值 5
问题：(1) 由性质4可知，对偶问题最优解的表达式 Y* =？ (2) 求Y*是否有必要重新求解（ D）？ —— CBB -1 —— 不必。可以从原问题（P）的单纯形终表获得。 + + , 0 2 5 . . 1 2 1 2 1 2 x x x x x x s t 5 10 3 15 例如，在前面的练习中已知 Maxz = 2.5x 1 + x 2 的终表为 5 1 0 5 2 1 5 3 1 - 5 19 0 2 9 1 3 x x 2.5 0 0 0 0 - 0.5 X = (2, 0, 9, 0) = 5 z 请指出其对偶问题的最优解和最优值。 5 (0,0.5) = = w Y
5.互补松弛定理 若ⅹ与Y分别是(P)D)的可行解,则X和Y是(P)(D) 最优解的充要条件是YX=FX=0。 证:将(P)D)的约束化为等式:AX+X,=b,YA-Y=C, →因为X、Y是最优解,所以CX=乃b即 (4-Y1)X=Y(AX+)而YX,X≥0, 故只有YX=YX=0 <(自证)
5.互补松弛定理 最优解的充要条件是 。 若 与 分别是 、 的可行解，则 和 是 、 0 (P) (D) ( ) ( ) YX = Y X = X Y X Y P D s s （自证）。 故只有 。 而 因为 、 是最优解，所以 即 证：将 、 的约束化为等式： = = − = + = + = − = 0 ( ) ( ), , 0, , (P) (D) , , YX Y X YA Y I X Y AX IX YX Y X X Y CX Yb A X IX b YA Y I C s s s s s s s s
直观上 原始问题的变量原始问题的松弛变量 X X n n+1 n+m y1…yi m ym+1…ym+i.y ntm 对偶问题的变量对偶问题的松弛变量 Xym=0yxn+=0(i=1,2…m,=1,2, 在一对变量中,其中一个大于0,另一个一定等于0
y1… yi… ym ym+1 … ym+j … yn+m x1 … xj … xn xn+1…xn+i…xn+m 对偶问题的变量 对偶问题的松弛变量 原始问题的变量 原始问题的松弛变量 xjym+j=0 yixn+i=0 (i=1,2,…,m; j=1,2,…,n) 在一对变量中，其中一个大于0，另一个一定等于0 直观上