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

福建农林大学运筹学期末考试试卷(B)卷

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

学年 第 学期

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

专业 学号

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

1. 目标规划模型中，目标约束ax d d g中的g称为

2. 线性规划问题的单纯形法中,有最优解的判别准则是 所有检验数非负且最优值为常数 。 3. 如果流f fij中所有fij 0，则称f是流。

ttt 1

4. 如果B0 (P01,P02,...,P0m)，Bt为最优基，则Bt为(P01,P02,...,P0m)。

5. 无向图中的环是 端点重合的边 。 二、单项选择题（选择正确答案的字母填入空格处，每小题2分，共10分）

1.线性规划的非对称形式的原问题和对偶问题数学模型中，互补松弛性的描述式为 C 。

*

***A. y*xs 0,ysx 0 B. y*xs 0 **C. ysx 0 D．yx 0

**

2. 若(V1,V1)为最大截集，则

A. c(V1,V1)为最小截量 B. c(V1,V1)为最大流流量 C. c(V1,V1)为(V1,V1)的截量 D. c(V1,V1)为最小截量 3. 最短路求解的主要内容是 D 。

A. 关键路线 B. 最短路线

C. 最短路长 D. 最短路线和最短路长 4. 线性规划问题的价值系数变化后，当最优表中 B 不发生变化。

A. 非基变量检验数 B. 限定常数、技术系数和基变量检验数

福建农林大学运筹学期末考试试卷(B)卷

C. 检验数 D. 目标函数值的相反数 5. 网络计划中关键工序aij的TFij C 。

A.>0 B.<0 C.=Lj-Ei-Tij D.=Lj

三、判断题（正确打“√”；错误打“×”；每小题2分，共10分）

1. 在增广链上确定的流量调整量只能是负的。（ × ） 2. 目标规划模型中必须有目标约束。（ √ ） 3. 线性规划问题有最优解。（ × ）

4. 网络计划中，非关键路线上工序的施工时间延长可能导致工期延长。（ √ ）

5. 树中可能存在环。（ × ） 四、问答题（每小题5分，共20分）

1. 闭回路的定义及应用。

m×n表可以划分为m×n个格，一个格也可以称为一个点，在不同的 m×n表中，格或点代表不同的含义。取产销平衡表来介绍闭回路定义。 在产销平衡表中取偶数个点xi0,j0,xi1,j1,...,xip,jp，若这些点满足

i0 i1, j1 j2

i2 i3, j3 j4 ……

i(p 1) ip,jp j0 或满足

j0 j1, i1 i2

j2 j3, i3 i4 ……

福建农林大学运筹学期末考试试卷(B)卷

j(p 1) jp,ip i0 则称这些点构成一条闭回路。

闭回路用来进行方案调整，计算检验数，判断可行解是否基本解等等。 2. 最大流问题的线性规划模型。

maxv(f)

0 fij cijaij A

i s v(f)

s..t

f f i 1,2, ,n sj js 0

ajs v(f) asj Ai t

3. 线性规划模型的特点。 略。

4. 目标规划模型中目标约束的结构。 略。

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

1.c c1,c2 1,1 ，用单纯形法求解； 2.画出可行域；

3.指出c c1,c2 变动下的最优解。

minz c1x1 c2x2

(P):

x1 x2 10 s..t x1 x2 5 x,x 0 12

解： ⑴ 单纯形法求解如下：

福建农林大学运筹学期末考试试卷(B)卷

x* (5,0,5,0,0)T,z* 5。

2.可行域如下：

福建农林大学运筹学期末考试试卷(B)卷

六、（10分）

用破圈法或避圈法求图1的最大生成树，并指出其权重和（10分）

说明：P c。

福建农林大学运筹学期末考试试卷(B)卷

解：⑴避圈法：首先确定应选的边数为顶点数减1，即应选7条边。 所选的边染上红色，旁边标明选边序号，结果如下图所示。

最大生成树权为85. ⑵避圈法略。

1．求解

2．给出一个合理的实际意义。

minz P(d d) Pd11122

七、（10分） 对(OP)，要求

x1 x2 d1 d1 10

(OP):s..t x1 2x2 d2 d2 5

x,x,d ,d ,d ,d 0 121122

解：⒈⑴单纯形法

福建农林大学运筹学期末考试试卷(B)卷

T ⑵图解法

相关图形见图2。

⑴ 考虑硬约束，可行域为第一限象； ⑵ 考虑P1，最优解在直线AB上； ⑶ 考虑P2，最优解在点A上。 因此，x (10,0)T,z {0,5P2}

。

福建农林大学运筹学期末考试试卷(B)卷

x1 1

图2

⒉略。

八、（10分）

（教材P155例7）有某种机床,可以在高低两种不同的负荷下进行生产,在高负荷下生产时,产品的年产量为g,与年初投入生产的机床数量u1的关系为

g=g(u1)=8u1,这时,年终机床完好台数将为au1,(a为机床完好率，0<a<1,设a=0.7).在低负荷下生产时,产品的年产量为h,和投入生产的机床数量u2的关系为

h=h(u2)=5u2,相应的机床完好率为b(0<b<1,设b=0.9),一般情况下a<b。假设某厂开始有x=1000台完好的机床，现要制定一个五年生产计划，问每年开始时如何重新分配完好的机床在两种不同的负荷下生产的数量，以使在5年内产品的总产量为最高。

解：首先构造这个问题的动态规划模型。 ⑴ 变量设置

福建农林大学运筹学期末考试试卷(B)卷

①设阶段变量k表示年度，因此，阶段总数n=5。

②状态变量sk表示第k年度初拥有的完好机床台数，同时也是第k-1年度末时的完好机床数量。

③决策变量uk，表示第k年度中分配于高负荷下生产的机床台数。于是sk- uk便为该年度中分配于低负荷下生产的机床台数。

这里uk与uk均取连续变量，当它们有非整数数值时．可以这样理解：如sk＝0.6，就表示一台机器在k年度中正常工作时间只占6/10；uk=0.4时，就表示一台机床在k年度只有4/10的时间于高负荷下工作。 ⑵ 状态转移方程为

sk 1 auk b(sk uk) 0.7uk 0.9(sk uk)⑶ 允许决策集合,Dk(sk) uk0 uk sk

⑷ 目标函数。设vk(sk,uk)为第k年度的产量，则vk(sk,uk)=8uk+5(sk-uk),因此，目标函数为

vk,n(sk) vk(sk,uk) vk 1(sk 1,uk 1) v5(s5,u5) ⑸ 递推方程。

令fk(sk)表示由第k年的状态sk出发，采取最优分配方案到第5年度结束这段时间的产品产量，根据最优化原理有以下递推关系：

fk(sk) max vk(sk,uk) fk 1(sk 1) k 5,4,3,2,1

uk Dk(sk)

f6(s6) 0

⑹ 边界条件：s1＝1000，s6≥0。 分阶段求解见下表。

福建农林大学运筹学期末考试试卷(B)卷

由表5可得最优策略：p1(1000) 0

,0,810,567,397 。目标函数最优值：

f1(1000) 23691.2个。

表1

九、（10分）

对表1，用表上作业法求解。

'解：根据产销平衡可知表1中不限应取为2，—应取为M，因此问题的基础数据表等价与表2： 表2

⑴关于x的计算 用伏格尔法确定x

福建农林大学运筹学期末考试试卷(B)卷

说明：决定A,II和A,IV两个数字格，后者是补零的格。

福建农林大学运筹学期末考试试卷(B)卷

0注意空格x11检验数为零，但取它为入基变量时调整量为零，所以最优解唯一，为

x0，最优值z* 5 3 4 4 2 5 5 13 106

福建农林大学运筹学期末考试试卷(B)卷

位势（0）

检验数（0）

本文来源：https://www.bwwdw.com/article/7j94.html