2018年武汉理工大学管理学院881运筹学考研核心题库
● 摘要
一、选择题
1． 无约束最优化问题
）问题的（ ）。
A. 全局最优解
B. 局部最优解
C. 极点
D .K-T点
【答案】B
【解析】局部最优解即在X*的某邻域，满足
A. 最大流
B. 最大割
C. 最小流
D. 最小割
【答案】D
【解析】网络从发点到收点的各通路中，由容量决定其通过能力，最小割集则是这些路中的咽喉部分，或者叫瓶口, 其容量最小，它决定了整个网络的最大通过能力。
3． 单纯形法求解最大化线性规划问题，如果存在“左端≥右端常数”的约束条件，对此约束条件应引入（ ）。
A. 可控变量
B. 环境变量
C. 人工变量
D. 松弛变量
【答案】D
【解析】约束方程为“≥”不等式，则可在“≥”不等式左端减去一个非负剩余变量（也可称松弛变量）。 ，则称X*是函数的局部最优解。2． 若f 是G 的一个流，K 为G 的一个割，且f 的流量等于K 的容量，则K 一定是（ ）。 中，如果在X*的某个领域内满足，则X ’是
4． 关于最小费用最大流，求解时不会用到下面哪种方法（ ）。
A.Dijkstra 算法
B.Floyd 算法
C.Ford 一Fulkerson 算法
D. 奇偶点作业法
【答案】D
【解析】奇偶点作业法为中国邮递员问题中寻找欧拉圈时所用的方法，最小费用最大流问题并不涉及此法。
二、填空题
5． 无向连通图G 是欧拉图的充要条件是_____。
【答案】G 中无奇点
6． 某极小化线性规划问题的对偶问题的最优解的第1个分量为y l =-12，则该问题的第1个约束条件的右端常数项的对偶价格为:_____。
【答案】-12
【解析】由对偶问题的经济解释可知，原问题约束条件的右端常数项的对偶价格等于对偶问题的最优解中相 应的分量的值。
7． 流f 为可行流必须满足_____条件和_____条件。
【答案】容量限制条件和平衡条件
【解析】在运输网络的实际问题中可以看出，对于流有两个明显的要求:一是每个弧上的流量不能超过该弧 的最大通过能力（即弧的容量）; 二是中间点的流量为零。因为对于每个点，运出这点的产品总量与运进这点的 产品总量之差，是这点的净输出量，简称为是这一点的流量; 由于中间点只起转运作用，所以中间点的流量必为 零。易而发点的净流出量和收点的净流入量必相等，也是这个方案的总输送量。
8． 若P （k ）是f （x ）在x （K ）处的下降方向，则满足_____。
【答案】均有
【解析】若存在实数
，使对于任意的，就称方向）为均有下式成立:
点的一个下降方向。
三、判断题
9． 在任一图G 中，当点集v 确定后，树图是G 中边数最少的连通图。（ ），
【答案】×
【解析】连通且不含圈的无向图称为树。
10．如果线性规划问题无最优解，则它的对偶问题也一定没有最优解。（ ）
【答案】√
【解析】它的对偶问题可能无解，也可能有无界解。
11．网络图中任何一个结点都表示前一工序的结束和后一工序的开始。（ ）
【答案】×
【解析】网络图的起始点只表示一工序的开始，结束点只表示一工序的结束。
12．利用破圈法求赋权图的最小支撑树时，每次都是任取一个圈并去掉其中权最小的边，直到该赋权图不再 含圈时，便得到最小支撑树。（ ）
【答案】×
【解析】利用破圈法求最小支撑树时，每次任取一个圈，去掉圈中权最大的边。
13．如果线性规划问题有最优解，则它对偶问题也一定有最优解。（ ）
【答案】√
【解析】由对偶定理知，原命题为真，且线性规划问题与它的对偶问题的最优值相等。
四、计算题
14．某公司现拥有资金3万元。现做今后3年的投资计划每年允许投资额不能超过5万元. 若某年投资x 元，当年有l/3可能性损失x 元，而有2/3可能性增收x 元。现要确定能使3年后将拥有资金超过5万元的可能性最大的投资力案
试结合题中说明，当用动态规划方法求解时的下列基本概念（不必计算）:
（l ）阶段变量:
（2）状态变量、状态集台:
（3）决策变量、允许决策范围
（4）状态转移关系:
（5）递推方程。
【答案】（l ）阶段变量k :按三年的投资计划，分为3个阶段;
（2）状态变量s k :表示第k 年初投资时剩余的全部资金金额
状态集合为:s 1=3
（3）决策变量x k :表示第k 年初用于投资的金额
（4）状态转移关系为: