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

运筹学期中考试卷答案一 写出下列线性规划问题的对偶问题1、 解： 2、 解： 二 简单计算题1、下表为某求极大值线性规划问题的初始单纯形表及迭代后的表，为松弛变量，求表中al值及各变量下标mt的值。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、已知线性规划问题： 其最优解为，试写出其对偶问题的最优解。解：设对偶变量为，写出对偶问题根据强对偶性质，有； 在根据松弛互补原理，由于最优解中不等于零，因此对应对偶问题的约束条件取严格等号，即。联立两个方程可以求出：三 计算题）1、采用隐枚举法求解0-1规划问题。max Z=32+5x1+2x2x32 (a)x1+4x2+4 (b)x1+x2 3 (c) 4x2 + x36 (d)x1,x2,x3 = 0或1解：求解过程见下表：(x1,x2,x3)Z值约束条件过滤条件abcd（0,0,0）0z0（0,0,1）5z5（0,1,0）-2（0,1,1）3（1,0,0）3（1,0,1）8z8（1,1,0）1（1,1,1）6所以，最优解（x1,x2,x3）=(1,0,1)，z=82、考虑以下线性规划问题Max Z(x) = 2x1 - x2 + x3 S.t. x1 + x2 + x3 6-x1 + 2x2 4x1 ，x2 ，x3 0最终单纯形表为：Cj2-1100CBXBbX1X2X3X4X52X16111100X51003111j0-3-1-201）写出此线性规划的最优解、最优基 B 和它的逆 B-1 ；2）求此线性规划的对偶问题的最优解；3）试求 c2 由 -1 变为 2 时，此线性规划的最优解；4）若 b1 = 6 变为 4，最优解及最优值是什么？解：1) x* = (6,0,0,0,10)T B和B-1分别为2) y* = (2, 0)T3) c2 由 -1 变为 2 时，则x2的检验数等于0，因所有的检验数均小于等于0，所以原解仍是最优解。x* = (6,0,0,0,10)T4) b=B-1b=由于检验数没变，而且b值均大于0，故最优基不变，最优解为：x* = (4，0, 0，0, 8)T z* = 83、分析0时最优解的变化。 Max z = 2x1 + x2 s.t. 5x215 6x1+2x224+4 x1+x2 5+ x1,x20=0时，最优单纯形表为：Cj23000CBXBbX1X2X3X4X50X315/20015/4-15/22X17/21001/4-1/21X23/2010-1/43/2j000-1/4-1/2解：b=Bb=最终单纯形表变为：Cj21000CBXBbX1X2X3X4X50X315/2-5/20015/4-15/22X17/2+1/21001/4-1/21X23/2+1/2010-1/43/2j000-1/4-1/2当3时，15/2-5/20，此时原问题不是可行解，用对偶单纯形法继续迭代：j21000CBXBbX1X2X3X4X50X315/2-5/20015/4-15/22X17/2+1/21001/4-1/21X23/2+1/2010-1/43/2j000-1/4-1/20X5-1+1/300-2/15-1/