运筹学11-图与网络.ppt

如图v2是已经标记的点, v3是未标记的点 (v3 ,v2)是非零流弧, v3可以标记: [v2-,e3] e3=min{e2, x32}=min{11,3} [-, ∞] [vs+, 11] [v2-, 3] [v2+, 4] [v3+, 3] [v5+, 4] vs 11 5 4 3 15 vt v5 v3 v4 v2 (4) (9) (1) (5) (7) (5) (8) 10 7 9 (3) 6 vt已经标记, 找到流量增广链。 vs 10 11 5 6 4 7 3 9 15 vt v5 v3 v4 v2 (4) (9) (3) (1) (5) (7) (5) (8) [-, ∞] [vs+, 11] [v2-, 3] [v2+, 4] [v3+, 3] [v5+, 4] 正向流流量增加et，逆向流流量减少et 调整后流量 f=17 vs 10 11 5 4 3 15 vt v5 v3 v4 v2 (8) (9) (3) (1) (5) (7) (9) (8) (4) 9 6 7 [-, ∞] [vs+, 7] [v2-, 3] [v3+, 1] [v3+, 3] [v4+, 3] vt已经标记, 找到流量增广链。 正向流流量增加et=3，逆向流流量减少et 调整后流量 f=20 vs 10 11 5 4 3 15 vt v5 v3 v4 v2 (11) (9) （0） (4) (5) (7) (9) (11) (4) 9 6 7 Vs，v2已经标记，其余点不能标记，已经最优 最大流量 fmax=20 vs 10 11 5 4 3 15 vt v5 v3 v4 v2 (11) (9) (0) (4) (5) (7) (9) (11) (4) 9 6 7 [-, ∞] [vs+, 4] 思考：影响网络最大流的网络瓶颈在那里？ 算法的步骤流程总结 ①为网络分配初始流xij标在图中弧旁的( )内 ②寻求增广链，若不存在，则已最优, 否则 ③在增广链上调整流量，产生新的可行流。 重复②、③两步，直到最优。 第十一章习题 P290 1(c)、 2 第三步 对T(vj)求 v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 注意观察：V2的后向连接线 后向连接线的连接点 k=2, 不是最优，继续 v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 在所有的T(vj)中确定最小的 v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 注意观察：V3的后向连接线 后向连接线的连接点 k=3, 不是最优，继续 v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 k=5, 不是最优，继续 v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 k=6=n, 已经是最优。如果希望计算v1到v4的最短距离，继续 v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 最短路问题实例 (p279) （设备更新问题）． 某企业使用一台设备，这种设备在一定年限内随着时间推移逐渐损坏，设备使用的时间越长，每年的维修费用就越大，在每年年初，管理人员需要决定是购置新设备，还是继续使用旧的设备．若购置新设备，就要支付一定的购置费用；若继续使用旧设备，则需支付一定的维修费用。现在的问题是如何制定一个n年之内的设备更新计划，使得总的支付费用最少。我们用一个五年之内要更新某种设备的计划为例，若己知该种设备在各年年初的价格为下表 第一年 第二年 第三年 第四年 第五年 11 11 12 12 13 使用不同时间(年)的设备所需要的维修费用为下表 使用年数 0—1 1—2 2—3 3—4 4—5 维修费用 5 6 8 11 18 求：5年内，哪些年初购置新设备，使5年内的总费用最小。 解：（1）分析：可行的购置方案（更新计划）是很多的， 如： 1） 每年购置一台新的，则对应的费用为： 11+11+12+12+13 +5+5+5+5+5 = 84 2 )第一年购置新的，一直用到第五年年底，则总费用为： 11+5+6+8+11+18 = 59 显然不同的方案对应不同的费用。 第i年度 1 2