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

一、选择题

1． 运输问题中，m+n-l个变量构成基本可解的充要条件是它不含（ ）。

A. 松弛变量

B. 多余变量

C. 闭回路

D. 圈

【答案】C

【解析】位于闭回路上的一组变量，它们对应的运输问题约束条件的系数列向量线性相关，因而在运输问题基可行解的迭代过程中，不允许出现全部顶点由填有数字的格构成的闭回路。也就是说，在确定运输问题的基可行解时，除要求基变量的个数为（m+n-l）外，还要求运输表中填有数字的格不构成闭回路。

2． 用线性规划制定某一企业的生产计划问题，两种资源的影子价格分别为y 甲=5，y 乙=8，说明这两种资源在该企业中的稀缺程度为:（ ）。

A. 甲比乙更稀缺

B. 甲和乙同样稀缺

C. 乙比甲更稀缺

D. 甲和乙都不稀缺

【答案】C

【解析】影子价格是对系统内部资源稀缺程度的一种客观评价，某种资源的影子价格越高，说明该资源在系统内越稀缺，增加该资源的供应量对系统目标函数值的贡献也越大。 3． 某一线性规划问题中的某一资源的影子价格为4，当其可用量在其灵敏度允许范围内增加一个单位时（假 定资源获得价格不变），下述正确的是（ ）。

A. 收益减少4个单位

B. 收益增加4个单位

C. 最优解不会发生变化

D. 产量一定增加4个单位

【答案】B

【解析】某种资源的影子价格的经济意义是在其他条件不变的情况下，单位资源变化所引起的目标函数的最 优值的变化。

4． 己知Y i 为线性规划的对偶问题的最优解，若Y i >0，说明（ ）。

A. 原问题的最优解x i =0

B. 在最优生产计划中第i 种资源己完全耗尽

C. 在最优生产计划中第i 种资源有剩余

D. 无法判断

【答案】B

【解析】当影子价格为0时，表示某种资源未得到充分利用; 而当资源的影子价格不为零时，表明该种资源在生产中己耗费完毕。

二、填空题

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

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

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

【答案】

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

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

【答案】z-l

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

7． 在灵敏度分析时, 当LP 某系数发生变化使原最优单纯形表中的解为该LP 的一个正侧解，但不是可行解, 为求新的最优解, 处理办法是:_____。

【答案】对偶单纯形法

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

【答案】G 是连通图

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

三、简答题

9． 试写出求解最短径路的Dijkstra 算法的步骤。

【答案】Dijkstra 算法的步骤为:

（l ）给v s 以p 标号，P （v S ）二0，其余各点均给T 标号，T （v i ）=+∞。 （2）若v i 点为刚得到P 标号的点，考虑这样的点v i ，（v i ，vj ）属于E ，且v i 为T 标号。对v j 的T 标号进行如下修改:T （v j ）=min[T（v i ），p （v i ）+lij ]

（3）比较所有具有T 标号的点，把最小者改为P 标号，即: 当存在两个以上最小者时，可同时改为P 标号。若全部点均为P 标号时停止，否则用代V i 转回（2）。