第四章习题第四章习题4.2已知线性规划问题已知线性规划问题max z=3x1+2x2 s.t -x1+2x2 4 3x1 +2x2 14 x1- x2 3 x1,x2 0min f=4w1+14w2 +3w2 s.t -w1+3w2 +3w2 3 2w1+2w2 -w2 2 w1，w2 ，w2 0（2）如果愿问题与对偶问题都有可行解，则如果愿问题与对偶问题都有可行解，则二者都有最优解。二者都有最优解。由原题可见，下列解是原问题与对偶问由原题可见，下列解是原问题与对偶问题的可行解。题的可行解。X（0）=（0，0）TW（0）=（0，1，0）T4.3min z=2xmin z=2x1 1-x-x2 2 +2x+2x3 3 s.t -x s.t -x1 1+x+x2 2 +x+x3 3 = = 4 4 -x -x1 1+x+x2 2 -Kx-Kx3 3 6 6X X1 1 0 0，X X2 2 0, X 0, X3 3无约束无约束无约束无约束 最优解最优解最优解最优解: : X（0）=（-5，0，-1）T先变成变量大于先变成变量大于0写出符合写出符合4.18,4.11,4.06条件的标准型条件的标准型min z=2xmin z=2x1 1-x-x2 2 +2x+2x3 3 s.t -x s.t -x1 1+x+x2 2 +x+x3 3 = = 4 4 -x -x1 1+x+x2 2 -Kx-Kx3 3 6 6X X1 1 0 0，X X2 2 0, X 0, X3 3无约束无约束无约束无约束 最优解最优解最优解最优解: : X（0）=(-5，0，-1)Tmax z=max z=- -2x2x1 1+ +x x2 2 - -2x2x3 3 s.t -x s.t -x1 1+x+x2 2 +x+x3 3 = = 4 4 -x -x1 1+x+x2 2 -Kx-Kx3 3 6 6X X1 1 0 0，X X2 2 0, X 0, X3 3无约束无约束无约束无约束 最优解最优解最优解最优解: : X（0）=(-5，0，-1)T写出对偶问题写出对偶问题min f=4w1+6w2 s.t w1+w2 2 w1+w2 1 w1-kw2 = -2 w1无约束无约束 ，w2 0令令XX1 1 = -X-X1 1 max z=2x z=2x1 1+ +x x2 2 - -2x2x3 3 s.t x s.t x1 1+x+x2 2 +x+x3 3 = = 4 4 x x1 1+x+x2 2 -Kx-Kx3 3 6 6X X1 1 0 0 ，X X2 2 0, X 0, X3 3无约束无约束无约束无约束 最优解最优解最优解最优解: : X（0）=（5，0，-1）T写出目标等式和互补松紧条件写出目标等式和互补松紧条件根据定理4.2.5， X（0）=（-5，0，-1）TZ*= 2x2x1 1+ +x x2 2 - -2x2x3 3 = 2 2 （5 5）-0-0 -2-2（-1-1）=12=12 f*=Z*= f*=Z*= 4w1+6w2 =124.2.7 w1= 0w2 = 2 4.2.7 w1+w2 = 2求解求解代入w1-kw2 = -1 A求得求得K=14.4对偶问题对偶问题min f=20wmin f=20w1 1+20w+20w2 2 s.t w s.t w1 1+2w+2w2 2 1 1 2w 2w1 1+w+w2 2 2 2 2w 2w1 1+3w+3w2 2 3 3 3w 3w1 1+2w+2w2 2 4 4 w w1 1 0 0，w w2 2 0 0max z=xmax z=x1 1+2+2x x2 2 + +3x3x3 3 + +4 4x x3 3 s.t x s.t x1 1+2x+2x2 2 +2x+2x3 3 + +3 3x x4 4 20 20 2x 2x1 1+x+x2 2 +3x+3x3 3 + +2 2x x4 4 20 20X X1 1 ，X X2 2, , X X3 0 0无约束无约束无约束无约束 续续W*1=1.2 0W*2=0.2 0由互补松弛条件可得由互补松弛条件可得: x x1 1+2x+2x2 2 +2x+2x3 3 +3x+3x4 4 = = 20 ( 20 (4.4.1)4.4.1) 2x 2x1 1+x+x2 2 +3x+3x3 3 +2x+2x4 4 = = 20 20续续将将W*1=1.2，W*2=0.2代入对偶问题的约代入对偶问题的约束条件。束条件。 w1+2w2 = 1.2+2 0.2=1.6 1 2w1+w2 = = 2 1.2 +0.2 =2.6 2 2w1+3w2 =2 1.2 +3 0.2 =3 3w1+2w2 = 3 1.2 +2 0.2 =4 由互补松弛条件定理可知由互补松弛条件定理可知X*1=0，X*2=0代入代入( (4.4.1)4.4.1)得得 x x1 1+2x+2x2 2 +2x+2x3 3 +3x+3x4 4 = = 20 ( 20 (4.4.1)4.4.1) 2x2x1 1+x+x2 2 +3x+3x3 3 +2x+2x4 4 = = 20 20解得解得解得解得: x*: x*3 3 = = 4 4 x* x*4 4 = = 4 4原问题最优解原问题最优解:X*=（0，0，4，4）T4.5min z=8xmin z=8x1 1+6x+6x2 2 +3x+3x3 3 +6x+6x4 4 s.t x s.t x1 1+2x+2x2 2 +x+x4 4 3 3 3x 3x1 1+x+x2 2 +x+x3 3 +x+x4 4 6 6 x x3 3 +x+x4 4 2 2 3x 3x1 1 +x+x3 3 2 2X Xj j 0, j=1,2,3,4 0, j=1,2,3,4 最优解最优解最优解最优解: : X（0）=(1，1，2 ， 0)T化标准型化标准型max z=-8xmax z=-8x1 1-6x-6x2 2 -3x-3x3 3 -6x-6x4 4 s.t -x s.t -x1 1-2x-2x2 2 -x-x4 4 3 3 -3x -3x1 1-x-x2 2 -x-x3 3 -x-x4 4 6 ( 6 ( 4.5.1)4.5.1) -x -x3 3 -x-x4 4 2 2 -3x -3x1 1 -x-x3 3 2 2X Xj j 0, j=1,2,3,4 0, j=1,2,3,4 最优解最优解最优解最优解: : X（0）=（1，1，2 ， 0）T写写对偶问题对偶问题min f=3wmin f=3w1 1+6w+6w2 2 +2w+2w3 3 +2w+2w4 4 s.t -w s.t -w1 1-3w-3w2 2 ww4 4 -8-8 -2w -2w1 1-w-w2 2 -6 -6 -w -w1 1-w-w3 3 ww4 4 - -3 ( 3 ( 4.5.2)4.5.2) -w -w1 1-w-w2 2 -w-w3 3 - - 4 4 w wi i 0 I=1,2,3,4 0 I=1,2,3,4 max z=-8xmax z=-8x1 1-6x-6x2 2 -3x-3x3 3 -6x-6x4 4 s.t -x s.t -x1 1-2x-2x2 2 -x-x4 4 3 3 -3x -3x1 1-x-x2 2 -x-x3 3 -x-x4 4 6 6 4.5.1)4.5.1) -x -x3 3 -x-x4 4 2 2 -3x -3x1 1 -x-x3 3 2 2X Xj j 0, j=1,2,3,4 0, j=1,2,3,4 最优解最优解最优解最优解: : X（0）=（1，1，2 ， 0）T互补松弛条件互补松弛条件最优解最优解最优解最优解: : X（0）=（1，1，2 ， 0）T即X Xj j 0, j=1,2,3 0, j=1,2,3s.t -w1-3w2 w4 =-8 -2w1-w2 = = -6 ( 4.5.3) -w1-w3 w4 =-=-3代原问题约束条件左端代原问题约束条件左端X（0）=（1，1，2 ， 0）T,x x1 1+2x+2x2 2 +x+x4 4 =1+2+0=3=1+2+0=3 3x 3x1 1+x+x2 2 +x+x3 3 +x+x4 4 =3+1+2+0=3+1+2+0= 6 6 x x3 3 +x+x4 4 =2+0=2+0= 2 2 3x 3x1 1 +x+x3 3 =1+2=1+2 2 2 互补松弛定理互补松弛定理互补松弛定理互补松弛定理w4 =0=0w w4 4 =0=0代入代入代入代入对偶问题约束条件对偶问题约束条件对偶问题约束条件对偶问题约束条件s.t -ws.t -w1 1-3w-3w2 2 ww4 4 = =-8-8 -2w -2w1 1-w-w2 2 = = -6 ( -6 ( 4.5.3)4.5.3) -w -w1 1 -w-w3 3 ww4 4 =-=-3 3 w w4 4 =0=0解得解得解得解得: : w w1 1 =2 =2 w w2 2 = = 2 w 2 w3 3 = = 1 1对偶问题最优解对偶问题最优解:w w*=（2，2，1 ， 0）T, 4.7已知线性规划问题已知线性规划问题max z=10x1+5x2 s.t 3x1+4x2 9 5x1 +2x2 8 x1,x2 0化成化成标准型标准型max z=10x1+5x2 s.t 3x1+4x2 +x3 = 9 5x1 +2x2 +x4 = 8 x1,x2 0A表表4.710500CBXBbx1x2x3x45x23/2015/14-3/1410x1110-1/72/7-Z-35/200-5/14-25/14B-1(1) CC+ C(1)目标函数中的价值系数目标函数中的价值系数c1，c2分别在什么范围内变动分别在什么范围内变动时时,上述最优解不变。上述最优解不变。当当C由由CC+ C时时新检验数新检验数=（C+ C）-（CB+ CB）B-1A 4.5.2目标涵数目标涵数Z=（CB+ CB）B-1b 4.5.3若若0时时，最最优优解解仍仍为为最最优优解解，目目标标值值发发生生了了变变化化。否则，重新迭代。否则，重新迭代。解解:c1 C1）变量变量=C-（CB+ CB）B-1A变变 =C- CB B-1A=（ C1 ，5，0，0）-（5， C1） B-1(P1， P2， P3， P4) （B：E） （E：B-1）B-1=5/14 -3/14-1/7 2/7BC=（5， C1）B*/B （5， C1）4 32 5B= B =4 5-3 2=14B11 B21B12 B22B*= =4 32 5B21 =（-1）（1+2） = -35 -3-2 45/14 -3/14-1/7 2/7B-1=（5， C1）P（P1， P2， P3， P4）=3 4 1 05 2 0 1AHV代入代入=（ C1 ，5，0，0）-（5， C1） B-1(P1， P2， P3， P4)= （ C1 ，5，0，0）- （5， C1） 5/14 -3/14-1/7 2/73 4 1 05 2 0 1=（ C1 ，5，0，0）-C1 ，5，(25-2 C1 )/14 ， (4 C1 - 25)/14 每个分量小于每个分量小于0= 0 ，0，-(25-2 C1 )/14 ， -(4 C1 - 15)/14 -(25-2 C1 )/14 0 C1 25/2 -(4 C1 - 15)/14 0 C1 15/4 15/4 C1 25/2 B*/B （ C1 ， C2）3 4 5 2 B= B =4 5-3 2=14B11 B21B12 B22B*= =3 45 2B21 =（-1）（1+2） = -42 -4-5 3-1/7 2/75/14 -3/14B-1=代入代入=（ C1 ，5，0，0）-（ C1 ， 5 ） B-1（P1， P2， P3， P4）= （ C1 ，5，0，0）- （ C1 ， 5 ）-1/7 2/7 5/14 -3/143 4 1 05 2 0 1=（ C1 ，5，0，0）-C1 ，5，(25-2 C1 )/14 ， (4 C1 - 25)/14 矩阵乘法的性质矩阵乘法的性质(AB)C=A(BC)(A+B)C=AC+BCC(A+B)=CA+CBK(AB)=(KA)B=A(KB)(2)约束右端项约束右端项b1约束右端项约束右端项b1，b2当一个不变时，另一个在什当一个不变时，另一个在什么范围变化时，原问题的最优解保持不变。么范围变化时，原问题的最优解保持不变。解：解：当右端列向量当右端列向量b b+ b改变第三列改变第三列X B =B-1b XB = B-1 （b+ b）-Z =-CBB-1 b -Z =-CBB-1（ b+ b）A、若若XB = B-1 （b+ b） 0因为因为 没有变没有变则最优基不变，最优解为则最优基不变，最优解为XB 和和 Z 不大于不大于0B、若若XB = B-1(b+ b) 0因为因为0没有变，没有变， XB = B-1 （b+ b） XN = 0XBXN=B-1(b+ b) 0正则解正则解b2不变不变XB = B-1(b+ b)=5/14 -3/14-1/7 2/7b18= 0（5 b1 -24）/14（16- b1 ）/7求解不等式求解不等式(5b1 -24)/14 0(16- b1)/7 0 24/5 b1 16解法2(1) 解:（1）当 其它值不变，C1发生变化后最优单纯表变为如下C1 500CBXBbX1X2X3X45X23/2015/14-3/14C1X1110-1/72/7-Z-35/200-(25-2 C1 )/14 -(4 C1 - 15)/14 要保持最优解不变，所有检验数应要保持最优解不变，所有检验数应 0 0故：故： - -（25-2C25-2C 1 1）/14/14 0 0， C C 1 1 25/225/2；-(4 C4 C 1 1 - 15)/14 - 15)/14 0 0，C C 1 1 15/415/4所以所以15/415/4 C C 1 1 25/2 25/2 (2)b103/215/14-1/700（2）由于目标函数中其它参数不变，b1变化不影响检验数，如果变化后XB0那么最优基也不变。B-1b+B-1 = + b1b1-21/5， b17。b1+b124/5，b1+ b116。b1的范围是-21/5，7，即b1的范围是24/5，16。（3）目标函数目标函数目标函数变为目标函数变为max z=12x1+4x2 时，最优时，最优解如何变化？解如何变化？根本是根本是c1，c2同时变化同时变化解解.基变量基变量=C-（CB+ CB）B-1A变变 =C- CB B-1A=（ C1 ， C2，0，0）-（ C2 ， C1） B-1（P1， P2， P3， P4） （B：E） （E：B-1）B-1=5/14 -3/14-1/7 2/7P（P1， P2， P3， P4）3 4 1 05 2 0 1代入代入= （ C1 ， C2，0，0）-（ C2 ， C1） B-1（P1， P2， P3， P4）= （ C1 ， C2，0，0） - （ C2 ， C1）5/14 -3/14-1/7 2/73 4 1 05 2 0 1= （ C1 ， C2，0，0） -C1 ， C2 ，(5 C2 -2 C1 )/14 ， (4 C1 - 3 C2)/14 每个分量每个分量= 0 ，0，-(5 C2 -2 C1 )/14 ， -(4 C1 - 3 C2)/14 =（0，0，2/7，-18/7）表表4.7.110500CBXBbx1x2x3x44x23/2015/14-3/1412x1110-1/72/7-Z-35/2002/7-18/7表表4.7.212400CBXBbx1x2x3x44x221/5014/51-3/512x1110-1/72/7-Z-35/2002/7-18/7表表4.7.212400CBXBbx1x2x3x40x321/5014/51-3/512x18/512/501/5-Z-96/50-4/50-18/7最优解最优解最优解最优解: : X=（8/5，0，21/5 ， 0）T(4)右端项右端项约束右端项由约束右端项由变为变为最优解为多少最优解为多少?981119XBXB = B-1 （b+ b） =5/14 -3/14-1/7 2/71119-1/727/7=B-15/14 -3/14-1/7 2/7B-1=表表4.7 . 4110500CBXBbx1x2x3x45x2-1/7015/14-3/1410x127/710-1/72/7-Z-265/700-5/14-25/14表表4.7 . 4210500CBXBbx1x2x3x45x2-1/7015/14-3/1410x127/710-1/72/7-Z-265/700-5/14-25/14 j/arj25/3表表4.7 . 4310500CBXBbx1x2x3x45x22/30-14/3-5/3110x127/710-1/72/7-Z-265/700-5/14-25/14 j/arj25/3表表4.7 . 4310500CBXBbx1x2x3x40x42/30-14/3-5/3110x111/314/31/30-Z-110/30-25/3-10/30 j/arj25/3最优解最优解最优解最优解: : X=（11/3，0，0 ， 2/3）T4.6题题其中X2变为X2500。即某一个约束的右端项变化为350-500b = B-1 （b+ b）=1 0 -2 -3 1 5 0 0 1800900 500-2001000 500=Z =CB B-1 b =（3，0，8）-2001000 500=34004.6(1)用用b ， Z 最终单纯形表可得：最终单纯形表可得： C38000CBXBb-x1x2x3x4x53x1-2001010-20x4100000-3158x250001001-Z -3400 00-30-24.6(11） C38000CBXBb-x1x2x3x4x53x1-2001010-20x4100000-3158x250001001-Z -3400 00-30-2j/a rj1主行乘主行乘-1/2得得4.6(12） C38000CBXBb-x1x2x3x4x53x1100-1/20-1/2010x4100000-3158x250001001-Z -3400 00-30-2j/a rj1主行主行分别乘分别乘-5加到第二行，乘加到第二行，乘-1加到第三行，把加到第三行，把x1换换成成x5，系数系数3变成变成0。4.6(2)用用对偶对偶单纯形法可得：单纯形法可得： C38000CBXBb-x1x2x3x4x50x5100-1/20-1/2010x45005/20-1/2108x24001/211/200-Z -3200 -10-400最优解最优解： XB=（0，400，0，500，100）T ，Z=3200