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

一、简答题

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

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

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

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

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

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

2． 试将Norback 和love 提出的几何法与C 一W 节约算法进行比较。

【答案】（1）几何法:首先找出凸包，然后考查以不在旅行线路上的点为角顶，以线路上的点的连线为对边的角的大小，选出最大者所对应的角顶，插入到旅行线路中，反复进行直至形成哈密尔顿回路。

（2）C 一W 节约算法:首先以某一点为基点，确定初始解，然后考查基点之外的其它点的连线所构成的弧的 节约值的大小，选出节约值最大者所对应的弧，插入到旅行线路中，直至旅行线路中包含所有的点。

3． 试写出求解最短径路的Dijkstra 算法的步骤。

【答案】Dijkstra 算法的步骤为:

（l ）给v s 以p 标号，P （v S ）二0，其余各点均给T 标号，T （v i ）=+∞。

（2）若v i 点为刚得到P 标号的点，考虑这样的点v i ，（v i ，vj ）属于E ，且v i 为T 标号。对v j 的T

，p （v i ）+lij ] 标号进行如下修改:T （v j ）=min[T（v i ）

（3）比较所有具有T 标号的点，把最小者改为P 标号，即:

4． 试写出M/M/1排队系统的Little 公式。

【答案】M/M/1排队系统的Little 公式为

当存在两个以上最小者时，可同时改为P 标号。若全部点均为P 标号时停止，否则用代V i 转回（2）。

5． 简述目标规划单纯形法求解的基本思想。

【答案】第一步，建立初始单纯形表，在表中将检验数行按优先因子个数分别列成K 行，置k=l; 第二步，检查该行中是否存在负数，且对应的前k 一1行的系数是零。若有负数取其中最小者对应的变量为换入变量，转第三步。若无负数。则转第五步;

第三步，按最小比值规则确定换出变量，当存在两个和两个以上相同的最小比值时，选取具有较高优先级别 的变量为换出变量;

第四步，按单纯形法进行基变换运算，建立新的计算表，返回第二步;

第五步，当k=K时，计算结束。表中的解即为满意解。否则置k=k+l，返回到第二步。