当前位置:问答库>考研试题

2017年太原科技大学工业工程系893运筹学考研题库

  摘要

一、填空题

1. 如果运输问题单位运价表的某一行(或某一列)元素分别加上一个常数k ,最优调运方案是否会发生变化: _____。

【答案】不发生变化

【解析】如果运输问题单位运价表的某一行(或某一列)元素分别加上一个常数k ,最优调运方案中各变量的 检验数均不发生变化,所以最优调运方案不发生变化。

2. 运输问题任一基可行解非零分量的个数的条件是_____。

【答案】小于等于行数+列数-1

【解析】任意运输问题的基可行解可变量个数为:行数+列数一l 。然而基变量也可能等于0,所以运输问题 任一基可行解非零分量的个数小于等于行数+列数一1。

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

【答案】对偶单纯形法

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

【答案】无可行解

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

二、选择题

5.

是某个目标约束条件所对应的目标函数,该目标函数就从逻辑上来看所表达的

A. 恰好完成目标值

B. 不超过目标值

C. 完成和超额完成目标值

D. 不能表示任何意义

【答案】D

【解析】目标规划的目标函数是按各自目标约束的正、负偏差变量和赋予相应的优先因子及权系数而构造的。 当每一目标值确定后,决策者的要求是尽可能缩小偏离目标值。因此目标规划的目标函数只能是

。 本题对应的目标函数是求maxZ ,所以没有任何意义。 含义是( )。

6. 若f 是G 的一个流,K 为G 的一个割,且f 的流量等于K 的容量,则K 一定是( )。

A. 最大流

B. 最大割

C. 最小流

D. 最小割

【答案】D

【解析】网络从发点到收点的各通路中,由容量决定其通过能力,最小割集则是这些路中的咽喉部分,或者叫瓶口, 其容量最小,它决定了整个网络的最大通过能力。

7. 求一个赋权图中包括指定边集的最小连接方案(最小树),下面( )方法是正确的。

A. 最小树的初始边集为图中最小权边,按其余各边的权从小到大,逐一检查选取

B. 最小树的初始边集为某一条指定边,按其余各边边的权从小到大,逐一检查选取

C. 最小树的初始边集为所有指定边的集合,按其余各边边的权从小到大,逐一检查选取

D. 最小树的初始边集为权最小的一条指定边,按其余各边边的权从小到大,逐一检查选取

【答案】C

【解析】该问题不是简单的最短路问题,它要求最小连接方案包括指定边集,所以,最小树的初始边集应为 所有指定边的集合。

8. 运输问题中,m+n-l个变量构成基本可解的充要条件是它不含( )。

A. 松弛变量

B. 多余变量

C. 闭回路

D. 圈

【答案】C

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

三、证明题

9. 设线性规划问题1是

()是其对偶问题的最优解。

又设线性规划问题2是

其中k i 是给定的常数,求证

【答案】问题1的矩阵表示为

其中

问题2的矩阵表示为

。 设X 1 为它的一个可行解,其对偶问题的最优解为

其中

问题1的对偶问题为

问题2的对偶问题为 =

由此可知,问题1的对偶问题与问题2的对偶问题有相同的约束条件,所以问题1的对偶问题的最优解一定是问题2的对偶问题的一个可行解。

。 设X 2 为它的一个可行解,其对偶问题的最优解为Y 2 又因为Y 2是问题2对偶问题的最优解,所以,

因为原问题与对偶问题的最优值相等,所以