运筹学复习题

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

联系客服:779662525#qq.com(#替换为@)