选择路为V1 →V2 →V5 →V6 。弧（V1 ，V2）的顺流流量为6，决定了pf=6，改

进的网络流量图如图所示：

V2 6 0 6 0 6 5 5 6 0 第二次迭代 后的总流量 0 0 0 8 4 5 2 0 0 6 V5 12 6 0 6 5 0 6 11→ V4 V1 V6 →11 V3 第三次迭代：选择路为V1→V4 →V6 。弧（V1 ，V4）的顺流流量为6， 决定了pf=6，改进的网络流量图如图所示：

V2 6 0 4 0 6 0 5 5 6 6 0 0 0 5 2 0 6 V5 6 6 17→ V4 V1 6 0 5 0 6 V6 17→ 第三次迭代 后的总流量 第四次迭代：选择路为V1→V3→V4 →V2→V5→V6 。弧（V2 ，V5）的顺流流量 为2，决定了pf=2，改进的网络流量图如图所示：

V2 6 0 2 0 2 4 0 5 3 5 7 4 6 0 6 2 0 2 5 0 5 第四次迭代 后的总流量 0 6 8 0 V3 V5 6 4 6 8 6 V4 19→ V1 V6 19→ V3 第五次迭代：选择路为V1→V3→V4→V5→V6 。弧（V1 ，V3）的顺流流量为3， 决定了pf=3，改进的网络流量图如图所示：

V2 6 0 2 0 8 3 2 5 2 0 V5 4 1 8 0 5 6 11 22→ V1 0 3 0 7 11 4 1 6 5 2 0 V4 V6 22→ 第五次迭代 后的总流量 V3 在通过第五次迭代后在图中已找不到从发点到收点的一条路上的每一条弧顺流容量都大于零，运算停止。我们已得到此网络的从 V1到V6的最大流量，最大流量为22，也就是公路的最大流量为每小时通过22千辆车。 (16) 最小费用最大流问题

请求下面网路图中的最小费用最大流,图中弧(Vi , Vj)的赋权（Cij , bij），其中Cij为从Vi 到Vj 的流量，bij 为Vi 到Vj 的单位流量的费用。

V2

（5，3）

（2，4）

V4

（2，4）

V1

（4，1）

（1，1）

（1，2）

（1，2）

V6

（5，2）

V3

（3，3）

V5

（17）一台机器、n个零件的排序问题 某车间只有一台高精度的磨床，常常出现很多零件同时要求这台磨床加工的情况，现有六个零件同时要求加工，这六个零件加工所需要的时间如表所示： 零件 加工时间/小时 零件 加工时间/小时 1 1.8 4 0.9 2 2.0 5 1.3 3 0.5 6 1.5 我们应该按照什么样的加工顺序来加工这六个零件，才能使得这六个零件在车间里停留的平均时间为最少？

解：对于一台机器n个零件的排序问题，我们按照加工时间从少到多排出加工零件的顺序就能使各个零件的平均停留时间为最少。 零件 加工时间/小时 停留时间 零件 加工时间/小时 停留时间 3 0.5 0.5 6 1.5 4.2 4 0.9 1.4 1 1.8 6.0 5 1.3 2.7 2 2.0 8 （18）两台机器、n个零件

某工厂根据合同定做一些零件，这些零件要求先在车床上车削，然后再在磨床上加工，每台机器上各零件加工时间如表所示： 零件 车床 磨床 零件 车床 磨床 1 1.5 0.5 4 1.25 2.5 2 2.0 0.25 5 0.75 1.25 3 1.0 1.75 应该如何安排这五个零件的先后加工顺序才能使完成这五个零件的总的加工时间为最少？

解：我们应该一方面把在车床上加工时间越短的零件，越早加工，减少磨床等待的时间，另一方面把在磨床上加工时间越短的零件，越晚加工，也就是说把在磨床上加工时间越长的零件，越早加工，以便充分利用前面的时间，这样我们得到了使完成全部零件加工任务所需总时间最少的零件排序方法。

车床 5 3 4 1 2 磨床 5 3 4 1 2 等待时间

（19）在一台车床上要加工7个零件，下表列出它们的加工时间，请确定其加工顺序，以使各零件在车间里停留的平均时间最短。 零件 1 2 3 4 5 6 7 Pi 10 11 2 8 14 6 5 解：各零件的平均停留时间为： 6P1?5P2?4P3?3P4?2P5?P6

6由此公式可知，要让停留的平均时间最短，应该让让加工时间越少的零件排在越前面，加工时间越多的零件排在后面。

所以，此题的加工顺序为：3，7，6，4，1，2，5

(20) 有7个零件，先要在钻床上钻孔，然后在磨床上加工，下表列出了各个零件的加工时间，确定各零件加工顺序，以使总加工时间最短。 零件 1 2 3 4 5 6 7 钻床 6.7 2.3 5.1 2.3 9.9 4.7 9.1 磨床 4.9 3.4 8.2 1.2 6.3 3.4 7.4

解：此题为两台机器，n 个零件模型，这种模型加工思路为：钻床上加工时 间越短的零件越早加工，同时把在磨床上加工时间越短的零件越晚加工。 根据以上思路，则加工顺序为：2，3，7，5，1，6，4。

（21）根据下表绘制计划网络图

V2 a V6 b V4 f h d V1 V7 i V5

c V3 解：

e j g V3 c d

V4

f

a

V1

b

V2

e

V6

g V5

(22)对21题，通过调查与研究对完成每个活动的时间作了3种统计，如表所示，请求出每个活动的最早开始时间，最晚开始时间，最早完成时间，最晚完成时间；找出关键工序；找出关键路线；并求出完成此工程项目所需平均时间；如果要求我们以98%的概率来保证工作如期完成，我们应该在多少天以前就开始这项工作。 活动（工序） 乐观时间/天 最可能时间/天 悲观时间/天 a 1.5 2 3 b 3 4 6 c 3.5 5 6 d 3 4 5.5 e 2.5 3 4 f 1 2 4 g 2 4 5 解：显然这三种完成活动所需时间都具有一定概率，根据经验，我们可以假定这