运筹学期末复习资料

1、1.用两阶段法求解线性规划问题 （1）max z=-2-+-+2-=2 2+-3+=6+=7，,02.下表是某求极大化线性规划问题计算得到的单纯形表。表中无人工变量，d，为待定常数，试说明这些常数分别取何值时，以下结论成立。（1）表中解为唯一最优解；（2）表中解为最优解，但存在无穷多最优解；（3）该线性规划问题具有无界解；（4）表中解非最优，对解改进，换入变量为，换出变量为。基b d4100 2-1-301-10 3-500-4100-30解：（1）有唯一最优解时，d0，0，0（2）存在无穷多最优解时，d0，0，=0或d0，=0，0.（3）有无界解时，d0，0，0且（4）此时，有d0，0并且，

2、3/d/43.已知线性规划问题 应用对偶理论证明该问题最优解的目标函数值不大于25.4.用对偶单纯形法求解下列线性规划问题：cj3 2 1 0 0 0CB xB bx1 x2 x3 x4 x5 x60 x4 60 x5 40 x6 41 1 1 1 0 01 0 1 0 1 00 1 1 0 0 1cjzj 3 2 1 0 0 00 x4 23 x1 40 x6 40 1 2 1 1 01 0 1 0 1 0 0 1 1 0 0 0cjzj0 2 4 0 3 00 x4 23 x1 42 x2 40 0 3 1 1 11 0 1 0 1 00 1 1 0 0 1cjzj0 0 7 0 3 2x

3、4为2，无法迭代，此题无解。5.已知线性规划问题 maxZ=2x1+x2+5x3+6x4其对偶问题的最优解为Yl=4，Y2=1，试应用对偶问题的性质求原问题的最优解。解：原问题的对偶问题为min w=8y1+12y2s·t 2y2+2y22 2y21y1+y25y1+2y26y1 ，y20把y=4,y=1代入上式，可知头两个约束为严格不算式，则X=0, X=0，可得 X3+X4=8 解得： X=4 X3+2X4=12 X=4则原问题最优解为X*=（0，0，4，4）T，Z*=446.MaxZ=3X1+4X2X1+X252X1+4X2123X1+2X28X1,X20其最优解为： 基变量X

4、1X2X3X4X5X33/2001-1/8-1/4X25/20103/8-1/4X11100-1/41/2j000-3/4-1/21） 写出该线性规划的对偶问题。2） 若C2从4变成5，最优解是否会发生改变，为什么？3） 若b2的量从12上升到15，最优解是否会发生变化，为什么？解：1)对偶问题为Minw=5y1+12y2+8y3 y1+2y2+3y33y1+4y2+2y34 y1,y202)当C2从4变成5时，4=-9/85=-1/4由于非基变量的检验数仍然都是小于0的，所以最优解不变。3）当若b2的量从12上升到15X 9/8 29/8 1/4由于基变量的值仍然都是大于0的，所以最优解的基变量不会发生变化。7.给出线性规划问题 用单纯形表求解得单纯形表如下，试分析下列各种条件变化下最优解（基）的变化： xl x2 x3 x4 x5 xB -Z -8 0 0 -3 -5 -1 xl x2 1 2 1 0 -1 4 -1 0 1 2 -1 1(1) 分别确定目标函数中变量X1和X2的系数c1，c2在什么范围内变动时最优解不变；(2) 目标函数中变量X3的系数变为6； （3）增添新的约束X1+2x