运筹学期末考试试卷(AB)卷复习课程.doc

运筹学期末考试试卷(AB)卷

精品文档
福建农林大学考试试卷 （ A ）卷
学年 第 学期
课程名称： 运 筹 学 考试时间 120分钟
专业 年级 班 学号 姓名
题号
一
二
三
四
五
六
七
八
九
总得分
得分

评卷人签字

复核人签字

得分
一、填空题（每空2分，共10分）

1. 目标规划模型中，对目标约束，求最大的目标函数为。
2. 增广链上的调整量 大于 零。
3. 用Dijkstra算法求解最短路问题时，距离矩阵的元素必须满足 非负要求 。
4. 线性规划的退化基本解的非零分量 至多m 个。
5. 树是 无圈 的连通图。

得分
二、单项选择题（选择正确答案的字母填入空格，每小题2分，共10分）

1. 线性规划的基本解中，非基变量取 C 值。
A．零 B．非零
C．非负 D．非正
2.增广链是在 B 下定义的。
A．零流 B．可行流
C．不可行流 D．非零流
3. 在约束为的线性规划中, ，则基的最小数目为 D 。
A． B．0
C．m D．1
4. 互为对偶的两个线性规划问题，如果其中一个无有限最优解，则另外一个 A 。
A．无可行解 B．有可行解
C．有最优解 D．无有限最优解
5. 如果目标规划问题（OP）没有满意解，则 A 。
A．（OP）无可行解 B．（OP）有可行解
C．（OP）有无穷多最优解 D．（OP）可能有可行解

得分
四、问答题（每小题5分，共20分）

1. 对偶单纯形法的求解要点。
⑴建立初始规范型（检验数非正，有负的限定常数），转⑵。
⑵解的检验：出现无可行解特征，停止；限定常数非负，转单纯型法；其他转⑶。
⑶进行基变换，转⑵。
2.最大流算法中流量调整量的确定。
设为可行流，在f下进行标号，如果无法给vt标上号，为最大流，无需确定流量调整量，否则。
3.网络计划中时差的计算。
可以据下图计算：

ESij
EFij

LSij
LFij(Lj)
TFij
FFij
Ej

4. 最短路问题的基础数据与求解内容。
距离矩阵；最短路线，最短路长。
得分
五、（第一小题2分，第二小题5分，第三小题3分，共10分）

对：要求：
1. 写出；
2. 用单纯形法或对偶单纯形法确定或的最优解；
3. 从或的最终表出发，据对偶理论直接确定或的解。
：
解：1. ：

2. 选择⑴用单纯形法或确定的最优解；

cj
2 1 0 0
θ
cB
xB
b
x1 x2 x3 x4
0
0
x3
x4
10
15
1 1 0
0 1 0 1
10/1
-
-z
0
2 1 0 0

cj
2 1 0 0
θ
cB
xB
b
x1 x2 x3 x4
2
0
x1
x4
10
15
1 1 0
0 1 0 1

-z
-20
0 -1 -2 0

。
选择⑵用对偶单纯形法确定的最优解；

cj
-10 -15 0 0
cB
xB
b
y1 y2 y3 y4
0
0
y3
y4
-2
-1
-1 0 1 0
-1 -1 0 1
w
0
-10 -15 0 0
θ
- - -

cj
-10 -15 0 0
cB
xB
b
y1 y2 y3 y4
-10
0
y1
y4
2
1
1 0 -1 0
0 -1 -1 1
w
20
0 -15 -10 0

得分
六、对图1，求网络图的最大流。（共10分）

vs
vt
v1
v2
v3
(4,0)
(6,0)
(3,0)
(8,0)
(3,0)
(5,0)
(8,0)
(cij,fij)
图1

解：⑴ 取，用标号法确定如图2所示,由图2知，
，见图3。

⑵用标号法确定如图3所示,由图3知，
，见图4。
⑶用标号法确定如图4所示,由图4知，
不存在，故。

vs
vt
v1
v2
v3
(0,4)
(0,6)
(0,3)
(0,8)
(0,3)
(0,5)
(0,8)

图2
(-,+∞)
(vs,6)
,5)
(v1,6)
,5)
(v3,6)
,5)

vs
vt
v1
v2
v3
(0,4)
(6,6)
(0,3)
(6,8)
(0,3)
(0,5)
(6,8)

图3
(-,+∞)
(vs,4)
,5)
(v2,4)
,5)

vs
vt
v1
v2
v3
(4,4)
(6,6)
(0,3)
(6,8)
(0,3)
(4,5)
(6,8)

图4
(-,+∞)

得分
七、对表1，用动态规划方法确定最优策略（共10分）

考虑一辆汽车三年的设备更新策略，开始时现有汽车的机龄为2年，取＝1，其余
有关数据见表1。试制定三年中的设备更新策略，使三年内的净收入最大。
表1
年代
期 前
第一年
第二年
第三年
阶 段
1 2 3
1 2 3
2 3
3
机 龄
2 3 4
0 1 2
0 1
0
收 入
20 18 18
22 21 20
27 25
29
运行费用
10 10 11
6 6 8
5 6
5
更新费用
38 38 40
30 32 37
31 35
33

解：模型假设略。

3
4*
18-11＋0
29－5-40＋0
7
K*
2
20－8＋0
29－5－37+0
12
K
1
25－6＋0
29－5－35+0
19
K
2
3*
18－10＋7
27－5－38+19
15
K*
1
21－6＋12
27－5－32+19
27
K
1
2*
20－10+15
22-6－38+27
25
K*

得分
八、（10分）表2是某厂原材料和产品规格的基础数据，要求建立一个线性规划模

型，以确定净收入最大的产品方案。（不求解）
表2

产品规格要求
原料成本
单价（元/kg）
可用量
（kg）
甲 乙 丙
原
材
料
A
B
C
≥80％ ≥50％

≤20％ ≤60％ ≤50％
3．00
2．00
1．00
2000
2500
1500
加工费（元/kg）
0.50 0.40 0.30

售价（元/kg）
3.40 2.85 2.25

模型略，具体可参考P38例11。

得分
九、视图1的问题中为aij的长度，要求用Dijkstra算法确定vs到vt的最短路。

（共10分）
解1：用标号法：

vs
vt
v1
v2
v3
8
12
3
14
3
9
14

图5

最短路线，最短路长17。
解2：列表求解：
i j
s
1
2
3
t
s
0
12
8
+∞
+∞
1
+∞
0
3
14
+∞
2
+∞
+∞
0
3
9
3
+∞
+∞
+∞
0
14
t
+∞
+∞
+∞
+∞
0

i j
s
1
2
3
t
1，2

3

4

5

最短路线，最短路长17。

得分
九、（10分）

某部门在今后5年内考虑给下述项目投资，已知：
项目1，从第1年到第4年年末可以投资，并于次年年末收回本利106％，但每年的投资限额为3万元；
项目2，第0年年末可以投资，并于第5年年末收回本利151％；
项目3，从第2年年末可以投资，并于第5年年末收回本利150％；
项目4，5年内每年年初可以购买公债，并于当年年末收回本利106％。
该部门拟在第1年年初投入资金30万元，在第2年年初再投入资金5万元（不含已收回的本利），第3年年末提走资金5万元，收回的本利可以用于再投资。请建立一个线性规划模型，以确定第5年年末回收的本利最大的投资方案。（不求解）
收集于网络，如有侵权请联系管理员删除