运筹学考试题库及答案

运筹学考试题库及答案

一、选择题（本题型共15题，每题2分，共30分）

1.下列关于线性规划问题的说法中，错误的是（）A.线性规划问题的可行域是凸集B.线性规划问题的最优解一定在可行域的顶点处取得C.线性规划问题的目标函数是线性函数D.在标准型中所有变量均为非负

2.对偶问题的对偶问题是（）A.原问题B.无界问题C.与原问题不同的问题D.退化问题

3.在图论中，由若干条边连接若干个顶点组成的图形称为（）A.网络B.路径C.树D.图

4.下列哪项不属于图论中的基本要素（）A.顶点B.边C.权D.圈

5.动态规划的基本方程中，状态转移方程描述的是（）A.从一个状态到另一个状态的变化关系B.状态的取值范围C.决策的选择方式D.目标函数的构成

6.整数规划问题中，若要求变量只能取0或1，则称为（）A.纯整数规划B.0-1整数规划C.混合整数规划D.目标规划

7.排队论中，服务强度ρ表示（）A.顾客到达率与服务率的比值B.服务台数量C.顾客等待时间D.服务台利用率

8.在决策论中，“自然状态”指决策者（）第1页共6页A.可控制的因素B.无法控制但已知概率的因素C.无法控制且概率未知的因素D.需要决策的结果

9.下列关于单纯形法的说法中，正确的是（）A.单纯形法的迭代过程是从可行域顶点到顶点转移B.初始基可行解必须是单位矩阵C.可求解所有类型的线性规划问题D.当检验数均为负时问题无最优解10图论中，若图中任意两顶点间仅有一条路径，则该图称为（）A.完全图B.树C.有向图D.无圈图

11.目标规划中，偏差变量d⁺表示（）A.超过目标值部分B.未达到目标值部分C.目标值本身D.偏差的绝对值A图中存在负权边时，Dijkstra算法仍适用B.Floyd-Warshall算法可求解所有顶点间最短路C.最短路目标是路径权之和最小D动态规划的核心是状态转移方程

13.线性规划问题中，基变量的个数等于（）A.约束条件个数B.决策变量个数C.约束矩阵的秩D.非基变量个数

14.动态规划的基本要素不包括（）A.状态B.决策C.状态转移方程D.目标函数值

15.M/M/∞排队模型表示（）A.输入泊松流，服务负指数分布，1个服务台B.输入指数分布，服务泊松流，多个服务台C.服务台数量无限多，顾客无需等待第2页共6页D.输入泊松流，服务常数分布，1个服务台

二、填空题（本题型共10题，每题3分，共30分）

1.线性规划标准型中，所有变量均为（），约束条件均为（），目标函数为（极大化/极小化）

2.图论中无圈的连通图称为（），其边数等于顶点数（）

3.动态规划的基本思想是将复杂问题分解为（），核心是（）

4.单纯形法中，非基变量检验数（）时需进行换基迭代，此时当前基可行解（）最优解

5.整数规划按变量整数要求分为（纯整数规划）、（混合整数规划）和（）

6.最大流问题常用算法是（），其原理是通过寻找（）增加流量

7.排队论中，系统稳态分布指运行时间足够长时各状态概率（），此时的平均等待时间称为（）

8.目标规划的优先因子P₁、P₂…P表示（），权系数d₁⁺表示ₖ（）

9.线性规划基可行解中，基变量对应的列向量构成（单位矩阵），非基变量列向量（）

10.有向图的边具有（），其权可取值（）或（）

三、判断题（本题型共10题，每题2分，共20分）

1.线性规划问题的可行域一定有界（）

2.对偶问题最优解等于原问题最优解（）

3.最大流问题中弧的容量可为0（）

4.动态规划状态转移方程中，状态仅与当前状态有关（）

5.整数规划解必为原线性规划最优解的整数部分（）

5.M/M/∞模型中顾客到达后无需等待（）第3页共6页

6.目标规划中d⁺·d⁻=0（）

7.完全图的边数为nn-1/2（n为顶点数）（）

8.单纯形法中所有非基变量检验数≤0时为最优解（）

9.最短路问题存在负权边时无最短路径（）

四、简答题（本题型共8题，每题5分，共40分）

1.简述线性规划问题的一般形式及三个基本要素

2.说明图论中“树”的定义及主要性质

3.解释动态规划中“状态”与“决策”的概念及作用

4.什么叫基可行解？与基解的区别是什么？

5.排队论中“输入过程”“服务机制”“排队规则”分别指什么？

6.整数规划与线性规划的主要区别是什么？列举两种整数规划类型

7.目标规划目标函数与线性规划目标函数的核心差异是什么？

8.简述最大流与最小割集定理的关系

五、计算题（本题型共6题，每题10分，共60分）

1.用单纯形法求解线性规划max z=3x₁+2x₂s.t.x₁+x₂≤802x₁+x₂≤100x₁≤x₂x₁,x₂≥0

六、案例分析题（本题型共2题，每题15分，共30分）

1.某物流公司A、B仓库库存100吨、80吨，需运往C、D、E零售点（需求

60、

70、50吨），单位运费（元/吨）A→C=2，A→D=3，A→E=5；B→C=4，B→D=1，B→E=6第4页共6页

（1）建立运输问题模型并求最小总运费；

（2）若B库存减至50吨，最小总运费如何变化？答案汇总

一、选择题答案

1.B

2.A

3.D

4.D

5.A

6.B

7.D

8.B

9.A

10.B

11.A

12.A

13.C

14.D

15.C

二、填空题答案

1.非负，等式

2.树，-

13.子问题，状态转移方程

4.0，非

5.0-1整数规划

6.Ford-Fulkerson算法，增广链

7.稳定，稳态等待时间

8.优先级分级，偏差相对权重

9.非单位向量

10.方向，正数，负数

三、判断题答案

1.×

2.×

3.√

4.√

5.×

6.√

7.√

8.√

9.√

10.×

四、简答题答案精简

1.一般形式max/min z=Σcᵢxᵢ；s.t.Σaᵢⱼxⱼ≤=bᵢ；xⱼ≥0要素决策变量、目标函数、约束条件

2.定义无圈连通图；性质n顶点n-1边，任意两顶点唯一路径，添加边产生唯一圈

3.状态系统当前情况；决策特定状态下的选择；作用状态确定位置，决策决定转移

4.基可行解满足约束的基解；区别基可行解分量非负，基解不一定

5.输入过程顾客到达规律；服务机制服务时间分布与台数；排队规则服务顺序

6.区别整数规划变量为整数；类型纯整数、0-

1、混合整数规划第5页共6页

7.目标规划优先满足高优先级目标；线性规划直接追求目标极值，无优先级

8.最大流流量=最小割集容量

五、计算题答案

1.最优解x₁=20,x₂=60,z=240

六、案例分析题答案

1.

（1）最小总运费480元（A→C=60，A→D=10，A→E=30；B→D=60，B→E=20）；

（2）B库存50吨时，总运费430元（减少50元）第6页共6页。