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

一、判断题

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

【答案】×

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

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

【答案】×

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

3． 若X 1, X 2分别是某一线性规划问题的最优解，则

其中λ1, λ2为正实数。（ ）

【答案】×

【解析】λ1, λ2不但应该是正实数，还应该满足λ1﹢λ2=1。

4． 对于一个有n 个变量，m 个约束方程的标准线性规划SLP ，其基可行解的数目恰好是个。（ ）

【答案】×

【解析】其基解的个数最多是个，且一般情况下，基可行解的数目小于基解的个数。 5． 如果线性规划问题有最优解，则它一定是基可行解。（ ）

【答案】√

【解析】基解且可行才有可能是最优解。 也是该线性规划问题的最优解，

二、填空题

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

【答案】G 是连通图

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

最终可以得到G 的一个支撑子图Gk ， 它不含圈，于是Gk 就是G 的一个支撑树。

7． Fibonacoi 法在[2，6]区间上取的初始点是_____。

【答案】，

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

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

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

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

9． 两阶段法中，若第一阶段目标函数最优值不为0，则原问题_____。

【答案】无可行解

【解析】第一阶段目标函数值不是0，则说明最优解的基变量中含有非零的人工变量，表明原先性规划问题五可行解。

三、计算题

10．试求解下列线性规划问题:

将本问题的目标变成maxz=-xl +x2，约束条件不变，何为其解?

【答案】（1）用图解法可得图

由图形可知，在（0，l ）处，-x 1+x2取得最大值为1。 故最优解为x 1=0，x 2=1，目标函数值为z=1。

（2

）当目标函数变为

故最优解为x 1+x2=111．试用SUMT 外点法求解

并求出当罚因子等于1和10时的近似解。

【答案】构造惩罚函数

令，得的解为

; 当M=l0时，

【答案】设

定义拉格朗日函数 。 。 即，由于约束条件不变，即为上图中所示的阴影部分，故目标函数值为下z=l。 由x 1+x2=0可 得，目标函数与边界直线x 1+x2=0平行。 所以，当M=1时，12．试用乘子法求解非线性规划问题（取c=2）:

于是得到

解得，