当前位置：问答库＞考研试题

一、简答题

1． 对在多台设备上加工多个工件的工件排序问题来说，应如何衡量不同排序方案的优劣? 你认为应有哪 些准则? 这些准则的适用条件是什么? 请举出两个实例加以详细说明。

【答案】（l ）应根据工期最短、成本最低、质量最优等优劣标准来衡量不同排序方案的优劣。 （2）设备充分利用、总加工时间最短等某一或某几种目标函数最优。

（3）每个工件在m 台设备加工都有一定的先后顺序，工件在不同设备的加工顺序不同的情况不作考虑以及 信息掌握情况和资源约束等适用条件。

（4）举例。建筑施工流水作业问题:在不同的施工段上按一定的施工工艺进行施工，而施工工艺又由不同 的施工工序组成，每道施工工序都要消耗一定的人工费用，机械台班和材料费用，并且某些施工工序之间有一定的先后约束关系，如支起模板后才能浇注混凝土，而此问题关注不同施

使整个施工按照最短施工时间保持一定施工节拍进行流工工序如何搭接排序组成一定施工工艺，

水作业，同时消耗人、机、材等资源也合理。

2． 试说明C 一W 节约算法的基本思想，你认为还可用它解决哪些方面的问题? 举例加以说明。

【答案】（1）C 一W 节约算法的基本思想（以旅行商问题为例）:优先考虑将节约值最大的弧插入到旅行线路中， 这样在满足访问若干城市各一次且仅一次的条件下，最大限度地缩短了路程。 （2）举例。运用C 一W 节约算法:设n 个不同用户为n 个点，维修点为基点，n 个用户点中从点i 到点j 的 长度为工人骑摩托车的交通时间加上点i 与点j 维修时间总和的一半。优先考虑将节约值最大的长度加入工作线路中去进行迭代。

3． 说明本书所述货运车辆优化调度算法的原理和求解步骤，并绘出求解过程框图。请简要回答以下问题。

（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）推广到多目标情形:车辆优化的目标函数可以有很多个，如总运费最小，司机总的驾驶时间最短，车 辆满载行驶的时间最长等; 而约束条件，如路径的最大输入输出流、车载量、发车和收车约束等。也可以加入惩 罚算子将约束条件转化为惩罚函数，利用多目标方法进行求解。

4． 在线性规划的灵敏度分析中，当基变量的价值系数变化后，最优表中哪些数据会发生变化，怎样变化。

【答案】基变量的价值系数变化后，可能会引起伏表中基变量检验数的变化。 设Cr 是基变量Xr 的系数。因，当Cr 变化△Cr ，时，就引起C B 的变化，这时有:

可见，当Cr 变化成△Cr 后，最终表中的检验数是:

二、计算题

5． 某工地为了研究发放工具应设置几个窗口，对于请领和发放工具分别做了调查记录。 （l ）以10分钟为一段，记录了100段时间内每段到来请领工具的工人数，如表所示。

表

，如表所示 （2）记录了1000次发放工具（服务）所用时间（秒）

表

试完成下列问题:

（l ）平均到达率和平均服务率（单位:人/分钟）。

（2）利用统计学的方法证明:若假设到来的数量服从参数兄=1.6的泊松分布，服务时间服从参 数刀=0.9 的负指数分布，这是可以接受的。

（3）这时只设一个服务员是不可行的，为什么? 试分别就服务员人数c=2，3，4各种情况计算 等待时间W q （注 意用下表的数据）。 多服务台的数值表