铁路行车组织总复习题及答案(西南交大)

2.在A2站切割,开行列流5,2,3,2,2,0,长程车流或分割,或压缩,得过渡方案②(图2-3-14)。这样调整比过渡方案①净节省60车小时。方案值F节?1660?60?1720(车小时)。

N53?180N52?20450500300125275350200○○○○○○4202404502703157701806300260○△280○360150175○N51?120N50?50N32?110N31?14N30?80N41?15N40?90N20?22改编车数改编能力500350图2-3-14 过渡方案②

2Nt3.考虑到41节?450,值较大,将N51,N31压缩发站与N41合并,开行列流4,1,

结果见图2-3-15,比过渡方案②净节省

3244T集??N51?N31?N41?t节?T集??N51?N32?N31?N30?t节??

?1750?1635?115(车小时)F?1720?115?1835(车小时)

方案值节。

在图2-3-15基础上经过多次试调,再也找不到节省车小时更多的方案,故图2-3-15所示即为最优方案。 N53?18N52?20450500300125275350200○○○○○○4202404502703157701806300260○△280○360150175○N51?12N50?50N32?11N31?14N30?80N41?15N40?90N20?22改编车数改编能力500350图2-3-15 最优方案

第3步 检查

对最优方案比较各站改编车数与改编能力,发现A4站能力不适应,必须改选。在最优

3,1,吸收N31和N30,则A4站改编车数减少220

车,能力可以适应,A2站改编车数减少80,A1站改编车数增加80,均能适应(见图2-3-16),

方案基础上针对A4站能力不足恢复列流

但车小时损失:520+280=800,节省:350+200+240=790,净损失10车小时。方案值(车小时)。因其较最优方案损失很小,故作为最佳方案当选。 F节?1825 N53?18N52?20450500300125275350200○○420240450270○○○31577041014080260○△280○○360150○175○N51?12N50?50N32?11N31?14N30?80N41?15N40?90N20?22改编车数改编能力500350图2-3-16 最佳方案

最佳方案的列流图如图2-3-17所示。 AT集t节550A5102.5A520A5003.0AA3.5200+50120+150140+8050+90+2200+18100+1804070160+8060+90+110+120图2-3-17 最佳方案列流图

上面的两个例子说明,表格计算法具有直观、简便、计算工作量小等优点,在支点站数不多且基本上呈直线的方向上,用它往往能方便地找到最优或接近最优的编组方案,因而作为一种传统的方法长期以来得到了广泛的应用。

这个方法在算法上有两个本质的缺点。一个是当初始方案形成之后,如何逐步逼近最优解,没有一个确定的规则可以遵循,这就使得方案的调整带有较大的盲目性和试探性;另一个是当方案调整到一定的程度之后,如何判别是否达到最优,没有一个确定的准则,往往依赖于人的经验和直觉,这就难以保证不漏掉最优解,特别是支点站数较多时更是如此。因此,无论从计算的复杂性或结果的可靠性而言,用表格计算法求解最佳方案,支点站数都不宜超过8个。

第四节 整数规划模型和二次0-1规划模型简介

一、整数规划模型

由运筹学我们知道,整数规划问题是一类特殊的线性规划问题,它要求全体(或部分)变量为非负整数。当把编组计划问题化为整数规划问题来研究时,不仅要求所有变量均为非负整数,还限制部分变量取值为0或1,所以实际上形成了混合型0-1整数规划问题。下面通过一个具有5个支点站方向的例子(见图2-3-18)来说明建模思想。

A4N40N41AAAAN42NNN图2-3-18 5个支点站方向的直达车流图

首先定义两组变量:

kAxij1.——表示车流?i,j?(含Ai后方站发往j但在Ai站改编中转的车流)在Ak站改编

kxi?j?kij的车流量,这里,,为非负整数;

2.

xij——0-1变量,表示是否开行列流i,j,若开行,xij=1,不开行,xij=0,这里,

i?j。

由这两组变量及式(2-3-5),可以写出对应图2-3-18的整数规划目标函数表达式为

432minF耗??x40?x41?x42?T集??x30?x31?T集?x20T集333322222?t节?t节??x40?x41?x42??x40?x41?x30?x31

根据技术站车流组织的原则建立下面的约束条件方程。

第1组 考虑A4站发出的车流

111??x1t节40?x30?x20? (2-3-15)

N40如果单开,则x40?1?N40x40?N40;N40如果不单开,与较短车流合并,在A3,

321x?x?xAA404040?N40。或2,或1站改编(注:只考虑第1次改编),则综合这两种情况,

321x?x?x404040?N40x40?N40 (2-3-16)

同理,对N41和N42,有

32x?x?N41x41?N41 (2-3-17)4141

x42?N42x42?N42 (2-3-18)

第2组 考虑中间各支点站发出的车流

这时要注意的是,后方站发出在本站改编的车流一律加入到本站的车流中。先看N30。

33,0x?1Nx403030如果开行这支列流,则,它吸收的车流有,还有,写成式子就是

3?x3N?x4040因,所以上式变成

3403?N30x30?x40?N30

?33xxx403040展开后等式左边出现了二次项:,为了保持线性约束,把括号中的用N40替代,

3?N40?N30?x30?x40?N30

如果不开行3,0这支列流,则

21x30?x30?N30 2133xxxx?0,上式取“=”号,否则取30304040这里之所以用“?”号,是因为或中包含,当

“>”号。综合上面两种情况,得约束方程

213??x?x?N?Nx?x?N30 303040303040 (2-3-19)

NN同理,对31和20,有 23??x?N?Nx?x?N31 (2-3-20)3141313141

122??x?N?N?Nx?x?x?N20 (2-3-21)20403020204030

从式(2-3-19)的推导过程不难知道,第2组3个约束方程(2-3-19)~(2-3-21)已

经包含了长程车流压缩发站的车流合并方式,但没有包含压缩到站的情况,所以还需建立一组约束条件方程。

第3组 考虑长程车流压缩到站与较短车流合并的情况 观察图2-3-18知,只有当列流4,1,4,2,3,1至少有一支开行时,才有长程车流压缩到站的可能。

当列流4,1开行,x41?1,这时N40可以与N41合并,即压缩到站在A1改编,有

11N40x41?x140,也可以不与N41合并,则x40?0,因此,N40x41?x40,即

1Nx?x404140?0 (2-3-22)

当列流

4,2N开行,x42?1,可能压缩到站与N42合并的车流有40、N41两支,故有

22??N?Nx?x?x?0 4041424041 (2-3-23)

NN当列流3,1开行,x31?1,可能压缩到站与N31合并的车流有40、30两支,故有

1??N?Nx?x?0 40303130 (2-3-24)

上式中的x30包含了x40在内。

式(2-3-16)~(2-3-24)便是用整数规划法求解5个支点站方向最优编组方案的约束条件方程组。至此,对应图2-3-18的整数规划模型便构造出来了。此模型共有16个变量,其中6个是0-1变量,9个约束条件方程。

把上面的例子推广到有n个支点站A0,A1,?,An?1的方向,得一般整数规划模型如下:

13?i?2?n?2k?n?1k?1k????minF耗??T???xij???t节???xij?i?2?j?0?k?1?i?k?1j?0? (2-3-25)

n?1i集

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4