运筹学基础(第2版)何坚勇 第四章习题答案

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第四章习题,1,4.2,已知线性规划问题,max z=3x,1,+2x,2,s.t -x,1,+2x,2,4,3x,1,+2x,2,14,x,1,- x,2,3,x,1,x,2,0,min f=4w,1,+14w,2,+3w,2,s.t -w,1,+3w,2,+3w,2,3,2w,1,+2w,2,-w,2,2,w,1,，w,2,，w,2,0,2,（,2,）,如果愿问题与对偶问题都有可行解，则二者都有最优解。,由原题可见，下列解是原问题与对偶问题的可行解。,X,（,0,）,=,（,0,，,0,）,T,W,（,0,）,=,（,0,，,1,，,0,）,T,3,4.3,min z=2x,1,-x,2,+2x,3,s.t -x,1,+x,2,+x,3,=,4,-x,1,+x,2,-Kx,3,6,X,1,0,，,X,2,0, X,3,无约束,最优解,:,X,（,0,）,=,（,-5,，,0,，,-1,）,T,先变成变量大于,0,4,写出符合,4.18,4.11,4.06,条件的标准型,min z=2x,1,-x,2,+2x,3,s.t -x,1,+x,2,+x,3,=,4,-x,1,+x,2,-Kx,3,6,X,1,0,，,X,2,0, X,3,无约束,最优解,:,X,（,0,）,=(-5,，,0,，,-1),T,max z=,-,2x,1,+,x,2,-,2x,3,s.t -x,1,+x,2,+x,3,=,4,-x,1,+x,2,-Kx,3,6,X,1,0,，,X,2,0, X,3,无约束,最优解,:,X,（,0,）,=(-5,，,0,，,-1),T,5,写出对偶问题,min f=4w,1,+6w,2,s.t w,1,+w,2,2,w,1,+w,2,1,w,1,-kw,2,=,-2,w,1,无约束,，,w,2,0,令,X,1,=,-X,1,max,z=2x,1,+,x,2,-,2x,3,s.t x,1,+x,2,+x,3,=,4,x,1,+x,2,-Kx,3,6,X,1,0,，,X,2,0, X,3,无约束,最优解,:,X,（,0,）,=,（,5,，,0,，,-1,）,T,6,写出目标等式和互补松紧条件,根据定理,4.2.5,，,X,（,0,）,=,（,-5,，,0,，,-1,）,T,Z*=,2x,1,+,x,2,-,2x,3,=,2,（,5,）,-0,-2,（,-1,）,=12, f*=Z*=,4w,1,+6w,2,=12,4.2.7,w,1,=,0,w,2,=,2,4.2.7,w,1,+w,2,=,2,7,求解,代入,w,1,-kw,2,=,-1,A,求得,K=1,8,4.4,对偶问题,min f=20w,1,+20w,2,s.t w,1,+2w,2,1,2w,1,+w,2,2,2w,1,+3w,2,3,3w,1,+2w,2,4,w,1,0,，w,2,0,max z=x,1,+2,x,2,+,3x,3,+,4,x,3,s.t x,1,+2x,2,+2x,3,+,3,x,4,20,2x,1,+x,2,+3x,3,+,2,x,4,20,X,1,，,X,2,X,3,0,无约束,9,续,W*,1,=1.2,0,W*,2,=0.2,0,由互补松弛条件可得,:,x,1,+2x,2,+2x,3,+3x,4,=,20 (,4.4.1),2x,1,+x,2,+3x,3,+2x,4,=,20,10,续,将,W*,1,=1.2,，,W*,2,=0.2,代入对偶问题的约束条件。,w,1,+2w,2,=,1.2+2,0.2=1.6,1,2w,1,+w,2,=,2,1.2,+0.2,=2.6,2,2w,1,+3w,2,=2,1.2,+3,0.2,=3,3w,1,+2w,2,=,3,1.2,+2,0.2,=4,11,由互补松弛条件定理可知,X*,1,=0,，,X*,2,=0,代入,(,4.4.1),得,x,1,+2x,2,+2x,3,+3x,4,=,20 (,4.4.1),2x,1,+x,2,+3x,3,+2x,4,=,20,解得,: x*,3,=,4,x*,4,=,4,原问题最优解,:,X,*,=,（,0,，,0,，,4,，,4,）,T,12,4.5,min z=8x,1,+6x,2,+3x,3,+6x,4,s.t x,1,+2x,2,+x,4,3,3x,1,+x,2,+x,3,+x,4,6,x,3,+x,4,2,3x,1,+x,3,2,X,j,0, j=1,2,3,4,最优解,:,X,（,0,）,=(1,，,1,，,2,，,0),T,13,化标准型,max z=-8x,1,-6x,2,-3x,3,-6x,4,s.t -x,1,-2x,2,-x,4,3,-3x,1,-x,2,-x,3,-x,4,6 (,4.5.1),-x,3,-x,4,2,-3x,1,-x,3,2,X,j,0, j=1,2,3,4,最优解,:,X,（,0,）,=,（,1,，,1,，,2,，,0,）,T,14,写,对偶问题,min f=3w,1,+6w,2,+2w,3,+2w,4,s.t -w,1,-3w,2,w,4,-8,-2w,1,-w,2,-6,-w,1,-w,3,w,4,-,3 (,4.5.2),-w,1,-w,2,-w,3,-,4,w,i,0 I=1,2,3,4,max z=-8x,1,-6x,2,-3x,3,-6x,4,s.t -x,1,-2x,2,-x,4,3,-3x,1,-x,2,-x,3,-x,4,6,4.5.1),-x,3,-x,4,2,-3x,1,-x,3,2,X,j,0, j=1,2,3,4,最优解,:,X,（,0,）,=,（,1,，,1,，,2,，,0,）,T,15,互补松弛条件,最优解,:,X,（,0,）,=,（,1,，,1,，,2,，,0,）,T,即,X,j,0, j=1,2,3,s.t -w,1,-3w,2,w,4,=,-8,-2w,1,-w,2,=,-6 (,4.5.3),-w,1,-w,3,w,4,=-,3,16,代原问题约束条件左端,X,（,0,）,=,（,1,，,1,，,2,，,0,）,T,x,1,+2x,2,+x,4,=1+2+0=3,3x,1,+x,2,+x,3,+x,4,=3+1+2+0=,6,x,3,+x,4,=2+0=,2,3x,1,+x,3,=1+2,2,互补松弛定理,w,4,=0,17,w,4,=0,代入,对偶问题约束条件,s.t -w,1,-3w,2,w,4,=,-8,-2w,1,-w,2,=,-6 (,4.5.3),-w,1,-w,3,w,4,=-,3,w,4,=0,解得,:,w,1,=2,w,2,=,2 w,3,=,1,对偶问题最优解,:,w,*,=,（,2,，,2,，,1,，,0,）,T,18,4.7,已知线性规划问题,max z=10x,1,+5x,2,s.t 3x,1,+4x,2,9,5x,1,+2x,2,8,x,1,x,2,0,化成,标准型,max z=10x,1,+5x,2,s.t 3x,1,+4x,2,+x,3,=,9,5x,1,+2x,2,+x,4,=,8,x,1,x,2,0,A,19,表4.7,10,5,0,0,C,B,X,B,b,x,1,x,2,x,3,x,4,5,x,2,3/2,0,1,5/14,-3/14,10,x,1,1,1,0,-1/7,2/7,-Z,-35/2,0,0,-5/14,-25/14,B,-1,20,(1),C,C+,C,(1)目标函数中的价值系数c,1,，c,2,分别在什么范围内变动时,上述最优解不变。,当,C,由,C,C+,C,时,新检验数,=,（,C+,C,）,-,（,C,B,+,C,B,）,B,-1,A,4.5.2,目标涵数,Z=,（,C,B,+,C,B,）,B,-1,b,4.5.3,若,0,时，最优解仍为最优解，目标值发生了变化。否则，重新迭代。,21,解,:,c,1,C,1,）,变量,=,C-,（,C,B,+,C,B,）,B,-1,A,变,=C- C,B,B,-1,A,=,（,C,1,，,5,，,0,，,0,）,-,（,5,，,C,1,）,B,-1,(P,1,，,P,2,，,P,3,，,P,4,),（,B,：,E,） （,E,：,B,-1,）,B,-1,=,5/14 -3/14,-1/7 2/7,B,C=,（,5,，,C,1,）,22,B*/B,（,5,，,C,1,）,4 3,2 5,B=,B,=4,5-3 2=14,B,11,B,21,B,12,B,22,B*= =,4 3,2 5,B,21,=（-1）,（1+2）,=,-3,5 -3,-2 4,5/14 -3/14,-1/7 2/7,B,-1,=,（5， C,1,）,23,P,（P,1,， P,2,， P,3,， P,4,）=,3 4 1 0,5 2 0 1,A,HV,24,代入,=,（,C,1,，,5,，,0,，,0,）,-,（,5,，,C,1,）,B,-1,(P,1,，,P,2,，,P,3,，,P,4,),=,（,C,1,，,5,，,0,，,0,）,-,（,5,，,C,1,）,5/14 -3/14,-1/7 2/7,3 4 1 0,5 2 0 1,=,（ C,1,，5，0，0）-C,1,，5，(25-2 C,1,)/14 ， (4 C,1,- 25)/14 ,25,每个分量小于,0,=,0,，,0,，,-(25-2 C,1,)/14,，,-(4 C,1,- 15)/14 ,-(25-2 C,1,)/14,0,C,1, 25/2,-(4 C,1,- 15)/14,0,C,1, 15/4,15/4 ,C,1, 25/2,26,B*/B,（,C,1,，,C,2,）,3 4,5 2,B=,B,=4,5-3 2=14,B,11,B,21,B,12,B,22,B*= =,3 4,5 2,B,21,=（-1）,（1+2）,=,-4,2 -4,-5 3,-1/7 2/7,5/14 -3/14,B,-1,=,27,代入,=,（,C,1,，,5,，,0,，,0,）,-,（,C,1,，,5,）,B,-1,（,P,1,，,P,2,，,P,3,，,P,4,）,=,（,C,1,，,5,，,0,，,0,）,-,（,C,1,，,5,）,-1/7 2/7 5/14 -3/14,3 4 1 0,5 2 0 1,=,（ C,1,，5，0，0）-C,1,，5，(25-2 C,1,)/14 ， (4 C,1,- 25)/14 ,28,矩阵乘法的性质,(AB)C=A(BC),(A+B)C=AC+BC,C(A+B)=CA+CB,K(AB)=(KA)B=A(KB),29,(2),约束右端项,b1,约束右端项,b,1,，,b,2,当一个不变时，另一个在什么范围变化时，原问题的最优解保持不变。,30,解：,当右端列向量,b,b+,b,改变第三列,X,B,=B,-1,b,X,B,=,B,-1,（,b+,b,）,-Z =-C,B,B,-1,b,-Z,=,-C,B,B,-1,（,b+,b,）,A,、,若,X,B,= B,-1,（,b+,b,）,0,因为没有变,则最优基不变，最优解为,X,B,和,Z,31,不大于,0,B,、,若,X,B,= B,-1,(,b+,b)0,因为,0,没有变，,X,B,= B,-1,（,b+,b,）,X,N,= 0,X,B,X,N,=,B,-1,(b+,b),0,正则解,32,b,2,不变,X,B,= B,-1,(,b+,b),=,5/14 -3/14,-1/7 2/7,b,1,8,=,0,（5 b,1,-24）/14,（16-,b,1,）/7,33,求解不等式,(5b,1,-24)/14,0,(16-,b,1,)/7 0,24/5 ,b,1,16,34,解法,2(1),解,:,（,1,）当其它值不变，,C,1,发生变化后最优单纯表变为如下,C,1,5,0,0,C,B,X,B,b,X,1,X,2,X,3,X,4,5,X,2,3/2,0,1,5/14,-3/14,C,1,X,1,1,1,0,-1/7,2/7,-Z,-35/2,0,0,-(25-2 C,1,)/14,-(4 C,1,- 15)/14,要保持最优解不变，所有检验数应,0,故：,-,（,25-2C,1,）,/14,0,，,C,1,25/2,；,-(,4 C,1,- 15)/14,0,，,C,1,15/4,所以,15/4,C,1,25/2,35,(2),b,1,0,3/2,1,5/14,-1/7,0,0,（,2,）由于,目标函数中其它参数不变，,b,1,变化不影响检验数，,如果变化后,X,B,0,那么最优基也不变。,B,-1,b+B,-1,= +,b,1,b,1,-21/5,， ,b,1,7,。,b,1,+,b,1,24/5,，,b,1,+ ,b,1,16,。,b,1,的范围是,-21/5,，,7,，即,b,1,的范围是,24/5,，,16,。,36,（,3,）,目标函数,目标函数变为,max z=12x,1,+4x,2,时，最优解如何变化？,根本是,c,1,，,c,2,同时变化,37,解,.,基变量,=,C-,（,C,B,+,C,B,）,B,-1,A,变,=C- C,B,B,-1,A,=,（,C,1,，,C,2,，,0,，,0,）,-,（,C,2,，,C,1,）,B,-1,（,P,1,，,P,2,，,P,3,，,P,4,）,（,B,：,E,） （,E,：,B,-1,）,B,-1,=,5/14 -3/14,-1/7 2/7,38,P,（,P,1,，,P,2,，,P,3,，,P,4,）,3 4 1 0,5 2 0 1,39,代入,=,（,C,1,，,C,2,，,0,，,0,）,-,（,C,2,，,C,1,）,B,-1,（,P,1,，,P,2,，,P,3,，,P,4,）,=,（,C,1,，,C,2,，,0,，,0,）,-,（,C,2,，,C,1,）,5/14 -3/14,-1/7 2/7,3 4 1 0,5 2 0 1,=,（,C,1,，,C,2,，,0,，,0,）,-C,1,，,C,2,，,(5,C,2,-2 C,1,)/14,，,(4 C,1,- 3,C,2,)/14 ,40,每个分量,=,0 ，0，-(5,C,2,-2 C,1,)/14 ， -(4 C,1,- 3,C,2,)/14 ,=（0，0，,2/7,，-18/7）,41,表4.7.1,10,5,0,0,C,B,X,B,b,x,1,x,2,x,3,x,4,4,x,2,3/2,0,1,5/14,-3/14,12,x,1,1,1,0,-1/7,2/7,-Z,-35/2,0,0,2/7,-18/7,42,表4.7.2,12,4,0,0,C,B,X,B,b,x,1,x,2,x,3,x,4,4,x,2,21/5,0,14/5,1,-3/5,12,x,1,1,1,0,-1/7,2/7,-Z,-35/2,0,0,2/7,-18/7,43,表4.7.2,12,4,0,0,C,B,X,B,b,x,1,x,2,x,3,x,4,0,x,3,21/5,0,14/5,1,-3/5,12,x,1,8/5,1,2/5,0,1/5,-Z,-96/5,0,-4/5,0,-18/7,最优解,:,X,=,（,8/5,，,0,，,21/5,，,0,）,T,44,(4),右端项,约束右端项由,变为,最优解为多少,?,9,8,11,19,45,X,B,X,B,= B,-1,（b+,b）,=,5/14 -3/14,-1/7 2/7,11,19,-1/7,27/7,=,46,B,-1,5/14 -3/14,-1/7 2/7,B,-1,=,47,表4.7 . 41,10,5,0,0,C,B,X,B,b,x,1,x,2,x,3,x,4,5,x,2,-1/7,0,1,5/14,-3/14,10,x,1,27/7,1,0,-1/7,2/7,-Z,-265/7,0,0,-5/14,-25/14,48,表4.7 . 42,10,5,0,0,C,B,X,B,b,x,1,x,2,x,3,x,4,5,x,2,-1/7,0,1,5/14,-3/14,10,x,1,27/7,1,0,-1/7,2/7,-Z,-265/7,0,0,-5/14,-25/14,j,/a,rj,25/3,49,表4.7 . 43,10,5,0,0,C,B,X,B,b,x,1,x,2,x,3,x,4,5,x,2,2/3,0,-14/3,-5/3,1,10,x,1,27/7,1,0,-1/7,2/7,-Z,-265/7,0,0,-5/14,-25/14,j,/a,rj,25/3,50,表4.7 . 43,10,5,0,0,C,B,X,B,b,x,1,x,2,x,3,x,4,0,x,4,2/3,0,-14/3,-5/3,1,10,x,1,11/3,1,4/3,1/3,0,-Z,-110/3,0,-25/3,-10/3,0,j,/a,rj,25/3,最优解,:,X,=,（,11/3,，,0,，,0,，,2/3,）,T,51,4.6,题,其中,X,2,变为,X,2,500,。,即某一个约束的右端项变化为,350-500,b,=,B,-1,（,b+,b,）,=,1 0 -2,-3 1 5,0 0 1,800,900,500,-200,1000,500,=,Z,=C,B,B,-1,b,=（3，0，8）,-200,1000,500,=3400,52,4.6(1),用,b,，,Z,最终单纯形表可得：,C,3,8,0,0,0,C,B,X,B,b,-,x,1,x,2,x,3,x,4,x,5,3,x,1,-200,1,0,1,0,-2,0,x,4,1000,0,0,-3,1,5,8,x,2,500,0,1,0,0,1,-Z,-3400,0,0,-3,0,-2,53,4.6(11）,C,3,8,0,0,0,C,B,X,B,b,-,x,1,x,2,x,3,x,4,x,5,3,x,1,-200,1,0,1,0,-2,0,x,4,1000,0,0,-3,1,5,8,x,2,500,0,1,0,0,1,-Z,-3400,0,0,-3,0,-2,j,/a ,rj,1,主行乘,-1/2,得,54,4.6(12）,C,3,8,0,0,0,C,B,X,B,b,-,x,1,x,2,x,3,x,4,x,5,3,x,1,100,-1/2,0,-1/2,0,1,0,x,4,1000,0,0,-3,1,5,8,x,2,500,0,1,0,0,1,-Z,-3400,0,0,-3,0,-2,j,/a ,rj,1,主行,分别乘,-5,加到第二行，乘,-1,加到第三行，把,x,1,换成,x,5,，,系数,3,变成,0,。,。,55,4.6(2),用,对偶,单纯形法可得：,C,3,8,0,0,0,C,B,X,B,b,-,x,1,x,2,x,3,x,4,x,5,0,x,5,100,-1/2,0,-1/2,0,1,0,x,4,500,5/2,0,-1/2,1,0,8,x,2,400,1/2,1,1/2,0,0,-Z,-3200,-1,0,-4,0,0,最优解,：,X,B,=,（,0,，,400,，,0,，,500,，,100,）,T,，,Z,=3200,56,