运筹学2010-2011期中考试A卷答案

运筹学期中考试卷答案一．写出下列线性规划问题的对偶问题1、max321342xxxz08023402260243321321321321xxxxxxxxxxxxst,,解：min321804060yyy0,,3222434223321321321321yyyyyyyyyyyyst2、min32122xxxz无约束3213213210064xxxxxxxxxst,,解：max2164yyz021221212121yyyyyyyyst无约束、二．简单计算题1、下表为某求极大值线性规划问题的初始单纯形表及迭代后的表，54xx,为松弛变量，求表中a～l值及各变量下标m～t的值。XBbix1x2x3x4x5Xm6bcd10Xn1-13e01cj-zja1-200Xsfg2-11/20Xt4hi11/21cj-zj07jkl解：因为需要两个基变量，根据出示单纯形表和第二个单纯形表得出m=4，n=5，g=1，h=0，l=0进而推出s=1，t=5；根据第一个单纯形表到第二个单纯形表变换，得出1+6/b=4，进而b=2，而6/b=f，从而f=3；c/b=2，从而c=4；d/b=-1，从而d=-2；e+d/b=1，从而e=2；同理i=3+c/b，从而i=5；a、2、-1分别为x1、x2、x3的价格系数（根据初始单纯形表的特点），再根据第二个单纯形表，得1-2a=7，得出a=-3，同理得出0-1/2a=k，求得k=3/2；同理j=-2-（-1）*a=-5即：a=-3，b=2，c=4，d=-2，e=2，f=3，g=1，h=0，i=5，j=-5，k=3/2，l=0，m=4，n=5，s=1，t=5。2、已知线性规划问题：3212xx2xmin无约束3213213210064xxxxxxxxxst,,其最优解为1x0x5x321,,，试写出其对偶问题的最优解。解：设对偶变量为21yy,，写出对偶问题216y4yzmax0yy2yy1yy2yy21212121,无约束st根据强对偶性质，有121920526y4y21）)(；在根据松弛互补原理，由于最优解中5x1不等于零，因此对应对偶问题的约束条件取严格等号，即2y-y-21。联立两个方程可以求出21yy,：2y0y126y4y2yy212121,三．计算题）1、采用隐枚举法求解0-1规划问题。maxZ=31x–22x+53xx1+2x2–x3≤2(a)x1+4x2+3x≤4(b)x1+x2≤3(c)4x2+x3≤6(d)x1,x2,x3=0或1解：求解过程见下表：(x1,x2,x3)Z值约束条件过滤条件abcd（0,0,0）0√√√√z≥0（0,0,1）5√√√√z≥5（0,1,0）-2（0,1,1）3（1,0,0）3（1,0,1）8√√√√z≥8（1,1,0）1（1,1,1）6所以，最优解（x1,x2,x3）=(1,0,1)，z=82、考虑以下线性规划问题MaxZ(x)=2x1-x2+x3S.t.x1+x2+x3≤6-x1+2x2≤4x1，x2，x3≥0最终单纯形表为：Cj2-1100CBXBbX1X2X3X4X52X16111100X51003111Σj0-3-1-201）写出此线性规划的最优解、最优基B和它的逆B-1；2）求此线性规划的对偶问题的最优解；3）试求c2由-1变为2时，此线性规划的最优解；4）若b1=6变为4，最优解及最优值是什么？解：1)x*=(6,0,0,0,10)TB和B-1分别为2)y*=(2,0)T3)c2由-1变为2时，则x2的检验数等于0，因所有的检验数均小于等于0，所以原解仍是最优解。x*=(6,0,0,0,10)T4)b´=B-1b=84441101由于检验数没变，而且b值均大于0，故最优基不变，最优解为：x*=(4，0,0，0,8)Tz*=83、分析λ≥0时最优解的变化。Maxz=2x1+x2s.t.5x2≤156x1+2x2≤24+4λx1+x2≤5+λx1,x2≥0λ=0时，最优单纯形表为：Cj23000CBXBbX1X2X3X4X50X315/20015/4-15/22X17/21001/4-1/21X23/2010-1/43/2σj000-1/4-1/2解：⊿b´=B⊿b=5215/415/20101/41/24201/43/212最终单纯形表变为：Cj21000CBXBbX1X2X3X4X50X315/2-5/2λ0015/4-15/22X17/2+1/2λ1001/4-1/21X23/2+1/2λ010-1/43/2σj000-1/4-1/22/32/172/12/322/12/7130002/12/302/12/702/52/15zxx最优解为：当λ≥3时，15/2-5/2λ≤0，此时原问题不是可行解，用对偶单纯形法继续迭代：j21000CBXBbX1X2X3X4X50X315/2-5/2λ0015/4-15/22X17/2+1/2λ1001/4-1/21X23/2+1/2λ010-1/43/2σj000-1/4-1/20X5-1+1/3λ00-2/15-1/612X13+2/3λ10-1/151/601X23011/500σj00-1/15-1/30结果表明，当λ≥3时，b全部大于0，非基变量的检验数均小于0，最优基不再变化，此时最优解为：3/49323/231zxx