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

精品

精品

福建农林大学考试试卷 （ A ）卷

学年 第 学期

课程名称： 运 筹 学 考试时间 120分钟

专业 年级 班 学号 姓名

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

1. 目标规划模型中，对目标约束ax d d g -

+

+-=，求ax 最大的目标函数为min()d d -

+

-。 2. 增广链上的调整量 大于 零。

3. 用Dijkstra 算法求解最短路问题时，距离矩阵的元素必须满足 非负要求 。

4. 线性规划的退化基本解的非零分量 至多m 个。

5. 树是 无圈 的连通图。 二、单项选择题（选择正确答案的字母填入空格，每小题2分，共10分）

1. 线性规划的基本解中，非基变量取 C 值。 A ．零 B ．非零 C ．非负 D ．非正

2.增广链是在 B 下定义的。

A ．零流

B ．可行流

C ．不可行流

D ．非零流

3. 在约束为0,0≥≥X b AX ＝的线性规划中, (),ij m n A A a r m ?==，则基的最小数目为 D 。 A ．m

n C 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 为可行流，在f 下进行标号，如果无法给v t 标上号，f 为最大流，无需确定流量调整量，否则()t l v θ=。

3.网络计划中时差的计算。

可以据下图计算：

4. 最短路问题的基础数据与求解内容。

五、（第一小题2分，第二小题5分，第三小题3分，共10分） 对)(P ：要求：

1. 写出)(D ；

2. 用单纯形法或对偶单纯形法确定)(P 或)(D 的最优解；

精品

精品 3. 从)(P 或)(D 的最终表出发，据对偶理论直接确定)(D 或)(P 的解。

)(P ：12

12212

max 210..15

,0z x x x x s t x x x =++≤??≤??≥? 解：1. )(D ：

12

11212

min 10152..1

,0w y y y s t y y y y =+≥??+≥??≥? 2.

**(10,0,0,15),20T x z ==。

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

精品

**20w =

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

精品

精品

解：⑴ 取{}()

000,0f v f ==，用标号法确定0μ如图2所示,由图2知，

{}00100011330,,,()6,()()6s t t a a a l v v f v f μμθθ+=====+=，1f 见图3。

⑵用标号法确定1μ如图3所示,由图3知， {}112111221,,()4,()()10s t t a a l v v f v f μμθθ+=====+=，2f 见图4。

⑶用标号法确定2μ如图4所示,由图4知， 2μ不存在，故*2f f =。

精品

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

考虑一辆汽车三年的设备更新策略，开始时现有汽车的机龄为2年，取 ＝1，其余有关数据见表1。试制定三年中的设备更新策略，使三年内的净收入最大。

解：模型假设略。

精品

*

1,3(2){,,}p K K K = 1(3)25f =

八、（10分）表2是某厂原材料和产品规格的基础数据，要求建立一个线性规划模 型，以确定净收入最大的产品方案。（不求解） 表2

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