福州市教育局网-学党章心得体会

温州大学期中考试试卷

2015-2016 学年第 一 学期
考试科目
运筹学B
试卷类型


总分
学
院
-
-
-
-
-
-
--
-
-
-
-
-
-
-
-
--
-
-
-
-
-
-
-
-
--
-
-
-
-
-
-
-
-
--




班
级
-
-
--
-
-
-
-
-
-
-
-
--
-
-
-
-
-
-
-
-
--
-
-
-
-
-
-
-
-
--





姓
名
-
--
-
-
-
-
-
-
-
-
--
-
-
-
-
-
-
-
-
--
-
-
-
-
-
-
-
-
--
-
-
-
-



学
号-
-
-
-
-
-
-
-
-
--
-
-
-
-
-
-
-
-
--
-
-
-
-
-
-
-
-
--
-
-
-
-
-
-

考试形式
题号
得分
开卷（仅允许带教材）
考试对象
一

60
二

20
三

20





一、简答题（每小题10分，共60分）
1、
某企业在今后三年内有4种投资机会。第①种：三年内每年年初投
得分
资，年底可获利润20%，并将本金收回；第②种：第一年年初投资，第二
年年底可获利润50%，并 将本金收回，但该项目投资不得超过万元；第③种：第二年年初
投资，第三年年底收回本金，并获利润6 0%，但该项目投资不得超过万元；第④种：第三
年年初投资，于该年年底收回本金，且获利40%，但 该项目投资不得超过万元。现在该企
业准备拿出万元资金，问如何制定投资计划，使到第三年年末本利和 最大。为此，设x
ij
为第i年投资到第j个方案的资金，共6个决策变量。分析投资情况见下 表。

年份 第一年初
①x
11
出
投
资
额


②x
12
出


第一年底
（第二年初）
入
①x
21
出


③x
23
出

第二年底
（第三年初）

入
①x
31
出
入

④x
34
出
第三年底


入

入
入
试根据上述决策变量和投资分析表写出该问题的线性规划模型。
解：
max z1.6x
23
1.2x
31
1.4x
34
(or 0.2x
11
0.2x
21
0.2x
31
0.5x< br>12
0.6x
23
0.4x
34
)

x
11
x
12
3


x
12
 2

x
21
x
23
1.2x
11
(or x
11
x
12
x
21
x
23
31.2x
11
)

s.t.

x
231.5

xx1.5x1.2x
1221

3134< br>
x
34
1


x
11
0,x
12
0,x
21
0,x
23
0,x
310,x
34
0


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

maxz5x
12x
2

4x
1
x
2
20

xx 10


s.t.

12

x
1
x
2
2


x
1
0, x
2
0
解： < br>x
2
6
5
4
2
0
456
x
1



3、将下面的线性规划问题写成标准化形式。
maxz x
1
x
2
2x
3

2x
1
 x
2
5x
3
12

x2x7x6


123
s.t.


x
1
6x
3
4


x
1
0, x
2
0, x
3
0
解：
maxzx
1< br>'x
2
2x
3

2x
1
' x
2
5x
3
y
1
12

x'2x7x 6


123
s.t.


x
1
' 6x
3
y
2
4


x
1
'0, x
2
0, x
3
0, y
1
0, y
2
0


4、写出下列线性规划问题的对偶问题。
m axzx
1
x
2
2x
3

2x
1< br> x
2
5x
3
12

x2x7x6


123
s.t.


x
1
6x
3
4


x
1
0, x
2
0, x
3
0
解：

minw1 2y
1
6y
2
4y
3

2y
1
 y
2
y
3
1

y2y 1


12
s.t.


5y
17y
2
6y
3
2


y
10, y
2
任意, y
3
0


5、简述单纯形法和对偶单纯形的异同点，填入下表。
答：
相同点： 都含一个单位子矩阵，都要进行换基迭代，都用于求解线性规划问题的原问题。
不同点：

初始状态 常数列非负
算法结束
检验数全非正，结束计算
判断准则
换基方法
检验数正者，入基，按照与常数列的
最小比例选择出基变量
单纯形法 对偶单纯形法
检验数非正
常数列全非负，结束计算
常数列负者，出基，按照与检验
数的最小比例选择入基变量


6、下面命题是否正确解释理由。
（1）线性规划问题的可行解如为最优解，则该可行解一定为基可行解。
（2）单纯形法迭代计算中，必须选取同最大正检验数σ
j
对应的变量作为入基变量。
（3）线性规划问题增加一个约束条件，可行域的范围一般将缩小；减少一个约束条件，
可行域 的范围一般将扩大。
（4）如果线性规划问题的对偶问题无可行解，则原问题也一定无可行解。 （5）如果X
1
，X
2
都是某个线性规划问题的最优解，则X=λ
1
X
1
+λ
2
X
1
（λ
1
，λ
2
是正实数）也
是这个问题的最优解。
答：
（1）不正确。在存在多个最优基解的情况下，它们的凸组合不是基解，但仍为最优解。
（2）不正确。只需选取正检验数σ
j
对应的变量入基，都可以使目标值增大。
（3）正确。增加约束的可行域是原可行域的子集。
（4）不正确。此时原问题还可能有无界解。
（5）不正确。X
1
，X
2
的凸组合才是最优解。

二、计算题（共20分）
使用单纯形法求解下列线性规划问题，写出求解步骤，并给出：（1）最优
得分
解，（2）最优值。
maxzx
1
2x
2
x
3

< br>2x
1
x
2
x
3
4
s..t


x

1
2x
2
6


x
1
,x
2
,x
3
0
解：
参考步骤：
c
B

基
b x
1
x
2
x
3
x
4
x
5

0 x
4
4 2 1 1 1 0
0 x
5
6 1 2 0 0 1
j

-1 2 1 0 0
0 x
4
1 32 0 1 1 -12
2 x
2
3 12 1 0 0 12
j

-2 0 1 0 -1
1 x
3
1 32 0 1 1 -12
2 x
2
3 12 1 0 0 12
j

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

三、计算题（共20分）
使用对偶单纯形法求解下列线性规划问题，写出求解步骤，并给出： （1）
最优解，（2）最优值。
max z6x
1
3x
2< br>4x
3

3x
1
2x
2
 x
3
4
s.t.


4xx


1

2
4x
3
12

x
1
,x
2
,x
3
0
解：
先引入2个人工变量，构造单位子矩阵：
max z6x
1
3x2
4x
3

3x
1
2x
2
 x
3
x
4
4
s.t.


4x +x


1
 x
2
4x
3

5
12

x
1
,x
2
,x
3
,x
4
,x
5
0
初始单纯形表：
c
B

基
b x
1
x
2
x
3
x
4
x
5

0 x
4
-4 -3 -2 -1 1 0
0 x
5
-12 -4 1 [ -4 ] 0 1

-6 -3 -4 0 0
因为(-4)(-4)=min{(-6)(-4), (-4)(-4)}，x
3
进基，x
5
出基：
c
B

基
b x
1
x
2
x
3
x
4
x
5

得分

0
-4
x
4

x
3

-1
3
[ -2 ]
1
-94
-14
0
1
1
0
-14
-14
-1
x
5

18
-38
-34
-2 -4 0 0

因为(-2)(-2)=min{(-2)(-2), (-4)(-94), (-1)(-14)}，x
1
进基，x
4
出基：
c
B
b x
1
x
2
x
3
x
4

基
-6
-4
x
1

x
3

12
52
1
0
98
-118
0
1
0
-12
12
-1 0 -74

得最优解(x
1
, x
2
, x
3
)=(12, 0, 52)，最优值z*=-13。