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

一、填空题

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

【答案】

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

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

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

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

3． 若x 为某极大化线性规划问题的一个基可行解，

用非基变量表达其目标函数的形式为

则X 为该LP 最优解的条件是:_____。

【答案】

。 【解析】求极大化问题，则当所有非基变量的检验数均为非正时，即得最优解。线性规划最优时要求非基变 量检验数小于等于0，所以

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

【答案】G 是连通图

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

二、计算题

5． 某一印刷厂有六项加工任务，对印刷车间和装订车间所需时间（单位:天）如表所示，试求最优的加工顺序和总加工天数。

表

【答案】加工天数矩阵为

根据最优排序规则，其最优加工顺序为J 4→J 1→J 3→J 2→J 5→J 6，总加工时间为44天。

6． 对下列整数规划问题，问用先解相应的线性规划然后凑整的办法能否得到最优整数解?

（1）

（2）

【答案】 （1）在该线性规划问题的约束条件中分别加入松弛变量

，化为标准型

先不考虑上述模型中的整数约束，利用单纯形法进行求解，如表所示。

表

此时的最优解为

用分支定界法进一步求解此整数规划.

记

题：

求得B 1的最优解

求得B 2的最优解为

于是得到

，因为，最优目标值。 时，为可行解，z=13; 当凑整

为

对该最优解进行凑整，当凑整

为时均为非可行解。 为可行解，所以。将原问题分解为两个子问，。

。 ，再将B 1 分解为两个子问题：

求得B 3 的最优解为