福建农林大学考试试卷 （ B ）卷
学年 第 学期
课程名称： 运 筹 学 考试时间 120分钟
专业 年级 班 学号 姓名
1. 目标规划模型中，目标约束ax d d g -
+
+-=中的g 称为 目标值 。

2. 线性规划问题的单纯形法中,有最优解的判别准则是 所有检验数非负且最优值为常数 。

3. 如果流{}
ij f f =中所有0ij f =，则称f 是 零 流。

4. 如果001020(,,...,)m B P P P =，t B 为最优基，则1
t B -为01020(,,...,)t
t
t
m P P P 。

5. 无向图中的环是 端点重合的边 。

二、单项选择题（选择正确答案的字母填入空格处，每小题2分，共10分）
1.线性规划的非对称形式的原问题和对偶问题数学模型中，互补松弛性的描述式为 C 。

A. **
**0,0s s y x y x == B. **
0s y x = C. **0s y x = D ．**
0y x =
2. 若11(,)V V 为最大截集，则 C 。

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

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

A. 非基变量检验数
B. 限定常数、技术系数和基变量检验数
一、填空题（每空2分，共10分）
C. 检验数
D. 目标函数值的相反数 5. 网络计划中关键工序a ij 的TF ij C 。

A.>0
B.<0
C.=L j -E i -T ij
D.=L j
三、判断题（正确打“√”；错误打“×”；每小题2分，共10分）
1. 在增广链上确定的流量调整量只能是负的。

（ × ）
2. 目标规划模型中必须有目标约束。

（ √ ）
3. 线性规划问题有最优解。

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

（ √ ）
5. 树中可能存在环。

（ × ）
四、问答题（每小题5分，共20分）
1. 闭回路的定义及应用。

m ×n 表可以划分为m ×n 个格，一个格也可以称为一个点，在不同的 m ×n 表中，格或点代表不同的含义。

取产销平衡表来介绍闭回路定义。

在产销平衡表中取偶数个点jp ip j i j i x x x ,1,10,0,...,,，若这些点满足
,10i i = 21j j =
,32i i = 43j j = ……
,)1(ip p i =-0j jp = 或满足
,10j j = 21i i =
,32j j = 43i i =
……
,)1(jp p j =-0i ip = 则称这些点构成一条闭回路。

闭回路用来进行方案调整，计算检验数，判断可行解是否基本解等等。

2. 最大流问题的线性规划模型。

max ()
0()..0
1,2,,()sj js ij ij ij sj js a A a v f f c a A v f i s s t f f i n v f i t ∈≤≤∈⎧
⎪
=⎧⎪
⎨⎪
-==⎨⎪⎪⎪-=⎩⎩
∑∑ 3. 线性规划模型的特点。

略。

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

略。

五、（第一小题5分，第二小题3分，第三小题2分，共10分） 对)(P ：要求：
1.()()12,1,1c c c ==，用单纯形法求解；
2.画出可行域；
3.指出()12,c c c =变动下的最优解。

1122
121212
min 10():
..5,0z c x c x x x P s t x x x x =++≤⎧⎪-≥⎨⎪≥⎩
解： ⑴ 单纯形法求解如下：
**(5,0,5,0,0),5T x z ==。

2.可行域如下：
说明：P c =-。

六、（10分）
用破圈法或避圈法求图1的最大生成树，并指出其权重和（10分）
解：⑴避圈法：首先确定应选的边数为顶点数减1，即应选7条边。

所选的边染上红色，旁边标明选边序号，结果如下图所示。

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

七、（10分） 对)(OP ，要求
1．求解
2．给出一个合理的实际意义。

11122
12111222121122
min ()10
():..25
,,,,,0z P d d P d x x d d OP s t x x d d x x d d d d +-+
-+-+
-+-+=++⎧++-=⎪++-=⎨⎪≥⎩
解：⒈⑴单纯形法
求解过程见下表，据下表得。

}
5,0{,)0,10(
T **
⑵图解法
相关图形见图2。

⑴ 考虑硬约束，可行域为第一限象； ⑵ 考虑P 1，最优解在直线AB 上； ⑶ 考虑P 2，最优解在点A 上。

因此，。

}
5,0{,)0,10(2P z x T ==**
x1
+
1
图2
⒉略。

八、（10分）
（教材P155例7）有某种机床,可以在高低两种不同的负荷下进行生产,在高负
荷下生产时,产品的年产量为g,与年初投入生产的机床数量u
1的关系为g=g(u
1
)=8u
1,
这时,年终机床完好台数将为au
1
,(a为机床完好率，0<a<1,设a=0.7).在低负荷下
生产时,产品的年产量为h,和投入生产的机床数量u
2的关系为h=h(u
2
)=5u
2
,相应的
机床完好率为b(0<b<1,设b=0.9),一般情况下a<b。

假设某厂开始有x=1000台完好的机床，现要制定一个五年生产计划，问每年开始时如何重新分配完好的机床在两种不同的负荷下生产的数量，以使在5年内产品的总产量为最高。

解：首先构造这个问题的动态规划模型。

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

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

③决策变量u k ，表示第k 年度中分配于高负荷下生产的机床台数。

于是s k - u k
便为该年度中分配于低负荷下生产的机床台数。

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

⑵ 状态转移方程为
⑶ 允许决策集合,}{k k k k k s u u s D ≤≤=0)(
⑷ 目标函数。

设v k (s k ,u k )为第k 年度的产量，则v k (s k ,u k )=8u k +5(s k -u k ),因此，目标函数为
),(),(),()(555111,u s v u s v u s v s v k k k k k k k n k +++=+++
⑸ 递推方程。

令f k (s k )表示由第k 年的状态s k 出发，采取最优分配方案到第5年度结束这段时间的产品产量，根据最优化原理有以下递推关系：
}{)(),(max )(11)
(++∈+=k k k k k s D u k k s f u s v s f k k k 1,2,3,4,5=k
0)(66=s f
⑹ 边界条件：s 1＝1000，s 6≥0。

分阶段求解见下表。

)
(9.07.0)(1k k k k k k k u s u u s b au s -+=-+=+
由表5可得最优策略：}{397,567,810,0,0)1000(1=p 。

目标函数最优值：
2.23691)1000(1=f 个。

九、（10分）
对表1，用表上作业法求解。

表1
'解：根据产销平衡可知表1中不限应取为2，—应取为M ，因此问题的基础数据表等价与表2： 表2
⑴关于0
x 的计算
用伏格尔法确定0
x
说明：决定,A II 和,A IV 两个数字格，后者是补零的格。

x检验数为零，但取它为入基变量时调整量为零，所以最优解唯一，为注意空格
11
z=⨯+⨯+⨯+⨯=
x，最优值*534425513106
位势（0）
检验数（0）。