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

山东科技大学本科毕业设计(论文)

为了充分发挥该铁路线的货运能力,需要排定一张最优的货车运行时刻表,即要求每天发出最多的货运列车且不干扰已排定的客运列车。 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

山东科技大学本科毕业设计(论文)

?A=0:00,2:00,4:00…… ?B=5:00,7:00,9:00…… ?C=9:00,11:00,13:00……

?D=16:00,18:00,20:00……

于是货车在相邻两站的运行时间为(若不受客车干扰):

??A,?B?:?0,5?,?2,7?,?4,9?,?6,11?,?8,13?,?10,15?,?12,17?,?14,19?,?16,21?,?18,23?,?20,15?,?22,27???(25点即翌日1点,余类推)

??B,?C?:?5,9?,?7,11?,?9,13?,?11,15?,?13,17?,?15,19?,?17,21?,?19,23?,?21,25?,?23,27?,?25,29?,?27,31??

??C,?D?:?9,6?,?11,18?,?13,20?,?15,22?,?17,24?,?19,26?,?21,28?,?23,30?,?25,32?,?27,34?,?29,36?,?3??(2)令?A,?B,?C,?D为客车从某站开出或到达某站的时刻,依题意:

''''?A'=2:00,7:00,12:00,17:00,22:00 ?B'=5:00,10:00,15:00,20:00,25:00(即1:00) ?C'=7:00,12:00,17:00,22:00,27:00(即3:00)

?D'=12:00,17:00,22:00,27:00(即3:00),32:00(即8:00)

于是客车在相邻两站之间的运行时间为:

??

'A,?B:?2:00,5:00?,?7:00,10:00?,?12:00,15:00?,?17:00,20:00?,?22:00,25:00?'???

'B,?C:?5:00,7:00?,?10:00,12:00?,?15:00,17:00?,?20:00,22:00?,?25:00,27:00??24