当前位置:问答库>考研试题

2016年长沙理工大学交通运输工程学院904运筹学[专业硕士]考研强化班模拟试题及答案

  摘要

一、填空题

1. 图G=(V ,E )有生成树的充分必要条件是___。

【答案】G 是连通图

【解析】图G 是连通图,如果G 不含圈,那么G 本身是一个树,从而G 使它自身的一个支撑树。现设G 含圈,任取一个圈,从圈中任意地去掉一条边,得到G 的一个支撑子图Gl 。如果Gl 不含圈,那么Gl 是G 的 一个支撑树,如果Gl 仍含圈,那么从Gl 中再任取一个圈,如此重复,最终可以得到G 的一个支撑子图Gk , 它不含圈,于是Gk 就是G 的一个支撑树。

2. 某极小化线性规划问题的对偶问题的最优解的第1个分量为y l =-12,则该问题的第1个约束条件的右端常数项的对偶价格为:_____。

【答案】-12

【解析】由对偶问题的经济解释可知,原问题约束条件的右端常数项的对偶价格等于对偶问题的最优解中相 应的分量的值。

3. 对于线性规划问题:MaxZ=CX.AX≦b.X ≧0,若B=(P 1,P 2,…,P m )为A 中m 个线性无关的列向量, 且为该LP 的一个可行基,则对应于基B 的基可行解为:_____,该基可行解为最优解的条件是:_____。 【答案】,对于一切有。

【解析】若B=(P 1,P 2,…,P m )为A 中m 个线性无关的列向量,

此时令非基变量

, 这时变量的个数等于线性方程组的个数,用高斯消去法,可求得对应

于基B 的基可行解

为。由最优解的判别定理,若对于一

, 则所求得的基可 行解为最优解。

4. 现有m 个约束条件,若某模型要求在这m 个条件中取”个条件作为约束,用,1变量来实现 该问题的约束条件组为:_。

【答案】

【解析】0一l 变量取1时取该约束条件,否则不取,又一共取S 个约束条件。则可得到约束条件

组为:

二、计算题

5. 某工程公司在未来l~4月份内需完成三项工程:第一项工程的工期为1~3月份,总计需劳动 力80人月; 第二项工程的工期为1~4月份,总计需劳动力100人月; 第三项工程的工期为3~4月份,总计需劳动力120人月。该公司每月可用劳力为80人,但任一项工程上投入的劳动力任一月内不准超过60人。问该工 程公司能否按期完成上述三项工程任务,应如何安排劳力? (请将该问题归结为网络最大流问题求解)

,如下图所示。

【答案】可以构建网络图(弧上数字为最大流量)

其中,结点1、2、3、4分别代表1、2、3、4月份,结点5、6、7分别代表第一、二、三项工程。通过标号 与调整,得到的最大流如下图所示。

该最大流问题有多重最优解,上图仅给出一种。

所以该公司能按期完成上述三项工程任务,安排劳力的方案可以为:1月份,安排60人做第一项任务、20 人做第二项任务; 2月份,安排60人做第二项任务; 3月份,安排60人做第三项任务、20

人做第一项任务; 4 月份,安排60人做第四项任务、20人做第三项任务。 6. 在图中,分别求v l 至v 6,v l 至V 4,v6至vZ 和vZ 至vs 的最短路和最短距离。

【答案】用Floyd 方法求解

令网络的权矩阵为

其中,

为到的距离 由表示从v i 到v j 点的或直接

有边或借v 1点为中间点是的最短路长,括弧中元素为更新元素,得

表示从vi 到vj 点最多经v l ,v 2的最短路长,得以此类推,