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

一、判断题

1． 运输问题是一种特殊的线性规划模型，因而其求解结果也可能出现四种情况之一:有惟一最优解，有无穷多最优解，无界解，无可行解。（ ）

【答案】×

【解析】运输问题是一种特殊的线性规划模型，它总存在可行解，或是存在惟一最优解，或是有无穷最优解。

2． 如果图T 是树，则T 中一定存在两个顶点，它们之间存在两条不同的链。（ ）

【答案】X

【解析】连通且不含圈的无向图称为树。因此任意两点间必定只有一条链。

3． 目标规划问题的日标函数都是求最大化问题的。（ ）

【答案】×

【解析】当每一目标值确定后，决策者的要求是尽可能缩小偏离目标值，因此目标规划的目标函数只能是最小化的。

4． 结点最早时间同最迟时间相等的点连接的线路就是关键路线。（ ）

【答案】√

【解析】关键路线是指总时差为零的工作链，而该工作链是由一系列最早时间同最迟时间相等的点连接而成的。

二、填空题

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

【解析】由分支定界法的原理可以，良容易得至“结果，其中〔b j 〕为不大于bj 的最大整数。 6． Fibonacoi 法在[2，6]区间上取的初始点是_。

【答案】，

【解析】由Fibonacci 的计算方法可知。

一、判断题

1． 网络图中任何一个结点都表示前一工序的结束和后一工序的开始。（ ）

【答案】x

【解析】网络图的起始点只表示一工序的开始，结束点只表示一工序的结束。

2． 在任一图G 中，当点集v 确定后，树图是G 中边数最少的连通图。， （ ）

【答案】X

【解析】连通且不含圈的无向图称为树。

3． 利用破圈法求赋权图的最小支撑树时，每次都是任取一个圈并去掉其中权最小的边，直到该赋权图不再 含圈时，便得到最小支撑树。（ ）

【答案】x

【解析】利用破圈法求最小支撑树时，每次任取一个圈，去掉圈中权最大的边。

4． 指派问题效率矩阵的每个元素乘以同一大于0的常数k ，将不影响最优指派方案。（ ）

【答案】✓

【解析】效率矩阵每个元素乘以同一大于0的常数k ，即目标函数的系数同时增大k 倍，不会影响最优基的变化，故不影响最优指派方案。

二、填空题

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

【答案】z-l

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

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

【答案】G 是连通图

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