5 13

0 0 1 12 5 2 4 3 12 12 9 10 22 22 4 9 0 5 5 22 27 31 31 6 4 关键线①—③—④—⑥ 计划工期31

2．某项工程各工序的工序时间及所需要的人数如表所示，现有人数为14人，试确定工程完工时间最短的各工序的进度计划。

工序代号 A B C D E F G H 紧前工序 － － － － B C F，D E，G 工序时间（天） 4 2 2 2 3 2 3 4 需要人数 11 5 8 6 10 9 4 2

列出所有路线共四条

① ⑥ 需4天

① ④ ⑤ ⑥ 需9天 ① ② ③ ⑤ ⑥ 需11天 ① ③ ⑤ ⑥ 需9天

9

故关键路线为

① ② ③ ⑤ ⑥ 需11天 具体时间－资源的最优安排为

0～2天 做工序C需8人 同时做工序D需6人 2～4天 做工序B需5人 同时做工序F需9人 4～7天 做工序E需10人 同时做工序G需4人 7～11天 做工序A需11人 同时做工序H需2人

九．最小支撑树和最大流问题

1. 自已选用适当的方法，对下图求最小(生成树)。 V1

2. 用标号法求下列网络V1→V7的最短路径及路长。

V1

5 4 3 1 V6

V2 1 V3 5 3 6

1

3

V5

2

V3

6 5 V2 3 3 3 V5 V4 5 2

3

V3

V5

V6

V1

V6 L=13

V2

V4

7 V7

7 V4

答案：最短路径：V1→V3→V5→V6→V7 L=10

5. 求如图所示的网络的最大流和最小截集(割集)，每弧旁的数字是（cij , fij ）。（15分）

10

V1 (5,0) (3,3) (3,3)

VS （4,1） V2

(4,0) (9,3)

(8,4)

V3 Vt (6,0) 最大流为：14

V1 (5,3) (3,3) (3,0) V2 Vs (4,4) (4,1) (9,7) (8,8) Vt V3 (6,6)

7. 求如图所示的网络的最大流和最小截集(割集)，每弧旁的数字是（cij , fij ）。（10分） V1 (4,4 ) V3

(9,5) (6,3)

VS (3,1) (3,0) (4,1) Vt

(5,3) (7,5) V2 (5,4) V4

解：

V1 (4,4) V3 (9,7) (6,4) (3,2) (4,0) Vs Vt (5,4) (7,7)

V2 (5,5) V4 最大流＝11

11