2017年哈尔滨工业大学深圳研究生院850运筹学考研仿真模拟题
● 摘要
一、选择题
1. 求一个赋权图中包括指定边集的最小连接方案(最小树),下面( )方法是正确的。
A. 最小树的初始边集为图中最小权边,按其余各边的权从小到大,逐一检查选取 B. 最小树的初始边集为某一条指定边,按其余各边边的权从小到大,逐一检查选取 C. 最小树的初始边集为所有指定边的集合,按其余各边边的权从小到大,逐一检查选取 D. 最小树的初始边集为权最小的一条指定边,按其余各边边的权从小到大,逐一检查选取 【答案】C
【解析】该问题不是简单的最短路问题,它要求最小连接方案包括指定边集,所以,最小树的初始边集应为 所有指定边的集合。
2.
是某个目标约束条件所对应的目标函数,该目标函数就从逻辑上来看所表达的含义是( )。
A. 恰好完成目标值 B. 不超过目标值 C. 完成和超额完成目标值 D. 不能表示任何意义 【答案】D
【解析】目标规划的目标函数是按各自目标约束的正、负偏差变量和赋予相应的优先因子及权系数而构造的。 当每一目标值确定后,决策者的要求是尽可能缩小偏离目标值。因此目标规划的目标函数只能是。 本题对应的目标函数是求maxZ ,所以没有任何意义。
3. 关于最小费用最大流,求解时不会用到下面哪种方法( )。
A.Dijkstra 算法 B.Floyd 算法
C.Ford 一Fulkerson 算法 D. 奇偶点作业法 【答案】D
【解析】奇偶点作业法为中国邮递员问题中寻找欧拉圈时所用的方法,最小费用最大流问题并不涉及此法。
4. 用线性规划制定某一企业的生产计划问题,两种资源的影子价格分别为y 甲=5,y 乙=8,说明这两种资源在该企业中的稀缺程度为:( )。
A. 甲比乙更稀缺
B. 甲和乙同样稀缺 C. 乙比甲更稀缺 D. 甲和乙都不稀缺 【答案】C
【解析】影子价格是对系统内部资源稀缺程度的一种客观评价,某种资源的影子价格越高,说明该资源在系统内越稀缺,增加该资源的供应量对系统目标函数值的贡献也越大。
二、简答题
5. 一个运输问题,如果其单位运价表的某一行元素分别加上一个常数,最优调运方案是否发生变化,试说明理由(用表或直接用公式);
【答案】最优方案不会发生变化。因为在计算任意空格的检验数时,若其通过变化行的一个基格,则其必经过两个基格,
则最优方案不发生变化。
6. 试简述求解整数规划模型的分枝定界法剪枝的几种情况。
【答案】(l )某枝已经达到其范围内的最优解; (2)某枝域内没有可行解时,即是不可行域; (3)某枝所得数据不优于当前最优解时。
三、计算题
7. 某公司在某地区采矿,拟建采矿点共有五个K 1、K 2、K 3、K 4和K 5,其相互之间距离如图所示。 该公司拟建四个冶炼车间F 1、F 2、F 3和F 4,其相互之间距离如图所示。所有采矿点所采的矿石都要通过公路运 往冶炼车间。采矿点K5与主干公路相连。其到两个公路连接点G 1和G 2的距离分别为15公里、8公里。冶炼车间F 4与主干公路相连,其到两个连接点G 3和G 4的距离分别为5公里、4公里。四个公路连接点G 1、G 2、G 3和 G 4之间都己经有公司相连,其距离如图所示。由于修建公路的费用非常巨大,所以公路建设方案必须保证建设 线路最短。同时,为了节省运费,矿石运距要尽可能缩短。请用图论的方法找出五个拟建采矿点之间的公路线路 建设最优方案,找出四个拟建冶炼车间之间的公路线建设最优方案,并指出矿石如何进行调运。
图
【答案】五个拟建采矿点之间,寻找最优建设方案,即寻求各点至ks 的最短距离。 采用逐
次逼近法计算根据方程
开始令
距离。则有:
,即k 5与k j 无点时即直接连接时的
所以最优建设方案如图所示
图
最短建设路线1.1km.
同理,可得四个拟建冶炼车间之间的公路线建设最优方案是:
图
建设最短公路线0.8+0.6+0.7=2.1km 同理可知,从K5到F4的最短距离为K5一一G2一一G4一一F4 L=8+90+8=l06km