信息与计算科学毕业论文最大流问题及应用

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

为了充分发挥该铁路线的货运能力，需要排定一张最优的货车运行时刻表，即要求每天发出最多的货运列车且不干扰已排定的客运列车。 4.1.2 问题分析

求解这个问题较为复杂，但可将其转化为网络最大流问题。 （1）设A、B两市及其间的车站共P个。每个车站有nk条岔道（k=1,2,3…P）,可停放nk列列车。从第k站到第k+1站的行车时间货车为tk个小时，客车为tk' 个小时。

设?k为火车到达第k站并从第k站开出的时刻 设?k为客车到达第k站并从第k站开出的时刻 设?k?1为货车到达第k+1站并从第k+1站开出的时刻 设?k?1为客车到达第k+1站并从第k+1站开出的时刻 于是显然有?k?1??k?tk ?k'?1??k'?tk'

（2）若??k,?k?1?与?',?'k?1有公共部分，则称??k,?k?1?与?',?'k?1是相交的，否则成为不相交的。显然有当只??k,?k?1?与?',?'k?1相交情况下客车才有可能（并非必然）在第k站与地k+1站间追上货车。

''（3）在??k,?k?1?与?',?'k?1相交情况下，?k，?k?1，?k，?k?1间的相交关系

''????????可由图4.1.1所示：

20

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

图4.11

情况Ⅵ为途中货车追上了客车故不符合题意。情况Ⅰ与情况Ⅱ中在第k站与第k+1站间不发生在途中追上货车。而在情况Ⅲ中必发生在第k站与第k+1

21

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

站间客车在途中追上货车。 于是有下列结论：

若??'k,?'k?1?在??k,?k?1?内，即?'k??k及?'k?1??k?1，则在第k站与第k+1站必发生客车追上货车情况。否则在第k站与第k+1站之间不发生客车追上货车情况。 （4）绘制网络图

用（k，?k）表示第k站处于时刻?k的状态，如在?k=2.3在（k，2.6），（k，6.6）状态开出的货车不会再途中被客车追上，则在图中表现为（k，2.6）及（k，6.6）两节点为起点的两条水平方向的直线弧，而在（k，4.6）状态下开出的货车会在途中被客车追上，则不能从该点引出水平方向的直线弧（图4.1.2），垂直方向的直线弧并联着同一车站的相邻状态。

22

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

图4.1.2

上图中各弧旁的数字为容量，因铁路线是单向单轨的，故水平方向的弧容量为1，垂直方向的弧的容量为各站的岔道数量，在列出全部状态的网络图中求最大流，此最大流即为允许开出的最多货运列车数。 4.1.3 问题求解

以货运列车的运行时间为基础绘制网络图。

（1）令?A,?B,?C,?D为火车从某站开出或到达某站的时刻。依题意，若不受客车干扰则：

23