产地(1 x6销地 2 可以找到条有向路 P4(V1,V2V3V4V6) 能再增加1吨运输量 产地(8 (6)销地 5
16 可以找到一条有向路 ： P 4 （ V 1 , V 2 , V 3 , V 4 , V 6 ） 能再增加 1吨运输量 1 2 3 4 5 4 4 8 4 2 产地 6 销地 12 7 3 42 211 2 3 3 1 1 2 3 4 5 4 4 8 4 2 产地 6 销地 12 7 3 32 21 2 2 3
4 产地 6)销地 5(v1,v3v4,V6 也可再增加1吨运输量 2 4 产地(1 8 6)销地 思考:还能再增 加运输量吗? 3
17 P 5 （ V 1 ， V 3 ， V 4 ， V 6 ） 也 可再增加 1吨运输量 1 2 3 4 5 4 4 8 4 2 产地 6 销地 12 7 3 43 212 2 4 3 1 思考：还能再增 加运输量吗？ 1 2 3 4 5 4 4 8 4 2 产地 6 销地 12 7 3 42 211 2 3 3 1
观察有向路P6(V1,V3,V2,V4,V6) 口正方向的边(V1,V3)、(V2,V)、(V4,V)都可 增加运输量; 口反方向的边(V3,V2)的运输量为1; 产地(1 6)销地 3
18 ◼ 观察有向路P6（V1，V3，V2，V4，V6） 正方向的边（V1，V3）、（V2，V4）、（V4，V6）都可 增加运输量； 反方向的边（V3，V2）的运输量为1； 1 2 3 4 5 4 4 8 4 2 产地 6 销地 1 2 7 3 4 3 2 1 2 2 4 3 1
如果将反向边(V3,V2)的运量调到正向边(V2,V4)上 去完成,这样有向路P。(Ⅵ1,V3,V2,V4,V6)的运量可增 加1 2 产地 6)销地 5 3 2 反向边上流量含义: 节点2需要发出1吨货物,而节点3需要接收1吨货物 可以让该路径上的节点3前一条边增加流量,保持节点3的总进 入流量不变; 同时让该路径上节点2之后的边上也增加流量,保持节点2的出 发流量不变。 19
19 ◼ 如果将反向边（V3，V2）的运量调到正向边（V2，V4）上 去完成，这样有向路P6（V1，V3，V2，V4，V6）的运量可增 加1。 1 2 3 4 5 4 4 8 4 2 产地 6 销地 1 2 7 3 4 3 2 1 2 2 4 3 1 反向边上流量含义： • 节点2需要发出1吨货物，而节点3需要接收1吨货物； • 可以让该路径上的节点3前一条边增加流量，保持节点3的总进 入流量不变； • 同时让该路径上节点2之后的边上也增加流量，保持节点2的出 发流量不变
这里要注意,节点4 到节点6一定还应该 2"(4 有剩余的运输能力。 产地G48 6)销地 2 再找不到可“改进”的 有向路了,该交通网的 最大运输量为8吨。 产地(1 6)销地 3 2
20 这里要注意，节点 4 到节点 6一定还应该 有剩余的运输能力。 再找不到可 “改进 ” 的 有向路了，该交通网的 最大运输量为 8吨。 1 2 3 4 5 4 4 8 4 2 产地 6 销地 12 7 3 44 312 2 5 3 0 1 2 3 4 5 4 4 8 4 2 产地 6 销地 12 7 3 43 212 2 4 3 1