当前位置：问答库＞考研试题

一、填空题

1． 无向连通图G 是欧拉图的充要条件是_____。

【答案】G 中无奇点

2． 网络中如果树的节点个数为z ，则边的个数为_____。

【答案】z-l

【解析】由树的性质可知，树的边数=数的节点数-1

3． 图G=（V ，E ）有生成树的充分必要条件是_____。

【答案】G 是连通图

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

4． 某整数规划模型，解其松弛问题得到最优解。若其中某分量x j 二场为非整数，用分支定界法求解时，针对 该分量构造的两个约束条件应为:_____。

【答案】

【解析】由分支定界法的原理可以，良容易得至“结果，其中〔b j 〕为不大于bj 的最大整数。

二、选择题

5． 在网络中，设通过弧（v i ，v j ）的流量和容量分别为f ij 和c ij ，若弧（v i ，v j ）是非饱和弧则有（ ）

【答案】C

6． 线性规划灵敏度分析应在（ ）的基础上，分析系数的变化对最优解产生的影响。

A. 初始单纯形表

B. 最优单纯形表

C. 对偶问题初始单纯形表

D. 对偶问题最优单纯形表

【答案】BD

【解析】灵敏度分析的是当系数的一个或几个发生变化时, 已求得的线性规划问题的最优解会有什么变化，所以进行灵敏度分析是在最优单纯形表或对偶问题的最优单纯形表的基础上分析的, 最优单纯形表反映的就是系数变化前己求得的最优解。

7． 运输问题中，m+n-l个变量构成基本可解的充要条件是它不含（ ）。

A. 松弛变量

B. 多余变量

C. 闭回路

D. 圈

【答案】C

【解析】位于闭回路上的一组变量，它们对应的运输问题约束条件的系数列向量线性相关，因而在运输问题基可行解的迭代过程中，不允许出现全部顶点由填有数字的格构成的闭回路。也就是说，在确定运输问题的基可行解时，除要求基变量的个数为（m+n-l）外，还要求运输表中填有数字的格不构成闭回路。

8． 对于动态规划，下列说法正确的有（ ）

A. 在动态规划模型中，问题的阶段数等于问题中的子问题的数目

B. 动态规划中，定义状态时应保证在各个阶段中所做决策的相互独立性

C. 对一个动态规划问题，应用顺推成逆推解法可能会得出不同的最优解

D. 假如一个线性规划问题含有8个变量和6个约束，则用动态规划方法求解时将划分为6个阶段，每个阶 段的状态将有一个8维的向量组成

【答案】AB

【解析】对于一个动态规划问题，不论是采用顺推法还是逆推法，只能得到一个唯一的解; 假如一个线性规 划问题含有8个变量和6个约束，则用动态规划方法求解时将按照变量的个数划分为8个阶段，每个阶段的状态 将有一个6维的向量组成。

三、计算题

9． 建立数学模型一家汽车制造商有5家过时的工厂，管理层考虑更新这些工厂以生产一种新型轿车的发动机组、变速器和一种主要配件A 。更新每个工厂的成本和更新后的生产能力如表所示:

表

工厂可用于更新的资金为1300万元，工厂3和工厂4位于同一地区，最多只能更新一个工厂，此外，工厂1与工厂5具有相关性，工厂5所需要的某些零件必须由工厂1生产。现计划需要180万个发动机、150万个变速器及200万个配件A ，管理层应决定更新哪些工厂以达到计划生产需要，并使总成本最小。试建立该问题的数学模型。

【答案】设x i =1表示更新工厂i ，x i =0表示不更新工厂i 。根据题意，可建立如下数学模型:

10．写出下列线性规划问题的对偶问题。

（1）

（2）

（3）