山东科技大学本科毕业设计（论文）

??'C,?D'?

:?7:00,12:00?,?12:00,17:00?,?17:00,22:00?,?22:00,27:00?,?27:00,32:00?

图4.1.3

（3）比较?A,?B及??A,?B?,我们发现?7:00,10:00?在?6:00,11:00?之内;

''??25

山东科技大学本科毕业设计（论文）

?17:00,20:00?在?16:00,21:00?之内。这说明若A站在6:00及16:00开出两列

货车，则该两列货车在到达B站前，必会被客车撞上。故这两次货运列车是不可行的。这表示在以货运列车的运行时刻为基础的网络图（图4.1.3）中为（A,6:00）及（A，16:00）两节点前未引出水平方向的直线弧。该图的各个节点中仅注明货运列车从该站开出或到达该站的时刻，站名省略了。

00?在?9:00,13:00?之内；比较?B,?C及??B,?C?,我们发现?7:00,12：''???20:00,22:00?在?19:00,23:00?之内，其在图4.1.3中的表示同前。

00,18:00?之内； 比较?C,?D与??C,?D?,我们发现?12:00,17:00?在?11：''???22:00,27:00?在?21:00,28:00?之内，其在图3中的表示同前。

（4）图4.1.3中各水平方向的直线弧的容量均为1。如前所述，它表示在该时间内，货车在相邻两站的行程中不会被客车追上，故可顺利地到达前方车站。垂直方向的直线弧的通量表示各站的岔道数。

（5）做网络的发点vs，并从vs向A站的各状态节点作辅助弧，辅助弧的容量等于以A站的各状态节点为起点的各弧的容量的总和。作网络的收点vt，并从D站的各状态节点向vt作辅助弧。辅助弧的容量等于以D站个状态节点为终点的各弧的容量总和。

（6）求图4.1.3所示容量网络的最大流

Ⅰ）以零流f={0,0,…………0}为初始流，但图4.1.3的各弧旁省略了零流量。

Ⅱ）以vij表示图3中第i行第j列的节点。用Ford-Fulkerson标号法求得以下增广链并按?值进行调整。

①vs(0,?*) v1,1(vs,6) v1,2(v1,1,1) v1,3(v1,2,1) v1,4(v1,3,1)

26

山东科技大学本科毕业设计（论文）

v1(v1,4,1) ??1 ②vs(0,?) v2,1(v1,6) v2,2(v2,1,1) v2,3(v2,2,1) v3,3(v2,3,1) v3,4(v3,3,1) v1(v3,4,1) ??1 ③vs(0,?) v3,1(vs,6) v3,2(v3,1,1) v4,2(v3,2,1) v4,3(v4,2,1) v4,4(v4,3,1) ④vs(0,?) vt(v5,4,1) ⑤vs(0,?) v6,4(v6,3,1)

vt(v6,4,1) ⑥vs(0,?) v8,3(v7,3,1)

v8,4(v8,3,1) ⑦vs(0,?) v9,3(v9,2,1)

v9,4(v9,2,1) ⑧vs(0,?) v10,4(v10,3,1)

vt(v10,4,1) v1(v4,4,1) ??1

v5,1(vs,6) v5,2(v5,1,1) v5,3(v5,2,1) v5,4(v5,3,1) ??1 v6,1(vs,6) v6,2(v6,1,1) v6,3(v6,2,1)

??1 v7,1(vs,6) v7,2(v7,1,1) v7,3(v7,2,1)

vt(v8,4,1) ??1 v8,1(vs,6) v8,2(v8,1,1) v8,2(v8,2,1)

v9,4(v9,3,1) vt(v9,4,1) ??1 v10,1(vs,6) v10,2(v10,1,1) v10,3(v10,2,1)

??1

27

山东科技大学本科毕业设计（论文）

⑨vs(0,?) v11,1(vs,6) v11,2(v11,1,1) v11,3(v11,2,1)

v11,4(v11,3,1)

vt(v11,4,1) ??1 ⑩vs(0,?) v12,1(vs,1,6) v12,2(v12,1,1) v12,3(v12,2,1)

v12,4(v12,3,1)

vt(v12,4,1) ??1 以上10条增广链的调整量均为??1。用它对初始流（零流）进行调整后，结果如图4.1.3所示。若对现行流继续标号，则只有A站的12个状态节点获得标号，即标号中断，不能延伸达vt。故现行流即为最大流，其流量

v(f)?fs,(1,1)?fs,(2,1)?fs,(3,1)?fs,(5,1)?fs,(6,1)?fs,(7,1)?fs,(8,1)?fs,(10,1)?fs,(11,1)?fs,(12,1)?1?1?1?1?1?1?1?1?1?1?10

结论 在本问题所给条件下各车站一昼夜中能开出的最多货运列车数位10列。

现由图4.1.3将A站以昼夜中能开出的10列货车的运行时刻及调度情况阐述如（货车一昼夜中在其他各站点的运行及调度情况可由同图作类似阐述）

①在0:00,8:00,10:00,18:00,20:00,22:00时刻所开出的货车在各站点均畅通。

②在2:00开出的货车，11:00到达C站时须在岔道内停留到13:00方可继续前行。

③在4:00开出的货车，9:00到达B站时，须在岔道内停留到11:00方可继续前行。

④在12:00开出的货车，21:00到达C站时，须在岔道内停留到23:00方可

28

山东科技大学本科毕业设计（论文）

继续前行。

⑤在14:00开出的货车，19:00到达B站时，须在岔道内停留到21:00方可继续前行。

至此已求得一昼夜中从A站开出的10次货运列车的最优调度及最优运行时刻表。

仿此，由图4.1.3可求得从其他各站点开出货车的最优调度及最优运行时刻表。

4.1.4 问题总结

本问题看似简单，是个追赶问题，只要计算出货车与客车在两站之间的运行时间即可控制货车的开出时间，其实不然，此问题是在追赶问题的基础上求最多可开出的货车辆数，我们把该问题转化成为最大流问题，应用Ford-Fulkerson标号法解决了这一问题。通过对算法的分析求解制定出了货车运行的最大数量并列出货车运行时间表，可见最大流算法的有效性和实用性。

29