2016年南京大学859系统分析与集成专业基础之《运筹学教程》考研冲刺密押卷及答案
● 摘要
目录
2016年南京大学859系统分析与集成专业基础之《运筹学教程》内部密押卷及答案（一）.... 2
2016年南京大学859系统分析与集成专业基础之《运筹学教程》内部密押卷及答案（二）.. 10
2016年南京大学859系统分析与集成专业基础之《运筹学教程》内部密押卷及答案（三）.. 19
2016年南京大学859系统分析与集成专业基础之《运筹学教程》内部密押卷及答案（四）.. 28
2016年南京大学859系统分析与集成专业基础之《运筹学教程》内部密押卷及答案（五）.. 38
一、简答题
1． 试说明C 一W 节约算法的基本思想，你认为还可用它解决哪些方面的问题? 举例加以说明。
【答案】（1）C 一W 节约算法的基本思想（以旅行商问题为例）:优先考虑将节约值最大的弧插入到旅行线路中， 这样在满足访问若干城市各一次且仅一次的条件下，最大限度地缩短了路程。 （2）举例。运用C 一W 节约算法:设n 个不同用户为n 个点，维修点为基点，n 个用户点中从点i 到点j 的 长度为工人骑摩托车的交通时间加上点i 与点j 维修时间总和的一半。优先考虑将节约值最大的长度加入工作线路中去进行迭代。
2． 说明本书所述货运车辆优化调度算法的原理和求解步骤，并绘出求解过程框图。请简要回答以下问题。
（1）若有两种车型的车可用，书中提出的模型应怎样修改? 在书中所提算法的启发下，试拟定出一套求解的迭代步骤。
（2）你认为应如何将书中提出的模型和算法推广到多目标的情形。
【答案】①货运车辆优化调度算法的原理:最小费用最大流原理。求解步骤为:a. 仅考虑重载点，运用表上作业法求出最优解作为原问题的可行解; b. 进行解的扩展和解的收缩，直至得到可接受的可行解; c. 以该可接受的可行解为依据确定初始行车线路; d. 根据具体约束条件进行调整，直至得到最优行车路线。求解过程框图如图所示。
图
（2）修改后的迭代算法即神经网络（neural networks）算法。
①建立结合矩阵:将车辆经过的点包括源点看成神经网络的结点，即神经元，令神经元数目为N ; i 神经元 和j 神经元的结合权值为，j 神经元的输出为r j 。
②将车辆调度的各种约束条件转化为约束能量函数为E 约。
，且r i （t ）只能取0或1，令神经元i 的阈值为③神经网络计算:令时刻t 神经元i 的输出为r i （t ）
Q i ，则输出能量
为
，其中，因此总的能量函数
为，则该网络相对处于稳定状态。由于如
果，且E 有界，系统必
趋向一个比较好的稳定状态，再把此稳定状态时r i （t ） 形成换位阵中元素为l 的结点连接起来，形成所求的最满意车辆调度线路。
④根据所形成的最满意线路来选择车辆调度方案。
（3）推广到多目标情形:车辆优化的目标函数可以有很多个，如总运费最小，司机总的驾驶时间最短，车 辆满载行驶的时间最长等; 而约束条件，如路径的最大输入输出流、车载量、发车和收车约束等。也可以加入惩 罚算子将约束条件转化为惩罚函数，利用多目标方法进行求解。
二、计算题
3． 已知下列资料，如表所示。
要求:（1）绘制网络图;
（2）计算各项时间参数;
（3）确定关键路线。
【答案】（1）由题意绘制网络图如图所示。
（2）事项最早时间见图“口”中的数字，事项最迟时间见图中“△”中的数字。
图
（3）总时差为零的工序为关键工序，
所以关键路线为
如图所示。
4． 某厂需用配件数量r 是一个随机变量，其概率服从泊松分布，时间t 内的需求概率为
平均每日需求为1（ 平均拖后时间天，方差。在生产循环周期内存储费C 1=1.25元，缺货费C 2=10元，装）备货时间为天的的概率服从正态分布
，配费 C 3=3元。问两年内应分多少批订货? 每次批量及缓冲存储量各为何值才能使总费用最小? 【答案】
下面计算L 及B ，各步算出的数值列于表中。