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

一、选择题

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

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

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

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

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

【答案】AB

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

2． 若是否采用j 项目的0--1变量为x ，那么j 个项目中至多只能选择一个项目的约束方程为（ ）。

D. 无法表示

【答案】C

【解析】A 表示的是至少选择一个项目，不符合; B 表示的是只能选择一个项目。

3． 单纯形法中，关于松弛变量和人工变量，以下说法正确的是（ ）。

A. 在最后的解中，松弛变量必须为0，人工变量不必为0

B. 在最后的解中，松弛变量不必为0，人工变量必须为0

C. 在最后的解中，松弛变量和人工变量都必须为0

D. 在最后的解中，松弛变量和人工变量都不必为0

【答案】B

【解析】松弛变量是在约束不等式号的左端加入的，在最后的解中，其值可以不必为0; 人工变量是在原约束条件为等式的情况下加入的，只有基变量中不再含有非零的人工变量时，原问题才有解，所有最后的解中人工变量必须为0。

4． 网络计划中的某工序（i ，j ），估计的最乐观时间为a ，最可能时间为m ，最保守时间为b ，则该工序的 期望工时和方差可以按下面（ ）计算。

【答案】A

二、计算题

5． 某工厂备购置一台新机器来扩大生产，新机器安装使用期为三年，在此之后不再使用。然而工作的三年内，负荷较大，随着时间的增长，运行和保修费用将有较大幅度增加。因此，在机器使用1年或2年后再购置一台新机器来代替它可能更经济，表给出了第i 年底购进一台新机器并在第j 年底将其卖掉所花费的总费用（购 置费加运行和保修费减残值，万元）。试将该问题描述成最短路问题，并求解。

表

【答案】把这个问题化为最短路问题。

图

用点v i 表示第i 年年初购进一台新设备，虚设一个点v 4，表示第3年年底。

边（v i ，v j ）表示第i 年初购进的设备一直使用到第j 年年初。

这样设备更新问题就变为:求从v 1，到v 4的最短路问题，计算结果表明:

为最短路，

路长为14. 即在第二年底更换新设备为最优决策，这时总费用为14万元。

6． 在有互相排斥的约束条件的问题中，如果约束条件是（≤）型的，我们可用加以y i M 项（y i 是0-1变量， M 是很大的常数）的方法统一在一个问题中。如果约束条件是（≥）型的，我们将怎样利用y i 和M 呢?

【答案】在互相排斥的约束条件问题中，如果约束条件是（≥）型，我们可以分别在m 个约束条件右端减去y i M ， 其中y i 是0-1变量，M 是充分大的正数，且

7． 试用乘子法求解非线性规划问题（取c=2）:

【答案】设

定义拉格朗日函数 。

于是得到

解得，

8． 用图解法求解下列线性规划问题，并指出问题是具有惟一最优解、无穷多最优解、无界解还是无可行解?

（1）

（2）

（3）