[运筹学]期中考试卷答案.doc

[运筹学]期中考试卷答案2、画出下列线性规划问题的图解法可行域。maxz=5x1-2x2ì4x1-x2£20ïx+x£10ï.íï-x1+x2£2ïîx1³0,x2³0解:13、将下面的线性规划问题写成标准化形式。maxz=x1+x2+2x3ì2x1+x2+5x3£12ïx+2x+7x=6ï.íïx1+6x3³4ïîx1£0,x2³0,x3³0解:maxz=-x1’+x2+2x3ì-2x1’+x2+5x3+y1=12ï-x’+2x+7x=6ï.íï-x1’+6x3-y2=4ïîx1’³0,x2³0,x3³0,y1³0,y2³04、写出下列线性规划问题的对偶问题。maxz=x1+x2+2x3ì2x1+x2+5x3£12ïx+2x+7x=6ï.íïx1+6x3³4ïîx1£0,x2³0,x3³0解:minw=12y1+6y2+4y3ì2y1+y2+y3£1ïy+2y³1ï.íï5y1+7y2+6y3³2ïîy1³0,y2任意,y3£05、简述单纯形法和对偶单纯形的异同点,填入下表。答:相同点:都含一个单位子矩阵,都要进行换基迭代,都用于求解线性规划问题的原问题。不同点:6、下面命题是否正确?解释理由。(1)线性规划问题的可行解如为最优解,则该可行解一定为基可行解。(2)单纯形法迭代计算中,必须选取同最大正检验数σj对应的变量作为入基变量。(3)线性规划问题增加一个约束条件,可行域的范围一般将缩小;减少一个约束条件,可行域的范围一般将扩大。(4)如果线性规划问题的对偶问题无可行解,则原问题也一定无可行解。(5)如果X1,X2都是某个线性规划问题的最优解,则X=λ1X1+λ2X1(λ1,λ2是正实数)也是这个问题的最优解。答:(1)不正确。在存在多个最优基解的情况下,它们的凸组合不是基解,但仍为最优解。(2)不正确。只需选取正检验数σj对应的变量入基,都可以使目标值增大。(3)正确。增加约束的可行域是原可行域的子集。(4)不正确。此时原问题还可能有无界解。(5)不正确。X1,X2的凸组合才是最优解。二、计算题(共20分)使用单纯形法求解下列线性规划问题,写出求解步骤,并给出:(1)最优解,(2)最优值。maxz=-x1+2x2+x3ì2x1+x2+x3£4ïs.