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

一、计算题

1． 设D=（W ，A ，C ）是一个网络。证明:如果D 中所有弧的容量c ij 都是整数，那么必存在一个最大流

初始号为:

。对于弧。 ，v j 的标号为:，因为c ij 均为整数，所以最终得至。调整量【答案】证明:将该问题转化为网络最大流的问题，并由寻求最大流的标号法进行求解。 ; 对于弧，v j 的标也为整数。故

标号最终结果，得最大流f 必为整数。

2． 下表给出了12种工件在设备A 和B 上的加工时间，试求:

（l ）若所有工件都先在设备A 上加工，再在设备B 上加工，试确定使总加工时间最短的工件加工顺序，并计算总加工时间;

（2）若工件8~12先在设备B 上加工，再在设备A 上加工，其他条件同上，试设计一启发式算法，以计算最小总加工时间和安排相应的工件最优加工顺序。

表

【答案】（l ）采用启发式算法进行计算，计算过程如下表所示。

由上表可以看出，总加工时间最短的工件加工顺序为 4→8→0→5→1→2→7→6→9→1→12→3 总加工时间为（2+3+3+4+6+8+12+7+9+5+10+11）+4=84。

（2）可设计如下启发式算法: ①

②

③

④将A j ，B j 删去，即不再考虑己排好加工顺序的工件j ；

⑤转入步骤②，直至步骤②中的工件加工时间表变成空集。

故设备A 最优加工顺序为7→2→5→6→l →3→4→12→9→1→10→8

设备B 最优加工顺序为12→9→11→10→8→7→2→5→6→1→3→4

总加工时间为（12+8+4+7+5+11+2）+（10+9+6+3+3）=49+31=80。

3． 现有某集团公司下属甲、乙、丙、丁、戊五个生产企业，生产同一种产品，价格、质量都相同。需要供 应A 、B 、C 三个地区。单位运输费用、各企业的产量、各地区的需求如表所示。其中B 地区的需求必须满足。集团公司的目标是使总运输费用最低。

试求解这个运输问题。

表

【答案】这是一个产销不平衡的运输问题，销量大于产量，构造一个虚拟的产地己，其产量为10。

，产地己到其由于B 地区的需求必须满足，所以产地己到B 地区的单位运价为M （无穷大的数）

他地区的单位运价为0。建立产销平衡表如表所示:

表

首先，用伏格尔法寻找得到初始基可行解。

表

用位势法计算各空格处的检验数为:

从上表中可以看出，各非基变量的检验数均大于0，所以己求得最优解。总运费为330。

4． 有10个城市，它们在坐标系中的位置如表所示，试完成以下工作。

（l ）用C 一W 节约算法求出经过每个城市一次且仅一次的一条最短线路。

（2）用Norback 和Love 提出的几何法，求出经过上述每个城市一次且仅一次的最短线路。 （3）比较上述两种方法得出的结果，并设计一种启发式方法，对上述较差的结果进行改进。

表

【答案】（l ）计算各点对之间的欧氏距离c ij ，计算结果如表所示。

表