2017年北华大学运筹学(同等学力加试)考研复试核心题库
● 摘要
一、简答题
1． 试将Norback 和love 提出的几何法与C 一W 节约算法进行比较。
【答案】（1）几何法:首先找出凸包，然后考查以不在旅行线路上的点为角顶，以线路上的点的连线为对边的角的大小，选出最大者所对应的角顶，插入到旅行线路中，反复进行直至形成哈密尔顿回路。
（2）C 一W 节约算法:首先以某一点为基点，确定初始解，然后考查基点之外的其它点的连线所构成的弧的 节约值的大小，选出节约值最大者所对应的弧，插入到旅行线路中，直至旅行线路中包含所有的点。
2． 试简述求解整数规划模型的分枝定界法剪枝的几种情况。
【答案】（l ）某枝已经达到其范围内的最优解; （2）某枝域内没有可行解时，即是不可行域; （3）某枝所得数据不优于当前最优解时。
二、计算题
3． 有一运输问题，它有3个重载点和2个车场，其运输表如表所示。表中小方框内的数字为两1、2和3三项运输业务的重载里程点 间的车辆空驶距离，（己将装卸车时间折算在内）分别为7，8和9，其他有关情况如表中所示。此外，要求车辆的每条行车路线总长度（包括重驶、空驶及装卸车所用时间的折算长度）L 在45~ 60之间。试用本章给出的车辆优化调度启发式算法，求出其满意的可接受可行解，并据此排出行车路线。
表
【答案】（l ）首先只考虑重载点的情况，利用伏格尔法进行求解，并且用位势法进行检验，得到只考虑重载点的最优解为
（2）解的扩展
第 2 页，共 61 页
按照由小到大顺序对
进行调整
（3）解的收缩 因为
所以，不需要进行解的收缩过程。从而得到可行解X （），其非零分量为:
,
（4）安排行车路线
第 3 页，共 61 页
l
以可行解l X （）为依据可安排行车线路，并且考虑到行车路线总长度，安排线路如下。
①通车数目为4，路线为4→1→3→1→5，线路总长为 6+10+12+10+（7×2+9）=60 ∈［45, 60］
②通车数目为3，路线为5→2→1→1→3→5，线路总长为 2+2+4+10+2+（7×2+8+9）=20+31=51 ∈［45, 60］ ③通车数目为3，路线为5→1→2→1→4，线路总长为 14+12+2+8+（7x2+8）=58 ∈［45, 60］
4． 一个小型的平价自选项市场只有一个收款出口，假设到达收款出口的顾客流为泊松流，平均每小时为 30人。收款员的服务时间服从负指数分布，平均每小时可服务40人。
（1）计算这个排队系统的数量指标择:
a ）在收款出口除了收款员外，专顾一名包装员。这样可以使每小时的服务率从40人提高到60人。
b ）增加一个收款出口，使排队系统变成M/M/2系统，每个收款出口每小时的服务率仍为40人。
请对这两个排队系统进行评价，并作出选择。 【答案】
（2）顾客对这个排队系统抱怨化费时间太多，商店为了改进服务，准备对以下两方案进行选
第 4 页，共 61 页
相关内容
相关标签