选择路为V1 →V2 →V5 →V6 。弧(V1 ,V2)的顺流流量为6,决定了pf=6,改
进的网络流量图如图所示:
V2 6 0 6 0 6 5 5 6 0 第二次迭代 后的总流量 0 0 0 8 4 5 2 0 0 6 V5 12 6 0 6 5 0 6 11→ V4 V1 V6 →11 V3 第三次迭代:选择路为V1→V4 →V6 。弧(V1 ,V4)的顺流流量为6, 决定了pf=6,改进的网络流量图如图所示:
V2 6 0 4 0 6 0 5 5 6 6 0 0 0 5 2 0 6 V5 6 6 17→ V4 V1 6 0 5 0 6 V6 17→ 第三次迭代 后的总流量 第四次迭代:选择路为V1→V3→V4 →V2→V5→V6 。弧(V2 ,V5)的顺流流量 为2,决定了pf=2,改进的网络流量图如图所示:
V2 6 0 2 0 2 4 0 5 3 5 7 4 6 0 6 2 0 2 5 0 5 第四次迭代 后的总流量 0 6 8 0 V3 V5 6 4 6 8 6 V4 19→ V1 V6 19→ V3 第五次迭代:选择路为V1→V3→V4→V5→V6 。弧(V1 ,V3)的顺流流量为3, 决定了pf=3,改进的网络流量图如图所示:
V2 6 0 2 0 8 3 2 5 2 0 V5 4 1 8 0 5 6 11 22→ V1 0 3 0 7 11 4 1 6 5 2 0 V4 V6 22→ 第五次迭代 后的总流量 V3 在通过第五次迭代后在图中已找不到从发点到收点的一条路上的每一条弧顺流容量都大于零,运算停止。我们已得到此网络的从 V1到V6的最大流量,最大流量为22,也就是公路的最大流量为每小时通过22千辆车。 (16) 最小费用最大流问题
请求下面网路图中的最小费用最大流,图中弧(Vi , Vj)的赋权(Cij , bij),其中Cij为从Vi 到Vj 的流量,bij 为Vi 到Vj 的单位流量的费用。
V2
(5,3)
(2,4)
V4
(2,4)
V1
(4,1)
(1,1)
(1,2)
(1,2)
V6
(5,2)
V3
(3,3)
V5
(17)一台机器、n个零件的排序问题 某车间只有一台高精度的磨床,常常出现很多零件同时要求这台磨床加工的情况,现有六个零件同时要求加工,这六个零件加工所需要的时间如表所示: 零件 加工时间/小时 零件 加工时间/小时 1 1.8 4 0.9 2 2.0 5 1.3 3 0.5 6 1.5 我们应该按照什么样的加工顺序来加工这六个零件,才能使得这六个零件在车间里停留的平均时间为最少?
解:对于一台机器n个零件的排序问题,我们按照加工时间从少到多排出加工零件的顺序就能使各个零件的平均停留时间为最少。 零件 加工时间/小时 停留时间 零件 加工时间/小时 停留时间 3 0.5 0.5 6 1.5 4.2 4 0.9 1.4 1 1.8 6.0 5 1.3 2.7 2 2.0 8 (18)两台机器、n个零件
某工厂根据合同定做一些零件,这些零件要求先在车床上车削,然后再在磨床上加工,每台机器上各零件加工时间如表所示: 零件 车床 磨床 零件 车床 磨床 1 1.5 0.5 4 1.25 2.5 2 2.0 0.25 5 0.75 1.25 3 1.0 1.75 应该如何安排这五个零件的先后加工顺序才能使完成这五个零件的总的加工时间为最少?
解:我们应该一方面把在车床上加工时间越短的零件,越早加工,减少磨床等待的时间,另一方面把在磨床上加工时间越短的零件,越晚加工,也就是说把在磨床上加工时间越长的零件,越早加工,以便充分利用前面的时间,这样我们得到了使完成全部零件加工任务所需总时间最少的零件排序方法。
车床 5 3 4 1 2 磨床 5