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