发布时间 : 星期六 文章铁路行车组织总复习题及答案（西南交大）更新完毕开始阅读2c44525fcf84b9d528ea7a74
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集