大学运筹学经典课件第二章――对偶理论与灵敏度分析_百汇总

1、2 第二章对偶理论与灵敏度分析 1 单纯形法的矩阵描述 设max z = CX r AX = b X三0 A为mxn阶矩阵RankA=m ,取B为可行基，7 为非基, X X = = XR 店闪 A/LC = Q CN BXB + NXN =b=b X XB B,X,XN N00 0 B-BXB + B B- -NXN = BNXN = B- - b b ()X + (CN - CRB-N)XN - Z = - -C CB BBBx xb b . . 矩阵单纯形表: IXB+ITNXN =Bb=Bb OX n+bjvX/v z = C B BNN 0 B Bb b 0 bNbN 1 C“B b

2、C“B b =BXBNXN =b=b IXR+BNXN =Bb =Bb ()Xfi +(r+(rN NX XN N z z bb 令 XN =0 得 XB=B% 二 Z = C”b, DN=CN-CBB7N 注！使 （XKJB为最优基 若能找到最伽，则最优解直接由上式求H 1 取可行基B,求3 2 若TN=CV-GB-/V0,则得最优解否则转下一步 3 基变换 若max（6）j 0=（片）则“入基 则/行对丿卫的出畢. 4 得到新的B,求出此Z?的 基可行解x = BB b b 0 目标函数2 = %5 -IrM Ti min （3 （矿|（n （八 (心I 亜复24步玄到求出结果 2 对偶问

3、题的提出 昭1制定生产计划 Mi: uiax z = 2X + 3X2 lx+ 2X9 8 4X W 16 4xo W 12 3 I yP y2, y3 0 则为叫的对偶问题， i 反之亦然。 I II 限制 设备台 时 1 2 8 台时 材料A 4 0 16kg 材料 0 4 12kg 利涧 2 3 maxz = 2JCJ + 3X2 + 2*2 8 4. 5 16 4A： r 2Y1 m 厂 v Y1 + 2y2 2 y2 $ 1 I yP y2 0 IO 2、 含等式的情况 _og. 3 in?x z 二 Xf + 2x, + 4x? 2X + x? + 3x = 3 X + 2x2 +

4、 5X3 W 4 Xp X2, X3 M 0 对偶:iuinw = 3y-3y”+4允 f 2y2y+ y2 M 1 y；- y+2y2 3 2 3yJ-3y+5y2 3 4 、y/ Yi, y2 0 般，原问题第i个约束取等式, 2X + x2 + 3X3 W 3 -2X - x9 3X3 W3 令yi=yf-yr,则： min w = 3yi+4y2 ” 2y】+ y2 1 y y】+2y2 N 2 3yx +5y2 N 4 y2 3（），儿无约束 对偶问题第i个变量无约束 对偶:min w = -3y+ 4y0 r-2y/ + y2 f J -y/ + 2y2 2 -3y/ + 5yQ

5、4 I yJ, y2 三o9 3、含的iuax问题 og. 4 mpx 7. = x（十 2x, + x： 0 2X + x? + 3x 2 3 * _2X - x2 - 3X3 W_3 x3 M 0, X4无约束 对偶：uiax w = 5yx + 4y2 + 6y3 (Yi + y2 M 2 Yi 十 丫3 V 3 -3y + 2y2 +3 W -5 yi- y2+ Y3 =1 0, y2 0, 丫3无约束 * 4 对偶问题的性质 1、对称性 对偶问题的对偶为原问题. maxz = CXy AX Wb, XPO u n minvv=r/A YAC. r 0 max(-vv) = - min

6、 w = -Yb. YAC=-YA0即 max(-iv) = -Yb -YA S -C r o minvv ) = -CX -AX -b X 0 inin(-vv ) = -CX (-AX -b x 2 0 min(-vv ) = -max v = maxvv = CX 令 z = /. maxz = CX AX Sb X 016 2.弱对偶性 设乂为原问题的可行M- V为对偶问题的可行解则存在 CX Yb 证明： 设乂 V分别为原I.题和对问逊的町行解 AX AX YAX C=YAC= YAX CX CX YAX Yb CX Yb 证毕 推论: （1） max问题任一町解的H标值为miri问

7、题H标值的一个卜界; （2） min问题任一可解的H标值为max问题H标值的一个上界。 3、无界性 、若原问题（对偶间题）为无界解,则对偶问题（原问题）为 无可行解。 注：该性质的逆不存在。若原（对偶）问题为无可行解,对偶 （原问题）问题或为无界解，或为无可行解。 15 4、最优性 设XS Y*分别为原问题和对偶问题可行解，当 CX*=Y*b时，X*, Y*分别为最优解。 证明： 设疋卩分别为原问题和对偶问迩的任一对行触 由弱对偶性 (1) CX Y*h = CX* H|j CX CX* X为最优解 (2) YbCX* = Y*b 即 YhYb *为最优解 证毕 若原问题仃最优解，那么对偶问题

8、也有最优解, 且口标值相等。 证明: 设X 为原问题的M优卅则K对应的基矩阵心在 全部检验数可表示为 C-CbBlA C0BlA C YAC 其中 Y* =CBB- 若厂为对偶问题的町行M则w =Yb = CBBh 因原问题最优赋 = /rb则其口标值为： Z = CXc = (CBCN b = CnBb = Y b = w Y*为対偶|i -J题的故优解，11.原f. U题利对偶I； J题 的目标值相等。 证毕 6、松弛性 若X*, Y方分别为原|i.J题及对偶问题的可行解, maxz = CX +0Xs minw = Yb+Ys0 AX + X、=b YA-YS=C X.Xs0 W必 将b

9、,C分別代入H标浙数: Z = CX =(YA-YJ X = YAX-YSX w=Yb = Y(AX + Xs) = YAX + YXs 若 X，厂为可行解当 J；X*=O,rX；=(W,yv#=z* x，厂为最优鮒 另一方血若X ，厂分别为垠优解则i/ = z* .必有r；x# =0,厂x；=o 证毕那么 YS*X*=O, Y*XS*=(), 最优解。 证明： 设原问题为： maxz = CX + 0X$ AX + XS =b X.XS 0 当且仅当X3 Y*分别为 设对偶问题为： min vv = Yb + YsO x：xnY 用分量表示： Jy；x； =0, j = 1,2, . ，舁;

10、 y：x； =o, i = 1,2, . ,m 7、检验数与解的关系 (1) 原问题卜瑕优检验数的负值为对偶问题的一个基解。 (2) 原问题最优检验数的负值为对偶问题的最优解。 分析：max z = CX + 0Xs = (C 0) (X XS)T AX + Xs = l/ X, Xs M 0 tu in w = Yb + Ys0 YA - Ys = C Y, Ys M 0 检验数：a = (C 0)-GBFA T) =(C- CBB - -CBBT) =(O C a s) a c = C - CBB1A X对应的检验数 a . = - QB 1 Xs对应的检验数 厂=(y； y；) 耳=(

11、(Jsi 52. ySt) 21 24 有 f 2X3* + 3XI* = 20 I3X3* + 2X1* = 20 昭c l2知: min w = 20y + 20yQ Yi + 2y2 1 2y【+ y2 2 v 2yt + 3y2 3 3儿 + 2y2 4 yP y2 0 的最优解为y/l- 2, y,*-0. 试用松弛件求対偶 问题的最优解。 解：对偶问题 max z = X + 2X2 + 3X3 + 4X4 X + 2X2 + 2X3 + 3X4 W 20 2xt + x2 + 3X3 + 2X4 W 20 Xp X2, x3, X4 M 0 y/xsl* = 0 yo*xs2*

12、= 0 yx= 0 ys2*x2* = 0 ys3*x3* = 0 ys/x4* = 0 y yr 2, y2*0. 2 0 Xsl = Xs2 = yt* + 2y2* = 1. 6 1 ysl* 2y/+ y2* = 2. 6 2 y s2* 2y+ 3y2* = 3 二右边 y= 3y+ 2y= 4 =右边 Vs4* .x/= 0 .- x/ = 0 X3审待25 最优解：Xj*= 0 x2*= 0 x3*= 4 x4*= 4 xsl*= 0 xs9*= 0 最大值:z*=28 = w* 5 对偶问题的经济含义一 最优情况：z* = w* = + 箫=y： 称y eg. 7max z =

13、 2x】+ 3x2 W 8 w 4X2 W 16 12 I xp x2 0 b1； 89 b9： 16 17 b3； 12 13 QJ A z* = z* -z* = 3/2 = Y1 Q2 (4. 25, 1. 875) z茫二 A z* = z* - z* = 1/8 = y2 A z* = 0 = y3* 2. 5) z* - z h = 15. 5 * 14. 125 6 对偶单纯形法 单纯形法：由 XB = B1b 0,使 OjWO, j = 对偶单纯形法：由o $ W 0(j= 1,i】)，使XB二B】bM0 步骤：(1)保持0 j W 0, 建立计算表格: 判别XB = BF M

14、 0是否成立? 若成立，XB为最优基变量; 若不成立，转(3)； 28 (3) 基变换 出基变量， 若min勺”; v 0=罕则耳入基。 J aQ J alk (4) 消元运算，得到新的XB。 重复(2) - (4)步，求出结果。 27 *8用対偶单纯形法求解 min w = 2xt + 3x2 + 4x;J f Xi + 2X2 + X3 M 1 2X - x2 + 3X3 三 4 I Xp x2, X3 M 0 30 最优解：x= 2, x2* = 0, x3* = 0, x4*= 1, x5* = 0 目赫柚:w* = -z* = 4 29 7灵敏度分析 今斩 变化对舉优解的彩吻。 最优

15、性条件：J =CN - CRB-N SO 或 cy = Ccy = C- -C CH HBBi iA0A0 或 b b j j = = Cj Cj -CRB p jp j 0h0Cp XR b xi x2 X3 x4 X5 0 X4 -1 -1 -2 -1 1 0 0 / X5 -4 -2f 1 -3 0 1 / -2 * 3 -4 0 0 z出 1 4/3 0 X4 1 0 -5/2 1/2 1 -1/2 -2 X1 2 1 -1/2 3/2 0 -1/2 0 4 -1 0 -1 -2 一3 4 0 0 Vx4, x50 代最优 32 7.1资源的变化 b b- - hj hj + + /?

16、/? 4- AhAh b = (bb = (b b?b?b,)b,) AhAh = (00- zlb () X X/ = Bb= Bb 亠 BB (/? + 4 = B b +B b + 由 B b + B AbB b + B Ab 求出少的变化范围保持问题的最优性不变 这里用到可行性条件 31 例1已知卜述问题的最优解及最优单纯形表, 1） 求少，的变化范围使最优基不变 2） 求4人=4时的最优解 maxz = 2Xj +3x? +0 x3 +0兀 +Ox5 X + 2“ + x, = 8 4x, + x4 = 16 034 最优单纯形表如下： 2 3 0 （）（） （）（） CR XR b

17、 b 小 心 1 2 4 4 1 0 0 1/4 0 0 4 4 0 0 2 1/2 1 _ 3 x x2 2 2 2 0 1 1/2 -1/8 0 1 0 0 -3/2 -1/8 0 此吋,X* =(4 2 0 0 4)7 Z =14 0 1/4 0_ _8_ 4 4 X； = Bb =Bb = -2 1/2 1 16 = 4 4 _I/2 -1/8 0 12 2 2 解：1) b b2 2 = 16 Z?2 4-少2 由最优匏纯形农得：| 0 1/4 B B = = -2 1/2 1/2 -1/8 0 1 0 少 H()=i(b+e) B (b + Ab) = Bb + BAbB (b +

18、 Ab) = Bb + BAb 4 +丛/4n0 =0/20 =-8zlZ?2 16 2 -必/8 n 0最优基不变 35 B (b + Ab) = B b + B AbB (b + Ab) = B b + B Ab 用对偶单纯形法计算o 0 c 4-Zk =c=c： E =5 +生-qzrH =s=s +&龙 令：& = + Jc S 0 =/1Q 4?斗 Yr斗=(1/8) = 1/8 即1/8时最优解不变 39 2 基变量价值系数女勺变化 分析： 原 ooN N = = C C“ “ 一 C CRB NN If 贝=C?V-(Q+Z1Q)B =CN -CBB N N _4

19、CBB N =o=oN N - - ACBB NN 其=(q c2 c ccjcj JQ =(0 0 - zlcr 0) 可见影响所有cr,变化42 方法： 令 - ACRB l lN N 00 求tlUc的变化范围 例3求例1 勺的变化范1羽,便最优解不变. 2 3 0 0 0 Cu XB b 心 *2 *3 x4 屯 2 xl 4 1 o 0 1/4 0 0 X5 4 0 0 2 1/2 1 3 x2 2 0 1 1/2 -1/8 0 0 0 -3/2 -1/8 0 解：CR=(2 0 3), ACACn n = (0 0 zlc2) 2 3 0 o 0 CB XB b 乞 1 p 屯 乞

20、 屯 2 X1 4 1 T o 0 1/4 0 o XS 4 0 0 L -. 2 1/2 1 3 X2 2 0 1 1 1/2 -1/8 0 0 1 0 -3/2 -1/8 0 J =(6 6)= (3/2 -1/8) 6 = 3 - P3 = t 上1戸3 43 心=6 _zkB l lp p4 4 =(T4 - -ziczicB Bp p4 444 3 3 V? cr = -= - (0 0 zlc2) -2 = - SO U/2丿 即-3zlc. 1时最优解不变 7.3技术系数的变化 分析： 讨论非基变量技术系数的变化 原 6 6 =c=ck k - -C CB BB B p pk k

21、 厂 1/4、 AC2- -3 AC2 Pk +少代 dzkn-l,此时瑕优解不变则 = = C Ck k 一 CBB l l(p(pk k 4- =5 -CRB p, -CRB 4PA =6 =6 C C B B 1 1 ApApk k =6 _(龙I 龙厂兀创)(0zkz O)7 =6 一勺如 时，最优解不变 6 = 6 -兀兀 2 如 24 = = W W 如 24 当曲2 2 45 例4求例1 A的变化范围， 使最优解不变. 解： 。24 =1，。24 +出24 = 1 + AZ24 CBB =(2 0 3)矿】 = (3/2 1/8 ()=(龙| 71.71.心) 例5在例1的基础上，企业要增加一个 新产品III每件产品蛊2个台时，原材料A 6kg, 原材料B3kg,利润5元/件，问如何安排各产 品的产量，使利润最大？ 解：设七为新产品生产的件数则有 0 1）计算cr3 cycy3 3= =c c3 3- -C CH HB B