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

一、判断题

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

【答案】×

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

2． 对自由变量x k ，

通常令

不可能同时出现

【答案】√

【解析】因为

不可能同时出现，其中。（ ） 在用单纯型法求得的最优解中，所以。 不能同时为基变量，则至少有一个为0。故最优解中3． 如果线性规划问题有最优解，则它对偶问题也一定有最优解。（ ）

【答案】√

【解析】由对偶定理知，原命题为真，且线性规划问题与它的对偶问题的最优值相等。 4． 如果线性规划问题无最优解，则它也一定没有基可行解。（ ）

【答案】×

【解析】当问题的解为为无界时，此时该规划问题无最优解，但存在基可行解。

5． 整数规划问题最优解的目标函数值一定优于其相应线性规划问题最优解的目标函数值。（ ）

【答案】×

【解析】因为附加了整数条件，其可行域比其相应线性规划问题的可行域减小，故整数规划问题最优解的目 标函数值一定不优于其相应线性规划问题最优解的目标函数值。

二、填空题

6． 当极大化线性规划模型达到最优时。某非基变量x j 的检验数为马. 当价格系数为c j 的变化量为△c j 时，原 线性规划问题最优解保持不变的条件是_____。

【答案】

，极大化 【解析】x j 为非基变量，其价格系数变化△c j 后，其检验数变为

7． 流f 为可行流必须满足_____条件和_____条件。

【答案】容量限制条件和平衡条件

【解析】在运输网络的实际问题中可以看出，对于流有两个明显的要求:一是每个弧上的流量不能超过该弧 的最大通过能力（即弧的容量）; 二是中间点的流量为零。因为对于每个点，运出这点的产品总量与运进这点的 产品总量之差，是这点的净输出量，简称为是这一点的流量; 由于中间点只起转运作用，所以中间点的流量必为 零。易而发点的净流出量和收点的净流入量必相等，也是这个方案的总输送量。

8． 对于线性规划问题: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 的基可行解

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

切

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

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

【答案】z-l

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

三、计算题

10．某银行正在为其全职和兼职出纳员制定一个有效的工作时间表，时间表必须满足包括足够顾客服务、职员体息等在内的银行运转条件。表给出的是每周一银行从9:00到17:00所需的出纳员人数。

表

全职员上从整点开始工作且连续工作4小时，随后是l 小时午餐时间，然后是2小时的班; 兼职员工从整点 开始做一个4小时班; 全职员工成本是每小时10元（60元/天），兼职员工成本是每小时6元（24元/天）:银行要求，每时段至少要有一个全职员工:如何安排员工作息既满足要求又使成本最小。试建立该问题的数学模型。

【答案】根据题意，全职人员只有从时间编号为1、2的时间段开始工作，兼职人员可以从时

间编号为1、2、3、 4、5的时间段开始工作。令从从时间编号为1、2的时间段开始工作的全职人员数分别为x ，、x :，从时间编号 为1、2、3、4、5的时间段开始工作的兼职人员数分别为y 1、y 2、y 3、y 4、y 5。则可建立如下数学模型:

11．某一警卫部门共有12支巡逻队，负责4个要害部门的警卫巡逻。对每个部位可以考虑派出2~4支巡逻 队，并且由于派出巡逻队的数目不同，各部位可能造成的损失会有差别，具体数字如表所示:

表

问该警卫部门应往各部位分别派多少巡逻队，总的预期损失为最小。要求明确表述出状态变量，决策变量，并写出状态转移方程和动态规划基本方程。

【答案】该问题可以看成是4阶段的决策问题，采用动态规划的逆序解法进行求解。

①分阶段k=l，2，3，4

②状态变量S K ，表示可以派往第k 个部位的巡逻队数目;

③决策变量x k ，表示派到第k 个部位的巡逻队数目;

④状态转移方程:

⑤阶段指标函数

⑥递推方程:

⑦边界条件:

逆序求解。

表示第k 阶段的预期损失;