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

2、画出下列线性规划问题的图解法可行域。

maxz5x12x2

4x1 x2 20 xx 10 12s.t. 

x1x2 2x10, x20

解：

1

3、将下面的线性规划问题写成标准化形式。

maxzx1x22x3

2x1 x25x312 x2x7x6

123

s.t. 

 x1 6x34x10, x20, x30

解：

maxzx1'x22x3

2x1' x25x3y1 12 x'2x7x 6

123

s.t. 

 x1' 6x3 y24x1'0, x20, x30, y10, y20

4、写出下列线性规划问题的对偶问题。

maxzx1x22x32x1 x25x312 x2x7x6

123

s.t. 

 x1 6x34x10, x20, x30

解：

minw12y16y24y32y1 y2 y3 1 y2y 1

12

s.t. 

5y17y26y32y10, y2任意, y30

5、简述单纯形法和对偶单纯形的异同点，填入下表。 答：

相同点： 都含一个单位子矩阵，都要进行换基迭代，都用于求解线性规划问题的原问题。 不同点：

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..tx12x2 6x,x,x0123

解：

参考步骤：

得最优解x*=(0,3,1)，最优值z*=7。

三、计算题（共20分）

使用对偶单纯形法求解下列线性规划问题，写出求解步骤，并给出：（1

）最优解，（2）最优值。

max z

6x13x24x3

3x12x2 x34



s.t.4x1

x24x312 x,x,x0123

解：

先引入2个人工变量，构造单位子矩阵：

max z6x13x24x3

3x12x2 x3x4 4



s.t.4x1 x24x3 +x512 x,x,x,x,x012345

初始单纯形表：

因为(-4)/(-4)=min{(-6)/(-4), (-4)/(-4)}，x3进基，x5出基：

因为(-2)/(-2)=min{(-2)/(-2), (-4)/(-9/4), (-1)/(-1/4)}，x

进基，x出基：

得最优解(x1, x2, x3)=(1/2, 0, 5/2)，最优值z*=-13。

2、画出下列线性规划问题的图解法可行域。

maxz5x12x2

4x1 x2 20 xx 10 12s.t. 

x1x2 2x10, x20

解：

1

3、将下面的线性规划问题写成标准化形式。

maxzx1x22x3

2x1 x25x312 x2x7x6

123

s.t. 

 x1 6x34x10, x20, x30

解：

maxzx1'x22x3

2x1' x25x3y1 12 x'2x7x 6

123

s.t. 

 x1' 6x3 y24x1'0, x20, x30, y10, y20

4、写出下列线性规划问题的对偶问题。

maxzx1x22x32x1 x25x312 x2x7x6

123

s.t. 

 x1 6x34x10, x20, x30

解：

minw12y16y24y32y1 y2 y3 1 y2y 1

12

s.t. 

5y17y26y32y10, y2任意, y30

5、简述单纯形法和对偶单纯形的异同点，填入下表。 答：

相同点： 都含一个单位子矩阵，都要进行换基迭代，都用于求解线性规划问题的原问题。 不同点：

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..tx12x2 6x,x,x0123

解：

参考步骤：

得最优解x*=(0,3,1)，最优值z*=7。

三、计算题（共20分）

使用对偶单纯形法求解下列线性规划问题，写出求解步骤，并给出：（1

）最优解，（2）最优值。

max z

6x13x24x3

3x12x2 x34



s.t.4x1

x24x312 x,x,x0123

解：

先引入2个人工变量，构造单位子矩阵：

max z6x13x24x3

3x12x2 x3x4 4



s.t.4x1 x24x3 +x512 x,x,x,x,x012345

初始单纯形表：

因为(-4)/(-4)=min{(-6)/(-4), (-4)/(-4)}，x3进基，x5出基：

因为(-2)/(-2)=min{(-2)/(-2), (-4)/(-9/4), (-1)/(-1/4)}，x

进基，x出基：

得最优解(x1, x2, x3)=(1/2, 0, 5/2)，最优值z*=-13。