2016年中国矿业大学(徐州)管理学院830运筹学考研必备复习题库及答案
● 摘要
一、填空题
1． 在用对偶单纯形法求解某线性规划问题时, 当进基变量x i 确定后，出基变量的选取原则是:_____。 【答案】
牛顿法的搜索方向为_。 拟牛顿法的搜索方向为_。 【答案】
【解析】最速下降法:
可
时，下降最快。
牛顿法：正定二次函
数
即搜索方向是
拟牛顿法
：
（单位阵）
3． 如果运输问题单位运价表的某一行（或某一列）元素分别加上一个常数k ，最优调运方案是否会发生变化: _____。 【答案】不发生变化
【解析】如果运输问题单位运价表的某一行（或某一列）元素分别加上一个常数k ，最优调运方案中各变量的 检验数均不发生变化，所以最优调运方案不发生变化。
4． 某整数规划模型，解其松弛问题得到最优解。若其中某分量x j 二场为非整数，用分支定界法求解时，针对 该分量构造的两个约束条件应为:_。 【答案】
若
是最优点，
则以
得
出
，
当
2． 最速下降法的搜索方向_。
【解析】由分支定界法的原理可以，良容易得至“结果，其中〔b j 〕为不大于bj 的最大整数。
二、简答题
5． 什么是可行流?
【答案】满足下列条件的网络流f 称为可行流 （l ）容量限制条件:对每一弧（v i ，v j
）
第 2 页，共 11 页
（2）平衡条件 对于中间点，流出量=流入量，即对每个
对于起点Vs ，记对于终点V t ，记
式中，V （f ）称为这个可行流f 的流量，即发点的净输出量（或收点的净输入量）。 6． 试写出求解最短径路的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 ，p （v i ）+lij ] 标号进行如下修改:T （v j ）=min[T（v i ）
（3）比较所有具有T 标号的点，把最小者改为P 标号，即:
当存在两个以上最
小者时，可同时改为P 标号。若全部点均为P 标号时停止，否则用代V i 转回（2）。
第 3 页，共 11 页
相关内容
相关标签