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对偶问题的最优解,所以,
因为原问题与对偶问题的最优值相等,所以
相关内容
相关标签